Non-Interior continuation methods for solving semidefinite complementarity problems

 There recently has been much interest in non-interior continuation/smoothing methods for solving linear/nonlinear complementarity problems. We describe extensions of such methods to complementarity problems defined over the cone of block-diagonal symmetric positive semidefinite real matrices. These extensions involve the Chen-Mangasarian class of smoothing functions and the smoothed Fischer-Burmeister function. Issues such as existence of Newton directions, boundedness of iterates, global convergence, and local superlinear convergence will be studied. Preliminary numerical experience on semidefinite linear programs is also reported. Received: October 1999 / Accepted: April 2002 Published online: December 19, 2002 RID="⋆" ID="⋆" This research is supported by National Science Foundation Grant CCR-9731273. Key words. semidefinite complementarity problem – smoothing function – non-interior continuation – global convergence – local superlinear convergence     

Superlinear／Quadratic One-step Smoothing Newton Methodf or P0-NCP

We propose a one-step smoothing Newton method for solving the non-linear complementarity problem with P0-function (P0-NCP) based on the smoothing symmetric perturbed Fisher function(for short, denoted as the SSPF-function). The proposed algorithm has to solve only one linear system of equations and performs only one line search per iteration. Without requiring any strict complementarity assumption at the P0-NCP solution, we show that the proposed algorithm converges globally and superlinearly under mild conditions. Furthermore, the algorithm has local quadratic convergence under suitable conditions. The main feature of our global convergence results is that we do not assume a priori the existence of an accumulation point. Compared to the previous literatures, our algorithm has stronger convergence results under weaker conditions.     

A Smoothing Levenberg-Marquardt Type Method for LCP

In this paper, we convert the linear complementarity problem to a system of semismooth nonlinear equations by using smoothing technique. Then we use Levenberg-Marquardt type method to solve this system. Taking advantage of the new results obtained by Dan, Yamashita and Fukushima [11, 33], the global and local superlinear convergence properties of the method are obtained under very mild conditions. Especially, the algorithm is locally superlinearly convergent under the assumption of either strict complementarity or certain nonsingularity. Preliminary numerical experiments are reported to show the efficiency of the algorithm.     

A Trust Region Method for Optimization Problem with Singular Solutions

In this paper, we propose a trust region method for minimizing a function whose Hessian matrix at the solutions may be singular. The global convergence of the method is obtained under mild conditions. Moreover, we show that if the objective function is LC ² function, the method possesses local superlinear convergence under the local error bound condition without the requirement of isolated nonsingular solution. This is the first regularized Newton method with trust region technique which possesses local superlinear (quadratic) convergence without the assumption that the Hessian of the objective function at the solution is nonsingular. Preliminary numerical experiments show the efficiency of the method. This work is partly supported by the National Natural Science Foundation of China (Grant Nos. 70302003, 10571106, 60503004, 70671100) and Science Foundation of Beijing Jiaotong University (2007RC014).     

Non-Interior Continuation Method for Solving the Monotone Semidefinite Complementarity Problem

Recently, Chen and Tseng extended non-interior continuation/ smooth- ing methods for solving linear/ nonlinear complementarity problems to semidefinite complementarity problems (SDCP). In this paper we propose a non-interior continuation method for solving the monotone SDCP based on the smoothed Fischer—Burmeister function, which is shown to be globally linearly and locally quadratically convergent under suitable assumptions. Our algorithm needs at most to solve a linear system of equations at each iteration. In addition, in our analysis on global linear convergence of the algorithm, we need not use the assumption that the Fréchet derivative of the function involved in the SDCP is Lipschitz continuous. For non-interior continuation/ smoothing methods for solving the nonlinear complementarity problem, such an assumption has been used widely in the literature in order to achieve global linear convergence results of the algorithms.     

Non-Interior Continuation Method for Solving the Monotone Semidefinite Complementarity Problem

Recently, Chen and Tseng extended non-interior continuation/ smooth- ing methods for solving linear/ nonlinear complementarity problems to semidefinite complementarity problems (SDCP). In this paper we propose a non-interior continuation method for solving the monotone SDCP based on the smoothed Fischer—Burmeister function, which is shown to be globally linearly and locally quadratically convergent under suitable assumptions. Our algorithm needs at most to solve a linear system of equations at each iteration. In addition, in our analysis on global linear convergence of the algorithm, we need not use the assumption that the Fréchet derivative of the function involved in the SDCP is Lipschitz continuous. For non-interior continuation/ smoothing methods for solving the nonlinear complementarity problem, such an assumption has been used widely in the literature in order to achieve global linear convergence results of the algorithms.     

P_0函数非线性互补问题的一步非内点连续方法的收敛性

本文对于Ｐ０函数非线性互补问题提出了一个基于Ｋａｎｚｏｗ光滑函数的一步非内点连续方法,在适当的假设条件下,证明了方法的全局线性及局部二次收敛性．特别,在方法的全局线性收敛性的分析中,不需要假定非线性互补问题的函数的Ｊａｃｏｂｉ阵是Ｌｉｐｓｃｈｉｔｚ连续的．文献中为了得到非内点连续方法的全局线性收敛性,这一假定是被广泛使用的．本文提出的方法在每一次迭代只须解一个线性方程式组．     

A smoothing Levenberg–Marquardt method for the extended linear complementarity problem

We consider the extended linear complementarity problem (XLCP), of which the linear and horizontal linear complementarity problems are two special cases. We reformulate the XLCP to a smooth equation by using some smoothing functions and propose a Levenberg–Marquardt method to solve the system of smooth equation. The global convergence and local superlinear convergence rate are established under certain conditions. Numerical tests show the effectiveness of the proposed algorithm.     

A self-adaptive trust region method for the extended linear complementarity problems

By using some NCP functions, we reformulate the extended linear complementarity problem as a nonsmooth equation. Then we propose a self-adaptive trust region algorithm for solving this nonsmooth equation. The novelty of this method is that the trust region radius is controlled by the objective function value which can be adjusted automatically according to the algorithm. The global convergence is obtained under mild conditions and the local superlinear convergence rate is also established under strict complementarity conditions. This work is supported by National Natural Science Foundation of China (No. 10671126) and Shanghai Leading Academic Discipline Project (S30501).     

Inexact Interior-Point Method

In this paper, we introduce an inexact interior-point algorithm for a constrained system of equations. The formulation of the problem is quite general and includes nonlinear complementarity problems of various kinds. In our convergence theory, we interpret the inexact interior-point method as an inexact Newton method. This enables us to establish a global convergence theory for the proposed algorithm. Under the additional assumption of the invertibility of the Jacobian at the solution, the superlinear convergence of the iteration sequence is proved.     

求解非线性互补问题的一类光滑Broyden-like方法

非线性互补问题可以等价地转换为光滑方程组来求解. 基于一种新的非单调线搜索准则, 提出了求解非线性互补问题等价光滑方程组的一类新的非单调光滑 Broyden-like 算法.在适当的假设条件下, 证明了该算法的全局收敛性与局部超线性收敛性. 数值实验表明所提出的算法是有效的.     

A smoothing Newton-type method for generalized nonlinear complementarity problem

By using a new type of smoothing function, we first reformulate the generalized nonlinear complementarity problem over a polyhedral cone as a smoothing system of equations, and then develop a smoothing Newton-type method for solving it. For the proposed method, we obtain its global convergence under milder conditions, and we further establish its local superlinear (quadratic) convergence rate under the BD-regular assumption. Preliminary numerical experiments are also reported in this paper.     

A new class of smoothing functions and a smoothing Newton method for complementarity problems

In this paper, we introduce a new class of smoothing functions, which include some popular smoothing complementarity functions. We show that the new smoothing functions possess a system of favorite properties. The existence and continuity of a smooth path for solving the nonlinear complementarity problem (NCP) with a P ₀ function are discussed. The Jacobian consistency of this class of smoothing functions is analyzed. Based on the new smoothing functions, we investigate a smoothing Newton algorithm for the NCP and discuss its global and local superlinear convergence. Some preliminary numerical results are reported.     

非线性互补约束规划问题的一个新的QP-free算法

本文研究了非线性互补约束均衡问题.利用互补函数以及光滑近似法,把非线性互补约束均衡问题转化为一个光滑非线性规划问题,得到了超线性收敛速度,数值实验结果表明本文提出的算法是可行的.     

A Superlinearly Convergent Implicit Smooth SQP Algorithm for Mathematical Programs with Nonlinear Complementarity Constraints

This paper discusses a special class of mathematical programs with nonlinear complementarity constraints, its goal is to present a globally and superlinearly convergent algorithm for the discussed problems. We first reformulate the complementarity constraints as a standard nonlinear equality and inequality constraints by making use of a class of generalized smoothing complementarity functions, then present a new SQP algorithm for the discussed problems. At each iteration, with the help of a pivoting operation, a master search direction is yielded by solving a quadratic program, and a correction search direction for avoiding the Maratos effect is generated by an explicit formula. Under suitable assumptions, without the strict complementarity on the upper-level inequality constraints, the proposed algorithm converges globally to a B-stationary point of the problems, and its convergence rate is superlinear.AMS Subject Classification: 90C, 49MThis work was supported by the National Natural Science Foundation (10261001) and the Guangxi Province Science Foundation (0236001, 0249003) of China.     

Smoothing Trust Region Methods for Nonlinear Complementarity Problems with P 0-Functions

By using the Fischer–Burmeister function to reformulate the nonlinear complementarity problem (NCP) as a system of semismooth equations and using Kanzow’s smooth approximation function to construct the smooth operator, we propose a smoothing trust region algorithm for solving the NCP with P ₀ functions. We prove that every accumulation point of the sequence generated by the algorithm is a solution of the NCP. Under a nonsingularity condition, local Q-superlinear/Q-quadratic convergence of the algorithm is established without the strict complementarity condition. This work was partially supported by the Research Grant Council of Hong Kong and the National Natural Science Foundation of China (Grant 10171030).     

A superlinearly and quadratically convergent SQP type feasible method for constrained optimization

A new SQP type feasible method for inequality constrained optimization is presented, it is a combination of a master algorithm and an auxiliary algorithm which is taken only in finite iterations. The directions of the master algorithm are generated by only one quadratic programming, and its step-size is always one, the directions of the auxiliary algorithm are new “secondorder“ feasible descent. Under suitable assumptions, the algorithm is proved to possess global and strong convergence, superlinear and quadratic convergence.     

A New Superlinearly Convergent SQP Algorithm for Nonlinear Minimax Problems

In this paper, the nonlinear minimax problems are discussed. By means of the Sequential Quadratic Programming （SQP）, a new descent algorithm for solving the problems is presented. At each iteration of the proposed algorithm, a main search direction is obtained by solving a Quadratic Programming （QP） which always has a solution. In order to avoid the Maratos effect, a correction direction is obtained by updating the main direction with a simple explicit formula. Under mild conditions without the strict complementarity, the global and superlinear convergence of the algorithm can be obtained. Finally, some numerical experiments are reported.     

二阶锥规划一个超线性收敛的非内部连续化算法

基于非光滑向量值最小函数的一个新光滑函数, 建立了二阶锥规划一个超线性收敛的非内部连续化算法. 该算法的特点如下: 首先, 初始点任意; 其次, 每次迭代只需求解一个线性方程组即可得到搜索方向; 最后, 在无严格互补假设下, 获得算法的全局收敛性、强收敛性和超线性收敛性. 数值结果表明算法是有效的.