Preprint A698/2011
Augmented Lagrangian methods applied to optimization problems with degenerate constraints, including problems with complementarity constraints

E.I. Uskov | Izmailov, A.F. | Solodov, M.V.

**Keywords: **

We consider global convergence properties of the augmented
Lagrangian methods on problems with degenerate constraints, with a
special emphasis on mathematical programs with complementarity
constraints (MPCC). In the general case, we show convergence to
stationary points of the problem under an error bound condition
for the feasible set (which is weaker than constraint
qualifications), assuming that the iterates have some modest
features of approximate local minimizers of the augmented
Lagrangian. For MPCC, we first argue that even weak forms of
general constraint qualifications that are suitable for
convergence of the augmented Lagrangian methods, such as the
recently proposed relaxed positive linear dependence condition,
should not be expected to hold and thus special analysis is
needed. We next obtain a rather complete picture, showing that
under the usual in this context MPCC-linear independence
constraint qualification feasible accumulation points of the iterates are
guaranteed to be
C-stationary for MPCC (better than weakly stationary), but in
general need not be M-stationary (hence, neither strongly
stationary). However, strong stationarity is
guaranteed if the generated dual sequence is bounded, which we show
to be the typical numerical behaviour even though the
multiplier set itself is unbounded.
Experiments with the ALGENCAN augmented Lagrangian solver on the
MacMPEC and DEGEN collections are reported, with comparisons
to the SNOPT and filterSQP implementations of the SQP method, to
the MINOS implementation of the linearly constrained Lagrangian
method, and to the interior-point solvers IPOPT and KNITRO.
We show that ALGENCAN is a very good option if one is
primarily interested in
robustness and quality of computed solutions.