An Accelerated Smoothing Newton Method with Cubic Convergence for Weighted Complementarity Problems

Smoothing Newton methods, which usually inherit local quadratic convergence rate, have been successfully applied to solve various mathematical programming problems. In this paper, we propose an accelerated smoothing Newton method (ASNM) for solving the weighted complementarity problem (wCP) by reformulating it as a system of nonlinear equations using a smoothing function. In spirit, when the iterates are close to the solution set of the nonlinear system, an additional approximate Newton step is computed by solving one of two possible linear systems formed by using previously calculated Jacobian information. When a Lipschitz continuous condition holds on the gradient of the smoothing function at two checking points, this additional approximate Newton step can be obtained with a much reduced computational cost. Hence, ASNM enjoys local cubic convergence rate but with computational cost only comparable to standard Newton's method at most iterations. Furthermore, a second-order nonmonotone line search is designed in ASNM to ensure global convergence. Our numerical experiments verify the local cubic convergence rate of ASNM and show that the acceleration techniques employed in ASNM can significantly improve the computational efficiency compared with some well-known benchmark smoothing Newton method.

Automated summary

In this paper, an accelerated smoothing Newton method (ASNM) is proposed for solving the weighted complementarity problem (wCP) by reformulating it as a system of nonlinear equations using a smoothing function. ASNM computes an additional approximate Newton step when the iterates are close to the solution set of the nonlinear system. This additional step can be obtained with a much reduced computational cost when a Lipschitz continuous condition holds on the gradient of the smoothing function at two checking points. The numerical experiments verify the local cubic convergence rate of ASNM and show its improved computational efficiency compared with some benchmark smoothing Newton methods.