Polyhedral Newton-min algorithms for complementarity problems

• 成果类型: Article; Early Access
• 署名作者: Dussault, Jean-Pierre; Frappier, Mathieu; Gilbert, Jean Charles
• 署名单位: University of Sherbrooke; University of Sherbrooke
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-025-02219-y
• 发表日期: 2025
• 关键词: augmented lagrangian algorithm; computational complexity; variational-inequalities; nonlinear programs; iterative method; normal maps; CONVERGENCE; systems; FLOW; CONSTRUCTION

摘要

The semismooth Newton method is a very efficient approach for computing a zero of a large class of nonsmooth equations. When the initial iterate is sufficiently close to a regular zero and the function is strongly semismooth, the generated sequence converges quadratically to that zero, while the iteration only requires to solve a linear system. If the first iterate is far away from a zero, however, it is difficult to force its convergence using linesearch or trust regions because a semismooth Newton direction may not be a descent direction of the associated least-squares merit function, unlike when the function is differentiable. We explore this question in the particular case of a nonsmooth equation reformulation of the nonlinear complementarity problem, using the minimum function. We propose a globally convergent algorithm using a modification of a semismooth Newton direction that makes it a descent direction of the least-squares function. Instead of requiring that the direction satisfies a linear system, it must be a feasible point of a convex polyhedron; hence, it can be computed in polynomial time. This polyhedron is defined by the often very few inequalities, obtained by linearizing pairs of functions that have close negative values at the current iterate; hence, somehow, the algorithm feels the proximity of a negative kink of the minimum function and acts accordingly. In order to avoid as often as possible the extra cost of having to find a feasible point of a polyhedron, a hybrid algorithm is also proposed, in which the Newton-min direction is accepted if a sufficient-descent-like criterion is satisfied, which is often the case in practice. Global and fast convergence to regular solutions is proved. Promising numerical experiments on a few linear complementarity problems are reported, using an implementation of the hybrid algorithm in Matlab.