Newton-type methods for optimization problems without constraint qualifications

Mikhail Solodov | Izmailov, Alexey

Keywords: constraints degeneracy | regularity | Newton method | mathematical programs with complementarity constraints

We consider equality-constrained optimization problems, where a given solution may not satisfy any constraint qualification, but satisfies the standard second-order sufficient condition for optimality. Based on local identification of the rank of the constraints degeneracy via the singular-value decomposition, we derive a modified primal-dual optimality system whose solution is locally unique, nondegenerate, and thus can be found by standard Newton-type techniques. Using identification of active constraints, we further extend our approach to mixed equality and inequality-constrained problems, and to mathematical programs with complementarity constraints (MPCC). In particular, for MPCC we obtain a local algorithm with quadratic convergence under the second-order sufficient condition only, without any constraint qualifications, not even the special MPCC constraint qualifications.

Anexos:

• siopt.pdf