Smoothing Newton and Quasi-Newton Methods for Mixed Complementarity Problems

The mixed complementarity problem can be reformulated as a nonsmooth equation by using the median operator. In this paper, we first study some useful properties of this reformulation and then derive the Chen-Harker-Kanzow-Smale smoothing function for the mixed complementarity problem. On the basis of this smoothing function, we present a smoothing Newton method for solving the mixed complementarity problem. Under suitable conditions, the method exhibits global and quadratic convergence properties. We also present a smoothing Broyden-like method based on the same smoothing function. Under appropriate conditions, the method converges globally and superlinearly.     

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.     

A Globally Convergent Smoothing Newton Method for Nonsmooth Equations and Its Application to Complementarity Problems

The complementarity problem is theoretically and practically useful, and has been used to study and formulate various equilibrium problems arising in economics and engineerings. Recently, for solving complementarity problems, various equivalent equation formulations have been proposed and seem attractive. However, such formulations have the difficulty that the equation arising from complementarity problems is typically nonsmooth. In this paper, we propose a new smoothing Newton method for nonsmooth equations. In our method, we use an approximation function that is smooth when the approximation parameter is positive, and which coincides with original nonsmooth function when the parameter takes zero. Then, we apply Newton's method for the equation that is equivalent to the original nonsmooth equation and that includes an approximation parameter as a variable. The proposed method has the advantage that it has only to deal with a smooth function at any iteration and that it never requires a procedure to decrease an approximation parameter. We show that the sequence generated by the proposed method is globally convergent to a solution, and that, under semismooth assumption, its convergence rate is superlinear. Moreover, we apply the method to nonlinear complementarity problems. Numerical results show that the proposed method is practically efficient.     

求解无限维非线性互补问题的光滑化牛顿法

研究一类无限维非线性互补问题的光滑化牛顿法.借助于非线性互补函数,将无限维非线性互补问题转化为一个非光滑算子方程.构造光滑算子逼近非光滑算子,在光滑逼近算子满足方向可微相容性的条件下,证明了光滑化牛顿法具有超线性收敛性.     

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

非线性互补问题光滑化拟牛顿算法的收敛性分析

给出求解p_0函数非线性互补问题光滑化拟牛顿算法,在p_0函数非线性互补问题有非空有界解集且F'是Lipschitz连续的条件下,证明了算法的全局收敛性.全局收敛性的主要特征是不需要提前假设水平集是有界的.     

A Complexity Analysis of a Smoothing Method Using CHKS-functions for Monotone Linear Complementarity Problems

We consider the standard linear complementarity problem (LCP): Find (x, y) R ²ⁿ such that y = M x + q, (x, y) 0 and x _i y _i = 0 (i = 1, 2, ... , n), where M is an n × n matrix and q is an n-dimensional vector. Recently several smoothing methods have been developed for solving monotone and/or P ₀ LCPs. The aim of this paper is to derive a complexity bound of smoothing methods using Chen-Harker-Kanzow-Smale functions in the case where the monotone LCP has a feasible interior point. After a smoothing method is provided, some properties of the CHKS-function are described. As a consequence, we show that the algorithm terminates in Newton iterations where is a number which depends on the problem and the initial point. We also discuss some relationships between the interior point methods and the smoothing methods.     

A Theoretical and Numerical Comparison of Some Semismooth Algorithms for Complementarity Problems

In this paper we introduce a general line search scheme which easily allows us to define and analyze known and new semismooth algorithms for the solution of nonlinear complementarity problems. We enucleate the basic assumptions that a search direction to be used in the general scheme has to enjoy in order to guarantee global convergence, local superlinear/quadratic convergence or finite convergence. We examine in detail several different semismooth algorithms and compare their theoretical features and their practical behavior on a set of large-scale problems.     

非线性互补问题的一种全局收敛的显式光滑Newton方法

本针对Po函数非线性互补问题，给出了一种显式光滑Newton方法，该方法将光滑参数μ进行显式迭代而不依赖于Newton方向的搜索过程，并在适当的假设条件下，证明了算法的全局收敛性。     

非线性互补问题的水平值估计算法

本文研究非线性互补问题（NCP）的求解算法,先将NCP转化为约束全局优化问题（CGOP）,然后直接移植求解问题（CGOP）的水平值估计算法^[4,5]来求解问题（NCP）．文章证明了算法对于NCP是收敛的,数值实验说明了算法的有效性．     

A New Class of Semismooth Newton-Type Methods for Nonlinear Complementarity Problems

We introduce a new, one-parametric class of NCP-functions. This class subsumes the Fischer function and reduces to the minimum function in a limiting case of the parameter. This new class of NCP-functions is used in order to reformulate the nonlinear complementarity problem as a nonsmooth system of equations. We present a detailed investigation of the properties of the equation operator, of the corresponding merit function as well as of a suitable semismooth Newton-type method. Finally, numerical results are presented for this method being applied to a number of test problems.     

A New Homotopy Method for Nonlinear Complementarity Problems

In this paper, we present a new homotopy method for the nonlinear complementarity problems. Without the regularity or non-singulary assumptions for▽F(x), we prove that our homotopy equations have a bounded solution curve. The numerical tests confirm the efficiency of our proposed method.     

Complementarity Functions and Numerical Experiments on Some Smoothing Newton Methods for Second-Order-Cone Complementarity Problems

Two results on the second-order-cone complementarity problem are presented. We show that the squared smoothing function is strongly semismooth. Under monotonicity and strict feasibility we provide a new proof, based on a penalized natural complementarity function, for the solution set of the second-order-cone complementarity problem being bounded. Numerical results of squared smoothing Newton algorithms are reported.     

A Smoothing Method for a Mathematical Program with P-Matrix Linear Complementarity Constraints

We consider a mathematical program whose constraints involve a parametric P-matrix linear complementarity problem with the design (upper level) variables as parameters. Solutions of this complementarity problem define a piecewise linear function of the parameters. We study a smoothing function of this function for solving the mathematical program. We investigate the limiting behaviour of optimal solutions, KKT points and B-stationary points of the smoothing problem. We show that a class of mathematical programs with P-matrix linear complementarity constraints can be reformulated as a piecewise convex program and solved through a sequence of continuously differentiable convex programs. Preliminary numerical results indicate that the method and convex reformulation are promising.     

A Null Space Approach for Solving Nonlinear Complementarity Problems

In this work, null space techniques are employed to tackle nonlinear complementarity problems （NCPs）. NCP conditions are transform into a nonlinear programming problem, which is handled by null space algorithms, The NCP conditions are divided into two groups, Some equalities and inequalities in an NCP are treated as constraints, While other equalities and inequalities in an NCP are to be regarded as objective function. Two groups are all updated in every step. Null space approaches are extended to nonlinear complementarity problems. Two different solvers are employed for all NCP in an algorithm.     

基于凝聚函数的互补问题的光滑化算法

对于不可微的"极大值"形式的函数,可以利用凝聚函数对其进行光滑逼近.借助这个技术,给出了求解线性互补问题的光滑方程组算法.首先是将互补问题转化为等价的非光滑方程组,再利用凝聚函数进行光滑逼近,从而转化为光滑方程组的求解问题.通过一些考题对这个算法进行了数值试验,结果显示了该算法的有效性和稳定性.     

Extended LQP Method for Monotone Nonlinear Complementarity Problems

To solve nonlinear complementarity problems (NCP), the logarithmic-quadratic proximal (LQP) method solves a system of nonlinear equations at each iteration. In this paper, the iterates generated by the original LQP method are extended by explicit formulas and thus an extended LQP method is presented. It is proved theoretically that the lower bound of the progress obtained by the extended LQP method is greater than that by the original LQP method. Preliminary numerical results are provided to verify the theoretical assertions and the effectiveness of both the original and the extended LQP method.     

非线性互补问题的组合同伦算法

针对拟P_*-映射和P(τ,α,β)-映射所对应的非线性互补问题,本文对其解的存在性及有效求解算法进行了研究.文中利用组合同伦方法给出了这两类非线性互补问题存在有界解的构造性证明,并利用预估校正方法对同伦路径进行跟踪,得到了互补问题的解.通过数值算例验证了该算法的有效性.     

非线性互补问题的逐次逼近类Broyden算法

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.     

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