Séminaire Modélisation, Optimisation, Dynamique

On relaxation Methods for Mathematical Programs with Complementarity Constraints

par Mounir Haddou (INSA Rennes)

Europe/Paris
XLIM Salle X.203

XLIM Salle X.203

FST-Université de Limoges, 123, Av. Albert Thomas.
Description

We consider the Mathematical Program with Complementarity Constraints of minimizing a function f under :
- the inequality constraints $g(x) \leq 0$,
- the equality constraints $h(x)=0$,
- and the complementary constraints $0 \leq G(x) \perp H(x) \geq 0$.
All functions are assumed to be continuously differentiable.

We propose a new family of relaxation schemes for mathematical programs with complementarity constraints that extends the relaxations converging to an M-stationary point [1, 2, 3]. We discuss the properties of the sequence of relaxed non-linear programs as well as stationarity properties of limiting points. We prove under a new and weak constraint qualification, that our relaxation schemes have the desired property of converging to an M-stationary point.
 
Unfortunately, in practice, relaxed problems are only solved up to approximate stationary points and the guarantee of convergence to an M-stationary point is lost [4].
 
We define a new strong approximate stationarity condition and prove that we can maintain our guarantee of convergence and attain the desired goal of computing an M-stationary point.
 
A comprehensive numerical comparison between existing relaxations methods is performed and shows promising results for our new methods. We also propose different extensions to tackle MPVC (vanishing constraints) and MOCC (cardinality constraints) problems.
 
[1] Flegel, Michael L and Kanzow, Christian, Abadie-type constraint qualification for mathematical programs with equilibrium constraints, 2005.
[2] Kadrani, Abdeslam and Dussault, Jean-Pierre and Benchakroun, Abdelhamid, A new regularization scheme for mathematical programs with complementarity constraints, 2009.
[3] Schwartz, Alexandra, Mathematical programs with complementarity  constraints: Theory, methods, and applications, 2011.
[4] Kanzow, Christian and Schwartz, Alexandra, The Price of Inexactness:  Convergence Properties of Relaxation Methods for Mathematical Programs with Complementarity Constraints Revisited, 2015.