Jean-Pierre Dussault

Mounir † Haddou

Abdeslam ‡ Kadrani

Migot

Tangi

How to Compute an M-Stationary Point of the MPCC

Keywords: nonlinear programming -MPCC -MPEC -relaxation methods -regularization methods -stationarity -constraint qualification -complementarity -optimization model with complementarity constraints AMS Subject Classification : 90C30, 90C33, 49M37, 65K05

, that relaxation methods with approximate stationary points fail to give guarantee of convergence. We show that by defining a new strong approximate stationarity we can attain the desired goal of computing an M-stationary point. We also provide an algorithmic strategy to compute such point. Existence of strong approximate stationary point in the neighborhood of an M-stationary point is proved.

Introduction

We consider the Mathematical Program with Complementarity Constraints min x∈R n f (x) s.t. g(x) ≤ 0, h(x) = 0, 0 ≤ G(x) ⊥ H(x) ≥ 0, (MPCC) with f : R n → R, g : R n → R p , h : R n → R m and G, H : R n → R q . All these functions are assumed to be continuously differentiable through this paper. The notation 0 ≤ u ⊥ v ≥ 0 for two vectors u and v in R q is a shortcut for u ≥ 0, v ≥ 0 and u T v = 0. In this context solving the problem means finding a local minimum. Even so this goal apparently modest is hard to achieve in general.

This problem has become an active subject in the literature since the last two decades and has been the subject of several monographs [START_REF] Luo | Mathematical programs with equilibrium constraints[END_REF][START_REF] Outrata | Mathematical Programs with Equilibrium Constraints: Theory and Numerical Methods[END_REF] and PhD thesis [START_REF] Flegel | Constraint Qualifications and Stationarity Concepts for Mathematical Programs with Equilibrium Constraints[END_REF][START_REF] Kadrani | Nouvelles Régularisations pour l'optimisation avec contraintes de complémentarité[END_REF][START_REF] Hoheisel | Mathematical programs with vanishing constraints[END_REF][START_REF] Veelken | A new relaxation scheme for mathematical programs with equilibrium constraints: Theory and numerical experience[END_REF][START_REF] Schwartz | Mathematical programs with complementarity constraints: Theory, methods, and applications[END_REF][START_REF] Coulibaly | An 1 Elastic Interior-Point Method for Mathematical Programs with Complementarity Constraints[END_REF]. The wide variety of applications that can be casted as an MPCC is one of the reason for this popularity. Among other we can cite truss topology optimization [START_REF] Hoheisel | Mathematical programs with vanishing constraints[END_REF], discrete optimization [START_REF] Abdallah | An exact penalty approach for mathematical programs with equilibrium constraints[END_REF], image restoration [START_REF] Bergounioux | A new relaxation method for a discrete image restoration problem[END_REF], optimal control [START_REF] Albrecht | Mathematical programs with complementarity constraints in the context of inverse optimal control for locomotion[END_REF][START_REF] Hintermüller | Mathematical Programs with Complementarity Constraints in Function Space: C-and Strong Stationarity and a Path-Following Algorithm[END_REF]. Otherwise, another source of problem are bilevel programming problems [START_REF] Dempe | Foundations of bilevel programming[END_REF][START_REF] Dempe | Bilevel programming problems: theory, algorithms and applications to energy networks[END_REF], where the lower-level problem is replaced by its optimality conditions. This may lead to a more general kind of problem called Mathematical Program with Equilibrium Constraint [START_REF] Outrata | Mathematical Programs with Equilibrium Constraints: Theory and Numerical Methods[END_REF] or Optimization Problem with Variational Inequality Constraint [START_REF] Ye | Necessary optimality conditions for optimization problems with variational inequality constraints[END_REF]. The MPCC formulation has been the most popular in the literature motivated by more accessible numerical approaches.

(MPCC) is clearly a non-linear programming problem and in general most of the functions involved in the formulation are non-convex. In this context solving the problem means finding a local minimum. Even so this goal apparently modest is hard to achieve in general due to the degenerate nature of the MPCC. Therefore, numerical methods that consider only first order informations may expect to compute a stationary point.

The wide variety of approaches with this aim computes the KKT conditions, which require that some constraint qualification holds at the solution to be an optimality condition. However, it is well-known that these constraint qualifications never hold in general for (MPCC). For instance, the classical Mangasarian-Fromowitz constraint qualification that is very often used to guarantee convergence of algorithms is violated at any feasible point. This is partly due to the geometry of the complementarity constraint that always has an empty relative interior.

These issues have motivated the definition of enhanced constraint qualifications and optimality conditions for (MPCC) as in [START_REF] Ye | Necessary optimality conditions for optimization problems with variational inequality constraints[END_REF][START_REF] Ye | Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints[END_REF][START_REF] Scheel | Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity[END_REF][START_REF] Flegel | On m-stationary points for mathematical programs with equilibrium constraints[END_REF] to cite some of the earliest research. In 2005, Flegel & Kanzow provide an essential result that defines the right necessary optimality condition to (MPCC). This optimality condition is called M(Mordukhovich)-stationary condition. The name comes from the fact that those conditions are derived by using Mordukhovich normal cone in the usual optimality conditions of (MPCC).

In view of the constraint qualifications issues that plague the (MPCC) the relaxation methods provide an intuitive answer. The complementarity constraint is relaxed using a parameter so that the new feasible domain is not thin anymore. It is assumed here that the classical constraints g(x) ≤ 0 and h(x) = 0 are not more difficult to handle than the complementarity constraint. Finally, the relaxing parameter is reduce to converge to the feasible set of (MPCC) similar to an homotopy technique. The interest for such methods has already been the subject of some PhD thesis in [START_REF] Schwartz | Mathematical programs with complementarity constraints: Theory, methods, and applications[END_REF][START_REF] Veelken | A new relaxation scheme for mathematical programs with equilibrium constraints: Theory and numerical experience[END_REF] and is an active subject in the literature.

These methods have been suggested in the literature back to 2000 by Scheel & Scholtes in [START_REF] Scheel | Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity[END_REF] replacing the complementarity ∀i ∈ {1, . . . , q} by G i (x)H i (x) -t ≤ 0.

For more clarity we denote Φ t (x) the map that relaxed the complementarity constraint and so in this case ∀i ∈ {1, . . . , q}

Φ SS i (G(x), H(x); t) = G i (x)H i (x) -t. (SS)
This natural approach is later extended by Demiguel, Friedlander, Nogales & Scholtes in [START_REF] Demiguel | A two-sided relaxation scheme for mathematical programs with equilibrium constraints[END_REF] by also relaxing the positivity constraints G(x) ≥ -t, H(x) ≥ -t. In [START_REF] Lin | A modified relaxation scheme for mathematical programs with complementarity constraints[END_REF], Lin & Fukushima improve this relaxation by expressing the same set with two constraints instead of three. This improvement leads to improved constraint qualification satisfied by the relaxed sub-problem. Even so the feasible set is not modified this improved regularity does not come as a surprise, since constraint qualification measures the way the feasible set is described and not necessarily the geometry of the feasible set itself. In [START_REF] Steffensen | A new relaxation scheme for mathematical programs with equilibrium constraints[END_REF], the authors consider a relaxation of the same type but only around the corner G(x) = H(x) = 0 in the following way ∀i ∈ {1, . . . , q}

Φ SU i (G(x), H(x); t) = G i (x) + H i (x) - |G i (x) -H i (x)|, if |G i (x) -H i (x)| ≥ t, tψ( Gi(x)-Hi(x) t ), otherwise, (SU)
where ψ is a suitable function as described in [START_REF] Steffensen | A new relaxation scheme for mathematical programs with equilibrium constraints[END_REF]. An example of such function being ψ(z) = 2 π sin( π 2 z + 3π 2 ) + 1.

In the corresponding papers it has been shown that under suitable conditions providing convergence of the methods they still might converge to some spurious point, called C-stationary point. The convergence to M-stationary being guaranteed only under some second-order condition. Up to this point it is to be noted that different methods used in the literature such as interior-point methods, smoothing of an NCP function and elastic net methods share a lot of common properties with the (SS) method and its extension.

A new perspective for those schemes has been motivated in [START_REF] Kadrani | A new regularization scheme for mathematical programs with complementarity constraints[END_REF] providing an approximation scheme with convergence to M-stationary point by considering ∀i ∈ {1, . . . , q}

Φ KDB i (G(x), H(x); t) = (G i (x) -t)(H i (x) -t).
(KDB) This is not a relaxation since the feasible domain of (MPCC) is not included in the feasible set of the subproblems. The method has been extended has a relaxation method through a NCP function in [START_REF] Kanzow | A New Regularization Method for Mathematical Programs with Complementarity Constraints with Strong Convergence Properties[END_REF] ∀i ∈ {1, . . . , q} as

Φ KS i (G(x), H(x); t) = φ(G i (x) -t, H i (x) -t). (KS)
In a recent paper, [START_REF] Kanzow | The Price of Inexactness: Convergence Properties of Relaxation Methods for Mathematical Programs with Complementarity Constraints Revisited[END_REF], Kanzow & Schwartz discuss convergence of the method (KS) considering sequence of approximate stationary points, that is a point that satisfy approximately the KKT conditions. They illustrate the fact that the method may converge to spurious weak-stationary point. Our motivation in this paper is to deal with this issue and present an algorithmic approach.

We present in this paper a generalized framework to study relaxation methods that encompass the methods KDB, KS and the recent butterfly relaxation. We introduce a new method called asymmetric relaxation that also belong to this framework. Then, by introducing a new kind of approximate stationary point we prove that the methods that belong to the generalized framework converge to M-stationary points. We also deal with the question of existence and computation of such point. Existence is proved in the neighbourhood of an M-stationary point without the need of constraint qualification. An active set-penalization scheme that is a generalization of the penalized-active-set method proposed in [START_REF] Kadrani | A globally convergent algorithm for mpcc[END_REF] is proposed to solve the sub-problems of the relaxation.

The rest of this paper is organized as follows : Section 2 introduces the basic knowledge from non-linear programming and mathematical programming with complementarity constraints that will be extensively used along this paper. Section 3 presents a unified framework to study relaxation methods and Section 4 illustrates that the strongest existing methods as well as a new asymmetric relaxation belong to this framework. Section 5 motivates the difficulty of computing a stationary point of MPCC by using approximate sequences of stationary point. These issues are solved in Section 6, which presents a new notion of approximate stationary point that is sufficient to guarantee the well-behaviour of relaxation methods. Section 7 discuss existence of approximate stationary points in a neighborhood of a solution that may not exist. These issues are handled in two steps. Firstly, Section 8 introduces the MPCC with slack variables. Secondly, Section 9 shows that for the MPCC with slack variables, existence of strong epsilon stationary points is guaranteed under very mild conditions. Finally, Section 10 presents an algorithmic strategy to compute the new approximate stationary point, while Section 11 shows preliminaries numerical results using this strategy.

Notations Through this paper, we use classical notation in optimization. Let x T denotes the transpose of a vector or a matrix x. The gradient of a function f at a point x with respect to x is denoted ∇ x f (x) and ∇f (x) when the derivative is clear from the context. supp(x) for x ∈ R n is the set of indices such that x i = 0 for i ∈ {1, . . . , n}. 1l is the vector whose components are all one. R + and R ++ denotes the set of non-negative and positive real numbers. Given two vectors u and v in R n , let u • v denotes the Hadamard product of two vectors so that u • v = (u i v i ) 1≤i≤n . We also use classical asymptotic Landau notations :

f (x) = o(g(x)
) as x → a if and only if for all positive constant M there exists a positive number

δ such that |f (x)| ≤ M |g(x)| for all |x -a| ≤ δ, in other words lim x→a f (x) g(x) = 0. f (x) = ω(g(x)
) as x → a if and only if for all positive constant M there exists a positive number δ such

that |f (x)| ≥ M |g(x)| for all |x -a| ≤ δ. f (x) ∼ (g(x)) as x → a if and only lim x→a f (x) g(x) = K with K a positive finite constant.

Preliminaries

We give classical definitions from non-linear programming and then present their enhanced version to MPCC that will be used in the sequel.

Non-Linear Programming

Let a general non-linear program be

min x∈R n f (x) s.t. g(x) ≤ 0, h(x) = 0, (NLP)
with g : R n → R p , h : R n → R m and f : R n → R. Denote F the feasible region of (NLP), the set of active indices I g (x) := {i ∈ {1, ..., p} | g i (x) = 0} at x, the generalized Lagrangian L r (x, λ) = rf (x) + g(x) T λ g + h(x) T λ h with λ = (λ g , λ h ) and M r (x) is the set of index r multipliers. By definition, λ is an index r multiplier for (NLP) at a feasible point x if (r, λ) = 0 and ∇ x L r (x, λ) = 0, λ ≥ 0, g(x) T λ = 0. An index 0 multiplier is also called singular multiplier, [START_REF] Bonnans | Perturbation analysis of optimization problems[END_REF], or an abnormal multiplier, [START_REF] Clarke | Optimization and nonsmooth analysis[END_REF]. We call a KKT-point a couple (x, λ) with λ an 1-index multiplier at x. A couple (x, λ) with λ a 0-index multiplier at x is called Fritz-John point.

In the context of solving non-linear program, that is finding a local minimum, one widely used technique is to compute necessary conditions also called optimality conditions. The principle tool is the Karush-Kuhn-Tucker (KKT) conditions. Let x * be a local minimum of (NLP) that satisfy a constraint qualification, then there exists λ ∈ M 1 (x * ) that satisfy

∇ x L 1 (x * , λ) = 0, min(-g(x * ), λ g ) = 0, h(x * ) = 0.
(KKT)

A point (x * , λ) that satisfy (KKT) is called a stationary point. In the context of numerical computation it can be difficult to compute stationary points. Hence, it is of interest to consider epsilon-stationary points. Definition 2.1 (epsilon-stationary point). Given a general non-linear program (NLP) and ≥ 0. We say that

(x * , λ) ∈ R n × R m × R p is an epsilon-stationary point (or an epsilon-KKT point) if it satisfies ∇ x L 1 (x * , λ) ∞ ≤ , and
g i (x * ) ≤ , λ g i ≥ 0, |λ g i g i (x * )| ≤ , ∀i ∈ {1, . . . , p}, |h i (x * )| ≤ , ∀i ∈ {1, . . . , m}.
At = 0 we get the classical definition of a stationary point of (NLP).

Mathematical Program with Complementarity Constraints

Let Z be the set of feasible points of (MPCC). Given x ∈ Z, we denote

I +0 (x) := {i ∈ {1, . . . , q} | G i (x) > 0 and H i (x) = 0}, I 0+ (x) := {i ∈ {1, . . . , q} | G i (x) = 0 and H i (x) > 0}, I 00 (x) := {i ∈ {1, . . . , q} | G i (x) = 0 and H i (x) = 0}.
We define the generalized MPCC-Lagrangian function of (MPCC) as

L r M P CC (x, λ) := rf (x) + λ g g(x) + λ h h(x) -λ G G(x) -λ H H(x), with λ := (λ g , λ h , λ G , λ H ).
We remind that the tangent cone of a set X at x * ∈ X is a closed cone defined by

T X (x * ) := {d ∈ R n | ∃t k ≥ 0 and x k → X x * s.t. t k (x k -x * ) → d}.
The cone L M P CC , defined in [START_REF] Scheel | Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity[END_REF], is given as the following not necessarily convex cone

L M P CC (x * ) := {d ∈ R n |∇g i (x * ) T d ≤ 0 ∀i = 1, . . . , p, ∇h i (x * ) T d = 0 ∀i = 1, . . . , m, ∇G i (x * ) T d = 0 ∀i ∈ I 0+ (x * ), ∇H i (x * ) T d = 0 ∀i ∈ I +0 (x * ), ∇G i (x * ) T d ≥ 0, ∇H i (x) T d ≥ 0 ∀i ∈ I 00 (x * ), (∇G i (x * ) T d)(∇H i (x * ) T d) = 0 ∀i ∈ I 00 (x * )}.
Due to [START_REF] Flegel | Abadie-type constraint for mathematical programs with equilibrium constraints[END_REF], one always has the following inclusions

T Z (x * ) ⊆ L M P CC (x * ).
Given a cone K ⊂ R n , the polar of K is the cone defined by

K • := {z ∈ R n | z T x ≤ 0, ∀x ∈ K}.
We can now define a mild constraint qualification for (MPCC) called MPCC-Guignard CQ.

Definition 2.2. Let x * ∈ Z. We say that MPCC-GCQ holds at

x * if T • Z (x * ) = L • M P CC (x * ).
In general, there does not exist KKT stationary points since (MPCC) is highly degenerate and does not satisfy classical constraint qualification from non-linear programming. So we introduce weaker stationary concepts as in [START_REF] Scheel | Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity[END_REF][START_REF] Ye | Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints[END_REF].

Definition 2.3. [Stationary point] x * ∈ Z is said • Weak-stationary if there exists λ ∈ R m × R p × R q × R q such that ∇ x L 1 M P CC (x * , λ) = 0, min(-g(x * ), λ g ) = 0, h(x * ) = 0, ∀i ∈ I +0 (x * ), λ G i = 0, and ∀i ∈ I 0+ (x * ), λ H i = 0;
• Clarke-stationary point if x * is weak-stationary and ∀i ∈ I 00 (x * ), λ G i λ H i ≥ 0;

• Alternatively (or Abadie)-stationary point if x * is weak-stationary and

∀i ∈ I 00 (x * ), λ G i ≥ 0 or λ H i ≥ 0; • Mordukhovich-stationary point if x * is weak-stationary and ∀i ∈ I 00 (x * ), either λ G i > 0, λ H i > 0 or λ G i λ H i = 0; • Strong-stationary point if x * is weak-stationary and ∀i ∈ I 00 (x * ), λ G i ≥ 0, λ H i ≥ 0.
Relations between these notions are straightforward from the definition.

The following theorem is a keystone to define necessary optimality conditions for (MPCC).

Theorem 2.1 ([14]

). A local minimum of (MPCC) that satisfies MPCC-GCQ or any stronger MPCC-CQ is an M-stationary point. Therefore, devising algorithms to reach KKT stationary points (S-stationary) is not possible in general, and we must satisfy ourselves in devising algorithms reaching M-stationary points. The following example due to Kanzow and Schwartz exhibits a situation where the global minimizer is not a KKT point but an M-stationary point. We will return to this example later on.

Example 2.1.

min x∈R 3 x 1 + x 2 -x 3 s.t. g 1 (x) := -4x 1 + x 3 ≤ 0, g 2 (x) := -4x 2 + x 3 ≤ 0, 0 ≤ G(x) := x 1 ⊥ H(x) := x 2 ≥ 0.
The global solution is (0, 0, 0) t but is not a KKT point. Indeed, the gradient of the Lagrangian equal to zero yields

0 =   1 1 -1   + λ g 1   -4 0 1   + λ g 2   0 -4 1   -λ G 1   1 0 0   -λ H 2   0 1 0   + η   0 0 0   ,
and since λ g 1 + λ g 2 = 1(third line), summing the first two lines yields 2 -4(λ g

1 + λ g 2 ) -λ G 1 -λ H 2 = 0 and therefore λ G 1 + λ H 2 = -2;
both cannot be non-negative.

Apart from MPCC-GCQ there exists a wide variety of MPCC constraint qualification described in the literature. We conclude this section by defining only a short selection of them with interesting properties for relaxation methods. Most of these conditions are constraint qualification from non-linear programming that are extended for (MPCC).

One of the most principal constraint qualification used in the literature of (MPCC) is the MPCC-LICQ, see [START_REF] Scholtes | How stringent is the linear independence assumption for mathematical programs with complementarity constraints[END_REF] for a discussion on this CQ. In a similar way we extend CRCQ as in [START_REF] Guo | Second-order optimality conditions for mathematical programs with equilibrium constraints[END_REF]. A condition that is similar was used in [START_REF] Kanzow | A New Regularization Method for Mathematical Programs with Complementarity Constraints with Strong Convergence Properties[END_REF][START_REF] Hoheisel | Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints[END_REF] to prove convergence of relaxation methods for (MPCC). Definition 2.4. Let x * ∈ Z.

1. MPCC-LICQ holds at x * if the gradients

{∇g i (x * ) (i ∈ I g (x * )), ∇h i (x * ) (i = 1, . . . , m), ∇G i (x * ) (i ∈ I 00 (x * )∪I 0+ (x * )), ∇H i (x * ) (i ∈ I 00 (x * )∪I +0 (x * ))} are linearly independent.
2. MPCC-CRCQ holds at x * if there exists δ > 0 such that, for any subsets I 1 ⊆ I g (x * ), I 2 ⊆ {1, . . . , m}, I 3 ⊆ I 0+ (x * ) ∪ I 00 (x * ), and I 4 ⊆ I +0 (x * ) ∪ I 00 (x * ), the family of gradients

{∇g i (x * ) (i ∈ I 1 ), ∇h i (x * ) (i ∈ I 2 ), ∇G i (x * ) (i ∈ I 3 ), ∇H i (x * ) (i ∈ I 4 )}
has the same rank for each x ∈ B δ (x * ), where B δ (x * ) is the ball of radius δ centered at x * .

In order to prove convergence of very general relaxation methods we consider the definition of MPCC-CRSC, which was introduced and proved to be a constraint qualification very recently in [START_REF] Dussault | The new butterfly relaxation methods for mathematical program with complementarity constraint[END_REF].

The polar of the cone L M P CC is a key tool in the definition of constraint qualification. It is however not trivial to compute. Therefore, we introduce the following cone:

P M (x * ) := {d ∈ R n | ∃(λ g , λ h , λ G , λ H ) ∈ R p + × R m × R q × R q with λ G i λ H i = 0 or λ G i > 0, λ H i > 0 ∀i ∈ I 00 (x * ), d = i∈Ig(x * ) λ g i ∇g i (x * ) + m i=1 λ h i ∇h i (x * ) - i∈I 0+ (x * )∪I 00 (x * ) λ G i ∇G i (x * ) - i∈I +0 (x * )∪I 00 (x * ) λ H i ∇H i (x * )}.
Definition 2.5. Let x * ∈ Z. MPCC-CRSC holds at x * if for any partition I 00 ++ ∪ I 00 0-∪ I 00 -0 = I 00 (x * ) such that i∈Ig

λ g i ∇g i (x * ) + m i=1 λ h i ∇h i (x * ) - i∈I 0+ (x * )∪I 00 ++ λ G i ∇G i (x * ) - i∈I +0 (x * )∪I 00 ++ λ H i ∇H i (x * ) + i∈I 00 -0 λ G i ∇G i (x * ) + i∈I 00 0- λ H i ∇H i (x * ) = 0, with λ g i ≥ 0 (i ∈ I g (x * )),λ G i and λ H i ≥ 0 (i ∈ I 00 ++ ), λ G i > 0 (i ∈ I 00 -0 ), λ H i (i ∈ I 00 0-) > 0,
there exists δ > 0 such that the family of gradients

{∇g i (x) (i ∈ I 1 ), ∇h i (x) (i = 1, . . . , m), ∇G i (x) (i ∈ I 3 ), ∇H i (x) (i ∈ I 4 )},
has the same rank for every x ∈ B δ (x * ), where

I 1 := {i ∈ I g (x * )| -∇g i (x * ) ∈ P M (x * )}, I 3 := I 0+ (x * ) ∪ {i ∈ I 00 ++ |∇G i (x * ) ∈ P M (x * )} ∪ I 00 -0 , I 4 := I +0 (x * ) ∪ {i ∈ I 00 ++ |∇H i (x * ) ∈ P M (x * )} ∪ I 00 0-.
It is not necessary to add that the gradients -∇G i (x * ) and -∇H i (x * ) belong to P M (x * ). Indeed, we already require that λ G i and λ H i must be non-zero respectively for the indices i ∈ I 00 -0 and i ∈ I 00 0-and so it implies that these gradients belong to this set.

Furthermore, MPCC-CRSC is weaker than MPCC-CRCQ. Indeed, MPCC-CRCQ requires that every family of linearly dependant gradients remains linearly dependant in some neighbourhood, while the MPCC-CRSC condition consider only the family of gradients that are linearly dependant with coefficients that have M-stationary signs.

A Unified Framework for Relaxation/Approximation Methods

In the past decade, several methods have been proposed to compute an M-stationary point of (MPCC). The first was the approximation scheme proposed by [START_REF] Kadrani | A new regularization scheme for mathematical programs with complementarity constraints[END_REF], which was latter improved as a relaxation by [START_REF] Kanzow | A New Regularization Method for Mathematical Programs with Complementarity Constraints with Strong Convergence Properties[END_REF]. This relaxation scheme has been generalized recently in [START_REF] Dussault | The new butterfly relaxation methods for mathematical program with complementarity constraint[END_REF] to a more general family of relaxation schemes. We proposed in this section a unified framework that embraces those methods and may be used to derive new ones.

Consider the following parametric non-linear program R t (x) parametrized by the vector t:

min x∈R n f (x) s.t. g(x) ≤ 0, h(x) = 0, G(x) ≥ -t(t)1l, H(x) ≥ -t(t)1l, Φ(G(x), H(x); t) ≤ 0, (R t (x))
with t : R l + → R + such that lim t →0 t(t) → 0 and the relaxation map Φ : R n → R q . In the sequel we skip the dependency in t and denote t to simplify the notation. It is to be noted here that t is a vector of an arbitrary size denoted l as for instance in [START_REF] Dussault | The new butterfly relaxation methods for mathematical program with complementarity constraint[END_REF] where l = 2. The generalized Lagrangian function of (R t (x))

is defined for ν ∈ R p × R m × R q × R q × R q as L r Rt (x, ν) := rf (x) + g(x) T ν g + h(x) T ν h -G(x) T ν G -H(x) T ν H + Φ(G(x), H(x); t) T ν Φ .
Let I Φ be the set of active indices for the constraint Φ(G(x), H(x); t) ≤ 0, i.e.

I Φ (x; t) := {i ∈ {1, . . . , q} | Φ i (G(x), H(x); t) = 0}.
The definition of a generic relaxation scheme is completed by the following hypotheses:

• Φ(G(x), H(x); t) is a continuously differentiable real valued map extended component by component, so that

Φ i (G(x), H(x); t) := Φ(G i (x), H i (x); t). (H1)
• Direct computations give that the gradient with respect to x for i ∈ {1, . . . , q} of Φ i (G(x), H(x); t) for all x ∈ R n is given by

∇ x Φ i (G(x), H(x); t) = ∇G i (x)α H i (x; t) + ∇H i (x)α G i (x; t),
where α H (x; t) and α G (x; t) are continuous maps by smoothness assumption on Φ(G(x), H(x); t), which we assume satisfy ∀x ∈ Z

lim t →0 α H (x; t) = H(x) and lim t →0 α G (x; t) = G(x).
(H2)

• At the limit when t goes to 0, the feasible set of the parametric non-linear program (R t (x)) must converges to the feasible set of (MPCC). In other words, given F(t) the feasible set of (R t (x)) it holds that lim

t →0 F(t) = Z, (H3)
where the limit is assumed pointwise.

• At the boundary of the feasible set of the relaxation of the complementarity constraint it holds that for all i ∈ {1, . . . , q}

Φ i (G(x), H(x); t) = 0 =⇒ F Gi (x; t) = 0 or F H i (x; t) = 0, (H4)
where

F G (x; t) := G(x) -ψ(H(x); t), F H (x; t) := H(x) -ψ(G(x); t), (1)
and ψ is a continuously differentiable real valued function extended component by component. Note that the function ψ may be two different functions in (1) as long as they satisfy the assumptions below.

Those functions ψ(H(x); t), ψ(G(x); t) are non-negative for all

x ∈ {x ∈ R n | Φ(G(x), H(x); t) = 0} and satisfy ∀z ∈ R q lim t →0 ψ(z; t) = 0. ( H5
)
We will prove in Lemma 6.1 that this generic relaxation scheme for (MPCC) converges to an M-stationary point requiring the following essential assumption on the functions ψ. As t goes to 0 the derivative with respect to the first variable of ψ satisfies ∀z ∈ R q lim t →0 ∂ψ(x; t) ∂x

x=z = 0. (H6)
We conclude this section by giving an explicit formula for the relaxation map at the boundary of the feasible set. Lemma 3.1. Given Φ(G(x), H(x); t) be such that for all i ∈ I Φ (x; t)

Φ i (G(x), H(x); t) = F Gi (x; t)F H i (x; t).
The gradient with respect to x of Φ i (G(x), H(x); t) for i ∈ I Φ (x; t) is given by

∇ x Φ i (G(x), H(x); t) := ∇G i (x)α H i (x; t) + ∇H i (x)α G i (x; t), with α G i (x; t) = F Gi (x; t) - ∂ψ(x; t) ∂x x=Hi(x) F H i (x; t), α H i (x; t) = F H i (x; t) - ∂ψ(x; t) ∂x x=Gi(x) F Gi (x; t).

Existing Methods under the Unified Framework

In this section, we illustrate the fact that the existing methods in the literature fall under this unified framework. Indeed, the approximation method from Kadrani et al. [START_REF] Kadrani | A new regularization scheme for mathematical programs with complementarity constraints[END_REF] as well as the two relaxation methods from Kanzow & Schwartz [START_REF] Kanzow | A New Regularization Method for Mathematical Programs with Complementarity Constraints with Strong Convergence Properties[END_REF] and from Dussault,Haddou & Migot [START_REF] Dussault | The new butterfly relaxation methods for mathematical program with complementarity constraint[END_REF] satisfy those hypothesis. We conclude this section by presenting a new asymetric relaxation method that also belong to our framework. An optimization method that satisfies all of the 6 hypothesis defined in the previous section is called an UF-method.

The Boxes Approximation

In 2009 Kadrani, Dussault and Bechakroun introduce a method, which enjoys the desired goal to converge to an M-stationary point, see [START_REF] Kadrani | A new regularization scheme for mathematical programs with complementarity constraints[END_REF]. Their original method consider an approximation of the complementarity constraints as a union of two boxes connected only on one point (t, t) (here t ∈ R), in the following way ∀i ∈ {1, . . . , q}:

Φ KDB i (x; t) = (G i (x) -t)(H i (x) -t). (2)
This is not a relaxation but an approximation, since the feasible domain of the relaxed problem does not include the feasible domain of (MPCC) as illustrated on Figure 2.

Proposition 4.1. The approximation scheme (R t (x)) with ( 2) is an UF-method.

Proof. Continuity of the map Φ as well as (H3) has been proved in [START_REF] Kadrani | A new regularization scheme for mathematical programs with complementarity constraints[END_REF]. (H4) is satisfied by construction considering ψ(z; t) = t. In this case (H6) and (H5) are obviously satisfied. Now, we consider (H2). Direct computations give that the gradient of Φ for all i ∈ {1, . . . , q} is given by Therefore, α G i and α H i are given by

∇ x Φ KDB i (x; t) = ∇G i (x)(H i (x) -t) + ∇H i (x)(G i (x) -t).
α H i (x; t) = H i (x) -t, α G i (x; t) = G i (x) -t. It clearly holds that α G i (x; t) → t →0 G i (x) and α H i (x; t) → t →0 H i (x).
So, in this case (H2) is satisfied. This completes the proof that all of the 6 hypothesis are satisfied and so the approximation ( 2) is an UF-method.

The L-shape Relaxation

The previous method has latter been extended to a relaxation in [START_REF] Kanzow | A New Regularization Method for Mathematical Programs with Complementarity Constraints with Strong Convergence Properties[END_REF] as illustrated on Figure 3 using a piecewise NCP function by considering ∀i ∈ {1, . . . , q}

Φ KS i (x; t) = φ(G i (x) -t, H i (x) -t), (3)
where φ : R 2 → R is a continuously differentiable NCP-function with for instance

φ(a, b) = ab, if a + b ≥ 0, -1 2 (a 2 + b 2 ), if a + b < 0.
Proposition 4.2. The relaxation scheme (R t (x)) with ( 3) is an UF-method.

Proof. Continuity of the map Φ as well as (H3) has been proved in [START_REF] Kanzow | A New Regularization Method for Mathematical Programs with Complementarity Constraints with Strong Convergence Properties[END_REF]. (H4) is satisfied by construction considering ψ(z; t) = t. In this case (H6) and (H5) are obviously satisfied. Now, we consider (H2). Direct computations give that the gradient of Φ for all i ∈ {1, . . . , q} is given by

∇ x Φ KS i (x; t) = ∇G i (x)(H i (x) -t) + ∇H i (x)(G i (x) -t), if H i (x) -t + G i (x) -t ≥ 0, -∇G i (x)(G i (x) -t) -∇H i (x)(H i (x) -t), else.
Therefore, α G i and α H i are given by In the case

α H i (x; t) = H i (x) -t, if H i (x) -t + G i (x) -t ≥ 0, -(G i (x) -t), otherwise, α G i (x; t) = G i (x) -t, if H i (x) -t + G i (x) -t ≥ 0, -(H i (x) -t), otherwise.
H i (x) -t + G i (x) -t ≥ 0 it clearly holds that α G i (x; t) → G i (x) and α H i (x; t) → H i (x)
. So, in this case (H2) is satisfied.

In the case

H i (x)-t+G i (x)-t < 0 the opposite holds that is α G i (x; t) → -H i (x) and α H i (x; t) → -G i (x)
. However, it is to be noted that sequences x t with x t → t →0 x * that belong to this case satisfy i ∈ I 00 (x * ). To sum up, in this case for

x ∈ Z then α G i (x; t) → H i (x) = G i (x) = 0 and α H i (x; t) → G i (x) = H i (x) = 0.
This proves that (H2) holds in this case too and so this hypothesis holds for this relaxation.

This completes the proof that all of the 6 hypothesis are satisfied and so the relaxation ( 3) is an UFmethod.

The Butterfly Relaxation

The butterfly family of relaxations deal with two positive parameters (t 1 , t 2 ) defined such that for all i ∈ {1, . . . , q}

Φ B i (x; t) := φ(F 1i (x; t), F 2i (x; t)), (4)
with

F 1i (x; t) := H i (x) -t 1 θ t2 (G i (x)), F 2i (x; t) := G i (x) -t 1 θ t2 (H i (x)),
where θ t2 : R →] -∞, 1] are continuously differentiable non-decreasing concave function with θ(0) = 0, and lim t2→0 θ t2 (x) = 1 ∀x ∈ R ++ completed in a smooth way for negative values by considering θ t2 (z < 0) = zθ (0)t1 t2 .

We assume the following relation between the parameter

t 1 = o(t 2 ) and t 1 = ω(t 2 2 ).
This method is illustrated on Figure 4.

Proposition 4.3. The relaxation scheme (R t (x)) with ( 4) is an UF-method.

Proof. Continuity of the map Φ as well as (H3) has been proved in [START_REF] Dussault | The new butterfly relaxation methods for mathematical program with complementarity constraint[END_REF]. (H4) is satisfied by construction considering ψ(z; t) = t 1 θ t2 (z). In this case (H5) and (H6) are obviously satisfied. The latter being insured by t 1 = o(t 2 ). Now, we consider (H2). Direct computations give that the gradient of Φ for all i ∈ {1, . . . , q} is given by

∇ x Φ B i (x; t) =          F 1i (x; t) -t 1 θ t2 (G i (x))F 2i (x; t) ∇G i (x) + F 2i (x; t) -t 1 θ t2 (H i (x))F 1i (x; t) ∇H i (x), if F 1i (x; t) + F 2i (x; t) ≥ 0, t 1 θ t2 (G i (x))F 1i (x; t) -F 2i (x; t) ∇G i (x) + t 1 θ t2 (H i (x))F 2i (x; t) -F 1i (x; t) ∇H i (x), if F 1i (x; t) + F 2i (x; t) < 0.
Therefore, α G i and α H i are given by

α H i (x; t) = F 1i (x; t) -t 1 θ t2 (G i (x))F 2i (x; t), if F 1i (x; t) + F 2i (x; t) ≥ 0, t 1 θ t2 (G i (x))F 1i (x; t) -F 2i (x; t), otherwise, α G i (x; t) = F 2i (x; t) -t 1 θ t2 (H i (x))F 1i (x; t), if F 1i (x; t) + F 2i (x; t) ≥ 0, t 1 θ t2 (H i (x))F 2i (x; t) -F 1i (x; t), otherwise.
In the case F 1i (x; t) + F 2i (x; t) ≥ 0 it clearly holds that α G i (x; t) → G i (x) and α H i (x; t) → H i (x). So, in this case (H2) is satisfied.

In the case F 1i (x; t) + F 2i (x; t) < 0 the opposite holds that is α G i (x; t) → -H i (x) and α H i (x; t) → -G i (x). However, it is to be noted that sequences x t with x t → t →0 x * that belongs to this case satisfy i ∈ I 00 (x * ). Therefore, in this case for x ∈ Z then α

G i (x; t) → H i (x) = G i (x) = 0 and α H i (x; t) → G i (x) = H i (x) = 0.
This proves that (H2) holds in this case too and so this hypothesis holds for this relaxation.

This completes the proof that all of the 6 hypothesis are satisfied and so the relaxation ( 4) is an UFmethod.

An Asymmetric Relaxation

Up till now we only consider relaxation methods that are symmetric. We can define also asymmetric relaxation methods illustrated on Figure 5 that respect the hypothesis of our unified framework.

Let I G and I H be two sets of indices such that I G ∪I H = {1, . . . , q} and I G ∩I H = ∅. Then, the relaxation constraint is defined with Proposition 4.4. The relaxation scheme (R t (x)) with ( 5) is an UF-method.

Φ i (G(x), H(x); t) = (G i (x) -t)H i (x), for i ∈ I G , G i (x)(H i (x) -t), for i ∈ I H . (5)
Proof. Continuity of the map Φ(G(x), H(x); t) as well as (H3) can be easily deduce from the definition of ( 5). (H4) is satisfied by construction considering ψ(z; t) = t or 0. In this case (H5) and (H6) are obviously satisfied. Now, we consider (H2). Direct computations give that the gradient of Φ for all i ∈ {1, . . . , q} is given by

∇ x Φ i (G(x), H(x); t)(x) = ∇G i (x)H i (x) + ∇H i (x)(G i (x) -t), for i ∈ I G , ∇G i (x)(H i (x) -t) + ∇H i (x)G i (x), for i ∈ I H .
Therefore, α G i and α H i are given by

α H i (x; t) = H i (x), for i ∈ I G , H i (x) -t, for i ∈ I H , α G i (x; t) = G i (x) -t, for i ∈ I G , G i (x), for i ∈ I H .
Clearly in both cases (H2) is satisfied. This completes the proof that all of the 6 hypothesis are satisfied and so the relaxation ( 3) is an UFmethod.

Motivations on Epsilon-Solution to the Regularized Subproblems

We have seen in the previous sections a general framework to define relaxations of (MPCC). From an algorithmic point of view, the main idea of relaxation methods to solve (MPCC) is to compute a sequence of stationary points or more precisely approximate stationary points for each value of a sequence of parameter {t k }. The following definition is a specialization of Definition 2.1 for (R t (x)). It consists in replacing most "0" in (KKT) by small quantities .

Definition 5.1. x k is an epsilon-stationary point for (R t (x)) with k ≥ 0 if there exists ν k ∈ R m × R p × R q × R q × R q such that ∇L 1 Rt (x k , ν k ; t k ) ∞ ≤ k and g i (x k ) ≤ k , ν g,k i ≥ 0, |g i (x k )ν g,k i | ≤ k ∀i ∈ {1, . . . , p}, |h(x k )| ≤ k ∀i ∈ {1, . . . , m}, G i (x k ) + tk ≥ -k , ν G,k i ≥ 0, ν G,k i (G i (x k ) + tk ) ≤ k ∀i ∈ {1, . . . , q}, H i (x k ) + tk ≥ -k , ν H,k i ≥ 0, ν H,k i (H i (x k ) + tk ) ≤ k ∀i ∈ {1, . . . , q}, Φ i (G(x k ), H(x k ); t k ) ≤ k , ν Φ,k i ≥ 0, ν Φ,k i Φ i (G(x k ), H(x k ); t k ) ≤ k ∀i ∈ {1, . . . , q}.
Unfortunately, it has been shown in [START_REF] Kanzow | The Price of Inexactness: Convergence Properties of Relaxation Methods for Mathematical Programs with Complementarity Constraints Revisited[END_REF] (Theorem 9 and 12) or [START_REF] Dussault | The new butterfly relaxation methods for mathematical program with complementarity constraint[END_REF] (Theorem 4.3) for the KDB, L-shape and butterfly relaxations that under this definition, sequences of epsilon-stationary points only converge to weak-stationary point without additional hypothesis. Our goal of computing an M-stationary point with a realistic method is far from obvious. Indeed, epsilon-stationary points have two main drawbacks considering our goal. The difficulties may come from the approximation of the complementarity condition and the approximate feasibility as shown in Example 5.1 or from the approximation of the feasibility of the relaxed constraint as illustrated in Example 5.2. In those examples, we consider the scheme (2) in order to simplify the presentation, but these observations can be easily generalized to the others methods.

Kanzow and Schwartz provide the following example exhibiting convergence to a W-stationary point.

Example 5.1. Consider the problem

min x∈R 2 x 2 -x 1 s.t. 0 ≤ x 1 ⊥ x 2 ≥ 0.
If we perturb the relation ν Φ Φ(x 1 , x 2 ; t) ≤ (leaving the other conditions ν Φ ≥ 0, Φ(x 1 , x 2 ; t) ≤ 0), ν Φ may be positive when the constraint Φ(x 1 , x 2 ; t) is not active. For the case KDB Φ(x 1 , x 2 ; t) = (x 1 -t)(x 2 -t) = -2 with = t 2 , the point x(t, ) = (t-, t+ ) T ≥ (0, 0) T is epsilon-stationary for small enough : Φ(x 1 , x 2 ; t) ≤ and the choice ν Φ = 1 makes the Lagrangian (-1, 1) T + ν Φ Φ(x 1 , x 2 ; t) vanish. x(t) converges to the origin when t, -→ 0 but the origin is only weakly stationary.

Now, if the complementarity constraint is relaxed, but the complementarity condition is guaranteed convergence may occur to C-stationary points as shown in the following example.

Example 5.2. Consider the problem

min x∈R 2 1 2 ((x 1 -1) 2 + (x 2 -1) 2 ) s.t. 0 ≤ x 1 ⊥ x 2 ≥ 0.
We specialize the relations in Definition 5.1 as the following, for t and close to 0.

x 1 -1 x 2 -1 -ν G 1 0 -ν H 0 1 + ν Φ x 2 -t x 1 -t ∞ ≤ , 0 ≤ ν G , (x 1 + t) ≥ 0, ν G (x 1 + t) ≤ , 0 ≤ ν H , (x 2 + t) ≥ 0, ν H (x 2 + t) ≤ , 0 ≤ ν Φ , (x 1 -t)(x 2 -t) ≤ , ν Φ [(x 1 -t)(x 2 -t) -] ≥ 0. The points (t + √ , t + √ ) T together with ν G = ν H = 0 and ν Φ = 1-t- √ √
+∞ satisfy the above relations. The limit point when t, -→ 0 is the origin, which is a C-stationary point with ν G = ν H = -1.

On this example, the relaxed regularized complementarity constraint is active for any small enough t, > 0; moreover, the relaxed regularized stationary point is a local maximum for t + 2 √ < 1. The origin is a local maximum for the original (MPCC).

Another example might help understanding the phenomenon.

min x∈R 2 -1 2 ((x 1 -1) 2 + (x 2 -1) 2 ) s.t. 0 ≤ x 1 ⊥ x 2 ≥ 0.
We again specialize the relations in Definition 5.1 as the following, for t and close to 0.

1 -x 1 1 -x 2 -ν G 1 0 -ν H 0 1 + ν Φ x 2 -t x 1 -t ∞ ≤ , 0 ≤ ν G , (x 1 + t) ≥ 0, ν G (x 1 + t) ≤ , 0 ≤ ν H , (x 2 + t) ≥ 0, ν H (x 2 + t) ≤ , 0 ≤ ν Φ , (x 1 -t)(x 2 -t) ≤ , ν Φ [(x 1 -t)(x 2 -t) -] ≥ 0.
This time, the points (t + √ , t + √ ) T are no more epsilon-stationary but the points x = (1, -t) T , ν H = 1 + t and x = (-t, 1) T , ν G = 1 + t are. Their limits are (1, 0) T and (0, 1) T which are KKT points for the original MPCC with ν H = 1, ν G = 0 or ν H = 0, ν G = 1. The point (-t, -t) T with ν H = 1 + t, ν G = 1 + t is also stationary, and of course converges to the origin, a local minimizer of the original MPCC.

In this example, the limit points are not minimizers for the original MPCC, but satisfy the first order KKT conditions for a minimizer. The second order conditions fails for those limit points. The two examples show limiting solutions of regularized subproblems which are not local minimizers of the original MPCC. The first one fails to satisfy a first order condition while the second one satisfies such a first order condition but not the second order one (it is a maximum on the active set).

The Figure 6 gives an intuition that explain the weak convergence in Example 5.2 by showing thefeasible set of the butterfly relaxed complementarity constraint. It can be noticed that this feasible set is very similar to the relaxation from Scheel and Scholtes, [START_REF] Scheel | Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity[END_REF]. Therefore, it is no surprise that we can not expect more than convergence to a C-stationary point in these conditions.

Convergence of Epsilon-Stationary Sequences

We now address the convergence of sequences of epsilon-stationary points. This motivates the definition of a new kind of epsilon-stationary point called strong epsilon-stationary point, which is more stringent regarding the complementarity constraint.

Definition 6.1. x k is a strong epsilon-stationary point for (R t (x)) with k ≥ 0 if there exists ν k ∈ R m × R p × R 3q such that ∇L 1 Rt (x k , ν k ; t k ) ∞ ≤ k and g i (x k ) ≤ k , ν g,k i ≥ 0, |g i (x k )ν g,k i | ≤ k ∀i ∈ {1, . . . , p}, |h(x k )| ≤ tk + O( k ) ∀i ∈ {1, . . . , m}, G i (x k ) + tk ≥ -k , ν G,k i ≥ 0, ν G,k i (G i (x k ) + tk ) ≤ k ∀i ∈ {1, . . . , q}, H i (x k ) + tk ≥ -k , ν H,k i ≥ 0, ν H,k i (H i (x k ) + tk ) ≤ k ∀i ∈ {1, . . . , q}, Φ i (G(x k ), H(x k ); t k ) ≤ 0, ν Φ,k i ≥ 0, ν Φ,k i Φ i (G(x k ), H(x k ); t k ) = 0 ∀i ∈ {1, . . . , q}.
In this case following a similar proof to the one of [START_REF] Kanzow | The Price of Inexactness: Convergence Properties of Relaxation Methods for Mathematical Programs with Complementarity Constraints Revisited[END_REF] and [START_REF] Dussault | The new butterfly relaxation methods for mathematical program with complementarity constraint[END_REF], we get an improved result that keep the nice properties of the relaxations without strong assumption on the sequence of { k }.

The following lemma shows that a sequence of strong epsilon-stationary points converges to a weakstationary point. This is not a new result since the same has been proved in [START_REF] Kanzow | The Price of Inexactness: Convergence Properties of Relaxation Methods for Mathematical Programs with Complementarity Constraints Revisited[END_REF] and [START_REF] Dussault | The new butterfly relaxation methods for mathematical program with complementarity constraint[END_REF] for a sequence of epsilon-stationary points. However, the new definition allows to go further by showing convergence to an M-stationary point. Lemma 6.1. Given {t k } a sequence of parameter and { k } a sequence of non-negative parameter such that both sequences decrease to zero as k ∈ N goes to infinity. Assume that k = o( tk ). Let {x k , ν k } be a sequence of strong epsilon-stationary points of (R t (x)) according to definition 6.1 for all k ∈ N with

x k → x * . Let {η G,k }, {η H,k } be two sequences such that η G,k := ν G,k -ν Φ,k α H (x k ; t k ), η H,k := ν H,k -ν Φ,k α G (x k ; t k ). (6)
Assume that the sequence of multipliers {ν h,k , ν g,k , η G,k , η H,k } is bounded. Then, x * is an M-stationary point of (MPCC).

Proof. The proof is divided in two parts. We first show that x * is a weak-stationary point and then we prove that is an M-stationary point.

Let us prove the first part of the lemma. By definition {x k , ν k } is a sequence of strong epsilon-stationary points of (R t (x)). We make the condition on the Lagrangian

∇L 1 Rt (x k , ν k ; t k ) ∞ ≤ k , more explicit. By construction of Φ(G(x), H(x); t) this condition becomes ∇f (x k ) + ∇g(x k ) T ν g,k + ∇h(x k ) T ν h,k -∇G(x k ) T η G,k -∇H(x k ) T η H,k ∞ ≤ k . (7)
Besides, the sequence of multipliers {ν h,k , ν g,k , η G,k , η H,k } is assumed bounded. Therefore, it follows that the sequence converges to some limit point

{ν h,k , ν g,k , η G,k , η H,k } → (ν h , ν g , η G , η H ).
It is to be noted that for k sufficiently large it holds supp(ν g ) ⊂ supp(ν g,k ),

supp(η G ) ⊂ supp(η G,k ), supp(η H ) ⊂ supp(η H,k ).
We prove that (x * , ν h , ν g , η G , η H ) is a weak-stationary point. Obviously, since k ↓ 0 it follows that x * ∈ Z, ∇ x L 1 M P CC (x * , ν h , ν g , η G , η H ) = 0 by [START_REF] Demiguel | A two-sided relaxation scheme for mathematical programs with equilibrium constraints[END_REF] and that ν g i = 0 for i / ∈ I g (x * ). It remains to show that for indices i ∈ I +0 (x * ), η G i = 0. The opposite case for indices i ∈ I 0+ (x * ) would follow in a completely similar way. So, let i be in I +0 (x * ). By definition of strong k -stationarity it holds for all k that

|ν G,k i (G i (x k ) + tk )| ≤ k . Therefore, ν G,k i → k→∞ 0 since k ↓ 0 and G i (x k ) → G i (x * ) > 0.
Without loss of generality we may assume that for k sufficiently large ν Φ,k i = 0 otherwise η G i = 0 and the proof is complete. By strong -stationarity ν Φ,k i = 0 implies that F H,i (x k ; t k ) = 0 by (H4). (H2) yields α H i (x k ; t k ) → H i (x * ) and so η G i = 0 unless ν Φ,k diverges as k grows. We now prove that the latter case leads to a contradiction.

Assume that ν Φ,k → ∞, boundedness hypothesis on η G i gives that there exists a finite non-vanishing constant C such that

ν Φ,k i α H i (x k ; t k ) → C. Moreover, since η H i is finite and ν Φ,k i α G i (x k ; t k ) → ∞ as G i (x k ) > 0 then necessarily ν H,k i → ∞. Furthermore, noticing that F H (x k ; t k ) = 0 gives H i (x k ) ≥ 0, leads to a contradiction with ν H,k i → ∞ since by -stationarity we get ν H,k i (H i (x k ) + tk ) = ν H,k i H i (x k ) + ν H,k i tk ≤ k ,
and k = o( tk ). We can conclude that for i ∈ I +0 (x * ), η G i = 0 and therefore x * is a weak-stationary point.

Now, let us prove that x * is even stronger that weak-stationary point since it is an M-stationary point. We now consider indices i ∈ I 00 (x * ). Our aim here is to prove that either

η G i > 0, η H i > 0 or η G i η H i = 0. It is clear that if ν Φ,k i = 0, then η G
i and η H i are non-negative values and the result holds true. So, without loss of generality we may assume that ν Φ,k i ≥ 0 and then

Φ i (G(x k ), H(x k ); t k ) = 0 by Definition 6.1. By construction of Φ i (G(x k ), H(x k ); t k ) given in hypothesis (H4) it follows that Φ i (G(x k ), H(x k ); t k ) = 0 ⇐⇒ F G,i (x k ; t k ) = 0 or F H,i (x k ; t k ) = 0 where we remind that F G,i (x k ; t k ) = G i (x k ) -ψ(H i (x k ); t k ), F H,i (x k ; t k ) = H i (x k ) -ψ(G i (x k ); t k ),
Without loss of generality we assume that F G,i (x k ; t k ) = 0 since the other case is completely similar. Furthermore by construction of

Φ i (G(x k ), H(x k ); t k ) it holds that G i (x k ) is non-negative in this case.
Considering one of the complementarity condition of the strong -stationarity gives

k ≥ |ν G,k i (G i (x k ) + tk )| = |ν G,k i G i (x k )| + |ν G,k i tk |, since G i (x k ) is non-negative and it follows that |ν G,k i tk | ≤ k .
Necessarily ν G,k i → k→∞ 0 as we assume in our statement that k = o( tk ). Now at x k we can use Lemma 3.1 that for F Gi (x k ; t k ) = 0 gives

α G i (x k ; t k ) = - ∂ψ(x; t k ) ∂x x=Hi(x k ) F H i (x k ; t k ), α H i (x k ; t k ) = F H i (x k ; t k ).
Obviously, if F H i (x k ; t k ) = 0 we are done and so assume that F H i (x k ; t k ) = 0. By hypothesis (H6), it holds that ∂ψ(x;t k )

∂x x=Hi(x k ) → k→∞ 0. Therefore, α G i (x k ; t k )ν Φ,k
i going to a non-zero limit would imply that

α H i (x k ; t k )ν Φ,k
i goes to infinity. However, this is a contradiction with η G i being finite. We can conclude that necessarily α G i (x k ; t k )ν Φ,k i converges to zero. Finally, we examine two cases regarding the sign of F H i (x k ; t k ). For F H i (x k ; t k ) ≤ 0, we get η G i , η H i non-negative, which satisfy the desired condition. For F H i (x k ; t k ) ≥ 0 we get ν H,k i → k→∞ 0 using the same argument than for ν G,k i . Thus, it follows that η H i = 0. This concludes the proof that x * is an M-stationary point, since additionally to the proof of weakstationarity of x * we proved for every i ∈ I 00 (x * ) that either

η H i > 0, η G i > 0 or η H i η G i = 0.
The following theorem is a direct consequence of both previous lemmas and is our main statement.

Theorem 6.1. Given {t k } a sequence of parameter and { k } a sequence of non-negative parameter such that both sequences decrease to zero as k ∈ N goes to infinity. Assume that k = o( tk ). Let {x k , ν k } be a sequence of epsilon-stationary points of (R t (x)) according to definition 6.1 for all k ∈ N with x k → x * such that MPCC-CRSC holds at x * . Then, x * is an M-stationary point of (MPCC).

Proof. The proof is direct by Lemma 6.1 and Corollary 2.3 of [START_REF] Dussault | The new butterfly relaxation methods for mathematical program with complementarity constraint[END_REF] that ensures boundedness of the sequence (6) under MPCC-CRSC.

Theorem (6.1) attains the ultimate goal, however it is not a trivial task to compute such a sequence of epsilon-stationary points. This is discussed later. Another important question is the existence of strong epsilon-stationary points in the neighbourhood of an M-stationary point. This problem is tackled in the following sections.

On Lagrange Multipliers of the Regularization

The following example develops on Example 2.1 due to Kanzow and Schwartz exhibits a situation where the regularized subproblems have no KKT point.

Example 7.1. The KDB regularized problem is

min x∈R 3 x 1 + x 2 -x 3 s.t. -4x 1 + x 3 ≤ 0, -4x 2 + x 3 ≤ 0, x 1 ≥ -t, x 2 ≥ -t, (x 1 -t)(x 2 -t) ≤ 0. (8)
The point (t, t, 4t) t is feasible so that the minimum value of this program is ≤ -2t. Moreover, whenever x 1 > t, we must have x 2 <= t to satisfy (x 1 -t)(x 2 -t) ≤ 0. This allows to conclude that (t, t, 4t) t is the global minimum of the regularized problem. ν G = ν H = 0 and the gradient of the Lagrangian equal to zero yields

0 =   1 1 -1   + ν g 1   -4 0 1   + ν g 2   0 -4 1   + ν Φ   0 0 0   , (9)
which cannot be satisfied.

This last example seems to contradict Theorem 4.6 in [START_REF] Kanzow | A New Regularization Method for Mathematical Programs with Complementarity Constraints with Strong Convergence Properties[END_REF], but MPCC-LICQ is not satisfied by four constraints in R 3 .

It has been pointed out earlier that a practical algorithm may not be able to compute stationary point of the regularized subproblem, but only some approximate epsilon-stationary point. An intuitive idea would be that weaker constraint qualification may guarantee existence of such points. However, the following one dimensional example shows that things are not that simple taking for instance the approximate method KDB, (2). G and H are linear functions, so MPCC-CRCQ holds at each feasible point. Clearly, x = 0 is an M-stationary point with λ G = -1 and λ H = 0. Indeed, the gradient of the Lagrangian is given by

0 = -1 -λ G .
We now verify that there is no epsilon-stationary point of the approximation KDB for this example :

min x∈R -x, s.t x ≥ -t, -t(x -t) ≤ 0.
Now, considering that the gradient of the Lagrangian function for this problem must be lower or equal as gives

-1 -ν G -tν Φ ≤ . Noticing that ν G , ν H , ν Φ ≥ 0 leads to 1 + ν G + tν Φ ≤ ,
which leads to a contradiction for < 1. So, there is no sequence of approximate stationary points that goes to the origin.

The previous example illustrates the fact that even so strong constraint qualification holds for the problem existence of epsilon-stationary point are not ensured at an M-stationary point. Even so, this problem seems intractable by reformulating the (MPCC) with slack variables things could be slightly different.

Example 7.3. (Example 7.2 continued) We now verify that there is strong epsilon-stationary point of the approximation KDB written with slack variables for this example :

min x∈R -x, s.t s G = x, s H = 0 , s G ≥ -t, s H ≥ -t, (s G -t)(s H -t) ≤ 0.
Given δ > 0, consider the point x = 0, (s G , s H ) = (t, t + δ) and Lagrange multiplier (ν s G , ν s H , ν G , ν H , ν Φ ) = (-1, 0, 0, 0, 1 δ ). • Condition on the gradient of the Lagrangian

|∇ x L 1 (x, s, ν)| = | -1 -ν s G | = 0, |∇ s G L 1 (x, s, ν)| = |ν s G -ν G + ν Φ (s H -t)| = 0, |∇ s H L 1 (x, s, ν)| = |ν s H -ν H + ν Φ (s G -t)| = 0. • Condition on the feasibility |x -s G | = t ≤ , |0 -s H | = t + δ ≤ , s G + t = 2t ≥ -, s H + t = 2t + δ ≥ -, (s G -t)(s H -t) = 0.
• Condition on the complementarity

|(s G + t)ν G | = 0, |(s H + t)ν H | = 0, |(s G -t)(s H -t)ν Φ | = 0.
This completes the proof that there is a strong epsilon-stationary point for the formulation with slack variables. This example motivates the use of slack variables to define the (MPCC) and in this case study the existence of strong epsilon-stationary point in a neighbourhood of an M-stationary point.

The MPCC with Slack Variables

Consider the following parametric non-linear program R t (x, s) parametrized by t:

min (x,s)∈R n ×R 2q f (x) s.t. g(x) ≤ 0, h(x) = 0, s G = G(x), s H = H(x), s G ≥ -t1l, s H ≥ -t1l, Φ(s G , s H ; t) ≤ 0, (R s t (x, s))
with lim t →0 t = 0 + and the relaxation map Φ(s G , s H ; t) : R q × R q → R q is defined by replacing G(x) and H(x) by s G and s H in the map Φ(G(x), H(x); t).

The generalized Lagrangian function of (R s t (x, s)) is defined as

L r s (x, s, ν; t) :=rf (x) + g(x) T ν g + h(x) T ν h -(G(x) -s G ) T ν s G -(H(x) -s H ) T ν s H -s G T ν G -s H T ν H + Φ(s G , s H ; t) T ν Φ .
Let F s be the feasible set of (R s t (x, s)). The following result is a direct corollary of Theorem 6.1 stating that the reformulation with slack variables does not alter the convergence result.

Corollary 8.1. Given {t k } a sequence of parameter and { k } a sequence of non-negative parameter such that both sequences decrease to zero as k ∈ N goes to infinity. Assume that k = o( tk ). Let {x k , ν k } be a sequence of strong epsilon-stationary points of (R s t (x, s)) for all k ∈ N with x k → x * such that MPCC-CRSC holds at x * . Then, x * is an M-stationary point of (MPCC).

Proof. Let h(x) : R n → R m ×R q ×R q be such that h(x) := (h(x), s G -G(x), s H -H(x)) and x := (x, s G , s H ). It is clear that the non-linear program (R s t (x, s)) fall under the formulation (R t (x)). Therefore, we can apply 6.1 to conclude this proof.

The following lemma giving an explicit form of the gradient of the Lagrangian function of (R s t (x, s)) can be deduced through direct computations.

Lemma 8.1. The gradient of L r s (x, s, ν; t) is given by

∇ x L r s (x, s, ν; t) = r∇f (x) + ∇g(x) T ν g + ∇h(x) T ν h -∇G(x) T ν s G -∇H(x) T ν s H , (10)
∇ s G L r s (x, s, ν; t) = ν s G -ν G + ∇ s G Φ(s G , s H ; t) T ν Φ , ∇ s H L r s (x, s, ν; t) = ν s H -ν H + ∇ s H Φ(s G , s H ; t) T ν Φ . (11)
There is two direct consequences of this result. First, it is easy to see from this lemma that computing a stationary point of L r s (x, s, ν; t) is equivalent to computing a stationary point of L r (x, ν; t). Secondly, a stationary point of L r s (x, s, ν; t) with r = 1 satisfies one of the condition of weak-stationary point of (MPCC) that is ∇L 1 M P CC (x, ν) = 0.

In the next section, we now consider the existence of strong epsilon-stationary point for the relaxation with slack variables (R s t (x, s)).

Existence of Strong Epsilon-Stationary Points for the Regularization with Slack Variables

Before stating our main result we give a serie of additional hypothesis on the relaxation and the function ψ.

It is essential to note once again, that all these hypothesis are not restrictive, since they are satisfied by the existing methods in the literature.

Lemma 9.2. Assume that (A1) and (A3) holds true. Then, giving constants c > 0, t > 0 and > 0 the following holds true for all t ∞ ∈ (0, t + c ]

ψ( t + c ; t) ≤ t + c .
Proof. Using assumption (A1) and then (A3) gives

ψ( t + c ; t) < ψ( t + c ; e( t + c )) ≤ t + c ,
which concludes the proof.

Lemma 9.3. Given positive constants t, c, , K. There exists a t * > 0 such that for all t ∈ (0, t * ] it holds that ∂ψ(x; t) ∂x

x= t+c ≤ K , and
0 ≤ t - ∂ψ(x; t) ∂x x=c ≤ K .
Proof. The proof is clear from Assumption (H6) on the relaxation.

Lemma 9.4. Assume that (A1) and (A4) holds true. Then, giving constants c > 0, t > 0 and > 0 with t > c the following holds true for all t ∞ ∈ (0, t -c ]

ψ( t -c ; t) ≤ t + c .
Proof. Using assumption (A1) and then (A4) gives

ψ( t -c ; t) < ψ( t -c ; e( t -c )) ≤ t -c ≤ t + c ,
which concludes the proof.

Main Theorem on Existence of Lagrange Multiplier

All of the supplementary assumptions made above are now used to derive the following result.

Theorem 9.1. Let x * ∈ Z be an M-stationary point and > 0 be arbitrarily small. Furthermore, assume that the hypothesis (A1),(A2),(A3),(A4) on ψ and the hypothesis (F1) or (F2) on the relaxation introduced above hold true. Then, there exists positive constants c, t * and t * with t * > c and a neighbourhood U (x * ) of (x * , 0) T such that for all t ∈ (0, t * ) and t ∈ (0, t * ) there exists (x, s) T ∈ U (x * ), which is strong epsilonstationary point of the relaxation (R s t (x, s)). Regarding the value of t * we need at least that t ∞ ≤ t -c . The constant c is given in the proof and depends on the multipliers of the M-stationary point.

Proof. The proof is conducted in two steps. First, we construct a point based on the solution that is a candidate to be a strong epsilon-stationary point. Then, we verify that this candidate is actually a strong epsilon-stationary point.

x * is assumed to be an M-stationary point. Therefore, there exists λ = (λ g , λ h , λ G , λ H ) such that

∇L 1 M P CC (x * , λ) = 0, min(λ g , -g i (x * )) = 0, h(x * ) = 0, λ G I +0 (x * ) = 0, λ H I 0+ (x * ) = 0, either λ G i > 0, λ H i > 0 either λ G i λ H i = 0 for i ∈ I 00 (x *
). Let c be the positive constant bounding the value of the Lagrange multipliers so that

c := max i∈supp(λ G ),j∈supp(λ H ) 1 |λ G i | + 1 |λ H j | .
Construction of the point (x, ŝ, ν) Let us construct a point (x, ŝ, ν) that satisfy the strong epsilonstationary conditions (6.1).

x := x * , νg := λ g , νh := λ h , νs G := λ G , νs H := λ H .

We now split into two cases (A) and (B) corresponding to the two different kind of relaxations. Denote the following set of indices

I 00 -0 (x * , λ) := {i ∈ {1, . . . , q} | λ G i < 0, λ H i = 0}, I 00 0-(x * , λ) := {i ∈ {1, . . . , q} | λ G i = 0, λ H i < 0}, I ν G := supp(ν s G ) \ (I 00 -0 (x * , λ) ∪ I 00 0-(x * , λ)), I ν H := supp(ν s H ) \ (I 00 -0 (x * , λ) ∪ I 00 0-(x * , λ)), A)
Consider the Case 1, we choose ŝG , ŝH , νG , νH and νΦ such that :

ŝG :=          ψ( t + c ; t), i ∈ I 00 -0 (x * , λ), t + c , i ∈ I 00 0-(x * , λ), -tν G νG , i ∈ I ν G , ∈ F otherwise, ŝH :=          t + c , i ∈ I 00 0-(x * , λ), ψ( t + c ; t), i ∈ I 00 -0 (x * , λ), -tν H νH , i ∈ I ν H , ∈ F otherwise, νG := νs G i for i ∈ I 0+ (x * ) ∪ I 00 (x * )\(I 00 -0 (x * , λ) ∪ I 00 0-(x * , λ)), 0
νΦ :=        -ν s G i α H i (s;t) , for i ∈ I 00 -0 (x * , λ), -ν s H i α G i (s;t) , for i ∈ I 00 0-(x * , λ), 0, otherwise.
(x, ŝ, ν) satisfy the stationarity : Finally, we verify that in both cases we satisfy the strong epsilonstationary conditions, that is

∇L 1 s (x, ŝ, ν; t) ∞ ≤ , and
g i (x) ≤ , νg i ≥ 0, |g i (x)ν g i | ≤ ∀i ∈ {1, . . . , p}, |h i (x)| ≤ t + c ∀i ∈ {1, . . . , m}, |G i (x) -ŝG,i | ≤ t + c ∀i ∈ {1, . . . , q}, |H i (x) -ŝH,i | ≤ t + c ∀i ∈ {1, . . . , q}, ŝG,i + t ≥ -, νG i ≥ 0, νG i (ŝ G,i + t) ≤ ∀i ∈ {1, . . . , q}, ŝH,i + t ≥ -, νH i ≥ 0, νH i (ŝ H,i + t) ≤ ∀i ∈ {1, . . . , q}, Φ i (ŝ G , ŝH ; t) ≤ 0, νΦ i ≥ 0, νΦ i Φ i (ŝ G , ŝH ; t) ≤ 0 ∀i ∈ {1, .
. . , q}. We split the rest of the proof of A) in 6 parts:

I. ∇ x L 1 s (x, ŝ, ν; t) ∞ ≤ , g i (x) ≤ , νg i ≥ 0, |g i (x)ν g i | ≤ ∀i ∈ {1, . . . , p} and |h i (x)| ≤ t + c ∀i ∈ {1, . . . , m}; II. ∇ s L 1 s (x, ŝ, ν; t) ∞ ≤ ; III. |G i (x) -ŝG,i | ≤ t + c , |H i (x) -ŝH,i | ≤ t + c ∀i ∈ {1, . . . , q}; IV. ŝG,i + t ≥ -, νG i (ŝ G,i + t) ≤ , ŝH,i + t ≥ -, νH i (ŝ H,i + t) ≤ ∀i ∈ {1, . . . , q}; V. Φ i (ŝ G , ŝH ; t) ≤ 0, , νΦ i Φ i (ŝ G , ŝH ; t) ≤ 0 ∀i ∈ {1, . . . , q}; VI. νG i ≥ 0, νH i ≥ 0, νΦ i ≥ 0.
Let us now run through these 6 conditions.

I. Since, x = x * and (ν g , νh , ν s G , ν s H ) = (λ g , λ h , λ G , λ H ) it holds that ∇ x L 1 s (x, ŝ, ν; t) ∞ = 0, and
g i (x) ≤ 0, νg i ≥ 0, |g i (x)ν g i | ≤ 0 ∀i ∈ {1, . . . , p}, |h i (x)| = 0 ∀i ∈ {1, . . . , m}.
II. The gradient of the Lagrangian with respect to s is given by

∇ s G L 1 s (x, ŝ, ν; t) = νs G -νG + νΦ α H (ŝ; t), ∇ s H L 1 s (x, ŝ, ν; t) = νs H -νH + νΦ α G (ŝ; t).
In the case I 00 -0 (x * , λ) (the case I 00 -0 (x * , λ) is similar by symmetry) it is true that νG i = νH i = 0 and

νΦ i = -ν s G i α H i (ŝ;t) . Therefore ∇ s G,i L 1 s (x, ŝ, ν; t) = 0, ∇ s H,i L 1 s (x, ŝ, ν; t) = -ν s G i α G i (ŝ; t) α H i (ŝ; t) = νs G i ∂ψ(x; t) ∂x x= t+c
, since for i ∈ I 00 -0 (x * , λ) by construction of ŝG , ŝH it holds that F Gi = 0 and ŝH,i = t + c . The conclusion follows by Lemma 9.3, which gives ∂ψ(x; t) ∂x

x= t+c ≤ .

Now, in the cases

I 0+ (x * ) ∪ I 00 (x * ) \ (I 00 -0 (x * , λ) ∪ I 00 0-(x * , λ)) and I +0 (x * ) ∪ I 00 (x * ) \ (I 00 -0 (x * , λ) ∪ I 00 0-(x * , λ
)) the construction of the multipliers gives directly that ∇ (s G ,s H ) L 1 s (x, ŝ, ν; t) = 0. This concludes the proof of II. III. x feasible for the MPCC yields to

|G i (x) -ŝG,i | = |ŝ G,i | and |H i (x) -ŝH,i | = 0, for i ∈ I 0+ (x * ), |G i (x) -ŝG,i | = 0 and |H i (x) -ŝH,i | = |ŝ H,i |, for i ∈ I +0 (x * ), |G i (x) -ŝG,i | = |ŝ G,i | and |H i (x) -ŝH,i | = |ŝ H,i |, for i ∈ I 00 (x * ).
By symmetry it is sufficient to consider the variables s G . We analyse the cases where i ∈ I 00 0-(x * , λ), I 00 -0 (x * , λ) and I ν G .

• Let i ∈ I 00 0-(x * , λ), then ŝG,i = t + c ;

• Let i ∈ I 00 -0 (x * , λ), then ŝG,i = ψ( t + c ; t) ≤ t + c by Lemma 9.2;

• Let i ∈ I ν G , then ŝG,i = νG i -t ≤ νG i + t ≤ t + c .
In every cases it holds that |ŝ G,i | ≤ t + c and so this III is verified. IV. By construction ŝG,i and ŝH,i are both non-negative as ψ(.; t) is assumed non-negative for indices i such that Φ i (ŝ G , ŝH ; t) = 0.

It remains to verify the condition in the case where i ∈ I ν G and i ∈ I ν H . However, in both cases it holds that

∀i ∈ I ν G , ŝG,i + t = -tν G i νG i + t = νG i > 0 ≥ -, ∀i ∈ I ν H , ŝH,i + t = -tν H i νH i + t = νH i > 0 ≥ -.
So, the feasibility in condition IV is satisfied. Now, regarding the complementarity condition it holds that

∀i ∈ I ν G , |(ŝ G,i + t)ν G i | = -tν G i νG i + t νG i = , ∀i ∈ I ν H , |(ŝ H,i + t)ν H i | = -tν H i νH i + t νH i = .
This proves that the complementarity condition holds true for the relaxed positivity constraints and so condition IV is verified. V. The feasibility Φ i (ŝ G , ŝH ; t) ≤ 0 and the complementarity condition νΦ i Φ i (ŝ G , ŝH ; t) ≤ 0 are satisfied by construction and by hypothesis on the relaxation.

VI. The multiplier νΦ is non-negative since for i ∈ I 00 -0 (x * , λ) it holds that

α H i (ŝ; t) = F H i (ŝ; t) - ∂ψ(x; t) ∂x x=s G,i F Gi (ŝ; t) = F H i (ŝ; t) > 0, (12)
since F Gi (ŝ; t) = 0 by construction of ŝG,i and F H ( t + c ; t) > 0 by Lemma 9.1. The case i ∈ I 00 0-(x * , λ) follows by symmetry.

The others multipliers are obviously non-negative by construction. This concludes the case VI.

The verification of all 6 cases proves that the point constructed above is strong epsilon-stationary, which concludes the proof of the relaxations (A). B) Consider the Case 2. Let ŝG , ŝH , νG , νH and νΦ be such that :

ŝG :=                ψ( t + c ; t), i ∈ I 00 -0 (x * , λ), t + c , i ∈ I 00 0-(x * , λ), -tν G νG , i ∈ I ν G ∩ I ν H , ψ -tν H νH ; t , i ∈ I ν H \ I ν G , ∈ F otherwise, ( 13
) ŝH :=                t + c , i ∈ I 00 0-(x * , λ), ψ( t + c ), i ∈ I 00 -0 (x * , λ), ψ -tν G νG ; t , i ∈ I ν G ∩ I ν H , -tν H νH , i ∈ I 2 , ∈ F otherwise, ( 14
) νG := νs G i for i ∈ I ν G ∩ I ν H , 0 otherwise, (15) νH
:= νs H i for i ∈ I ν H \ I ν G , 0 otherwise, (16) νΦ :
=        -ν s G i α H i (ŝ;t) for i ∈ I 00 -0 (x * , λ), -ν s H i α G i (ŝ;t) for i ∈ I 00 0-(x * , λ) ∪ I ν G ∩ I ν H , 0 otherwise. ( 17
)
Once again we run through the 6 conditions. It is to be noted that the variables involved in I. have not been changed so this condition stands true.

II. As pointed out earlier, the gradient of the Lagrangian with respect to s is given by

∇ s G L 1 s (x, ŝ, ν; t) = νs G -νG + νΦ α H (ŝ; t), ∇ s H L 1 s (x, ŝ, ν; t) = νs H -νH + νΦ α G (ŝ; t).
For indices i in I 00 -0 (x * , λ) and I 00 -0 (x * , λ) we refer to case (A). Let us consider indices i in

I ν G ∩ I ν H and I ν H \ I ν G . For i ∈ I ν G ∩ I ν H , then νG i > 0, νH i = 0 and νΦ i = -ν s H i α G i (ŝ;t)
and so the gradient of the Lagrangian with respect to s becomes

∇ s G,i L 1 s (x, ŝ, ν; t) = νs G i -νG i + νΦ i α H i (ŝ; t) = -ν s H i α H i (ŝ; t) α G i (ŝ; t) , ∇ s H,i L 1 s (x, ŝ, ν; t) = νs H i -νH i + νΦ i α G i (ŝ; t) = 0.
By construction of ŝG,i and ŝH,i , it holds that F H i (ŝ; t) = 0 and so

∇ s G L 1 s (x, ŝ, ν; t) = -ν s H i α H i (ŝ; t) α G i (ŝ; t) = νs H i ∂ψ(x; t) ∂x x=s G,i = νs H i ∂ψ(x; t) ∂x x= νs G i - t ≤ ,
for some t ∈ (0, t * ) according to Lemma 9.3. Now, for indices i ∈ I ν H \ I ν G it holds that νs G i = 0 so by the choice of multipliers ν G , ν H and ν Φ the gradient of the Lagrangian with respect to s vanishes.

This allows to conclude that the condition II holds true. III. Since x is feasible for the MPCC therefore

|G i (x) -ŝG,i | = |ŝ G,i | and |H i (x) -ŝH,i | = 0, for i ∈ I 0+ (x * ), |G i (x) -ŝG,i | = 0 and |H i (x) -ŝH,i | = |ŝ H,i |, for i ∈ I +0 (x * ), |G i (x) -ŝG,i | = |ŝ G,i | and |H i (x) -ŝH,i | = |ŝ H,i |, for i ∈ I 00 (x * ).
Let us consider the case where i ∈ I ν G ∩ I ν H noticing that i ∈ I ν H \ I ν G is similar by symmetry. The others cases have been checked in case (A) of this proof. It follows that

|ŝ G,i | = -tν G νG ≤ νG i + t ≤ t + c , |ŝ H,i | = ψ -tν G i νG i ; t .
The second condition is ensured by Lemma 9.4.

IV. and V. These conditions are straightforward and follows the same path that condition IV. in the case A.

VI. The proof for indices is very similar to the condition VI in case (A) except in the case where i is in

I ν G ∩ I ν H . In this case νΦ i = -ν s H i α G i (ŝ; t) = -ν s H i F Gi (ŝ; t) ,
since by construction of ŝG and ŝH , F H i (ŝ; t) = 0 here. Now, by definition of F G (ŝ; t) it follows

νΦ i = -ν s H i ŝG,i -ψ(ŝ H,i ; t) = -ν s H i /ν s G i -t -ψ(ŝ H,i ; t) ≥ 0,
for c ≤ t since ψ is non-negative whenever s G and s H are chosen such that F H i (s; t) = 0 (Assumption (H5)).

The verification of all 6 cases proves that the point constructed above is strong epsilon-stationary, which concludes the proof of the relaxations (B) and complete the whole proof.

It is to be noted that no constraint qualification is required for this result. This is a clear improvement over what was obtained in the literature in the ideal case of sequence of stationary points. For instance, Theorem 5.1 in [START_REF] Kadrani | A new regularization scheme for mathematical programs with complementarity constraints[END_REF] requires some second-order information to get a result on existence of stationary points for the regularized sub-problems. Theorem 9.2. For any M-stationary point of (MPCC) that satisfies MPCC-CRSC, there exists a sequence of strong epsilon-stationary points of the relaxation (R s t (x, s)) that converges to that point.

Proof. Theorem 9.1 gives more relations between the parameters that are compatible with Corollary 8.1. Indeed for a chosen sequence of arbitrarily small parameters { k }, Corollary 8.1 requires that k = o( tk ) and Theorem 9.1 requires that tk > c and t k must be sufficiently small, in particular smaller than tk -c k . Thus, a straightforward application of both of these results provides the result.

Previous section point out that such result can not be obtained without a formulation with slack variables.

How to Compute Strong Epsilon-Stationary Points

The previous section introduces the new concept of strong epsilon-stationary point of the relaxed subproblems. In this section, we answer the non-trivial question of how to compute such an approximate stationary point. We present here a generalization of the penalization with active set scheme proposed in [START_REF] Kadrani | A globally convergent algorithm for mpcc[END_REF] and illustrate the fact that it has the desired property.

A Penalization Formulation

The following minimization problem aims at finding (x, s) ∈ R n × R 2q so that min

x,s

Ψ ρ (x, s) := f (x) + 1 2ρ φ(x, s) s.t. s G ≥ -t1l, s H ≥ -t1l, Φ(s G , s H ; t) ≤ 0, (P t ρ (x, s))
where φ is the penalty function

φ(x, s) := max(g(x), 0), h(x), G(x) -s G , H(x) -s H 2 .
An adaptation of Theorem 6.1 gives the following result that validate the penalization approach.

Theorem 10.1. Given a decreasing sequence {ρ k } of positive parameter and { k } a sequence of non-negative parameter that decrease to zero as k ∈ N goes to infinity. Assume that k = o( tk ). Let {x k , ν k } be a sequence of strong epsilon-stationary points of (P t ρ (x, s)) according to Definition 6.1 for all k ∈ N with x k → x * such that MPCC-CRSC holds at x * . If x * is feasible, then it is an M-stationary point of (MPCC).

Proof. Assuming that x * is feasible for (MPCC), the result is a straightforward adaptation of Theorem 6.1.

Unfortunately, the strong assumption on the previous theorem that x * must be feasible is hard to avoid. Indeed, it is a classical pitfall of penalization methods in optimization to possibly compute a limit point that minimizes the linear combination of the constraints. In other words, we compute a point x * infeasible that satisfies

p i=1 max(-g i (x * ), 0)∇g i (x * )+ m i=1 h i (x * )∇h i (x * )- q i=1 max(G i (x * ), 0)∇G i (x * )- q i=1 max(H i (x * ), 0)∇H i (x * ) = 0.
This phenomenon has been well-known in non-linear programming methods for instance with filter methods. Such a point is sometimes called infeasible stationary point.

It is interesting to note that the way the penalty parameter ρ behave may provide some informations on the stationarity of the limit point. Indeed, if we find a stationary point of the initial problem without driving ρ to zero, then we get an S-stationary point. This observation was introduced in [START_REF] Coulibaly | An 1 Elastic Interior-Point Method for Mathematical Programs with Complementarity Constraints[END_REF] in the context of elastic interior-point for (MPCC) and then adapted to the penalization technique from [START_REF] Kadrani | A globally convergent algorithm for mpcc[END_REF].

Theorem 10.2. Let (x, s) be a strong epsilon-stationary point of (P t ρ (x, s)) with ρ > 0. If x is feasible for (MPCC), then x is an S-stationary point of (MPCC). This fact was already observed in Theorem 2 of [START_REF] Kadrani | A globally convergent algorithm for mpcc[END_REF] in a slightly weaker but similar framework. We do not repeat the proof, but gives an interpretation of this result.

It has been made clear in the proof of the convergence theorem, Theorem 6.1, that the case where x * is an M-stationary point only occur if the sequence of multipliers {ν Φ,k } diverges. Therefore, it is to be expected that the penalty parameter must be driven to its limit to observe such phenomenon.

Overview of the Algorithm

We present here the general steps of our algorithm to compute an M-stationary point of the (MPCC). The algorithm is composed of two loops: the regularization loop, and the penalization-active set loop.

The main loop presented in Algorithm 2 deals with the regularization method. Based on a predefined sequence of precision k , we compute the parameters of the relaxation t k and tk as well as a safeguard parameter used ρ min,k for the penalization. For each of these parameters, we compute a sequence {z k } of iterates and a sequence {ρ k } of penalty parameters using the penalization-active set strategy, such that z k+1 is an approximate stationary point of (P t ρ (x, s)) with ρ k+1 ≥ ρ min,k . The sequence of iterate is computed through the inner loop dealing with the penalization-active set strategy described in Algorithm 1. The penalization parameter is updated during the process each time not enough progress in term of feasibility is made. However, this reduction can be done only a finite number of time, since the parameter must be larger than the safeguard value ρ min,k . Then, Lemma 10.1 and Theorem 10.3 will show that the set of active constraints is also changed a finite number of times and guarantee convergence under mild assumption to a strong-epsilon stationary point, which should be sufficient to get convergence of the whole process according to Theorem 10.1.

In the sequel, we get into the details of the algorithm and its theoretical properties.

Active Set Method for the Penalized Problem

We discuss here an active set method to solve the penalized problem (P t ρ (x, s)). This method is an extension of the method proposed in [START_REF] Kadrani | A globally convergent algorithm for mpcc[END_REF] to the general class of methods presented in previous sections.

The set of points that satisfies the constraints of (R s t (x, s)) is denoted by F t, t and let β t, t(x, s) denotes the measure of feasibility

β t, t(x, s) := max(g(x), 0) 2 + h(x) 2 + G(x) -s G 2 + H(x) -s H 2 + max(-s G + t1l, 0) 2 + max(-s H + t1l, 0) 2 + max(-Φ(s G , s H ; t), 0) 2 .
Let W(s; t, t) be the set of active constraints among the constraints

s G ≥ -t1l, s H ≥ -t1l, Φ(s G , s H ; t) ≤ 0, (18)
and F R t, t denotes the set of points that satisfies those constraints. We can be even more specific when for some i ∈ {1, . . . , q} the relaxed constraint is active since

Φ i (s G , s H ; t) = 0 =⇒ s H,i = ψ(s G,i ; t) or s G,i = ψ(s H,i ; t).
Remark 10.1. It is essential to note here that active constraints act almost like bound constraints since an active constraint means that for some i ∈ {1, . . . , q} one (possibly both) of the two cases holds s G,i = -t or ψ(s H,i ; t), or s H,i = -t or ψ(s G,i ; t).

Considering the relaxation from Kanzow & Schwartz it is obviously a bound constraint since ψ(s G,i ; t) = ψ(s H,i ; t) = t. The butterfly relaxation gives ψ(s G,i ; t) = t 1 θ t2 (s H,i ) and ψ(s H,i ; t) = t 1 θ t2 (s G,i ). This is not a bound constraint but we can easily use a substitution technique. This key observation is another motivation to use a formulation with slack variables.

Furthermore, a careful choice of the function ψ may allow to get an analytical solution of the following equation in α for given values of s

G , s H , d s G , d s H : s G,i + αd s G,i -ψ(s H,i + αd s H,i ; t) = 0.
Solving exactly this equation is very useful while computing the largest step so that the iterates remain feasible along a given direction. For the butterfly relaxation with θ t2 (x) = x x+t2 , the equation above is reduced to the following second order polynomial equation if s H,i + αd s H,i ≥ 0:

(s H,i + αd s H,i + t 2 )(s G,i + αd s G,i ) -t 1 (s H,i + αd s H,i ) = 0. (19)
Algorithm 1 presents an active-set scheme to solve (P t ρ (x, s)), which is described in depth in the sequel of this section. Apart from some specific parameters most of the input data are given in this algorithm through where we denote

I G := {i ∈ {1, . . . , q} | s Gi = -t}, I H := {i ∈ {1, . . . , q} | s H i = -t}, I 0+ GH := {i ∈ {1, . . . , q} | s H i = ψ(s G ; t)}, I +0 GH := {i ∈ {1, . . . , q} | s Gi = ψ(s H ; t)}, I 00 GH := {i ∈ {1, . . . , q} | s Gi = s H i = ψ(0; t)}, S G := {i ∈ {1, . . . , q}}\(I G ∪ I +0 GH ∪ I 00 GH ), S H := {i ∈ {1, . . . , q}}\(I H ∪ I 0+ GH ∪ I 00 GH ).
S G and S H respectively denote the set of indices where the variables s G and s H are free. Some of the fixed variables are replaced by a constant and others are replaced by an expression that depends on the free variables. It is rather clear from this observation that the use of slack variables is an essential tool to handle the non-linear bounds.

A major consequence here is that the gradient of Ψ in this subspace can be done using the composition of the derivative formula:

∇Ψ Wj ρ (x, s S G ∪S H ) = J T Wj ∇Ψ ρ (x, s), (21)
where J Wj is an (n + 2q) × (n + #S G + #S H ) matrix defined such that

J Wj :=    J x Wj J s G Wj J s H Wj    .
The three sub-matrices used to define J Wj are computed in the following way

J x Wj = Id n , J s G Wj ,i =        e T i , for i ∈ S G , ∂ψ(x;t) ∂x x=s H e T i , for i ∈ I +0 GH , 0, for i ∈ ({1, . . . , q}\S G )\I +0 GH , J s H Wj ,i =        e T i , for i ∈ S H , ∂ψ(x;t) ∂x x=s G e T i , for i ∈ I 0+ GH , 0, for i ∈ ({1, . . . , q}\S H )\I 0+
GH , where J Wj ,i denotes the i-th line of a matrix and e i is a vector of zero whose i-th component is one. We may proceed in a similar way to compute the hessian matrix of Ψ ρ (x, s S G ∪S H ).

The feasible direction d j is constructed to lie in a subspace defined by the working set and satisfying the sufficient-descent direction conditions for z

j ∈ R n+|S G |+|S H | : ∇Ψ Wj (z j ) T d j ≤ -µ 0 ∇Ψ Wj (z j ) 2 , d j ≤ µ 1 ∇Ψ Wj (z j ) , (SDD)
where µ 0 > 0, µ 1 > 0.

The step length α j ∈ (0, ᾱ] is respectively computed to satisfy the Armijo and Wolfe conditions for

z j ∈ R n+|S G |+|S H | : Ψ(z j + α j d j ) ≤ Ψ(z j ) + τ 0 α j ∇Ψ Wj (z j ) T d j , τ 0 ∈ (0, 1), (22)
∇Ψ Wj (z j + α j d j ) T d j ≥ τ 1 ∇Ψ Wj (z j ) T d j , τ 1 ∈ (τ 0 , 1). (23)
If ᾱ satisfies the Armijo condition [START_REF] Kanzow | A New Regularization Method for Mathematical Programs with Complementarity Constraints with Strong Convergence Properties[END_REF], the active set strategy adds a new active constraint and the Wolfe condition ( 23) is not enforced. Otherwise, the Armijo condition requires α < ᾱ and the Wolfe condition is enforced.

The relaxing rule is given by the following scheme : Relax some constraint i 0 if and only if the two following conditions are fulfilled:

1. ν j i0 < 0;

2. No constraint was added at the arrival point (x k,j , s k,j ) and no constraint was deleted at the previous iteration.

The convergence result will rely on the fact that at least one step satisfying Wolfe's condition will be performed before removing an active constraint.

Remark 10.2. One should pay attention here that the algorithm is handling simultaneously the active-set strategy as well as the penalization, since the penalty parameter can be reduced if the feasibility is not reduced enough in step 13. This reduction can only happen a finite number of time (ρ ≥ ρ min ), which will be of importance to show the convergence of the algorithm. Since we expect to compute a strong -stationary, ρ min depends on .

Convergence of Algorithm 1

We now present an extension of the convergence analysis of [START_REF] Kadrani | A globally convergent algorithm for mpcc[END_REF] to Algorithm 1.

We make the following additional assumption on the problem:

• f is bounded from below;

• the gradients of the objective and constraints satisfy a Lipschitz condition.

Therefore, Ψ is also bounded from below, and ∇Ψ is Lipschitz with a constant denoted L ∇ . We restrict our study to the class of methods from the UF Framework that satisfies the following assumption Φ i (G(x), H(x); t) = 0 ⇐⇒ F Gi (x; t) = 0 or F H i (x; t) = 0.

This is a stronger assumption than (H4) presented earlier (page 8). This assumption excludes the relaxation KS. However, it still includes a large range of methods including the method KDB introduced earlier, but also,

• the approximate butterfly

Φ(a, b) = (b -t 1 θ t2 (a)) (a -t 1 θ t2 (b)) ; • the modified butterfly Φ(a, b) = < 0, if F 1i (x; t) < 0 & F 2i (x; t) < 0, (b -t 1 θ t2 (a)) (a -t 1 θ t2 (b)) , otherwise.
As pointed out in previous studies on active-set methods in the literature, the most important aspect of the convergence is the relaxing rule. So that, the working set should not be reduced unless the relaxing rule is satisfied. However, it is not clear for us, to know how to react in the situation, where s G,i = ψ(s H,i ; t) (or s H,i = ψ(s G,i ; t)) and Φ i (G(x), H(x); t) < 0.

We now move to the proof of the convergence of Algorithm 1. Thanks to the several remarks made in the previous section, we can adapt the proof given in [START_REF] Kadrani | A globally convergent algorithm for mpcc[END_REF] by following the same path.

Lemma 10.1. Let {z j } ∈ R n+|S G |+|S H | be a sequence computed on some active set W by using the relaxing rule. For each j ∈ N, it holds that z j+1 = z j + α j d j , where d j satisfies (SDD) and α j satisfies (22), [START_REF] Kanzow | The Price of Inexactness: Convergence Properties of Relaxation Methods for Mathematical Programs with Complementarity Constraints Revisited[END_REF]. Let {ρ j } be a sequence computed according to step 13 in Algorithm 1. Then, for any converging subsequence J ⊂ N, it holds that ∀ > 0, ∃ j ∈ N =⇒ ∀j ≥ j, x j is an -stationary point of (20) with ρ j ≥ ρ min .

Proof. Consider any working set W visited infinitely often but possessing a finite number of pairs of consecutive iterates. For such a working set, ᾱ is used infinitely often and cluster points actually belong to some other working set with at least one more active constraint than W. It suffices then to consider that the sequence {z j } possesses infinitely many pairs of consecutive iterates on W. Furthermore, the update of the penalty parameter is done only a finite number of time, since it is bounded below by ρ min and reduced at each update step. Thus, the sequence {ρ j } converges to some value ρ greater or equal than ρ min in a finite number of iteration.

By conditions (SDD), we have Ψ(z j+1 ) ≤ Ψ(z j ), for all j. By hypothesis, for all ¯ ≥ 0, there exists a j such that for all J j ≥ j Ψ(z j+1 ) -Ψ(z j ) ≤ ¯ .

Armijo condition, [START_REF] Kanzow | A New Regularization Method for Mathematical Programs with Complementarity Constraints with Strong Convergence Properties[END_REF], is satisfied by every iterate, Ψ(z j+1 ) ≤ Ψ(z j ) + τ 0 α j ∇Ψ W (z j ) T d j .

Since ∇Ψ W (z j ) T d j ≤ 0, we have Ψ(z j+1 ) ≤ Ψ(z j ) + τ 0 α j ∇Ψ W (z j ) T d j ≤ Ψ(z j ), ⇐⇒ Ψ(z j+1 ) -Ψ(z j ) ≤ τ 0 α j ∇Ψ W (z j ) T d j ≤ 0.

Now, for all j ≥ j, (25) and previous inequalities give

α j ∇Ψ W (z j ) T d j ≤ ¯ τ 0 . ( 26
)
Suppose that z j is not a stationary point of the restricted problem [START_REF] Kadrani | A new regularization scheme for mathematical programs with complementarity constraints[END_REF]. Then, there exists M > 0 such that for j sufficiently large, we have:

∇Ψ W (z j ) ≥ M. (27)
By using the first condition of (SDD), we have α j ∇Ψ Wj (z j ) T d j ≤ -µ 0 α j ∇Ψ Wj (z j ) 2 < 0.

Using assumption [START_REF] Outrata | Mathematical Programs with Equilibrium Constraints: Theory and Numerical Methods[END_REF], we get α j ∇Ψ Wj (z j ) T d j ≤ -µ 0 α j M 2 .

Using [START_REF] Luo | Mathematical programs with equilibrium constraints[END_REF], we obtain

α j ≤ ¯ τ 0 µ 0 M 2 . ( 28
)
The second part of (SDD) gives α j d j ≤ µ 1 α j ∇Ψ Wj (z j ) ≤ µ 1 α j L ∇ z j , using Lipschitz assumption. Now, by [START_REF] Scheel | Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity[END_REF], we have

α j d j ≤ ¯ µ 1 L ∇Ψ z j τ 0 µ 0 M 2 . ( 29
)
Let ≥ 0 be fixed. Assume that there is no j such that for all j ≥ j, z j is an -stationary point of (P t ρ (x, s)). The relaxing rule force the algorithm to take a relaxing step and the sufficient-long relaxing step, (23), implies for j ∈ [ j, ∞] α j > δ, [START_REF] Ye | Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints[END_REF] with δ independent of j. By using the sufficient-descent direction property of d j , for j sufficiently large, we have α j ∇Ψ W (z j ) T d j ≤ -µ 0 α j ∇Ψ W (z j ) 2 ≤ -µ 0 α j K, for some K > 0 (non-optimality implies ∇Ψ W (z j ) > ). Then, (32) implies Ψ(z j+1 ) ≤ Ψ(z j ) + τ 0 -µ 0 α j K.

Now, since [START_REF] Ye | Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints[END_REF], we have lim j→∞ Ψ(z j ) = -∞, which contradicts the fact that Ψ is bounded below, since f is bounded below. This concludes that necessarily there exists an index j such that for all j ≥ j, z j is an -stationary point of (P t ρ (x, s)).

The strong -stationary property trivially follows, since each iterates satisfy exactly the relaxed complementarity constraint, by the active-set strategy, and also the complementarity condition, since the support of the multipliers are computed exactly.

An Algorithm for MPCC

Along this paper, we analyze an algorithm to solve (MPCC) through a regularization scheme and an active set-penalization method to solve the sub-problems. The latter has been described in the previous sections. We now formally defined the regularization scheme in Algorithm 2.

Data: Let z 0 = (x 0 , s 0 ) be an initial point; Let ρ 0 be an initial value of the penalty parameter; Choose a sequence of precision { k }, a desired precision ∞ and a safeguard min ; Set k = 0 ; 1 Begin ; 2 repeat 3 (t k , tk , ρ min,k ):=Oracle( k ) ; 4 z k+1 , ρ k+1 = Algorithm1(z k , k , ρ k , ρ min,k ): from the starting point z k , use Algorithm 1 to compute z k+1 an approximate stationary point of (P t ρ (x, s)) with penalty parameter ρ k ≥ ρ k+1 ≥ ρ min,k ; 5 Set k ← k + 1;

6 until min(G(x k+1 , H(x k+1 ) ∞ ≤ ∞ and φ(z k+1 ) ≤ ∞ or k < min ; 7 return: f opt := f (x k+1 ) the optimal value at the solution x opt := x k+1 or a decision of infeasibility or unboundedness. Algorithm 2: Relaxation method for Problem (MPCC). In step 3 of Algorithm 2, an oracle compute (t, t, ρ min ) using the chosen value of k that respect the conditions discussed in Section 9.2, while the value of ρ min,k should also depend on the precision. Indeed, approximate feasibility of the iterates for k sufficiently large is not guaranteed by Algorithm 1, since we can reduce finitely many times ρ to some value ρ min . So, this safeguard value should be chosen sufficiently small.

According to Theorem 10.1 and Theorem 10.3, whenever the final iterate x k in Algorithm 2 is feasible for (MPCC) and satisfies MPCC-CRSC, then it is an M-stationary point up to some precision ¯ . Definition 10.1. x * is said an M stationary point up to ¯ , if there exists λ ∈ R m × R p × R q × R q satisfying ∇ x L 1 M P CC (x * , λ) ≤ ¯ , min(-g(x * ), λ g ) ≤ ¯ , h(x * ) ≤ ¯ , min(G(x * ), H(x * )) ≤ ¯ ,

G i (x * )λ G i ≤ ¯ , H i (x * )λ H i ≤ ¯ , min |λ G i λ H i |
, max(-λ G i , 0) + max(-λ H i , 0) ≤ ¯ ∀i ∈ {1, . . . , q}.

Finally, we can conclude the convergence of the whole process.

Theorem 10.4. Given { k } a sequence of non-negative parameter that decrease to zero as k ∈ N goes to infinity. Assume that k = o( tk ). Let {x k , s k } be a sequence of points computed by Algorithm 2. If for any k sufficiently large φ(x k , s k ) ≤ k and MPCC-CRSC holds at x k , then it holds that ∀ > 0, ∃ k =⇒ ∀k ≥ k, x k is an M-stationary point of (MPCC) up to .

Proof. Theorem 10.3 guarantees convergence of Algorithm 1 to a strong -stationary point of (P t ρ (x, s)). Therefore, Algorithm 2 computes a sequence of strong -stationary point, which converges to an Mstationary point under the stated assumptions as proved by Theorem 10.3.

The following corollary is a direct consequence and state the convergence of our approach. This is our main result proving convergence of the regularization-penalization-active set scheme to solve (MPCC).

Corollary 10.1. Given { k } a sequence of non-negative parameter that decrease to zero as k ∈ N goes to infinity. Assume that k = o( tk ). Let {x * , s * } be an accumulation point of the sequence of points {x k , s k } computed by Algorithm 2. If x * is feasible for (MPCC) and MPCC-CRSC holds at x * , then x * is an M-stationary point.

This algorithm is the first from the literature offering guarantees of convergence for (MPCC). Indeed, we remind here that most of the methods proposed face the problem of dealing with approximate stationary points as pointed out in [START_REF] Kanzow | The Price of Inexactness: Convergence Properties of Relaxation Methods for Mathematical Programs with Complementarity Constraints Revisited[END_REF].

Numerics

In what follows, we present a small set of instances to show the behaviour of our algorithm. Beforehand, we give some supplementary informations regarding the implementation of Algorithm 2 and Algorithm 1. An extended butterfly relaxation has been used, which consider t ∈ R 3 and ψ(z; t) = t 3 + t 2 θ 1 t1 (z -t 3 ), where θ 1 t1 (z-t 3 ) = z-t3 z-t3+t1 for z ≥ t 3 and θ 1 t1 (z-t 3 ) = z-t3 t1 -(z-t3) 2 2t 2 1 for z < t 3 . The list of parameters used in the process is detailed in Table 1. It is to be noted that no attempt has been made to optimize the performance of the algorithm and the results come from a straightforward implementation of the algorithm in the JULIA programming language. The direction d j used in Algorithm 1 is computed through a Newton method. The computation of the constrained step length along this direction is computed through a backtracking line search technique. A comparison between some methods to compute the descent direction has been conducted in [START_REF] Kadrani | A globally convergent algorithm for mpcc[END_REF].

We now introduce two examples and give the result of our method.

The first example is the continuation of Example 5.1, which illustrate a case where (0, 0) is a weakstationary point.

Figure 1 :

 1 Figure 1: Signs of λ G , λ H for indices i ∈ I 00 . From the left to the right : weak-stationary, C-stationary, A-stationary, M-stationary and S-stationay.

Figure 2 :

 2 Figure 2: Feasible set of the approximation (2).

Figure 3 :

 3 Figure 3: Feasible set of the relaxation (3).

Figure 4 :

 4 Figure 4: Feasible set of the relaxation (4).

Figure 5 :

 5 Figure 5: Feasible set of the relaxation (5) with I H = {1} and I G = ∅.

Figure 6 :

 6 Figure 6: Butterfly relaxation with a constraint Φ B (x; t) ≤ .

Example 7 . 2 .

 72 Consider the problem min x∈R -x, s.t 0 ≤ G(x) := x ⊥ H(x) := 0 ≥ 0.

i

  for i ∈ I +0 (x * ) ∪ I 00 (x * )\(I 00 -0 (x * , λ) ∪ I 00 0-(x * , λ)), 0 otherwise, and finally

Example 11 . 1 . 2 x 1

 11121 Consider the problemmin x∈R -x 2 s.t. 0 ≤ x 1 ⊥ x 2 ≥ 0, x 2 ≤ 1.

Acknowledgements

This research was partially support by a grant from "l'Ecole des Docteurs de l'UBL" and "le Conseil Régional de Bretagne". This research was partially supported by NSERC grant.

Assumptions

The assumptions made in this section are divided in two parts. The first part concerns assumptions on the domain of the relaxation. The second part is assumptions on the relaxation function ψ that has been used to define the relaxation map on the boundary of the feasible set in Section 3.

Assumptions on the Relaxations

We denote B c ((-t1l, -t1l) T ) the ball of radius c and centered in (-t1l, -t1l) T . We assume that the schemes considered in the sequel satisfy belong to one of two following cases for positive constants c, and t :

The first case includes the butterfly relaxation and the KS relaxation, while the second case includes the approximation KDB.

Assumptions on the Relaxation Function

For all t ∈ R l ++ , we make the following supplementary assumptions on the function ψ for all x ∈ R q . We remind here that the functions ψ are separable with respect to x.

Hypothesis (A1) in particular implies some monotonicity on the feasible set of the relaxed problems. Assumption (A4) is used for the second kind of relaxations only. It is to be noted here that the assumptions (A1),(A2),(A3) and (A4) are not the weakest for obtaining the following results. However, those assumptions are satisfied by all the relaxations defined in the literature. Lemma 9.1. Assume that (A1), (A2) and (A3) hold true. Then, giving constants c > 0, t > 0 and > 0 the following holds true for all t ∞ ∈ (0, t + c ) t + c -ψ(ψ( t + c ; t); t) > 0.

Proof. Using (A1), (A2) and that t ∞ ∈ (0, t + c ) yields t + c -ψ(ψ( t + c ; t); t) > t + c -ψ(ψ( t + c ; e( t + c )); e( t + c )) ≥ 0.

The conclusion comes from assumption (A3).

the relaxation loop that will be discussed in Algorithm 2 (page 35).

Data:

Input Data: x k-1 , s k-1 ; precision > 0 ; ρ 0 > 0 initial value of ρ, ρ min lower bound on the penalty parameter ; Algorithm Parameters: σ ρ ∈ (0, 1) update in ρ; τ vio ∈ (0, 1); sat:=true; Initial estimate of the multiplier ν 0 ; 1 Begin ; 2 Set j := 0, ρ := ρ 0 ; 3 (x k,0 , s k,0 , W 0 , A 0 )=Projection of (x k-1 , s k-1 ) if not feasible for (P t ρ (x, s)) ; 4 while sat and ∇L 1

Substitution of the variables that are fixed by the active constraints in W j ; 6 Compute a feasible direction d j that lies in the subspace defined by the working set W j (see [START_REF] Kadrani | A globally convergent algorithm for mpcc[END_REF]) and satisfies the conditions (SDD);

Compute ᾱ the maximum non-negative feasible step along d j ᾱ := sup{α : (x k,j , s k,j ) + αd j ∈ F t, t} Compute a step length α j ≤ ᾱ (see [START_REF] Kadrani | Nouvelles Régularisations pour l'optimisation avec contraintes de complémentarité[END_REF]) such that Armijo condition [START_REF] Kanzow | A New Regularization Method for Mathematical Programs with Complementarity Constraints with Strong Convergence Properties[END_REF] holds ;

Update the working set → W j+1 and compute A j+1 the matrix of gradients of active constraints

Determine the approximate multipliers ν j+1 = (ν G , ν H , ν Φ ) by solving

Relaxing rule : if ∃ i, ν j+1 i < 0 and (satisfy [START_REF] Kanzow | The Price of Inexactness: Convergence Properties of Relaxation Methods for Mathematical Programs with Complementarity Constraints Revisited[END_REF] or α j = 0 ) then 16 Update of the working set W j+1 (with an anti-cycling rule) ;

18 return: x k , s k , ρ or a decision of unboundedness. Algorithm 1: Active-Set Penalization Algorithm for the relaxed non-linear program (P t ρ (x, s)). At each step, the set W j denotes the set of active constraints of the current iterate s k,j . As pointed out in Remark 10.1, these active constraints fix some of the variables. Therefore, by replacing these fixed variables we can rewrite the problem in a subspace of the initial domain. Thus, we consider the following minimization problem

Wolfe condition, [START_REF] Kanzow | The Price of Inexactness: Convergence Properties of Relaxation Methods for Mathematical Programs with Complementarity Constraints Revisited[END_REF], gives that

and subtracting ∇Ψ Wj (z j ) T d j yields to

Using Cauchy-Schwarz inequality, we obtain

By Lipschitz assumption, it follows that

Using the second condition in (SDD) and ( 29) leads to

Using the first condition in (SDD) gives

By equation ( 30) and ( 27), we have

This, however, leads to a contradiction, since ¯ can be made arbitrarily small with the only consequence that j becomes larger. Here, we use that since J is a converging subsequence, there exists a positive constant that bounds the sequence. Thus, [START_REF] Outrata | Mathematical Programs with Equilibrium Constraints: Theory and Numerical Methods[END_REF] can not hold, which proves the result.

In order to prove the global convergence of Algorithm 1 we enrich the relaxation conditions by assuming that the current iterate satisfied the Wolfe conditions. This is denoted as sufficient-long relaxing step in [START_REF] Kadrani | A globally convergent algorithm for mpcc[END_REF]. We now state the result, which once again is a straightforward application of Theorem 3 from [START_REF] Kadrani | A globally convergent algorithm for mpcc[END_REF].

Theorem 10.3. Let {z j } ∈ R n+2q and {ρ j } be sequences computed by Algorithm 1. Then, for any converging subsequence J ⊂ N, it holds that ∀ > 0, ∃ j =⇒ ∀j ≥ j, x j is a strong -stationary point of (P t ρ (x, s)) with ρ j ≥ ρ min .

Proof. First, we verify the result for (not necessarily strong) -stationary point of (P t ρ (x, s)). Since, from Lemma 10.1, for each subsequence J ⊂ N, up to some rank, the iterates are -stationary points of some restricted problem, it suffices to examine an infinite subsequence {z j } of relaxing steps.

In the same way as in Lemma 10.1, the sequence of penalty parameter {ρ j } converges in finite number of iteration to some value ρ greater or equal to ρ min .

Let z j+ denote the point reached after a relaxation step has been taken

Since d j+ is a descent direction then By starting from the initial point (x 1 , x 2 ) = (1.0, 1.0), our algorithm finds the solution after 9 iterations. Table 2 summarizes the results of the algorithm.

The last example is a continuation of Example 2.1 and illustrates a case where the solution (0, 0, 0) t is an M-stationary point.

Example 11.2. Consider the problem

By starting from the initial point (x 1 , x 2 , x 3 ) = (0.5, 1.0, 1.0), our algorithm finds the solution after 8 iterations. Table 3 summarizes the results of the algorithm.

Concluding Remarks

A generalized framework presented in this article is used to analyze relaxation methods that aim to converge to M-stationary points. Motivated by the approximate resolution of the sub-problems we defined a new notion Iter of approximate stationary point. We proved existence of such approximate point in the neighbourhood of an M-stationary point and provided an algorithmic strategy to compute such point. The final section provide some preliminary numerical results to validate our approach. Although no attempt has been made to improve the code and we do believe that in many ways it could be improved. Further research concerns the implementation of this algorithmic strategy in JULIA and comparison with existing methods on the library of test problem MacMPEC, [START_REF] Leyffer | Macmpec: Ampl collection of mpecs[END_REF]. Theoretical analysis of the algorithm proposed here is the subject of future research.