Oliver Stein

(University of Karlsruhe, Germany)

Lifting Mathematical Programs with Complementarity Constraints

Tuesday 2 June 2009, 10.30-11.30

5161.0105 (Bernoulliborg)

Abstract:

Mathematical programs with complementarity constraints (MPCCs) constitute a class of optimization problems with applications in game theory, network design, and truss topology design, among many others. In its simplest form, a complementarity constraint states that two variables are sign restricted while their product vanishes. Such constraints are notorious for severe problems in the numerical solution of MPCCs, which is essentially due to their nonsmoothness.

We present a new smoothing approach for MPCCs, based on the orthogonal projection of a smooth manifold. We study regularity of the lifted feasible set and, since the corresponding optimality conditions are inherently degenerate, introduce a regularization approach involving a novel concept of tilting stability.

A correspondence between the C-index in the original problem and the quadratic index in the lifted problem is shown. In particular, a local minimizer of the MPCC may numerically be found by minimization of the lifted, smooth problem. We report preliminary computational experience with the lifting approach.