Optimization Online


Convergence Conditions for Newton-type Methods Applied to Complementarity Systems with Nonisolated Solutions

Andreas Fischer (Andreas.Fischer***at***tu-dresden.de)
Markus Herrich (Markus.Herrich***at***tu-dresden.de)
Alexey F. Izmailov (izmaif***at***ccas.ru)
Mikhail V. Solodov (solodov***at***impa.br)

Abstract: We consider a class of Newton-type methods for constrained systems of equations that involve complementarity conditions. In particular, at issue are the constrained Levenberg--Marquardt method and the recently introduced Linear Programming-Newton method, designed for the difficult case when solutions need not be isolated, and the equation mapping need not be differentiable at the solutions. We show that the only structural assumption needed for rapid local convergence of those algorithms is the piecewise error bound, i.e., a local error bound holding for the branches of the solution set resulting from partitions of the bi-active complementarity indices. The latter error bound is implied by various piecewise constraint qualifications, including some relatively weak ones. As further applications of our results, we consider Karush-Kuhn-Tucker systems arising from optimization or variational problems, and from generalized Nash equilibrium problems. In the first case, we show convergence under the assumption that the dual part of the solution is a noncritical Lagrange multiplier, and in the second case convergence follows under a certain relaxed constant rank condition. In both cases, this improves on results previously available for the corresponding problems.

Keywords: Complementarity condition, constrained equation, KKT system, generalized Nash equilibrium problem, error bound, LP-Newton method, constrained Levenberg-Marquardt method

Category 1: Complementarity and Variational Inequalities

Category 2: Nonlinear Optimization

Citation: Computational Optimization and Applications, http://link.springer.com/article/10.1007/s10589-015-9782-0

Download: [PDF]

Entry Submitted: 01/15/2015
Entry Accepted: 01/15/2015
Entry Last Modified: 09/01/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society