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.     

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).     

The non-interior continuation methods for solving theP0 function nonlinear complementarity problem

In this paper, we propose a new smooth function that possesses a property not satisfied by the existing smooth functions. Based on this smooth function, we discuss the existence and continuity of the smoothing path for solving theP ₀ function nonlinear complementarity problem ( NCP). Using the characteristics of the new smooth function, we investigate the boundedness of the iteration sequence generated by the non-interior continuation methods for solving theP ₀ function NCP under the assumption that the solution set of the NCP is nonempty and bounded. We show that the assumption that the solution set of the NCP is nonempty and bounded is weaker than those required by a few existing continuation methods for solving the NCP     

A Smoothing Newton Method for General Nonlinear Complementarity Problems

Smoothing Newton methods for nonlinear complementarity problems NCP(F) often require F to be at least a P ₀-function in order to guarantee that the underlying Newton equation is solvable. Based on a special equation reformulation of NCP(F), we propose a new smoothing Newton method for general nonlinear complementarity problems. The introduction of Kanzow and Pieper's gradient step makes our algorithm to be globally convergent. Under certain conditions, our method achieves fast local convergence rate. Extensive numerical results are also reported for all complementarity problems in MCPLIB and GAMSLIB libraries with all available starting points.     

The non-interior continuation methods for solving theP 0 function nonlinear complementarity problem

In this paper, we propose a new smooth function that possesses a property not satisfied by the existing smooth functions. Based on this smooth function, we discuss the existence and continuity of the smoothing path for solving theP ₀ function nonlinear complementarity problem ( NCP). Using the characteristics of the new smooth function, we investigate the boundedness of the iteration sequence generated by the non-interior continuation methods for solving theP ₀ function NCP under the assumption that the solution set of the NCP is nonempty and bounded. We show that the assumption that the solution set of the NCP is nonempty and bounded is weaker than those required by a few existing continuation methods for solving the NCP     

A new hybrid method for nonlinear complementarity problems

In this paper, a new hybrid method is proposed for solving nonlinear complementarity problems (NCP) with P ₀ function. In the new method, we combine a smoothing nonmonotone trust region method based on a conic model and line search techniques. We reformulate the NCP as a system of semismooth equations using the Fischer-Burmeister function. Using Kanzow’s smooth approximation function to construct the smooth operator, we propose a smoothing nonmonotone trust region algorithm of a conic model for solving the NCP with P ₀ functions. This is different from the classical trust region methods, in that when a trial step is not accepted, the method does not resolve the trust region subproblem but generates an iterative point whose steplength is defined by a line search. We prove that every accumulation point of the sequence generated by the algorithm is a solution of the NCP. Under a nonsingularity condition, the superlinear convergence of the algorithm is established without a strict complementarity condition.     

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.     

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.     

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 new smoothing and regularization Newton method for <Emphasis Type="Italic">P</Emphasis><Subscript>0</Subscript>-NCP

The nonlinear complementarity problem (denoted by NCP(F)) can be reformulated as the solution of a nonsmooth system of equations. In this paper, we propose a new smoothing and regularization Newton method for solving nonlinear complementarity problem with P ₀-function (P ₀-NCP). Without requiring strict complementarity assumption at the P ₀-NCP solution, the proposed algorithm is proved to be convergent globally and superlinearly under suitable assumptions. Furthermore, the algorithm has local quadratic convergence under mild conditions. Numerical experiments indicate that the proposed method is quite effective. In addition, in this paper, the regularization parameter ε in our algorithm is viewed as an independent variable, hence, our algorithm seems to be simpler and more easily implemented compared to many previous methods.     

A continuation method for linear complementarity problems with P 0 matrix

In this article, we propose a new continuation method for solving the linear complementarity problem (LCP). The method solves one system of linear equations and carries out only a one-line search at each iteration. The continuation method is based on a modified smoothing function. The existence and continuity of a smooth path for solving the LCP with a P ₀ matrix are discussed. We investigate the boundedness of the iteration sequence generated by our continuation method under the assumption that the solution set of the LCP is nonempty and bounded. It is shown to converge to an LCP solution globally linearly and locally superlinearly without the assumption of strict complementarity at the solution under suitable assumption. In addition, some numerical results are also reported in this article.     

Smoothing methods for nonsmooth, nonconvex minimization

We consider a class of smoothing methods for minimization problems where the feasible set is convex but the objective function is not convex, not differentiable and perhaps not even locally Lipschitz at the solutions. Such optimization problems arise from wide applications including image restoration, signal reconstruction, variable selection, optimal control, stochastic equilibrium and spherical approximations. In this paper, we focus on smoothing methods for solving such optimization problems, which use the structure of the minimization problems and composition of smoothing functions for the plus function (x)₊. Many existing optimization algorithms and codes can be used in the inner iteration of the smoothing methods. We present properties of the smoothing functions and the gradient consistency of subdifferential associated with a smoothing function. Moreover, we describe how to update the smoothing parameter in the outer iteration of the smoothing methods to guarantee convergence of the smoothing methods to a stationary point of the original minimization problem.     

A new smoothing Broyden-like method for solving nonlinear complementarity problem with a <Emphasis Type="Italic">P</Emphasis><Subscript>0</Subscript>-function

In this paper, we propose a new smoothing Broyden-like method for solving nonlinear complementarity problem with P ₀ function. The presented algorithm is based on the smoothing symmetrically perturbed minimum function φ(a, b) = min{a, b} and makes use of the derivative-free line search rule of Li et al. (J Optim Theory Appl 109(1):123–167, 2001). Without requiring any strict complementarity assumption at the P ₀-NCP solution, we show that the iteration sequence generated by the suggested algorithm converges globally and superlinearly under suitable conditions. Furthermore, the algorithm has local quadratic convergence under mild assumptions. Some numerical results are also reported in this paper.     

A new modified one-step smoothing Newton method for solving the general mixed complementarity problem

In last decades, there has been much effort on the solution and the analysis of the mixed complementarity problem (MCP) by reformulating MCP as an unconstrained minimization involving an MCP function. In this paper, we propose a new modified one-step smoothing Newton method for solving general (not necessarily P₀) mixed complementarity problems based on well-known Chen-Harker-Kanzow-Smale smooth function. Under suitable assumptions, global convergence and locally superlinear convergence of the algorithm are established.     

Smoothing inexact Newton methods for NCP with various nonmonotone techniques

Various iterative methods for solving nonlinear complementarity problems (NCP) are developed in recent years. In this paper we propose Jacobian smoothing inexact Newton methods for NCP with different nonmonotone strategies. The methods are based on semismooth equation reformulation of NCP by Fischer-Burmeister function. Nonmonotone line-search techniques are used for globalization procedure. Numerical performance of algorithms are compared. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A Regularization Newton Method for Solving Nonlinear Complementarity Problems

In this paper we construct a regularization Newton method for solving the nonlinear complementarity problem (NCP(F )) and analyze its convergence properties under the assumption that F is a P ₀ -function. We prove that every accumulation point of the sequence of iterates is a solution of NCP(F ) and that the sequence of iterates is bounded if the solution set of NCP(F ) is nonempty and bounded. Moreover, if F is a monotone and Lipschitz continuous function, we prove that the sequence of iterates is bounded if and only if the solution set of NCP(F ) is nonempty by setting , where is a parameter. If NCP(F) has a locally unique solution and satisfies a nonsingularity condition, then the convergence rate is superlinear (quadratic) without strict complementarity conditions. At each step, we only solve a linear system of equations. Numerical results are provided and further applications to other problems are discussed. Accepted 25 March 1998     

Smoothing Newton-Like Method for the Solution of Nonlinear Systems of Equalities and Inequalities

In this paper, we present a smoothing Newton-like method for solving non-linear systems of equalities and inequalities. By using the so-called max function, we transfer the inequalities into a system of semismooth equalities. Then a smoothing Newton-like method is proposed for solving the reformulated system, which only needs to solve one system of linear equations and to perform one line search at each iteration. The global and local quadratic convergence are studied under appropriate assumptions. Numerical examples show that the new approach is effective.     

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

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

A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities

In this paper we take a new look at smoothing Newton methods for solving the nonlinear complementarity problem (NCP) and the box constrained variational inequalities (BVI). Instead of using an infinite sequence of smoothing approximation functions, we use a single smoothing approximation function and Robinson’s normal equation to reformulate NCP and BVI as an equivalent nonsmooth equation H(u,x)=0, where H:ℜ ²ⁿ →ℜ ²ⁿ , u∈ℜ ⁿ is a parameter variable and x∈ℜ ⁿ is the original variable. The central idea of our smoothing Newton methods is that we construct a sequence {z ^k =(u ^k ,x ^k )} such that the mapping H(·) is continuously differentiable at each z ^k and may be non-differentiable at the limiting point of {z ^k }. We prove that three most often used Gabriel-Moré smoothing functions can generate strongly semismooth functions, which play a fundamental role in establishing superlinear and quadratic convergence of our new smoothing Newton methods. We do not require any function value of F or its derivative value outside the feasible region while at each step we only solve a linear system of equations and if we choose a certain smoothing function only a reduced form needs to be solved. Preliminary numerical results show that the proposed methods for particularly chosen smoothing functions are very promising. Received June 23, 1997 / Revised version received July 29, 1999?Published online December 15, 1999