In this paper,a two-step iteration method is established which can be viewed as a generalization of the existing modulus-based methods for vertical linear complementarity problems given by He and Vong(Appl.Math.Lett.1...In this paper,a two-step iteration method is established which can be viewed as a generalization of the existing modulus-based methods for vertical linear complementarity problems given by He and Vong(Appl.Math.Lett.134:108344,2022).The convergence analysis of the proposed method is established,which can improve the existing results.Numerical examples show that the proposed method is efficient with the two-step technique.展开更多
This paper addresses the generalized linear complementarity problem （GLCP） over a polyhedral cone. To solve the problem, we first equivalently convert the problem into an affine variational inequalities problem over...This paper addresses the generalized linear complementarity problem （GLCP） over a polyhedral cone. To solve the problem, we first equivalently convert the problem into an affine variational inequalities problem over a closed polyhedral cone, and then propose a new type of method to solve the GLCP based on the error bound estimation. The global and R-linear convergence rate is established. The numerical experiments show the efficiency of the method.展开更多
In this paper, a class of the stochastic generalized linear complementarity problems with finitely many elements is proposed for the first time. Based on the Fischer-Burmeister function, a new conjugate gradient proje...In this paper, a class of the stochastic generalized linear complementarity problems with finitely many elements is proposed for the first time. Based on the Fischer-Burmeister function, a new conjugate gradient projection method is given for solving the stochastic generalized linear complementarity problems. The global convergence of the conjugate gradient projection method is proved and the related numerical results are also reported.展开更多
Feasible-interior-point algorithms start from a strictly feasible interior point, but infeassible-interior-point algorithms just need to start from an arbitrary positive point, we give a potential reduction algorithm ...Feasible-interior-point algorithms start from a strictly feasible interior point, but infeassible-interior-point algorithms just need to start from an arbitrary positive point, we give a potential reduction algorithm from an infeasible-starting-point for a class of non-monotone linear complementarity problem. Its polynomial complexity is analyzed. After finite iterations the algorithm produces an approximate solution of the problem or shows that there is no feasible optimal solution in a large region. Key words linear complementarity problems - infeasible-starting-point - P-matrix - potential function CLC number O 221 Foundation item: Supported by the National Natural Science Foundation of China (70371032) and the Doctoral Educational Foundation of China of the Ministry of Education (20020486035)Biography: Wang Yan-jin (1976-), male, Ph. D candidate, research direction: optimal theory and method.展开更多
A one_step smoothing Newton method is proposed for solving the vertical linear complementarity problem based on the so_called aggregation function. The proposed algorithm has the following good features: (ⅰ) It solve...A one_step smoothing Newton method is proposed for solving the vertical linear complementarity problem based on the so_called aggregation function. The proposed algorithm has the following good features: (ⅰ) It solves only one linear system of equations and does only one line search at each iteration; (ⅱ) It is well_defined for the vertical linear complementarity problem with vertical block P 0 matrix and any accumulation point of iteration sequence is its solution.Moreover, the iteration sequence is bounded for the vertical linear complementarity problem with vertical block P 0+R 0 matrix; (ⅲ) It has both global linear and local quadratic convergence without strict complementarity. Many existing smoothing Newton methods do not have the property (ⅲ).展开更多
It has been shown in various papers that most interior-point algorithms for linear optimization and their analysis can be generalized to P_＊（κ） linear complementarity problems.This paper presents an extension of t...It has been shown in various papers that most interior-point algorithms for linear optimization and their analysis can be generalized to P_＊（κ） linear complementarity problems.This paper presents an extension of the recent variant of Mehrotra＇s second order algorithm for linear optimijation.It is shown that the iteration-complexity bound of the algorithm is O（4κ ＋ 3）√14κ ＋ 5 nlog（x0）Ts0/ε,which is similar to that of the corresponding algorithm for linear optimization.展开更多
A polynomial interior-point algorithm is presented for monotone linear complementarity problem （MLCP） based on a class of kernel functions with the general barrier term, which are called general kernel functions. Un...A polynomial interior-point algorithm is presented for monotone linear complementarity problem （MLCP） based on a class of kernel functions with the general barrier term, which are called general kernel functions. Under the mild conditions for the barrier term, the complexity bound of algorithm in terms of such kernel function and its derivatives is obtained. The approach is actually an extension of the existing work which only used the specific kernel functions for the MLCP.展开更多
A modified sequential linear programming algorithm is presented, whose subproblem is always solvable, for the extended linear complementarity problem (XLCP), the global convergence of the algorithm under assumption of...A modified sequential linear programming algorithm is presented, whose subproblem is always solvable, for the extended linear complementarity problem (XLCP), the global convergence of the algorithm under assumption of X-row sufficiency or X-colunm monotonicity is proved. As a result, a sufficient condition for existence and boundedness of solution to the XLCP are obtained.展开更多
The extended linear complementarity problem(denoted by ELCP) can be reformulated as the solution of a nonsmooth system of equations. By the symmetrically perturbed CHKS smoothing function, the ELCP is approximated by ...The extended linear complementarity problem(denoted by ELCP) can be reformulated as the solution of a nonsmooth system of equations. By the symmetrically perturbed CHKS smoothing function, the ELCP is approximated by a family of parameterized smooth equations. A one-step smoothing Newton method is designed for solving the ELCP. The proposed algorithm is proved to be globally convergent under suitable assumptions.展开更多
In this paper,by means of constructing the linear complementarity problems into the corresponding absolute value equation,we raise an iteration method,called as the nonlinear lopsided HSS-like modulus-based matrix spl...In this paper,by means of constructing the linear complementarity problems into the corresponding absolute value equation,we raise an iteration method,called as the nonlinear lopsided HSS-like modulus-based matrix splitting iteration method,for solving the linear complementarity problems whose coefficient matrix in R^(n×n)is large sparse and positive definite.From the convergence analysis,it is appreciable to see that the proposed method will converge to its accurate solution under appropriate conditions.Numerical examples demonstrate that the presented method precede to other methods in practical implementation.展开更多
In this paper,a new full-Newton step primal-dual interior-point algorithm for solving the special weighted linear complementarity problem is designed and analyzed.The algorithm employs a kernel function with a linear ...In this paper,a new full-Newton step primal-dual interior-point algorithm for solving the special weighted linear complementarity problem is designed and analyzed.The algorithm employs a kernel function with a linear growth term to derive the search direction,and by introducing new technical results and selecting suitable parameters,we prove that the iteration bound of the algorithm is as good as best-known polynomial complexity of interior-point methods.Furthermore,numerical results illustrate the efficiency of the proposed method.展开更多
In this paper,we discuss the perturbation analysis of the extended vertical linear complementarity problem(EVLCP).Under the assumption of the row W-property,we derive several absolute and relative perturbation bounds ...In this paper,we discuss the perturbation analysis of the extended vertical linear complementarity problem(EVLCP).Under the assumption of the row W-property,we derive several absolute and relative perturbation bounds of EVLCP,which extend some existing results.Several numerical examples are given to show the proposed bounds.展开更多
Recently, we have proposed an iterative projection and contraction (PC) method for a class of linear complementarity problems (LCP)([4]). The method was showed to be globally convergent, but no statement could be made...Recently, we have proposed an iterative projection and contraction (PC) method for a class of linear complementarity problems (LCP)([4]). The method was showed to be globally convergent, but no statement could be made about the rate of convergence. In this paper, we develop a modified globally linearly convergent PC method for linear complementarity problems. Both the method and the convergence proofs are very simple. The method can also be used to solve some linear variational inequalities. Several computational experiments are presented to indicate that the method is surprising good for solving some known difficult problems.展开更多
Asynchronous parallel multisplitting relaxation methods for solving large sparse linear complementarity problems are presented, and their convergence is proved when the system matrices are H-matrices having positive d...Asynchronous parallel multisplitting relaxation methods for solving large sparse linear complementarity problems are presented, and their convergence is proved when the system matrices are H-matrices having positive diagonal elements. Moreover, block and multi-parameter variants of the new methods, together with their convergence properties, are investigated in detail. Numerical results show that these new methods can achieve high parallel efficiency for solving the large sparse linear complementarity problems on multiprocessor systems.展开更多
Focuses on a study which presented a parallel chaotic multisplitting method for solving the large sparse linear complementarity problem. Preliminaries of the study; Equations of the parallel chaotic multisplitting met...Focuses on a study which presented a parallel chaotic multisplitting method for solving the large sparse linear complementarity problem. Preliminaries of the study; Equations of the parallel chaotic multisplitting method; Information on the convergence theories; Details on the parallel chaotic multisplitting relaxation methods.展开更多
Given a real(finite-dimensional or infinite-dimensional) Hilbert space H with a Jordan product,we consider the Lorentz cone linear complementarity problem,denoted by LCP(T,Ω,q),where T is a continuous linear operator...Given a real(finite-dimensional or infinite-dimensional) Hilbert space H with a Jordan product,we consider the Lorentz cone linear complementarity problem,denoted by LCP(T,Ω,q),where T is a continuous linear operator on H,ΩH is a Lorentz cone,and q ∈ H.We investigate some conditions for which the problem concerned has a unique solution for all q ∈ H(i.e.,T has the GUS-property).Several sufficient conditions and several necessary conditions are given.In particular,we provide two suficient and necessary conditions of T having the GUS-property.Our approach is based on properties of the Jordan product and the technique from functional analysis,which is different from the pioneer works given by Gowda and Sznajder(2007) in the case of finite-dimensional spaces.展开更多
In this paper, motivated by the complexity results of Interior Point Methods （IPMs） for Linear Optimization （LO） based on kernel functions, we present a polynomial time IPM for solving P.（a）-linear complementari...In this paper, motivated by the complexity results of Interior Point Methods （IPMs） for Linear Optimization （LO） based on kernel functions, we present a polynomial time IPM for solving P.（a）-linear complementarity problem, using a new class of kernel functions. The special case of our new class was considered earlier for LO by Y. Q. Bai et al. in 2004. Using some appealing properties of the new class, we show that the iteration bound for IPMs matches the so far best known theoretical iteration bound for both large and small updates by choosing special values for the parameters of the new class.展开更多
As applying the Levenberg-Marquardt method to the reformulation of linear complementarity problem,a modulus-based Levenberg-Marquardt method with non-monotone line search is established and the global convergence resu...As applying the Levenberg-Marquardt method to the reformulation of linear complementarity problem,a modulus-based Levenberg-Marquardt method with non-monotone line search is established and the global convergence result is presented.Numerical experiments show that the proposed method is efficient and outperforms the modulus-based matrix splitting iteration method.展开更多
In this paper, we adopt the robust optimization method to consider linear complementarity problems in which the data is not specified exactly or is uncertain, and it is only known to belong to a prescribed uncertainty...In this paper, we adopt the robust optimization method to consider linear complementarity problems in which the data is not specified exactly or is uncertain, and it is only known to belong to a prescribed uncertainty set. We propose the notion of the p-robust counterpart and the p-robust solution of uncertain linear complementarity problems. We discuss uncertain linear complementarity problems with three different uncertainty sets, respectively, including an unknown-but-bounded uncertainty set, an ellipsoidal uncertainty set and an intersection-of-ellipsoids uncertainty set, and present some sufficient and necessary （or sufficient） conditions which p-robust solutions satisfy. Some special eases are investigated in this paper.展开更多
This paper proposes a new infeasible interior-point algorithm with full-Newton steps for P_*(κ) linear complementarity problem(LCP),which is an extension of the work by Roos(SIAM J.Optim.,2006,16(4):1110-1136).The ma...This paper proposes a new infeasible interior-point algorithm with full-Newton steps for P_*(κ) linear complementarity problem(LCP),which is an extension of the work by Roos(SIAM J.Optim.,2006,16(4):1110-1136).The main iteration consists of a feasibility step and several centrality steps.The authors introduce a specific kernel function instead of the classic logarithmical barrier function to induce the feasibility step,so the analysis of the feasibility step is different from that of Roos' s.This kernel function has a finite value on the boundary.The result of iteration complexity coincides with the currently known best one for infeasible interior-point methods for P_*(κ) LCP.Some numerical results are reported as well.展开更多
基金supported by the Scientific Computing Research Innovation Team of Guangdong Province(no.2021KCXTD052)the Science and Technology Development Fund,Macao SAR(no.0096/2022/A,0151/2022/A)+3 种基金University of Macao(no.MYRG2020-00035-FST,MYRG2022-00076-FST)the Guangdong Key Construction Discipline Research Capacity Enhancement Project(no.2022ZDJS049)Technology Planning Project of Shaoguan(no.210716094530390)the ScienceFoundation of Shaoguan University(no.SZ2020KJ01).
文摘In this paper,a two-step iteration method is established which can be viewed as a generalization of the existing modulus-based methods for vertical linear complementarity problems given by He and Vong(Appl.Math.Lett.134:108344,2022).The convergence analysis of the proposed method is established,which can improve the existing results.Numerical examples show that the proposed method is efficient with the two-step technique.
基金supported by National Natural Science Foundation of China (No. 10771120)
文摘This paper addresses the generalized linear complementarity problem （GLCP） over a polyhedral cone. To solve the problem, we first equivalently convert the problem into an affine variational inequalities problem over a closed polyhedral cone, and then propose a new type of method to solve the GLCP based on the error bound estimation. The global and R-linear convergence rate is established. The numerical experiments show the efficiency of the method.
文摘In this paper, a class of the stochastic generalized linear complementarity problems with finitely many elements is proposed for the first time. Based on the Fischer-Burmeister function, a new conjugate gradient projection method is given for solving the stochastic generalized linear complementarity problems. The global convergence of the conjugate gradient projection method is proved and the related numerical results are also reported.
文摘Feasible-interior-point algorithms start from a strictly feasible interior point, but infeassible-interior-point algorithms just need to start from an arbitrary positive point, we give a potential reduction algorithm from an infeasible-starting-point for a class of non-monotone linear complementarity problem. Its polynomial complexity is analyzed. After finite iterations the algorithm produces an approximate solution of the problem or shows that there is no feasible optimal solution in a large region. Key words linear complementarity problems - infeasible-starting-point - P-matrix - potential function CLC number O 221 Foundation item: Supported by the National Natural Science Foundation of China (70371032) and the Doctoral Educational Foundation of China of the Ministry of Education (20020486035)Biography: Wang Yan-jin (1976-), male, Ph. D candidate, research direction: optimal theory and method.
文摘A one_step smoothing Newton method is proposed for solving the vertical linear complementarity problem based on the so_called aggregation function. The proposed algorithm has the following good features: (ⅰ) It solves only one linear system of equations and does only one line search at each iteration; (ⅱ) It is well_defined for the vertical linear complementarity problem with vertical block P 0 matrix and any accumulation point of iteration sequence is its solution.Moreover, the iteration sequence is bounded for the vertical linear complementarity problem with vertical block P 0+R 0 matrix; (ⅲ) It has both global linear and local quadratic convergence without strict complementarity. Many existing smoothing Newton methods do not have the property (ⅲ).
基金supported by the Natural Science Foundation of Hubei Province of China(2008CDZ047)
文摘It has been shown in various papers that most interior-point algorithms for linear optimization and their analysis can be generalized to P_＊（κ） linear complementarity problems.This paper presents an extension of the recent variant of Mehrotra＇s second order algorithm for linear optimijation.It is shown that the iteration-complexity bound of the algorithm is O（4κ ＋ 3）√14κ ＋ 5 nlog（x0）Ts0/ε,which is similar to that of the corresponding algorithm for linear optimization.
基金supported by the National Natural Science Foundation of China (Grant No.10771133)the Shanghai Pujiang Program (Grant No.06PJ14039)
文摘A polynomial interior-point algorithm is presented for monotone linear complementarity problem （MLCP） based on a class of kernel functions with the general barrier term, which are called general kernel functions. Under the mild conditions for the barrier term, the complexity bound of algorithm in terms of such kernel function and its derivatives is obtained. The approach is actually an extension of the existing work which only used the specific kernel functions for the MLCP.
文摘A modified sequential linear programming algorithm is presented, whose subproblem is always solvable, for the extended linear complementarity problem (XLCP), the global convergence of the algorithm under assumption of X-row sufficiency or X-colunm monotonicity is proved. As a result, a sufficient condition for existence and boundedness of solution to the XLCP are obtained.
基金Supported by the NNSF of China(11071041, 11171257)
文摘The extended linear complementarity problem(denoted by ELCP) can be reformulated as the solution of a nonsmooth system of equations. By the symmetrically perturbed CHKS smoothing function, the ELCP is approximated by a family of parameterized smooth equations. A one-step smoothing Newton method is designed for solving the ELCP. The proposed algorithm is proved to be globally convergent under suitable assumptions.
基金This work is supported by the National Natural Science Foundation of China with No.11461046the Natural Science Foundation of Jiangxi Province of China with Nos.20181ACB20001 and 20161ACB21005.
文摘In this paper,by means of constructing the linear complementarity problems into the corresponding absolute value equation,we raise an iteration method,called as the nonlinear lopsided HSS-like modulus-based matrix splitting iteration method,for solving the linear complementarity problems whose coefficient matrix in R^(n×n)is large sparse and positive definite.From the convergence analysis,it is appreciable to see that the proposed method will converge to its accurate solution under appropriate conditions.Numerical examples demonstrate that the presented method precede to other methods in practical implementation.
基金Supported by University Science Research Project of Anhui Province(2023AH052921)Outstanding Youth Talent Project of Anhui Province(gxyq2021254)。
文摘In this paper,a new full-Newton step primal-dual interior-point algorithm for solving the special weighted linear complementarity problem is designed and analyzed.The algorithm employs a kernel function with a linear growth term to derive the search direction,and by introducing new technical results and selecting suitable parameters,we prove that the iteration bound of the algorithm is as good as best-known polynomial complexity of interior-point methods.Furthermore,numerical results illustrate the efficiency of the proposed method.
基金supported by the National Natural Science Foundation of China(Nos.11961082,12071159 and U1811464).
文摘In this paper,we discuss the perturbation analysis of the extended vertical linear complementarity problem(EVLCP).Under the assumption of the row W-property,we derive several absolute and relative perturbation bounds of EVLCP,which extend some existing results.Several numerical examples are given to show the proposed bounds.
文摘Recently, we have proposed an iterative projection and contraction (PC) method for a class of linear complementarity problems (LCP)([4]). The method was showed to be globally convergent, but no statement could be made about the rate of convergence. In this paper, we develop a modified globally linearly convergent PC method for linear complementarity problems. Both the method and the convergence proofs are very simple. The method can also be used to solve some linear variational inequalities. Several computational experiments are presented to indicate that the method is surprising good for solving some known difficult problems.
基金Subsidized by The Special Funds For Major State Basic Research Projects G1999032803.
文摘Asynchronous parallel multisplitting relaxation methods for solving large sparse linear complementarity problems are presented, and their convergence is proved when the system matrices are H-matrices having positive diagonal elements. Moreover, block and multi-parameter variants of the new methods, together with their convergence properties, are investigated in detail. Numerical results show that these new methods can achieve high parallel efficiency for solving the large sparse linear complementarity problems on multiprocessor systems.
基金the National Natural Science Foundation of China (19601036) and Subsidized by the SpecialFunds for Major State Basic Research
文摘Focuses on a study which presented a parallel chaotic multisplitting method for solving the large sparse linear complementarity problem. Preliminaries of the study; Equations of the parallel chaotic multisplitting method; Information on the convergence theories; Details on the parallel chaotic multisplitting relaxation methods.
基金supported by National Natural Science Foundation of China(Grant No. 10871144)the Natural Science Foundation of Tianjin Province (Grant No. 07JCYBJC05200)
文摘Given a real(finite-dimensional or infinite-dimensional) Hilbert space H with a Jordan product,we consider the Lorentz cone linear complementarity problem,denoted by LCP(T,Ω,q),where T is a continuous linear operator on H,ΩH is a Lorentz cone,and q ∈ H.We investigate some conditions for which the problem concerned has a unique solution for all q ∈ H(i.e.,T has the GUS-property).Several sufficient conditions and several necessary conditions are given.In particular,we provide two suficient and necessary conditions of T having the GUS-property.Our approach is based on properties of the Jordan product and the technique from functional analysis,which is different from the pioneer works given by Gowda and Sznajder(2007) in the case of finite-dimensional spaces.
基金Supported by a grant from IPM (Grant No. 8890027)
文摘In this paper, motivated by the complexity results of Interior Point Methods （IPMs） for Linear Optimization （LO） based on kernel functions, we present a polynomial time IPM for solving P.（a）-linear complementarity problem, using a new class of kernel functions. The special case of our new class was considered earlier for LO by Y. Q. Bai et al. in 2004. Using some appealing properties of the new class, we show that the iteration bound for IPMs matches the so far best known theoretical iteration bound for both large and small updates by choosing special values for the parameters of the new class.
基金This research is supported by National Science Foundation of China(41725017)National Basic Research Program of China under grant number 2014CB845906+1 种基金It is also partially supported by the CAS/CAFEA international partnership Program for creative research teams(No.KZZD-EW-TZ-19 and KZZD-EW-TZ-15)Strategic Priority Research Program of the Chinese Academy of Sciences(No.XDB18010202)。
文摘As applying the Levenberg-Marquardt method to the reformulation of linear complementarity problem,a modulus-based Levenberg-Marquardt method with non-monotone line search is established and the global convergence result is presented.Numerical experiments show that the proposed method is efficient and outperforms the modulus-based matrix splitting iteration method.
基金Supported by the National Natural Science Foundation of China(No.10671010,10871144 and 10671145)
文摘In this paper, we adopt the robust optimization method to consider linear complementarity problems in which the data is not specified exactly or is uncertain, and it is only known to belong to a prescribed uncertainty set. We propose the notion of the p-robust counterpart and the p-robust solution of uncertain linear complementarity problems. We discuss uncertain linear complementarity problems with three different uncertainty sets, respectively, including an unknown-but-bounded uncertainty set, an ellipsoidal uncertainty set and an intersection-of-ellipsoids uncertainty set, and present some sufficient and necessary （or sufficient） conditions which p-robust solutions satisfy. Some special eases are investigated in this paper.
基金supported by the Natural Science Foundation of Hubei Province under Grant No.2008CDZ047
文摘This paper proposes a new infeasible interior-point algorithm with full-Newton steps for P_*(κ) linear complementarity problem(LCP),which is an extension of the work by Roos(SIAM J.Optim.,2006,16(4):1110-1136).The main iteration consists of a feasibility step and several centrality steps.The authors introduce a specific kernel function instead of the classic logarithmical barrier function to induce the feasibility step,so the analysis of the feasibility step is different from that of Roos' s.This kernel function has a finite value on the boundary.The result of iteration complexity coincides with the currently known best one for infeasible interior-point methods for P_*(κ) LCP.Some numerical results are reported as well.
