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 fu-Newton step interior-point algorithm is proposed for solving P_(*)(k)-linear complementarity problem based on a new search direction,which is an extension of Grimes'algorithm.It is proved that t...In this paper,a fu-Newton step interior-point algorithm is proposed for solving P_(*)(k)-linear complementarity problem based on a new search direction,which is an extension of Grimes'algorithm.It is proved that the number of iterations of the algorithm is O(n^(1/2)(1+4κ)logn/ε),which matches the best known iteration bound of the interior-point method for P_(*)(k)-linear complementarity problem.Some numerical results have proved the feasibility and efficiency of the proposed algorithm.展开更多
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, an ODE-type trust region algorithm for solving a class of nonlinear complementarity problems is proposed. A feature of this algorithm is that only the solution of linear systems of equations is required...In this paper, an ODE-type trust region algorithm for solving a class of nonlinear complementarity problems is proposed. A feature of this algorithm is that only the solution of linear systems of equations is required at each iteration, thus avoiding the need for solving a quadratic subproblem with a trust region bound. Under some conditions, it is proven that this algorithm is globally and locally superlinear convergent. The limited numerical examples show its efficiency.展开更多
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.展开更多
We applied the projection and contraction method to nonlinear complementarity problem (NCP). Moveover, we proposed an inexact implicit method for (NCP) and proved the convergence.
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.展开更多
This paper proposes an infeasible interior-point algorithm with full-Newton step for linear complementarity problem,which is an extension of Roos about linear optimization. The main iteration of the algorithm consists...This paper proposes an infeasible interior-point algorithm with full-Newton step for linear complementarity problem,which is an extension of Roos about linear optimization. The main iteration of the algorithm consists of a feasibility step and several centrality steps. At last,we prove that the algorithm has O(nlog n/ε) polynomial complexity,which coincides with the best known one for the infeasible interior-point algorithm at present.展开更多
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.展开更多
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.展开更多
In this paper, we consider the global error bound for the generalized complementarity problem (GCP) with analytic functions. Based on the new technique, we establish computable global error bound under milder conditio...In this paper, we consider the global error bound for the generalized complementarity problem (GCP) with analytic functions. Based on the new technique, we establish computable global error bound under milder conditions, which refines the previously known results.展开更多
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.展开更多
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 (ⅲ).展开更多
This paper proposes an infeasible interior-point algorithm for linear complementarity problem with full-Newton steps.The main iteration consists of a feasibility step and several centrality steps.No more than O（n log...This paper proposes an infeasible interior-point algorithm for linear complementarity problem with full-Newton steps.The main iteration consists of a feasibility step and several centrality steps.No more than O（n log（n /ε））iterations are required for getting ε-solution of the problem at hand,which coincides with the best-known bound for infeasible interior-point algorithms.展开更多
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.展开更多
基金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 the Optimization Theory and Algorithm Research Team(23kytdzd004)the General Programs for Young Teacher Cultivation of Educational Commission of Anhui Province of China(YQYB2023090)the University Science Research Project of Anhui Province(2024AH050631)。
文摘In this paper,a fu-Newton step interior-point algorithm is proposed for solving P_(*)(k)-linear complementarity problem based on a new search direction,which is an extension of Grimes'algorithm.It is proved that the number of iterations of the algorithm is O(n^(1/2)(1+4κ)logn/ε),which matches the best known iteration bound of the interior-point method for P_(*)(k)-linear complementarity problem.Some numerical results have proved the feasibility and efficiency of the proposed algorithm.
基金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.
基金Supported by the Natural Science Foundation of Hainan Province(80552)
文摘In this paper, an ODE-type trust region algorithm for solving a class of nonlinear complementarity problems is proposed. A feature of this algorithm is that only the solution of linear systems of equations is required at each iteration, thus avoiding the need for solving a quadratic subproblem with a trust region bound. Under some conditions, it is proven that this algorithm is globally and locally superlinear convergent. The limited numerical examples show its efficiency.
基金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.
基金Supported by the National Natural Science Foundation of China (No. 202001036)
文摘We applied the projection and contraction method to nonlinear complementarity problem (NCP). Moveover, we proposed an inexact implicit method for (NCP) and proved the convergence.
基金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.
基金Supported by the National Natural Science Fund Finances Projects(71071119)
文摘This paper proposes an infeasible interior-point algorithm with full-Newton step for linear complementarity problem,which is an extension of Roos about linear optimization. The main iteration of the algorithm consists of a feasibility step and several centrality steps. At last,we prove that the algorithm has O(nlog n/ε) polynomial complexity,which coincides with the best known one for the infeasible interior-point algorithm at present.
文摘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.
文摘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.
基金supported by National Natural Science Foundation of China (Nos. 11171180 and 11101303)Specialized Research Fund for the Doctoral Program of Chinese Higher Education (No. 20113705110002)Shandong Provincial Natural Science Foundation (Nos. ZR2010AL005 and ZR2011FL017)
文摘In this paper, we consider the global error bound for the generalized complementarity problem (GCP) with analytic functions. Based on the new technique, we establish computable global error bound under milder conditions, which refines the previously known results.
基金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.
文摘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 National Natural Science Foundation of China(71071119)
文摘This paper proposes an infeasible interior-point algorithm for linear complementarity problem with full-Newton steps.The main iteration consists of a feasibility step and several centrality steps.No more than O（n log（n /ε））iterations are required for getting ε-solution of the problem at hand,which coincides with the best-known bound for infeasible interior-point algorithms.
基金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.
