An LP-Newton method: nonsmooth equations, KKT systems, and nonisolated solutions (Q403631)

The authors provide a new Newton-type method for the solution of the constraint system of equations according to \[ F(z)= 0,\quad z\in\Omega, \] where \(\Omega\subset\mathbb{R}^n\) is a nonempty and closed (convex) set and \(F: \mathbb{R}^n\to\mathbb{R}^n\) is a continuous (but not necessary differentiable) vector-valued function. -- Let \(G(z)\) be a suitable substitute for the Jacobian \(F'(z)\). Then, as an improvement of the classical Newton method, in any step the subproblem \[ \begin{gathered} \min_{z,\gamma}\,\gamma\quad\text{s.t. }z\in \Omega,\quad \gamma\geq 0,\quad\| z-z^k\|\leq\gamma\| F(z^k)\|,\\ \| F(z^k)+ G(z^k)(z- z^k)\|\leq\gamma\| F(z^k)\|^2\end{gathered} \] is solved where \(\|\cdot\|\) denotes arbitrary norms. (If the infinity norms are used and if the set \(\Omega\) is polyhedral, then the subproblems are linear programming problems.) -- It is shown in the main theorem that under suitable assumptions the method converges locally quadratically to a solution of the system. In the second part of the paper, the authors analyze the used assumptions and apply the results to establish local convergence properties in the case of KKT systems.