Mathieu Frappier – Optimization Online

Polyhedral Newton-min algorithms for complementarity problems

Published: 2023/05/24

Complementarity and Variational Inequalities complementarity problem, global convergence, Least-square merit function, linesearch, Minimum function, Nonsmooth reformulation, p*-matrix, Polyhedral Newton-min algorithm, semismooth newton

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. … Read more

A lower bound on the iterative complexity of the Harker and Pang globalization technique of the Newton-min algorithm for solving the linear complementarity problem

Published: 2018/06/02, Updated: 2019/05/25

Jean-Pierre Dussault

Mathieu Frappier

Jean Charles Gilbert

Complementarity and Variational Inequalities, Nonsmooth Optimization fathi and murty problems, globalization, harker and pang algorithm, iteration complexity, line-search, linear complementarity problems, newton-min algorithm, nondegenerate matrix, p*-matrix, semismooth newton method

The plain Newton-min algorithm for solving the linear complementarity problem (LCP) 0 ≤ x ⊥ (Mx+q) ≥ 0 can be viewed as an instance of the plain semismooth Newton method on the equational version min(x,Mx+q) = 0 of the problem. This algorithm converges for any q when M is an M-matrix, but not when it … Read more