In this paper,we propose a new full-Newton step feasible interior-point algorithm for the special weighted linear complementarity problems.The proposed algorithm employs the technique of algebraic equivalent transform...In this paper,we propose a new full-Newton step feasible interior-point algorithm for the special weighted linear complementarity problems.The proposed algorithm employs the technique of algebraic equivalent transformation to derive the search direction.It is shown that the proximity measure reduces quadratically at each iteration.Moreover,the iteration bound of the algorithm is as good as the best-known polynomial complexity for these types of problems.Furthermore,numerical results are presented to show the efficiency of the proposed algorithm.展开更多
A family of neural networks is proposed to solve linear complementarity problems(LCP).The neural networks are constructed from the novel equivalent model of LCP,which is reformulated by utilizing the modulus and smoot...A family of neural networks is proposed to solve linear complementarity problems(LCP).The neural networks are constructed from the novel equivalent model of LCP,which is reformulated by utilizing the modulus and smoothing technologies.Some important properties of the proposed novel equivalent model are summarized.In addition,the stability properties of the proposed steepest descent-based neural networks for LCP are analyzed.In order to illustrate the theoretical results,we provide some numerical simulations and compare the proposed neural networks with existing neural networks based on the NCP-functions.Numerical results indicate that the performance of the proposed neural networks is effective and robust.展开更多
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,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.展开更多
A partition reduction method is used to obtain new upper bounds for the inverses of H-matrices and S-strictly diagonally dominant(S-SDD)matrices.The estimates are expressed via the determinants of third order matrices...A partition reduction method is used to obtain new upper bounds for the inverses of H-matrices and S-strictly diagonally dominant(S-SDD)matrices.The estimates are expressed via the determinants of third order matrices.Numerical experiments with various random matrices show that they are stable and better than the estimates presented in literatures.We use these upper bounds to improve known error estimates for linear complementarity problems with H-matrices and S-SDD matrices.展开更多
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 fr...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.展开更多
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 (ⅲ).展开更多
A new iterative method,which is called positive interior-point algorithm,is presented for solving the nonlinear complementarity problems.This method is of the desirable feature of robustness.And the convergence theore...A new iterative method,which is called positive interior-point algorithm,is presented for solving the nonlinear complementarity problems.This method is of the desirable feature of robustness.And the convergence theorems of the algorithm is established.In addition,some numerical results are reported.展开更多
Mehrotra-type predictor-corrector algorithm, as one of most efficient interior point methods, has become the backbones of most optimization packages. Salahi et al. proposed a cut strategy based algorithm for linear op...Mehrotra-type predictor-corrector algorithm, as one of most efficient interior point methods, has become the backbones of most optimization packages. Salahi et al. proposed a cut strategy based algorithm for linear optimization that enjoyed polynomial complexity and maintained its efficiency in practice. We extend their algorithm to P. （~） linear complementar- ity problems. The way of choosing corrector direction for our algorithm is different from theirs： The new algorithm has been proved to have an O（（1 ＋ 4k）（17 ＋ 19k）√1＋2kn 3/2 log（x0）Ts0/ε） worst case iteration complexity bound. An numerical experiment verifies the feasibility of the new algorithm.展开更多
The paper uses Euclidean Jordan algebras as a basic tool to extend smoothing functions, which include the Chen-Mangasarian class and the Fischer-Burmeister smoothing functions, to symmetric cone complementarity proble...The paper uses Euclidean Jordan algebras as a basic tool to extend smoothing functions, which include the Chen-Mangasarian class and the Fischer-Burmeister smoothing functions, to symmetric cone complementarity problems. Computable formulas for these functions and their Jacobians are derived. In addition, it is shown that these functions are Lipschitz continuous with respect to parameter # and continuously differentiable on J × J for any μ 〉 0.展开更多
A noninterior continuation method is proposed for semidefinite complementarity problem （SDCP）. This method improves the noninterior continuation methods recently developed for SDCP by Chen and Tseng. The main proper...A noninterior continuation method is proposed for semidefinite complementarity problem （SDCP）. This method improves the noninterior continuation methods recently developed for SDCP by Chen and Tseng. The main properties of our method are： （i） it is well d.efined for the monotones SDCP; （ii） it has to solve just one linear system of equations at each step; （iii） it is shown to be both globally linearly convergent and locally quadratically convergent under suitable assumptions.展开更多
In this paper, we present a new form of successive approximation Broyden-like algorithm for nonlinear complementarity problem based on its equivalent nonsmooth equations. Under suitable conditions, we get the global c...In this paper, we present a new form of successive approximation Broyden-like algorithm for nonlinear complementarity problem based on its equivalent nonsmooth equations. Under suitable conditions, we get the global convergence on the algorithms. Some numerical results are also reported.展开更多
Under some assumptions, the solution set of a nonlinear complementarity problem coincides with the set of local minima of the corresponding minimization problem. This paper uses a family of new merit functions to deal...Under some assumptions, the solution set of a nonlinear complementarity problem coincides with the set of local minima of the corresponding minimization problem. This paper uses a family of new merit functions to deal with nonlinear complementarity problem where the underlying function is assumed to be a continuous but not necessarily locally Lipschitzian map and gives a descent algorithm for solving the nonsmooth continuous complementarity problems. In addition, the global convergence of the derivative free descent algorithm is also proved.展开更多
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 class of strongly nonlinear implicit complementarity problems for set-valued mappings in Hilbert spaces is studied,Thereupon a new existence theorem is established and proved to be a solution to that kind of problems.
We establish that the generalized Fischer-Burmeister（FB） function and penalized Generalized Fischer-Burmeister （FB） function defined on symmetric cones are complementarity functions （C-functions）, in terms of Eu...We establish that the generalized Fischer-Burmeister（FB） function and penalized Generalized Fischer-Burmeister （FB） function defined on symmetric cones are complementarity functions （C-functions）, in terms of Euclidean Jordan algebras, and the Generalized Fischer-Burmeister complementarity function for the symmetric cone complementarity problem （SCCP）. It provides an affirmative answer to the open question by Kum and Lim （Kum S H, Lim Y. Penalized complementarity functions on symmetric cones. J. Glob. Optim.. 2010, 46： 475-485） for any positive integer.展开更多
In this paper,we prove existence results of soutions for the nonlinear implicit complementarity problems NICP(T,S,K) where K is a closed weakly locally compact convex cone in a reflexive Banach space E,T is a nonlinea...In this paper,we prove existence results of soutions for the nonlinear implicit complementarity problems NICP(T,S,K) where K is a closed weakly locally compact convex cone in a reflexive Banach space E,T is a nonlinear operator from K into E* (i. e.,the dual space of E) and S is a nonlinear operator from K into E. Our results are the essential improvements and extension of the results obtained previously by several authors including Thera,Ding,and Zeng.展开更多
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 class of smoothing modulus-based iterative method was presented for solving implicit complementarity problems. The main idea was to transform the implicit complementarity problem into an equivalent im...In this paper, a class of smoothing modulus-based iterative method was presented for solving implicit complementarity problems. The main idea was to transform the implicit complementarity problem into an equivalent implicit fixed-point equation, then introduces a smoothing function to obtain its approximation solutions. The convergence analysis of the algorithm was given, and the efficiency of the algorithms was verified by numerical experiments.展开更多
基金Supported by the Optimisation Theory and Algorithm Research Team(Grant No.23kytdzd004)University Science Research Project of Anhui Province(Grant No.2024AH050631)the General Programs for Young Teacher Cultivation of Educational Commission of Anhui Province(Grant No.YQYB2023090).
文摘In this paper,we propose a new full-Newton step feasible interior-point algorithm for the special weighted linear complementarity problems.The proposed algorithm employs the technique of algebraic equivalent transformation to derive the search direction.It is shown that the proximity measure reduces quadratically at each iteration.Moreover,the iteration bound of the algorithm is as good as the best-known polynomial complexity for these types of problems.Furthermore,numerical results are presented to show the efficiency of the proposed algorithm.
基金Supported by the National Natural Science Foundation of China(12371378,41725017,11901098).
文摘A family of neural networks is proposed to solve linear complementarity problems(LCP).The neural networks are constructed from the novel equivalent model of LCP,which is reformulated by utilizing the modulus and smoothing technologies.Some important properties of the proposed novel equivalent model are summarized.In addition,the stability properties of the proposed steepest descent-based neural networks for LCP are analyzed.In order to illustrate the theoretical results,we provide some numerical simulations and compare the proposed neural networks with existing neural networks based on the NCP-functions.Numerical results indicate that the performance of the proposed neural networks is effective and robust.
基金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 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 the Scientific Research Project of Education Department of Hunan Province(Grant No.21C0837).
文摘A partition reduction method is used to obtain new upper bounds for the inverses of H-matrices and S-strictly diagonally dominant(S-SDD)matrices.The estimates are expressed via the determinants of third order matrices.Numerical experiments with various random matrices show that they are stable and better than the estimates presented in literatures.We use these upper bounds to improve known error estimates for linear complementarity problems with H-matrices and S-SDD matrices.
文摘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.
基金Supported by the National Natural Science Foun dation of China(70371032)the Doctoral Educational Foundation 0f China of the Ministry of Education(20020486035)
文摘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.
文摘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 (ⅲ).
文摘A new iterative method,which is called positive interior-point algorithm,is presented for solving the nonlinear complementarity problems.This method is of the desirable feature of robustness.And the convergence theorems of the algorithm is established.In addition,some numerical results are reported.
基金Supported by the Natural Science Foundation of Hubei Province(Grant No.2008CDZ047)
文摘Mehrotra-type predictor-corrector algorithm, as one of most efficient interior point methods, has become the backbones of most optimization packages. Salahi et al. proposed a cut strategy based algorithm for linear optimization that enjoyed polynomial complexity and maintained its efficiency in practice. We extend their algorithm to P. （~） linear complementar- ity problems. The way of choosing corrector direction for our algorithm is different from theirs： The new algorithm has been proved to have an O（（1 ＋ 4k）（17 ＋ 19k）√1＋2kn 3/2 log（x0）Ts0/ε） worst case iteration complexity bound. An numerical experiment verifies the feasibility of the new algorithm.
基金Supported by the Funds of Ministry of Education of China for PhD (20020141013)the NNSF of China (10471015).
文摘The paper uses Euclidean Jordan algebras as a basic tool to extend smoothing functions, which include the Chen-Mangasarian class and the Fischer-Burmeister smoothing functions, to symmetric cone complementarity problems. Computable formulas for these functions and their Jacobians are derived. In addition, it is shown that these functions are Lipschitz continuous with respect to parameter # and continuously differentiable on J × J for any μ 〉 0.
基金This work was supported by the National Natural Science Foundation of China (10201001, 70471008)
文摘A noninterior continuation method is proposed for semidefinite complementarity problem （SDCP）. This method improves the noninterior continuation methods recently developed for SDCP by Chen and Tseng. The main properties of our method are： （i） it is well d.efined for the monotones SDCP; （ii） it has to solve just one linear system of equations at each step; （iii） it is shown to be both globally linearly convergent and locally quadratically convergent under suitable assumptions.
文摘In this paper, we present a new form of successive approximation Broyden-like algorithm for nonlinear complementarity problem based on its equivalent nonsmooth equations. Under suitable conditions, we get the global convergence on the algorithms. Some numerical results are also reported.
基金Supported by the National Science foundation of China(10671126, 40771095)the Key Project for Fundamental Research of STCSM(06JC14057)+1 种基金Shanghai Leading Academic Discipline Project(S30501)the Innovation Fund Project for Graduate Students of Shanghai(JWCXSL0801)
文摘Under some assumptions, the solution set of a nonlinear complementarity problem coincides with the set of local minima of the corresponding minimization problem. This paper uses a family of new merit functions to deal with nonlinear complementarity problem where the underlying function is assumed to be a continuous but not necessarily locally Lipschitzian map and gives a descent algorithm for solving the nonsmooth continuous complementarity problems. In addition, the global convergence of the derivative free descent algorithm is also proved.
基金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.
文摘A class of strongly nonlinear implicit complementarity problems for set-valued mappings in Hilbert spaces is studied,Thereupon a new existence theorem is established and proved to be a solution to that kind of problems.
基金The Specialized Research Fund(20132121110009)for the Doctoral Program of Higher Education
文摘We establish that the generalized Fischer-Burmeister（FB） function and penalized Generalized Fischer-Burmeister （FB） function defined on symmetric cones are complementarity functions （C-functions）, in terms of Euclidean Jordan algebras, and the Generalized Fischer-Burmeister complementarity function for the symmetric cone complementarity problem （SCCP）. It provides an affirmative answer to the open question by Kum and Lim （Kum S H, Lim Y. Penalized complementarity functions on symmetric cones. J. Glob. Optim.. 2010, 46： 475-485） for any positive integer.
文摘In this paper,we prove existence results of soutions for the nonlinear implicit complementarity problems NICP(T,S,K) where K is a closed weakly locally compact convex cone in a reflexive Banach space E,T is a nonlinear operator from K into E* (i. e.,the dual space of E) and S is a nonlinear operator from K into E. Our results are the essential improvements and extension of the results obtained previously by several authors including Thera,Ding,and Zeng.
基金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.
文摘In this paper, a class of smoothing modulus-based iterative method was presented for solving implicit complementarity problems. The main idea was to transform the implicit complementarity problem into an equivalent implicit fixed-point equation, then introduces a smoothing function to obtain its approximation solutions. The convergence analysis of the algorithm was given, and the efficiency of the algorithms was verified by numerical experiments.
