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 ...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.展开更多
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 (ⅲ).展开更多
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.展开更多
In this paper, we introduce a new class of two-parametric penalized function,which includes the penalized minimum function and the penalized Fischer-Burmeister function over symmetric cone complementarity problems. We...In this paper, we introduce a new class of two-parametric penalized function,which includes the penalized minimum function and the penalized Fischer-Burmeister function over symmetric cone complementarity problems. We propose that this class of function is a class of complementarity functions(C-function). Moreover, its merit function has bounded level set under a weak condition.展开更多
The generalized complementarity problem includes the well-known nonlinear complementarity problem and linear complementarity problem as special cases.In this paper, based on a class of smoothing functions, a smoothing...The generalized complementarity problem includes the well-known nonlinear complementarity problem and linear complementarity problem as special cases.In this paper, based on a class of smoothing functions, a smoothing Newton-type algorithm is proposed for solving the generalized complementarity problem.Under suitable assumptions, the proposed algorithm is well-defined and global convergent.展开更多
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 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.展开更多
A mechanism for proving global convergence in filter-SQP (sequence of quadratic programming) method with the nonlinear complementarity problem (NCP) function is described for constrained nonlinear optimization pro...A mechanism for proving global convergence in filter-SQP (sequence of quadratic programming) method with the nonlinear complementarity problem (NCP) function is described for constrained nonlinear optimization problem.We introduce an NCP function into the filter and construct a new SQP-filter algorithm.Such methods are characterized by their use of the dominance concept of multi-objective optimization,instead of a penalty parameter whose adjustment can be problematic.We prove that the algorithm has global convergence and superlinear convergence rates under some mild conditions.展开更多
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.展开更多
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.展开更多
基金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.
文摘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.
基金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 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.
文摘In this paper, we introduce a new class of two-parametric penalized function,which includes the penalized minimum function and the penalized Fischer-Burmeister function over symmetric cone complementarity problems. We propose that this class of function is a class of complementarity functions(C-function). Moreover, its merit function has bounded level set under a weak condition.
基金Supported by LIU Hui Centre for Applied Mathematics of Nankai University and Tianjin University
文摘The generalized complementarity problem includes the well-known nonlinear complementarity problem and linear complementarity problem as special cases.In this paper, based on a class of smoothing functions, a smoothing Newton-type algorithm is proposed for solving the generalized complementarity problem.Under suitable assumptions, the proposed algorithm is well-defined and global convergent.
基金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 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.
基金Project supported by the National Natural Science Foundation of China (Grant Nos.10571137,10771162)
文摘A mechanism for proving global convergence in filter-SQP (sequence of quadratic programming) method with the nonlinear complementarity problem (NCP) function is described for constrained nonlinear optimization problem.We introduce an NCP function into the filter and construct a new SQP-filter algorithm.Such methods are characterized by their use of the dominance concept of multi-objective optimization,instead of a penalty parameter whose adjustment can be problematic.We prove that the algorithm has global convergence and superlinear convergence rates under some mild conditions.
文摘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.
文摘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.