Global Linear and Quadratic One-step Smoothing Newton Method for P 0-LCP

We propose a new smoothing Newton method for solving the P ₀-matrix linear complementarity problem (P ₀-LCP) based on CHKS smoothing function. Our algorithm solves only one linear system of equations and performs only one line search per iteration. It is shown to converge to a P ₀-LCP solution globally linearly and locally quadratically without the strict complementarity assumption at the solution. To the best of author's knowledge, this is the first one-step smoothing Newton method to possess both global linear and local quadratic convergence. Preliminary numerical results indicate that the proposed algorithm is promising.     

A smoothing Newton method for second-order cone optimization based on a new smoothing function

A new smoothing function is given in this paper by smoothing the symmetric perturbed Fischer-Burmeister function. Based on this new smoothing function, we present a smoothing Newton method for solving the second-order cone optimization (SOCO). The method solves only one linear system of equations and performs only one line search at each iteration. Without requiring strict complementarity assumption at the SOCO solution, the proposed algorithm is shown to be globally and locally quadratically convergent. Numerical results demonstrate that our algorithm is promising and comparable to interior-point methods.     

垂直线性互补问题的一步全局线性和局部二次收敛光滑Newton法

基于凝聚函数,提出一个求解垂直线性互补问题的光滑Newton法.该算法具有以下优点:(i)每次迭代仅需解一个线性系统和实施一次线性搜索;(ⅱ)算法对垂直分块P0矩阵的线性互补问题有定义且迭代序列的每个聚点都是它的解.而且,对垂直分块P₀+R₀矩阵的线性互补问题,算法产生的迭代序列有界且其任一聚点都是它的解;(ⅲ)在无严格互补条件下证得算法即具有全局线性收敛性又具有局部二次收敛性.许多已存在的求解此问题的光滑Newton法都不具有性质(ⅲ).     

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 new one‐step smoothing newton method for the second‐order cone complementarity problem

In this paper, we present a new one‐step smoothing Newton method for solving the second‐order cone complementarity problem (SOCCP). Based on a new smoothing function, the SOCCP is approximated by a family of parameterized smooth equations. At each iteration, the proposed algorithm only need to solve one system of linear equations and perform only one Armijo‐type line search. The algorithm is proved to be convergent globally and superlinearly without requiring strict complementarity at the SOCCP solution. Moreover, the algorithm has locally quadratic convergence under mild conditions. Numerical experiments demonstrate the feasibility and efficiency of the new algorithm. Copyright © 2010 John Wiley & Sons, Ltd.     

一个新的求解二阶锥规划的非内部连续化算法

基于光滑Fischer-Burmeister函数,本文给出一个新的求解二阶锥规划的非内部连续化算法.算法对初始点的选取没有任何限制,并且在每一步迭代只需求解一个线性方程组并进行一次线性搜索.在不需要满足严格互补条件下,证明了算法是全局收敛且是局部超线性收敛的.数值试验表明算法是有效的.     

一个求解二阶锥规划的光滑牛顿算法

本文研究了二阶锥规划问题.利用新的最小值函数的光滑函数,给出一个求解二阶锥规划的光滑牛顿算法.算法可以从任意点出发,在每一步迭代只需求解一个线性方程组并进行一次线性搜索.在不需要满足严格互补假设条件下,证明了算法是全局收敛和局部二阶收敛的.数值试验表明算法是有效的.     

A nonmonotone smoothing Newton method for circular cone programming

The circular cone programming (CCP) problem is to minimize or maximize a linear function over the intersection of an affine space with the Cartesian product of circular cones. In this paper, we study nondegeneracy and strict complementarity for the CCP, and present a nonmonotone smoothing Newton method for solving the CCP. We reformulate the CCP as a second-order cone programming (SOCP) problem using the algebraic relation between the circular cone and the second-order cone. Then based on a one parametric class of smoothing functions for the SOCP, a smoothing Newton method is developed for the CCP by adopting a new nonmonotone line search scheme. Without restrictions regarding its starting point, our algorithm solves one linear system of equations approximately and performs one line search at each iteration. Under mild assumptions, our algorithm is shown to possess global and local quadratic convergence properties. Some preliminary numerical results illustrate that our nonmonotone smoothing Newton method is promising for solving the CCP.     

One-step smoothing Newton method for solving the mixed complementarity problem with a function

The mixed complementarity problem (denote by MCP(F)) can be reformulated as the solution of a smooth system of equations. In the paper, based on a perturbed mid function, we propose a new smoothing function, which has an important property, not satisfied by many other smoothing function. The existence and continuity of a smooth path for solving the mixed complementarity problem with a P₀ function are discussed. Then we presented a one-step smoothing Newton algorithm to solve the MCP with a P₀ function. The global convergence of the proposed algorithm is verified under mild conditions. And by using the smooth and semismooth technique, the rate of convergence of the method is proved under some suitable assumptions.     

Sub-quadratic convergence of a smoothing Newton method for second-order cone programming

In this paper, we present a smoothing Newton method for solving the second-order cone programming (SOCP) based on the Chen–Harker–Kanzow–Smale (CHKS) smoothing function. Our smoothing method reformulates SOCP as a nonlinear system of equations and then applies Newton’s method to the system. The proposed method solves only one linear system of equations and performs only one line search at each iteration. It is shown that the method is globally and locally sub-quadratically convergent under a nonsingularity assumption. Numerical results suggest that the method is promising.     

A smoothing method for second order cone complementarity problem

In this paper, the second order cone complementarity problem is studied. Based on a perturbed symmetrically smoothing function, which has coerciveness under proper conditions, we present a smoothing Newton method for this problem. The boundedness of the level set can be obtained from the coerciveness, which plays an important role in the convergence analysis. Furthermore, the proposed algorithm for the reformulation has no restrictions on the starting point and solves only one system of equations. Preliminary numerical results indicate that the algorithm is effective.     

Convergence of a non-interior continuation algorithm for the monotone SCCP

It is well known that the symmetric cone complementarity problem（SCCP） is a broad class of optimization problems which contains many optimization problems as special cases.Based on a general smoothing function,we propose in this paper a non-interior continuation algorithm for solving the monotone SCCP.The proposed algorithm solves at most one system of linear equations at each iteration.By using the theory of Euclidean Jordan algebras,we show that the algorithm is globally linearly and locally quadratically convergent under suitable assumptions.     

Smoothing Newton algorithm for the second-order cone programming with a nonmonotone line search

The smoothing-type algorithms, which are in general designed based on some monotone line search, have been successfully applied to solve the second-order cone programming (denoted by SOCP). In this paper, we propose a nonmonotone smoothing Newton algorithm for solving the SOCP. Under suitable assumptions, we show that the proposed algorithm is globally and locally quadratically convergent. To compare with the existing smoothing-type algorithms for the SOCP, our algorithm has the following special properties: (i) it is based on a new smoothing function of the vector-valued natural residual function; (ii) it uses a nonmonotone line search scheme which contains the usual monotone line search as a special case. Preliminary numerical results demonstrate that the smoothing-type algorithm using the nonmonotone line search is promising for solving the SOCP.     

A new non-interior continuation method for <Emphasis Type="Italic">P</Emphasis><Subscript>0</Subscript>-NCP based on a SSPM-function

In this paper, we consider a new non-interior continuation method for the solution of nonlinear complementarity problem with P ₀-function (P ₀-NCP). The proposed algorithm is based on a smoothing symmetric perturbed minimum function (SSPM-function), and one only needs to solve one system of linear equations and to perform only one Armijo-type line search at each iteration. The method is proved to possess global and local convergence under weaker conditions. Preliminary numerical results indicate that the algorithm is effective.     

Analysis of a non-interior continuation method for second-order cone programming

Based on the Chen-Harker-Kanzow-Smale (CHKS) smoothing function, a non-interior continuation method is presented for solving the second-order cone programming (SOCP). Our algorithm reformulates the SOCP as a nonlinear system of equations and then applies Newton’s method to the perturbation of this system. The proposed algorithm does not have restrictions regarding its starting point and solves at most one linear system of equations at each iteration. Under suitable assumptions, the algorithm is shown to be globally and locally quadratically convergent. Some numerical results are also included which indicate that our algorithm is promising and comparable to interior-point methods.     

非线性互补问题的一种不可行非内点连续算法

基于Chen-Harker—Kanzow-Smale光滑函数，对单调非线性互补问题NCP(f)给出了一种不可行非内点连续算法，该算法在每次迭代时只需求解一个线性等式系统，执行一次线搜索，算法在NCP(f)的解处不需要严格互补的条件下，具有全局线性收敛性和局部二次收敛性．     

Quadratic convergence of a smoothing Newton method for symmetric cone programming without strict complementarity

This paper deals with symmetric cone programming (SCP), which includes the linear programming (LP), the second-order cone programming (SOCP), the semidefinite programming (SDP) as special cases. Based on the Chen?CMangasarian smoothing function of the projection operator onto symmetric cones, we establish a smoothing Newton method for SCP. Global and quadratic convergence of the proposed algorithm is established under the primal and dual constraint nondegeneracies, but without the strict complementarity. Moreover, we show the equivalence at a Karush?CKuhn?CTucker (KKT) point among the primal and dual constraint nondegeneracies, the nonsingularity of the B-subdifferential of the smoothing counterpart of the KKT system, and the nonsingularity of the corresponding Clarke??s generalized Jacobian.     

A smoothing Newton method for the second-order cone complementarity problem

In this paper we introduce a new smoothing function and show that it is coercive under suitable assumptions. Based on this new function, we propose a smoothing Newton method for solving the second-order cone complementarity problem (SOCCP). The proposed algorithm solves only one linear system of equations and performs only one line search at each iteration. It is shown that any accumulation point of the iteration sequence generated by the proposed algorithm is a solution to the SOCCP. Furthermore, we prove that the generated sequence is bounded if the solution set of the SOCCP is nonempty and bounded. Under the assumption of nonsingularity, we establish the local quadratic convergence of the algorithm without the strict complementarity condition. Numerical results indicate that the proposed algorithm is promising.