nondegenerate matrix – Optimization Online

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

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