Back

G-2009-74

An \(\ell_1\) Elastic Interior-Point Method for Mathematical Programs with Complementarity Constraints

and

BibTeX reference

We propose an interior-point algorithm based on an elastic formulation of the \(\ell_1\)-penalty merit function for mathematical programs with complementarity constraints. The salient feature of our method is that it requires no prior knowledge of which constraints, if any, are complementarity constraints. Remarkably, the method allows for a uni ed treatment of both general, unstructured, degenerate problems and structured degenerate problems, such as problems with complementarity constraints, with no changes to accommodate one class or the other. Our results refi ne those of Gould et al. (2010) by isolating the degeneracy due to the complementarity constraints. The method naturally converges to a strongly stationary point or delivers a relevant certifi cate of degeneracy without recourse to second-order intermediate solutions. Preliminary numerical results on a standard test set illustrate the flexibility of the approach.

, 27 pages

This cahier was revised in September 2011

Research Axis

Research application

Publication

An \(\ell_1\) elastic interior-point method for mathematical programs with complementarity constraints
and
SIAM Journal on Optimization, 22(1), 187–211, 2012 BibTeX reference