J.-P Dussault
email: jean-pierre.dussault@usherbrooke.ca

M Haddou

T Migot

The New Butterfly Relaxation Method for Mathematical Programs with Complementarity Constraints

We propose a new family of relaxation schemes for mathematical programs with complementarity constraints. We discuss the properties of the sequence of relaxed non-linear programs as well as stationary properties of limiting points. A sub-family of our relaxation schemes has the desired property of converging to an M-stationary point. A stronger convergence result is also proved in the affine case. A comprehensive numerical comparison between existing relaxations methods is performed on the library of test problems MacMPEC which shows promising results for our new method.

Introduction

We consider the Mathematical Program with Complementarity Constraints (MPCC) min ∈R ( ) s.t. ( ) ≤ 0, ℎ( ) = 0, 0 ≤ ( ) ⊥ ( ) ≥ 0, [START_REF] Abdallah | Solving absolute value equation using complementarity and smoothing functions[END_REF] where : R → R, : R → R , ℎ : R → R and , : R → R are assumed continuously differentiable. The notation 0 ≤ ⊥ ≥ 0 for two vectors and in R is a shortcut for ≥ 0, ≥ 0 and = 0 for all ∈ {1, . . . , }. This problem has become an active subject in the literature in the last two decades. The wide variety of applications that can be cast as a MPCC is one of the reasons for this popularity.

The MPCC is a non-linear program, but with a special structure since, apart from the usual equality and inequality constraints, they have the additional complementarity constraints, which may be equivalently rewritten as ( ) ≥ 0, ( ) ≥ 0, ( ) ( ) ≤ 0, ∀ ∈ {1, . . . , }.

(

A popular approach to tackle a non-linear program 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 don't hold in general for [START_REF] Abdallah | Solving absolute value equation using complementarity and smoothing functions[END_REF] due to the complementarity constraint. For instance, the classical Mangasarian-Fromowitz constraint qualification is violated at any feasible point [START_REF] Ye | Exact penalization and necessary optimality conditions for generalized bilevel programming problems[END_REF].

During the past two decades, many researchers introduced necessary optimality conditions such as the Clarke (C-), Mordukhovich (M-), strong (S-), and Bouligand (B-) stationarity conditions for the MPCC; see, e.g., [START_REF] Flegel | A direct proof for M-stationarity under MPEC-GCQ for mathematical programs with equilibrium constraints[END_REF][START_REF] Kanzow | Mathematical programs with equilibrium constraints: enhanced fritz john-conditions, new constraint qualifications, and improved exact penalty results[END_REF][START_REF] Scheel | Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity[END_REF][START_REF] Ye | Constraint qualifications and 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] Ye | Necessary optimality conditions for optimization problems with variational inequality constraints[END_REF][START_REF] Ye | Exact penalization and necessary optimality conditions for generalized bilevel programming problems[END_REF]. Among these stationarities, the B-stationarity is known to be a good candidate for optimality, but since it is computationally difficult, it is rarely used in algorithmic analysis; the S-stationarity is the strongest and equivalent to the KKT conditions (see, e.g., [START_REF] Flegel | On the guignard constraint qualification for mathematical programs with equilibrium constraints[END_REF][START_REF] Guo | Solving mathematical programs with equilibrium constraints[END_REF]), but its interest is reduced since it does not always hold for the MPCC. The M-stationarity, which has already widely been investigated (see, e.g., [START_REF] Flegel | A direct proof for M-stationarity under MPEC-GCQ for mathematical programs with equilibrium constraints[END_REF][START_REF] Kanzow | Mathematical programs with equilibrium constraints: enhanced fritz john-conditions, new constraint qualifications, and improved exact penalty results[END_REF][START_REF] Outrata | Optimality conditions for a class of mathematical programs with equilibrium constraints[END_REF][START_REF] Ye | Constraint qualifications and 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] Ye | Necessary optimality conditions for optimization problems with variational inequality constraints[END_REF][START_REF] Ye | Exact penalization and necessary optimality conditions for generalized bilevel programming problems[END_REF]), is the most relevant concept since it is the weakest necessary condition holding, under suitable constraint qualifications, at any local minimizer of the MPCC and is computationaly tractable.

The feasible set of the MPCC involves a complementarity constraint equivalent to ( ) = 0 OR ( ) = 0. This is a thin set exhibiting some irregularity when ( ) = 0 AND ( ) = 0. It is this thinness that makes constraint qualifications fail at any feasible point. 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 ( ) ≤ 0 and ℎ( ) = 0 are not more difficult to handle than the complementarity constraint. Finally, as the relaxing parameter is reduced, convergence to the feasible set of (1) is obtained similarly to a homotopy technique.

These methods have been suggested in the literature back in 2000 by Scheel and Scholtes in [START_REF] Scheel | Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity[END_REF][START_REF] Scholtes | Convergence properties of a regularization scheme for mathematical programs with complementarity constraints[END_REF]. Their natural approach was later extended by Demiguel, Friedlander, Nogales and Scholtes in [START_REF] Demiguel | A two-sided relaxation scheme for mathematical programs with equilibrium constraints[END_REF] In [START_REF] Lin | A modified relaxation scheme for mathematical programs with complementarity constraints[END_REF], Lin and Fukushima improved this relaxation by expressing the same set with two constraints instead of three. This improvement leads to an 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 a 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 ( ) = ( ) = 0. In the corresponding papers it has been shown that under classical conditions convergence to some spurious points, called C-stationary points, may still happen, the convergence to M-stationary points being guaranteed only under some second-order condition.

A new perspective for those schemes has been given in [START_REF] Kadrani | A new regularization scheme for mathematical programs with complementarity constraints[END_REF] relaxing the constraints (2) by ≥ 0 as ( ( ) -) ( ( ) -) ≤ 0, ∀ ∈ {1, . . . , }.

(

This approximation scheme converges as decreases to 0 under classical assumptions to M-stationary points without second-order or strict complementarity-type conditions. This is not a relaxation since the feasible domain of ( 1) is not included in the feasible set of the sub-problems. The method has been extended as a relaxation method in [START_REF] Kanzow | A New Regularization Method for Mathematical Programs with Complementarity Constraints with Strong Convergence Properties[END_REF] through an NCP function :

( ( ) -, ( ) -) ≤ 0, ∀ ∈ {1, . . . , }, (4)
where ( ,

) := { , if + ≥ 0, -1 2 ( 2 + 2 ), otherwise}.
The main aim of this paper is to continue this discussion and extend the relaxation of Kanzow and Schwartz [START_REF] Kanzow | A New Regularization Method for Mathematical Programs with Complementarity Constraints with Strong Convergence Properties[END_REF] by introducing the new butterfly relaxation:

( ) -2 1 ( ( )), ( ) -2 1 ( ( )) ≤ 0, ∀ ∈ {1, . . . , }.
This new method handling two relaxing parameters, 1 and 2 , allows a non-linear perturbation, , of the domain. Thus, we extend the butterfly relaxation introduced in [START_REF] Dussault | Mathematical programs with vanishing constraints: constraint qualifications, their applications, and a new regularization method[END_REF] for mathematical program with vanishing constraints to the case of complementarity constraints.

The following example shows that the butterfly relaxation may improve the relaxations from [START_REF] Kadrani | A new regularization scheme for mathematical programs with complementarity constraints[END_REF] and [START_REF] Kanzow | A New Regularization Method for Mathematical Programs with Complementarity Constraints with Strong Convergence Properties[END_REF]. Indeed, it illustrates an example where their is no sequence of stationary point that converges to a non-optimal point.

Example 1 min

∈R 2 -1 s.t. 1 ≤ 1, 0 ≤ 1 ⊥ 2 ≥ 0.
In this example, there are two stationary points: an S-stationary point (1, 0) that is the global minimum and an M-stationary point (0, 0), which is not a local minimum. Unlike the relaxations (3) and ( 4) where for = 1 a sequence = ( , 2 ) , with the Lagrange multiplier associated to the regularized constraint Φ, = , may converge to (0, 0) as goes to infinity, there is no sequence of stationary points that converges to this undesirable point with the butterfly relaxation.

Our main contributions in this paper are the following: Definitions of stationary points of a non-linear program at the beginning of Section 2.1 page 4. Definitions of M-and S-stationarity points are given in Definition 3 page 6.

1. We prove convergence of the butterfly relaxation scheme to A-stationary points, and to M-stationary points for 2, = ( 1, ). 2. We prove for the affine MPCC that the butterfly relaxation scheme converges to S-stationary points under MPCC-LICQ, thus generalizing the situation of Example 1. 3. We prove that the butterfly relaxation scheme computing approximate stationary points at each step converges to an M-stationary point assuming 2, = ( 1, ) and = (max( ( ), ( )). 4. We provide extensive numerical results showing that the butterfly relaxation can efficiently solve the MPCC.

In Section 2, we introduce classical definitions and results from non-linear programming and MPCC literature. In Section 3, we define the relaxation scheme with the new butterfly relaxation. In Section 4, we prove theoretical results on convergence and the existence of multipliers of the relaxed sub-problems. We also provide an analysis of the convergence of approximate stationary points. We also generalize the situation of Example 1 to illustrate a situation where the non-linear perturbation allows us to escape from undesirable points. In Section 5, we provide an extensive numerical study by giving details on the implementation and a comparison with other methods. Finally, in Section 6, we discuss some perspectives of this work.

Preliminaries

In this section, we introduce classical notations and definitions for non-linear programs and mathematical programs with complementarity constraints used in the sequel.

Non-Linear Programming

Let a general non-linear program be min

∈R ( ) s.t. ( ) ≤ 0, ℎ( ) = 0, (5)
with : R → R, : R → R , and ℎ : R → R . Denote F the feasible region of (5), and I ( ) := { ∈ {1, ..., } : ( ) = 0} the set of active indices. The Lagrangian function of ( 5) is defined as L ( ,

) := ( ) + ( ) + ℎ( ) ℎ , where = ( , ℎ ) ∈ R × R is the vector of Lagrange multipliers.
We call a KKT point a couple ( , ) with ∈ F such that ∇ L ( , ) = 0, ≥ 0 and ( ) = 0. We call a stationary point if there exists such that ( , ) is a KKT point. We remind that the tangent cone of a set ⊆ R at * ∈ is a closed cone defined by

T ( * ) := { ∈ R | ∃ ≥ 0 and → →∞ * s.t. ( - * ) → →∞ }.
Another useful tool for our study is the linearized cone of (5) at * ∈ F defined by

ℒ( * ) := { ∈ R | ∇ ( ) ≤ 0, ∀ ∈ I ( * ), ∇ℎ ( ) = 0, ∀ = 1, . . . , }.
In the context of solving non-linear programs, that is finding a local minimum of (5), one widely used technique is to compute necessary conditions. The main tool is the Karush-Kuhn-Tucker (KKT) conditions. Let * be a local minimum of (5) that satisfies a constraint qualification, then there exists a Lagrange multiplier * such that ( * , * ) is a KKT point of [START_REF] Bazaraa | Foundations of optimization[END_REF]. Constraint qualifications are used to ensure the existence of the multiplier at * .

We now define some of the classical constraint qualifications. Note that there exists a wide variety of such notions and we define here those that are essential for our purpose. Remark 1 The definition of MFCQ given here is the most classical. It can be shown using some theorem of the alternative that this definition is equivalent to the family of active gradients being positively linearly independent, so that under MFCQ, the only solution of ∈I ( * ) ∇ ( * ) + =1 ℎ ∇ℎ ( * ) = 0 with ≥ 0, ∀ ∈ I ( * ) is the trivial solution.

A local minimum is characterized by the fact that there is no feasible descent direction for the objective function of [START_REF] Bazaraa | Foundations of optimization[END_REF], that is -∇ ( * ) ∈ T F ( * ) • , where T • denotes the polar cone of T . Given a cone ⊆ R , the polar of is the cone defined by

• := { ∈ R | ≤ 0, ∀ ∈ }.
On the other hand, the KKT conditions build ∇ using a linearization of the active constraints. In a classical way, we say that a point * ∈ F satisfies Guignard CQ if T F ( * ) • = ℒ( * ) • and Abadie CQ if T F ( * ) = ℒ( * ).

In the context of numerical computations, it is almost never possible to compute stationary points. Hence, it is of interest to consider -stationary points.

Definition 2 Given a general non-linear program (5) and ≥ 0. We say that ( ,

) ∈ R × R + is an -KKT point if it satisfies ∇ L ( , ) ∞ ≤ , ℎ( ) ∞ ≤ , ( ) ≤ , ≥ 0, ( ) ≤ , ∀ ∈ {1, . . . , }.
We say that is an -stationary point if there exists such that ( , ) is an -KKT point.

Mathematical Programs with Complementarity Constraints

We now specialize the general notions above to our specific case of (1). Let Z be the set of feasible points of (1). Given * ∈ Z, we denote In the sequel, we always consider these sets in * . In order to derive weaker optimality conditions, we consider an enhanced Lagrangian function. Let L be the generalized MPCC-Lagrangian function of (1) defined as -( )

I +0 := { ∈
L ( , ) := ( ) + ( ) + ℎ( ) ℎ -( )
with := ( , ℎ , , ) ∈ R × R × R × R .
We introduce more stationary concepts as in [START_REF] Luo | Mathematical programs with equilibrium constraints[END_REF][START_REF] Outrata | Optimality conditions for a class of mathematical programs with equilibrium constraints[END_REF][START_REF] Outrata | A generalized mathematical program with equilibrium constraints[END_REF][START_REF] Scheel | Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity[END_REF][START_REF] Ye | Constraint qualifications and 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] Ye | Necessary optimality conditions for optimization problems with variational inequality constraints[END_REF]. Those concepts are needed for two reasons:

• unless assuming a restrictive constraint qualification, a local minimizer * may fail to be a stationary point, so that optimality conditions need to be weakened in order to obtain a necessary condition; • when analyzing cluster points of algorithms, other weak stationarity conditions appear naturally.

Definition 3 A point * ∈ Z is said • W-stationary if there exists ∈ R × R × R × R such that
∇ L ( * , ) = 0, ≥ 0, = 0, ∀ ∉ I , = 0, ∀ ∈ I +0 , and, = 0, ∀ ∈ I 0+ ;

• C-stationary, if it is W-stationary and ≥ 0, ∀ ∈ I 00 ; • A-stationary, if it is W-stationary and ≥ 0 or ≥ 0, ∀ ∈ I 00 ; • M-stationary, if it is W-stationary and either > 0, > 0 or = 0, ∀ ∈ I 00 ; • S-stationary, if it is W-stationary and ≥ 0, ≥ 0, ∀ ∈ I 00 .

Relations between these definitions are straightforward from the definitions. As pointed out in [START_REF] Flegel | On the guignard constraint qualification for mathematical programs with equilibrium constraints[END_REF], strong stationarity is equivalent to the standard KKT conditions of an MPCC. In order to guarantee that a local minimum * of (1) is a stationary point in any of the previous senses, one needs to assume that a constraint qualification (CQ) is satisfied in * . Since most standard CQs are violated at any feasible point of (1), many MPCC-analogues of these CQs have been developed. Here, we mention only those needed later. Definition 4 Let * ∈ Z.

MPCC-LICQ holds at * if the only solution of

∈I ( * ) ∇ ( * ) + =1 ℎ ∇ℎ ( * ) - ∈I 0+ ∪I 00 ∇ ( * ) - ∈I +0 ∪I 00 ∇ ( * ) = 0 (6)
is the trivial solution. 2. MPCC-MFCQ holds at * if the only solution of ( 6) with ≥ 0, ∀ ∈ I ( * ), is the trivial solution.

3. MPCC-GMFCQ holds at * if the only solution of ( 6) with ≥ 0, ∀ ∈ I ( * ), and either = 0 or > 0, > 0, ∀ ∈ I 00 is the trivial solution. Note here that MPCC-MFCQ and MPCC-GMFCQ have been defined using the alternative form of MFCQ mentioned in the Remark 1. Note that each of these CQs implies that a local minimum is M-stationary, see [START_REF] Flegel | Abadie-type constraint qualification for mathematical programs with equilibrium constraints[END_REF][START_REF] Ye | Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints[END_REF], but only MPCC-LICQ is sufficient to guarantee strong stationarity of a local minimum, see [START_REF] Flegel | On the guignard constraint qualification for mathematical programs with equilibrium constraints[END_REF][START_REF] Luo | Mathematical programs with equilibrium constraints[END_REF][START_REF] Pang | Complementarity constraint qualifications and simplified bstationarity conditions for mathematical programs with equilibrium constraints[END_REF]. The MPCC-LICQ is among the first MPCC-tailored constraint qualifications and may already be found in [START_REF] Luo | Mathematical programs with equilibrium constraints[END_REF] and [START_REF] Scheel | Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity[END_REF], the MPCC-MFCQ was introduced in [START_REF] Scheel | Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity[END_REF] and presented in the form above in [START_REF] Hoheisel | Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints[END_REF].

The Butterfly Relaxation Method

Consider a family of continuously differentiable non-decreasing concave functions : R →] -∞, 1] such that (0) = 0, and, lim

→∞ ( ) = 1 ∀ ∈ R ++ .
Then, for 1 > 0, we introduce 1 ( ) := 1 if ≥ 0, and completed in a smooth way for negative values by considering 1 ( )

= (0)/ 1 if < 0.
Example 2 Examples of such functions are

1 1 ( ) := { + 1 , for ≥ 0, 1 , for < 0.}, and 2 1 ( ) := {1 -exp - 1 , for ≥ 0, 1 , for < 0.}.
Those functions have already been used in the context of complementarity constraints, for instance, in [START_REF] Abdallah | Solving absolute value equation using complementarity and smoothing functions[END_REF][START_REF] Abdallah | A sub-additive dc approach to the complementarity problem[END_REF].

To simplify the notation, we denote := ( 1 , 2 ). Using this family of functions, we denote

We propose a new family of relaxation of the complementarity constraint with two positive parameters ( 1 , 2 ) defined such that for all ∈ {1, . . . , } Φ ( ( ), ( );

) := 1 ( ; ) 2 ( ; ), if 1 ( ; ) + 2 ( ; ) ≥ 0, -1 2 1 ( ; ) 2 + 2 ( ; ) 2 otherwise. (7)
This new relaxation uses two parameters 1 and 2 chosen such that

2 (0) < 1 . (8)
This condition ensures that the intersection of the sets

{ ∈ R | 1 ( ; 1 , 2 ) = 0} and { ∈ R | 2 ( ; 1 , 2 ) = 0}
is reduced to the origin. In other words, the two branches of the relaxation does not cross each other. A typical choice will be to take

min ∈R ( ) s.t ∈ X , ¯ , ( , ¯ )
with

X , ¯ := { ∈ R : ( ) ≤ 0, ℎ( ) = 0, ( ) ≥ -¯ , ( ) ≥ -¯ , Φ ( ( ), ( ); ) ≤ 0},
where denotes the vector of all ones. This method is similar to the methods (3) from [START_REF] Kadrani | A new regularization scheme for mathematical programs with complementarity constraints[END_REF] and (4) from [START_REF] Kanzow | A New Regularization Method for Mathematical Programs with Complementarity Constraints with Strong Convergence Properties[END_REF] in the sense that they can also be written as a product of two functions. The main difference is that handling two parameters allows bringing the two "wings" of the relaxation closer. A comparison of the feasible set of these relaxations can be seen in Figure 1.

Fig. 1: The feasible set of the butterfly relaxation, the approximation from [START_REF] Kadrani | A new regularization scheme for mathematical programs with complementarity constraints[END_REF] and the relaxation from [START_REF] Kanzow | A New Regularization Method for Mathematical Programs with Complementarity Constraints with Strong Convergence Properties[END_REF].

The sets of indices used in the sequel are defined in the following way

I ( ; ¯ ) := { = 1, . . . , | ( ) + ¯ = 0}, I ( ; ¯ ) := { = 1, . . . , | ( ) + ¯ = 0}, I ( ; ) := { = 1, . . . , | Φ ( ( ), ( ); ) = 0}, I 0+ ( ; ) := { ∈ I ( ; ) | 1 ( ; ) = 0, 2 ( ; ) > 0}, I +0 ( ; ) := { ∈ I ( ; ) | 1 ( ; ) > 0, 2 ( ; ) = 0}, I 00 ( ; ) := { ∈ I ( ; ) | 1 ( ; ) = 2 ( ; ) = 0}.
Several relations between these sets follow directly from the definition of the relaxation. For instance, it holds that

I ∩ I = I ∩ I = ∅.
Additionally, by definition of the relaxation mapping, it holds

Φ ( ( ), ( ); ) = 0 =⇒ 1 ( ; ) + 2 ( ; ) ≥ 0.
The following two lemmas give more insights on the relaxation.

Lemma 1 Let ∈ X , ¯ , then it is true for the relaxation (7) that: (a) { ∈ I ( ; ) | 1 ( ; ) = 0, 2 ( ; ) < 0} = { ∈ I ( ; ) | 1 ( ; ) < 0, 2 ( ; ) = 0} = ∅; (b) ∈ I ( ; ) =⇒ ( ) ≥ 0, ( ) ≥ 0. Proof Case (a) is direct considering that Φ ( ( ), ( ); 1 , 2 ) ≠ 0 for 1 ( ; ) + 2 ( ; ) < 0.
By symmetry of the relaxation it is sufficient to assume that 1 ( ; ) = ( ) -2 1 ( ( )) = 0 for some = 1, . . . , . Then, by definition of 2 ( ; ) it holds that

2 ( ; ) = ( ) -2 1 ( ( )) = ( ) -2 1 ( 2 1 ( ( ))),
so ( ) ≥ 0 since in the other case, i.e. ( ) < 0, it would follow that

2 ( ; ) = ( ) (1 -( (0) 2 / 1 ) 2 ),
which would be negative using [START_REF] Dussault | Mathematical programs with vanishing constraints: constraint qualifications, their applications, and a new regularization method[END_REF]. Note that previous inequality holds true since, by definition of the function , it holds that 2 1 ( ) = 2 (0) / 1 for ≤ 0. Finally, ( ) ≥ 0 implies that ( ) ≥ 0 since 1 ( ; ) = 0.

The following lemma state two of the key features of the relaxation and follows from the observation that Φ ( ( ), ( ); ) → ( ) ( ) as ↓ 0.

Lemma 2

The set X , ¯ satisfy the following properties: 2. , ¯ ≥0 X , ¯ = Z. If the feasible set of the ( 1) is non-empty, then the feasible sets of the relaxed subproblems are also non-empty for all ≥ 0. If for some parameter ≥ 0 the set X , ¯ is empty, then it implies that Z is empty. Finally, if a local minimum of , ¯ already belongs to Z, then it is a local minimum of the [START_REF] Abdallah | Solving absolute value equation using complementarity and smoothing functions[END_REF].

1. lim , ¯ →0 X , ¯ = Z
Finally, numerical results will be presented in Sect. 5 and will show that these new methods are very competitive compared to existing methods.

Before moving to our main statements regarding convergence and regularity properties of the butterfly relaxation, we provide two technical lemmas. Direct computation gives the gradient of Φ ( ( ), ( ); ) in the following lemma.

Lemma 3 For all ∈ {1, . . . , }, the gradient of Φ ( ( ), ( ); ) w.r.t. for the relaxation [START_REF] Dussault | On approximate stationary points of the regularized mathematical program with complementarity constraints[END_REF] is given by

∇ Φ ( ( ), ( ); ) =                            1 ( ; ) -2 1 ( ( )) 2 ( ; ) ∇ ( ) + 2 ( ; ) -2 1 ( ( )) 1 ( ; ) ∇ ( ), if 1 ( ; ) ≥ -2 ( ; ), 2 1 ( ( )) 1 ( ; ) -2 ( ; ) ∇ ( ) + 2 1 ( ( )) 2 ( ; ) -1 ( ; ) ∇ ( ), if 1 ( ; ) < -2 ( ; ).
The following lemma illustrates the behavior of functions 1 and their derivatives.

Lemma 4

Given two sequences { 1, } and { 2, }, which converge to 0 as goes to infinity and ∀ ∈ N, ( 1, , 2, ) ∈ R 2 ++ . It holds true that

lim →∞ 2, 1, ( ) = 0 ∀ ∈ R ++ .
Furthermore, assuming that 2, = ( 1, ), yields to

lim →∞ 2, 1, ( ) = 0 ∀ ∈ R + .
Proof First part of the lemma follows from the definition of functions 1, . Indeed, it holds for all ∈ R + that 1, ( ) ∈ [0, 1]. Therefore, lim →∞ 2, 1, ( ) = 0. Second part of the lemma uses the fact that functions 1, are defined as perspective functions, that is for all ∈ R + 1, ( ) = , and so, computing the derivative gives

.

So, for sufficiently large 1, ≤ , and by concavity of , we get

0 ≤ lim →∞ 2, 1, ( ) ≤ lim →∞ 2, 1, ( 1, ) = lim →∞ 1, 1, (1),
and the result follows.

We focus on the sequel on the properties of these new relaxation schemes. We prove that the method converges to an A-stationary point in Theorem 1 and to an M-stationary point, Theorem 2, with some relation between the sequences { 2, } and { 1, }. Furthermore, we prove in the affine case convergence to S-stationary point under MPCC-LICQ (Theorem 3).

The main motivation to consider relaxation methods for ( 1) is to solve a sequence of regular problems. Under classical assumptions, the butterfly relaxed non-linear programs satisfy the Guignard CQ, as proved in Theorem 4.

Theoretical Properties

The study of the theoretical properties of the butterfly relaxation method is split into three parts: convergence of the sequence of stationary points, the existence of Lagrange multipliers for the relaxed non-linear program, and convergence of the sequence of approximate stationary points.

Convergence

In this section, we focus on the convergence properties of the butterfly relaxation method and the constraint qualifications guaranteeing convergence of the sequence of stationary points generated by the method. Our aim is to compute an M-stationary point or, at least, provide a certificate if we converge to an undesirable point.

We prove in Theorem 1 that the butterfly relaxation converges to an A-stationary point. This result is improved to convergence to M-stationary points for some choices on the parameters 2 and 1 in Theorem 2.

Finally, we prove convergence to S-stationary point in a specific situation in Theorem 3. To the best of our knowledge, this kind of result without second-order condition is new from the literature and allows the butterfly relaxation to escape from spurious points.

Theorem 1 Given two sequences { } and {¯ } of positive parameters satisfying [START_REF] Dussault | Mathematical programs with vanishing constraints: constraint qualifications, their applications, and a new regularization method[END_REF] and decreasing to zero. Let { , , , ℎ, , , , , , Φ, } be a sequence of KKT points of ( , ¯ ) with → * such that MPCC-MFCQ holds at * . Then, * is an A-stationary point.

Proof First, we identify the expressions of the multipliers of the complementarity constraint in Definition 3 through the stationary points of ( , ¯ ).The representation of ∇Φ immediately gives ∇Φ ( ( ), ( ); ) = 0, ∀ ∈ I 00 ( ; ). Thus, we can write

-∇ ( ) = =1 , ∇ ( ) + =1 ℎ, ∇ℎ ( ) - =1 , ∇ ( ) - =1 , ∇ ( ), (9)
where , = , , ℎ, = ℎ, and

, =              , , if ∈ I ( ; ¯ ), Φ, 2, 1, ( ( )) 2 ( ; ), if ∈ I 0+ ( ; ), -Φ, 1 ( ; ), if ∈ I +0 ( ; ), 0, otherwise, , =              , , if ∈ I ( ; ¯ ), Φ , 2, 1, ( ( )) 1
( ; ), if ∈ I +0 ( ; ), -Φ, 2 ( ; ), if ∈ I 0+ ( ; ), 0, otherwise.
First, by [START_REF] Flegel | Abadie-type constraint qualification for mathematical programs with equilibrium constraints[END_REF], it holds that ∇L ( , ) = 0 for all . Thus, the first condition of the W-stationary conditions is satisfied. Moreover, by definition of { , } it holds that I ( ) ⊆ I ( * ) and so lim →∞ , = 0, ∀ ∉ I ( * ).

Denote

∞ := , , ℎ, , , , , ∞ . Using the definition of , and , in (9) and since by [START_REF] Dussault | Mathematical programs with vanishing constraints: constraint qualifications, their applications, and a new regularization method[END_REF] it holds that 1, ( ( )) ≤ 1, (0) < 1 for all ∈ I ( ; ), it can be observed that

∞ = , , ℎ, , , , , , Φ, • 2 ( ; ), Φ, • 1 ( ; )) ∞ , (10)
where • denotes the componentwise product of two vectors. We now verify that: , / ∞ → 0 for indices ∈ I +0 . By symmetry, it would follow that , / ∞ → 0 for indices ∈ I 0+ . Let ∈ I +0 . Clearly ∈ I 0+ ( ; ) as otherwise ( ) = ¯ for ∈ I ( ; ) or ( ) = 2, 1, ( ( )) for ∈ I +0 ( ; ) which in both cases, for sufficiently large, contradicts the fact ( ) → ( * ) > 0. Now, ∈ I 0+ ( ; ) , . All in all the infinite norm is not obtained at these components.

yields , = Φ, 2, 1, ( ( )) 2 ( ; ). Moreover, ∞ ≥ | Φ, 2 ( ; )| by (10), thus , ∞ ≤ Φ, 2, 1, ( ( )) 2 ( ; ) | Φ, 2 ( ; )| = 2, 1, ( ( )) → 0
since ( ) → ( * ) > 0 and using Lemma 4. Now, let us prove that the sequence { } is bounded. Assume by contradiction that is not bounded, then the sequence { / ∞ } is bounded and converges, up to a subsequence to a non-trivial limit ˆ . Therefore, dividing ( 9) by ∞ and passing to the limit gives

∈I ( * ) ˆ ∇ ( * ) + =1 ˆ ℎ ∇ℎ ( * ) - ∈I 0+ ∪I 00 ˆ ∇ ( * ) - ∈I +0 ∪I 00 ˆ ∇ ( * ) = 0,
which leads to a contradiction since * satisfies MPCC-MFCQ.

So, the sequence { } is bounded, hence , → 0, ∀ ∈ I +0 and , → 0, ∀ ∈ I 0+ . Therefore, * is a W-stationary point of the MPCC.

Finally, let us now verify that * is an A-stationary point. Denote * the limit, up to a subsequence, of the sequence { }. Let ∈ I 00 . Assume without loss of generality that , * < 0 (the other case will be similar by symmetry) and we show that , * ≥ 0. , * < 0 implies that ∈ I +0 ( ; ) for sufficiently large by definition of , . So, , = Φ, 2,

1, ( ( )) 1 ( ; ), which is non-negative. So * is an A-stationary point.

The following example shows that the result of Theorem 1 is sharp since convergence cannot be ensured, assuming only that MPCC-GMFCQ holds at the limit point.

Example 3 Consider the following two-dimensional example min

∈R 2 2 s.t. 0 ≤ 1 + 2 2 ⊥ 1 ≥ 0.
MPCC-GMFCQ holds at (0, 0) . The point (0, 0) is even not a W-stationary point. In this case, there exists a sequence of stationary points of the relaxation such that { } converges to the origin. Given a sequence { }, with {1} ∈ I ( ; ), such that → (0, 0) then , = , = 0 and we can choose Φ, that satisfies

, = -, = 1 2 2
.

The sequence { } converges to an undesirable point.

The result of the Theorem 1 can be tightened if we consider a particular choice of parameter. It is an essential result since it shows that a subfamily of the butterfly relaxation has the desired property to converge to an M-stationary point.

Theorem 2 Given two sequences { } and {¯ } of positive parameters satisfying [START_REF] Dussault | Mathematical programs with vanishing constraints: constraint qualifications, their applications, and a new regularization method[END_REF] and decreasing to zero. Let { , , , ℎ, , , , , , Φ, } be a sequence of KKT points of ( , ¯ ) with → * such that MPCC-GMFCQ holds at * . If 2, = ( 1, ), then, * is an M-stationary point.

Proof

In the proof of Theorem 1 we already showed that: ∇L ( , ) = 0 for all , lim

→∞ , = 0, ∀ ∉ I ( * ), lim →∞ , / ∞ = 0, ∀ ∈ I +0 ,
( ; )/ ∞ = lim →∞ -, / ∞ < ∞.
Thus, lim →∞ , / ∞ = 0. Finally, following the same reasoning as in the proof of Theorem 1, using MPCC-GMFCQ, the sequence { } is bounded, and * is an M-stationary point.

The following example shows that this result is sharp, since it illustrates a situation where MPCC-GMFCQ does not hold and the method converges to an undesirable W-stationary point. This phenomenon only happens if the sequence of multipliers defined in (9) is unbounded.

Example 4 Consider the problem min ∈R 2 2 2 s.t. 0 ≤ 2 1 ⊥ 1 + 2 2 ≥ 0. The feasible set is Z = {( 1 , 2 ) ∈ R 2 | 1 = 0} ∪ {( 1 , 2 ) ∈ R 2 | 1 = -2 2 }. ( 0
, 0) is the unique M-stationary, with ( , = 0). MPCC-GMFCQ fails to hold at any point (0, ∈ R) since the gradient of 2 1 is non-zero for ≠ 0.

Consider a sequence such that for ( 1, , 2, ) sufficiently small 2 ( ; ) = 0 and 1

-2, 1, ( 1 + 2 )
.

Obviously, the sequence goes to * = (0, ≠ 0) , which is not a W-stationary point. Indeed, we have

, = 1 2, 1, ( 1 + 2 ) → ∞ and , = -1 ≠ 0.
The following result motivated by Example 1 shows that the butterfly relaxation may improve its behavior in some specific cases. Example 1 also indicates that this cannot be expected with the other relaxations. In the sequel, we denote supp( ) := { | ≠ 0} the non-zero indices of .

Theorem 3 Assume that , , ℎ, , are affine functions. Given two sequences { } and {¯ } of positive parameters satisfying [START_REF] Dussault | Mathematical programs with vanishing constraints: constraint qualifications, their applications, and a new regularization method[END_REF] and decreasing to zero as goes to infinity. Let { , , , ℎ, , , , , , Φ, } be a sequence of KKT points of ( , ¯ ) with → * such that MPCC-LICQ holds at * . If 2, = ( 1, ), and, for all sufficiently large supp( Φ, ) ∩ I +0 ∪ I 0+ = ∅,

then, * is an S-stationary point.

Proof Theorem 2 already proves that * is an M-stationary point. Assume by contradiction that * is not an S-stationary point. Then, it holds that this point cannot be a stationary point of ( , ¯ ). We already mention in the proof of Theorem 1 that for all it holds

-∇ = =1 , ∇ + =1 ℎ, ∇ℎ - =1 , ∇ - =1 , ∇ ,
where we omit the dependence in in the expression of the gradients, since they are constant by linear/affine assumption. Clearly, for sufficiently large, it holds that supp( , ) ⊆ I ( * ), supp( , ) ⊂ I 0+ ∪ I 00 and supp( , ) ⊆ I 00 ∪ I +0 by [START_REF] Flegel | A direct proof for M-stationarity under MPEC-GCQ for mathematical programs with equilibrium constraints[END_REF]. Now, by continuity, linear independence of these gradients holds in a neighbourhood of * . So, we get finite convergence of the , and for sufficiently large it holds

, = ,∞ , ℎ, = ℎ,∞ , , = ,∞ , , = ,∞ . (12)
Let ∈ I 00 ∩ supp( Φ,∞ ), where we remind that supp( Φ,∞ ) ⊆ supp( Φ, ) ⊆ I ( ; ). If no such index exists, then for all sufficiently large Φ, is zero and * is S-stationary. By stationarity assumption on * , we assume that ,∞ < 0 (the case ,∞ will be symmetrical). It implies that ∈ I +0 by definition of the multipliers in [START_REF] Flegel | Abadie-type constraint qualification for mathematical programs with equilibrium constraints[END_REF] and so , = -Φ, 1 ( ; ), and, , = Φ, 2,

1, ( ( )) 1 ( ; ).

We proved in Theorem 2 that , and , have bounded limits, so by Lemma 4 with 2, = ( 1, ) we have lim →∞ , = 0. By [START_REF] Fletcher | Solving mathematical programs with complementarity constraints as nonlinear programs[END_REF], we get Φ, = 0 for all sufficiently large, which contradicts ,∞ < 0.

Existence of Lagrange Multipliers for the Relaxed Sub-Problems

In this section, we study some regularity properties of the relaxed non-linear programs. Indeed, to guarantee the existence of a sequence of stationary points, the relaxed non-linear programs must satisfy some constraint qualifications in the neighborhood of the limit point.

Theorem 4 Let * ∈ Z, satisfying MPCC-LICQ. Then, there exists * > 0 and a neighborhood ( * ) of * such that:

∀ ∈ (0, * ] : ∈ ( * ) ∩ X , ¯ =⇒ standard GCQ holds at for ( , ¯ ). Proof Let ∈ ( * ) ∩ X , ¯ . We know that ℒ X , ¯ ( ) • ⊆ T X , ¯ ( ) • . So, it is sufficient to show the converse inclusion.
The linearized cone of( , ¯ ) is given by Let us compute the polar of the tangent cone. Consider the following set of nonlinear constraints parametrized by ∈ X , ¯ and a partition ( , , -) of I 00 ( ; ) , defined by

ℒ X , ¯ ( ) = { ∈ R | ∇ ( ) ≤ 0, ∀ ∈ I ( ), ∇ℎ ( ) = 0, ∀ = 1, . . . , , ∇
S ( , , -) ( ) := { ∈ R | ( ) ≤ 0, ℎ( ) = 0, ( ) ≥ -¯ , ( ) ≥ -¯ , Φ ( ( ), ( ); ) ≤ 0, ∉ I 00 ( ; ), 1 ( ; ) ≤ 0, 2 ( ; ) ≥ 0, ∈ , 1 ( ; ) ≥ 0, 2 ( ; ) ≤ 0, ∈ , 1 ( ; ) ≤ 0, 2 ( ; ) ≤ 0, ∈ -}. (13) Since ∈ X , ¯ , it is obvious that ∈ S ( , , -) ( ).
( , , -) is partition of I 00 ( ; ) means that ∪ ∪ -= I 00 ( ; ) and ∩

= ∩ -= ∩ -= ∅.
By construction of ( * ) and * , the gradients {∇ ( * ) ( ∈ I ( * )), ∇ℎ ( * ) ( = 1, . . . , ), ∇ ( * ) ( ∈ I 00 ∪ I 0+ ), ∇ ( * ) ( ∈ I +0 ∪ I 00 )} remain linearly independent for all ∈ ( * ) by continuity of the gradients and we have I ( ) ⊆ I ( * ), I ( ; ¯ ) ⊆ I 00 ∪ I 0+ , I ( ; ¯ ) ⊆ I +0 ∪ I 00 , I 00 ( ; ) ∪ I +0 ( ; ) ⊆ I 00 ∪ I 0+ , I 00 ( ; ) ∪ I 0+ ( ; ) ⊆ I +0 ∪ I 00 . [START_REF] Gill | SNOPT: An SQP algorithm for large-scale constrained optimization[END_REF] Therefore, by Lemma 6, LICQ holds for (13) at . Furthermore, by [START_REF] Schwartz | Mathematical programs with complementarity constraints: Theory, methods, and applications[END_REF]Lemma 8.10], and since LICQ in particular implies Abadie CQ it follows that

T X , ¯ ( ) = ∀( , , -) T S ( , , -) ( ) ( ) = ∀( , , -) ℒ S ( , , -) ( ) ( ).
By [START_REF] Bazaraa | Foundations of optimization[END_REF]Theorem 3.1.9], passing to the polar, we get

T X , ¯ ( ) • = ∀( , , -) ℒ S ( , , -) ( ) ( ) • . By [5, Theorem 3.2.2], we know that ℒ S ( , , -) ( ) ( ) • = { ∈I ( ) ∇ ( ) + =1 ℎ ∇ℎ ( ) - ∈I ( ;¯ ) ∇ ( ) - ∈I ( ;¯ ) ∇ ( ) + ∈I +0 ( ; )∪I 0+ ( ; ) Φ ∇Φ ( ( ), ( ); ) - ∈ ∇ ( ) + ∈ ∇ ( ) + ∈ ∇ ( ) - ∈ ∇ ( ) + ∈ - ∇ ( ) + ∈ - ∇ ( ) : ( , , , Φ ) ≥ 0}.
For ∈ T X , ¯ ( ) • , we have ∈ ℒ S ( , , -) ( ) ( ) • for any partition ( , , -) of I 00 ( ; ). If we fix and set -= ∅, then there exists some multipliers ℎ and , , , Φ ≥ 0 so that

= ∈I ( ) ∇ ( ) + =1 ℎ ∇ℎ ( ) - ∈I ( ;¯ ) ∇ ( ) - ∈I ( ;¯ ) ∇ ( ) + ∈I +0 ( ; )∪I 0+ ( ; ) Φ ∇Φ ( ( ), ( ); ) - ∈ ∇ ( ) + ∈ ∇ ( ) - ∈ ∇ ( ) + ∈ ∇ ( ).
Now, it also holds that ∈ ℒ S ( , , -) ( ) ( ) • and so there exists some multipliers ℎ and , , , Φ ≥ 0 such that

= ∈I ( ) ∇ ( ) + =1 ℎ ∇ℎ ( ) - ∈I ( ;¯ ) ∇ ( ) - ∈I ( ;¯ ) ∇ ( ) + ∈I +0 ( ; )∪I 0+ ( ; ) Φ ∇Φ ( ( ), ( ); ) + ∈ ∇ ( ) - ∈ ∇ ( ) + ∈ ∇ ( ) - ∈ ∇ ( ).
By the construction of * and ( * ), the gradients involved here are linearly independent and so the multipliers in both previous equations must be equal. Thus, the multipliers and with indices in ∪ vanish. Therefore, ∈ ℒ X At * = (0, 0) it holds that ∇Φ ( ( ), ( ); ) = (0, 0) and so ℒ X , ¯ ( * ) = R 2 , which is obviously different from the tangent cone at * for 2 (0) < 1 and ¯ > 0.

The following example shows that we cannot have a similar result using MPCC-GMFCQ.

Example 6 Consider the set

:= {( 1 , 2 ) | 0 ≤ 1 + 2 2 ⊥ 1 ≥ 0}.
MPCC-GMFCQ holds at * = (0, 0) , since the gradients are linearly dependent but only with coefficients = -that does not satisfy the condition given in Definition 4. Now, we can choose a sequence of points such that → * and Since ∇ ( * ) = ∇ ( * ) it holds that ∇ 2 ( * ; 0) = (0 0) and so MFCQ does not hold for [START_REF] Fourer | Ampl[END_REF].

It is disappointing to require MPCC-LICQ to obtain the only GCQ, but when I 00 is empty, we get the stronger LICQ.

Theorem 5 Let * ∈ Z, satisfying MPCC-LICQ. Then, there exists * > 0 and a neighborhood ( * ) of * such that ∀ ∈ (0, * ] : ∈ ( * ) ∩ X , ¯ and I 00 ( ; ) = ∅ =⇒ LICQ holds at for ( , ¯ ).

Proof Let ∈ ( * ) ∩ X , ¯ and sufficiently small. We prove that the gradients of the constraints involved in ( , ¯ ) are linearly independent, by verifying that the trivial solution is the only solution to the following equation

0 = ∈I ( ) ∇ ( ) + =1 ℎ ∇ℎ ( ) + ∈I ( ;¯ ) ∇ ( ) + ∈I ( ;¯ ) ∇ ( ) + ∈I +0 ( ; ) ∇ ( ) Φ ( 1 ( ; ) -2 ( ; ) 2 1 ( ( ))) + ∈I 0+ ( ; ) ∇ ( ) Φ ( 2 ( ; ) -1 ( ; ) 2 1 ( ( ))) .
MPCC-LICQ and the inclusions [START_REF] Gill | SNOPT: An SQP algorithm for large-scale constrained optimization[END_REF] give that the only solution is the trivial one.

Convergence of the epsilon-stationary points

Non-linear programming algorithms usually compute sequences of approximate stationary points or -stationary points (see Definition 2). We present below in relations ( 16)-( 21) our specific definition and hypothesis of -stationary points. This approach, which has become an active subject recently, can significantly alter the convergence analysis of relaxation methods, as shown in [START_REF] Kadrani | A new regularization scheme for mathematical programs with complementarity constraints[END_REF][START_REF] Kanzow | Convergence properties of the inexact Lin-Fukushima relaxation method for mathematical programs with complementarity constraints[END_REF][START_REF] Kanzow | The Price of Inexactness: Convergence Properties of Relaxation Methods for Mathematical Programs with Complementarity Constraints Revisited[END_REF] and [START_REF] Ramos | Mathematical Programms with Equilibrium Constraints: A sequential optimality condition, new constraint qualifications and algorithmic consequences[END_REF].

Previous results in [START_REF] Kanzow | The Price of Inexactness: Convergence Properties of Relaxation Methods for Mathematical Programs with Complementarity Constraints Revisited[END_REF] prove convergence to C-stationary point for the relaxation from Scheel and Scholtes [START_REF] Scholtes | Convergence properties of a regularization scheme for mathematical programs with complementarity constraints[END_REF] and the one from Lin and Fukushima [START_REF] Lin | A modified relaxation scheme for mathematical programs with complementarity constraints[END_REF], under some hypotheses on the sequence , respectively = ( ) and = (2 ). Furthermore, the authors in [START_REF] Kanzow | The Price of Inexactness: Convergence Properties of Relaxation Methods for Mathematical Programs with Complementarity Constraints Revisited[END_REF] also provide a counter-example with a sequence converging to a W-stationary point if these conditions do not hold. Additionally, the authors in [START_REF] Kanzow | The Price of Inexactness: Convergence Properties of Relaxation Methods for Mathematical Programs with Complementarity Constraints Revisited[END_REF], prove that relaxations (3) and ( 4) converge only to a W-stationary point and they require more hypotheses on the sequences and to prove the convergence to a C-or an M-stationary point.

In the same way as in Theorem 1, we consider through this section a sequence of multipliers that should verify the stationary conditions. We denote for all ∈ 0, it is sufficient to show that lim

→∞ | Φ, 2, 1, ( ( )) 2 ( ; )| | , -Φ, 2 ( ; )| = 0. (22)
We now consider two cases: either lim →∞ , = 0 or lim →∞ , ≠ 0.

• If lim →∞ , = 0. Then, the left-hand side in ( 22) is equal to lim

→∞ 2,
1, ( ( )), which goes to zero by Lemma 4 as 2, = ( 1, ).

• Consider the case, lim →∞ , ≠ 0. Dividing by ¯ in the compelmentarity condition in [START_REF] Kanzow | A New Regularization Method for Mathematical Programs with Complementarity Constraints with Strong Convergence Properties[END_REF] implies ( ) ∼ -¯ as = (¯ ). Thus, ( ) < 0 for sufficiently large. We prove that lim →∞ Φ, 2 ( ; ) = 0. Dividing by ( ) in the complementarity condition in [START_REF] Kanzow | Convergence properties of the inexact Lin-Fukushima relaxation method for mathematical programs with complementarity constraints[END_REF] gives for ( ) ∼ -¯ that Φ,

2 ( ; ) 1 - 2, 1, ( ( )) ( ) ≤ | ( )| → 0, (23) as = (¯ ). However, lim →∞ 2, 1, ( ( )) ( ) ≠ 1, otherwise ( ) ≤ 0 and
| ( )| ≥ | ( )| would yield lim →∞ 2, 1, ( ( )) ( ) ≤ lim →∞ 2, 1, ( ( )) ( ) = 0
as is non-decreasing and 2, = ( 1, ). Therefore, [START_REF] Leyffer | Macmpec: Ampl collection of mpecs[END_REF] follows as [START_REF] Lin | A modified relaxation scheme for mathematical programs with complementarity constraints[END_REF] implies lim →∞ Φ,

2 ( ; ) = 0.
The following result proves convergence of the butterfly relaxation in this context.

Theorem 6

Given the three sequences { }, {¯ }, { } decreasing to zero and satisfying [START_REF] Dussault | Mathematical programs with vanishing constraints: constraint qualifications, their applications, and a new regularization method[END_REF]. Assume that = (max(| ( )|, | ( )|)), = (¯ ) and 2, = ( 1, ). Let { , , , ℎ, , , , , , Φ, } be a sequence of -KKT points of ( , ¯ ) with → * such that MPCC-GMFCQ holds at * . Then, * is an M-stationary point.

The notation = (max(| ( )|, | ( )|)

) means here that for all = 1, . . . , , = (max(| ( )|, | ( )|)). For two sequences { }, {ℎ } with the same signs for sufficiently large, we also denote ∼ ℎ whenever lim →∞ /ℎ = 1.

Proof Proceeding in the same way as Theorem 2, we verify that:

(i) * ∈ Z, lim →∞ ∇L ( , ) = 0, lim →∞ , = 0, ∀ ∉ I ( * ), (ii) lim →∞ , / ∞ = 0, ∀ ∈ I +0 , lim →∞ , / ∞ = 0, ∀ ∈ I 0+ , (iii) lim →∞ , , / 2 ∞ = 0 or lim →∞ , / ∞ > 0, lim →∞ , / ∞ > 0, ∀ ∈ I 00 . 1 ( ; ) + 2 ( ; ) ≤ ( ) + -2 2, 1, ( ( )),
which is negative for sufficiently large by definition of and = ( ( )). So, = ( ( )) and ( ) > 0. Thus, dividing by ( ) in the complementarity condition [START_REF] Kanzow | Convergence properties of the inexact Lin-Fukushima relaxation method for mathematical programs with complementarity constraints[END_REF], we obtain lim

≤ 2 | ( )| . ( ; ) 1 - 2, 1, ( ( )) ( )
This implies that lim →∞ Φ, 2 ( ; ) = 0, by assumption on and > 1. Now, by definition of functions s and the triangle inequality, we get

1 ( ; ) + 2 ( ; ) ≤ 2| ( )| + 2 2, 1, (| ( )|) ∼ 2| ( )|. (25)
Using that 2 ( ; ) ∼ ( ) as noticed in the beginning of case (iii), we obtain that lim →∞ Φ,

2 ( ; ) = lim →∞ Φ,
( ) = 0. So, multiplying by Φ, and going to the limit in (25) yields to lim →∞ Φ,

1 ( ; ) + 2 ( ; ) = 0. As a consequence, it holds that lim →∞ ( , , , )/ ∞ = lim →∞ ( , , , ) ≥ 0.
All in all, we completed cases a) and b), so (iii) is satisfied. Finally, since (i)-(ii)-(iii) are satisfied, we conclude as in Theorem 2, so that under MPCC-GMFCQ the sequence { } is bounded and * is an M-stationary point.

The assumption in Theorem 6 is not entirely satisfactory since the sequence of parameter depends on the iterates. However, this is in the same vein as the existing results in [START_REF] Dussault | On approximate stationary points of the regularized mathematical program with complementarity constraints[END_REF][START_REF] Kanzow | The Price of Inexactness: Convergence Properties of Relaxation Methods for Mathematical Programs with Complementarity Constraints Revisited[END_REF]. Further research may try to exploit this weak point to propose more adequate conditions.

Another benefit of considering approximate stationary points is that they may exist even so the assumptions presented in previous section are not satisfied, see [START_REF] Andreani | New sequential optimality conditions for mathematical programs with complementarity constraints and algorithmic consequences[END_REF][START_REF] Andreani | A new sequential optimality condition for constrained optimization and algorithmic consequences[END_REF].

The following example, from [START_REF] Kanzow | A New Regularization Method for Mathematical Programs with Complementarity Constraints with Strong Convergence Properties[END_REF], shows that the butterfly relaxation with 2, = ( .

This sequence converges to * = (0, 0), which is an A-stationary point.

The -feasible set of the butterfly relaxation is similar to the relaxation from [START_REF] Scholtes | Convergence properties of a regularization scheme for mathematical programs with complementarity constraints[END_REF]. Therefore, it is not surprising that we can only expect to converge to a C-stationary point without strong hypotheses. Those issues clearly deserve a specific study that is left for further research.

Numerical Results

In this section, we focus on the numerical implementation of the butterfly relaxation. Our aim is to compare the new method with the existing ones in the literature and to show some of its features. This comparison uses the collection of test problems MacMPEC [START_REF] Leyffer | Macmpec: Ampl collection of mpecs[END_REF]. This collection has been widely used in the literature to compare relaxation methods as in [START_REF] Hoheisel | Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints[END_REF][START_REF] Kadrani | A new regularization scheme for mathematical programs with complementarity constraints[END_REF][START_REF] Steffensen | A new relaxation scheme for mathematical programs with equilibrium constraints[END_REF]. The test problems included in MacMPEC are extracted from the literature and real-world applications.

On the Implementation of the Butterfly Relaxation

Practical implementation could consider a slightly different model, by skipping the relaxation of the positivity constraint and adding a new parameter 3 in order to shift the intersection of both wings to the point ( ( ), ( )) = ( 3 , 3 ). This can be done by redefining 1 ( ; 1 , 2 , 3 ) and 2 ( ; 1 , 2 , 3 ) such that

1 ( ; 1 , 2 , 3 ) = ( ) -3 -2 1 ( ( ) -3 ), 2 ( ; 1 , 2 , 3 ) = ( ) -3 -2 1 ( ( ) -3 ).
Even if we did not give any theoretical proof regarding this modified system, this modification does not alter the behavior of the butterfly relaxation. This formulation is clearly an extension of the relaxation (4).

The numerical comparison of the butterfly relaxation with other existing methods considers three schemes:

1. ( 2 = 1 ) : 3 = 0, 2 = 1 ; 2. ( 2 = 1 3/2 ) : 3 = 0, 2 = 1 3/2 ; 3. ( 3 = 2 ,2 2 = 1 ) : 3 = 2 , 2 2 = 1 .
In all these tests, we fixed ¯ = 0. Our tests concern many variants, not all of which covered by our analysis, but they give a broader insight of the new relaxations.

Comparison of the Relaxation Methods

We provide in this section and Algorithm 1 some more details on the implementation and the comparison between relaxation methods. It is to be noted that we aim to compare the methods and so no attempt to optimize any method has been carried out.

We use 101 test problems from MacMPEC, which omit the problems that exceed the limit of 300 variables or constraints and some problems with the evaluation error of the objective function or the constraints. Algorithm 1 is coded in Matlab and uses the AMPL API. denotes the relaxed non-linear program associated with a generic relaxation, where except the butterfly methods, the parameter 1, does not play any role. At each step we compute +1 as a solution of starting from . Therefore, at each step, the initial point is more likely to be infeasible for . The iterative process stops when 2, and 1, are smaller than some tolerance, denoted min which is set as 10 -15 here, or when the solution +1 of is considered an -solution of (1). To consider +1 as a -solution, with set as 10 -7 , we check three criteria: ( ) := min( ( ), ( )) 2 ; (c) The complementarity between the Lagrange multipliers and the constraints of the last relaxed non-linear program:

( ) := ( ) • , ℎ( ) • ℎ , ( ) • , ( ) • , Φ ( ) • Φ ∞ .
Obviously, it is hard to ask a tighter condition on the complementarity constraint since the feasibility only guarantees that the product component-wise is less than . Using these criteria, we define a measure of optimality

( ) := max ( ), (

), ( ) .

A fourth criterion could be the dual feasibility, which is the norm of the gradient of the Lagrangian. However, solvers like SNOPT or MINOS do not use this criterion as a stopping criterion, but use the gradient of the Lagrangian scaled by the norm of the Lagrange multiplier. One reason among others to discard such a criterion could be numerical issues implied by the degeneracy in the KKT conditions. In the case of an infeasible or unbounded sub-problem , the algorithm stops and returns a certificate.

Data:

starting vector 0 ; initial relaxation parameter 0 ; update parameter ( 1 , 2 ) ∈ (0, 1) Step 4 in Algorithm 1 is performed using three different solvers accessible through AMPL [START_REF] Fourer | Ampl[END_REF], that are SNOPT 7.2-8 [START_REF] Gill | SNOPT: An SQP algorithm for large-scale constrained optimization[END_REF], MINOS 5.51 [START_REF] Murtagh | Minos 5.0 user's guide[END_REF] and IPOPT 3.12.4 [START_REF] Wächter | On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming[END_REF] with their default parameters. A previous similar comparison in the literature in [START_REF] Hoheisel | Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints[END_REF] only considered SNOPT to solve the sub-problems. We compare the butterfly schemes with the most popular relaxations SS from [START_REF] Scheel | Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity[END_REF] and (4). We also take into account the results of the non-linear programming solver without specific MPCC tuning denoted by NL.

In order to compare the various relaxation methods, we need to have a coherent use of the parameters. In a similar way as in [START_REF] Hoheisel | Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints[END_REF] we consider the value of the "intersection between G and H", which is ( , ) for ( 4) and ( 7), ( √ , √ ) for SS. Then, we run a sensitivity analysis on several values of the parameters ∈ {100, 25, 10, 5, 1, 0.5, 0.05} and ∈ {0.1, 0.075, 0.05, 0.025, 0.01}, which corresponds to 0 and as described in Table 1. In [START_REF] Hoheisel | Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints[END_REF], the authors consider as a stopping criterion the feasibility of the First, we see that the method NL is giving decent results. It is not a surprise, as was pointed out in [START_REF] Fletcher | Solving mathematical programs with complementarity constraints as nonlinear programs[END_REF]. Practical implementation of relaxation methods would select the best choice of parameters so that we focus most of our attention on the line 'best'. In Solver SNOPT NL SS KS all cases, the relaxations manage to improve or at least equal the number of problems solved by NL. By using SNOPT, KS and butterfly with 2 = 1 3/2 methods get 1% of improvement, and with IPOPT, the method butterfly with 2 = 1 3/2 is the only one that attains 100%. The relaxation methods seem to make a significant improvement over NL with MINOS. In this case, it is clear that the butterfly methods benefit from the introduction of the parameter , and the method with 3 = 2 , 2 2 = 1 is very competitive.

( 2 = 1 ) ( 3 = 2 ,2 2 = 1 ) ( 2 = 1 3/
Our goal by solving (1) is to compute a local minimum. The results using the local minimum criterion defined above as a measure of success are given in Table 3. Once again, we provide percentages of success.

In comparison with Table 2, this new criterion appears to be more selective. Independently of the solver, the relaxation methods with some correct choices of parameters provide improved results. Using SNOPT as a solver, the methods KS and butterfly give the highest number of results. The method butterfly with 2 = 1 3/2 even improved the number of problems that SNOPT alone solved on average. Similarly, as in the previous experiment, the butterfly method benefits from the introduction of the parameter when using MINOS as a solver.

Concluding Remarks

This paper proposes a new family of relaxation schemes for the mathematical program with complementarity constraints. We prove convergence of the method in the general case and show that a specific relation between the parameters allows the method to converge to the desired M-stationary point. Additionally, in the particular case where MPCC-LICQ holds, S-stationary conditions can be expected to hold at a local minimum. We prove that in the affine case, the butterfly relaxation method converges to such a point without assuming any second-order conditions or strict complementarity-type conditions, which is an improvement over other methods. We provide a complete numerical study with remarks regarding the implementation as well as a comparison with existing methods in the literature. These numerical experiments show that the butterfly schemes are very competitive.

Future research will focus on the main difficulty regarding relaxation schemes that are the convergence of approximate stationary sequences. A discussion regarding the above problem has been initiated in [START_REF] Dussault | On approximate stationary points of the regularized mathematical program with complementarity constraints[END_REF][START_REF] Kanzow | The Price of Inexactness: Convergence Properties of Relaxation Methods for Mathematical Programs with Complementarity Constraints Revisited[END_REF] and appeal for further study. with = -+ Φ 1 ( ; ) -Φ 2 ( ; ) + 1 ( ; ) -1 ( ; ) + 1 ( ; ) 2 1 ( ( )) -2 ( ; ) + 2 ( ; ) + 2 ( ; ) , = -+ Φ 2 ( ; ) -Φ 1 ( ; ) -2 ( ; ) + 2 ( ; ) + 2 ( ; ) 2 1 ( ( ))

+ 1 ( ; ) -1 ( ; ) + 1 ( ; ) .

By linear independence assumption, we obtain = 0, ℎ = 0, = 0, = 0, Φ = 0 ∀ ∈ I 0+ ( ; ) ∪ I +0 ( ; ), -1 ( ; ) 2 1 ( ( )) -2 ( ; ) = 0 and 2 ( ; ) 2 1 ( ( )) + 1 ( ; ) = 0, ∀ ∈ ,

1 ( ; )
2 1 ( ( )) + 2 ( ; ) = 0 and -2 ( ; ) 2 1 ( ( )) -1 ( ; ) = 0, ∀ ∈ , -1 ( ; ) 2 1 ( ( )) + 2 ( ; ) = 0 and -2 ( ; ) 2 1 ( ( )) + 1 ( ; ) = 0, ∀ ∈ -.

So, it follows for ∈ -that 2 ( ; ) = 1 ( ; ) 2 1 ( ( )) and 1 ( ; ) = 2 ( ; ) 2 1 ( ( )).

So 1 ( ; ) = 2 ( ; ) = 0, since ∈ I 00 ( ; ) gives 2 1 ( ( )) 2 1 ( ( )) = 2 1 (0) 2 1 (0) < 1 by properties of and ( 8). Similarly, we get 1 ( ; ) = 2 ( ; ) = 2 ( ; ) = 1 ( ; ) = 0.

Definition 1

 1 Let * ∈ F . (a) Linear Independence CQ (LICQ) holds at * if the family of gradients {∇ ( * ) ( ∈ I ( * )), ∇ℎ ( * ) ( = 1, ..., )} is linearly independent. (b) Mangasarian-Fromovitz CQ (MFCQ) holds at * if the family of gradients {∇ℎ ( * ) ( = 1, . . . , )} is linearly independent and there exists a ∈ R such that ∇ ( * ) < 0 ( ∈ I ( * )) and ∇ℎ ( * ) = 0 ( = 1, . . . , ).

  {1, . . . , } | ( * ) > 0 and ( * ) = 0}, I 0+ := { ∈ {1, . . . , } | ( * ) = 0 and ( * ) > 0}, I 00 := { ∈ {1, . . . , } | ( * ) = 0 and ( * ) = 0}.

2 (

 2 For indices∈ I 0+ ( ; ) (symmetry for indices ∈ I +0 ( ; )), then , ; ). Therefore, considering that 1, ( ( )) < 1, we get , <

  ( ) ≥ 0, ∀ ∈ I ( ; ¯ ), ∇ ( ) ≥ 0, ∀ ∈ I ( ; ¯ ), ∇Φ ( ( ), ( ); ) ≤ 0, ∀ ∈ I 0+ ( ; ) ∪ I +0 ( ; )}, using that ∇Φ ( ( ), ( ); ) = 0 for all ∈ I 00 ( , ).

Example 5 2 (

 52 and as has been chosen arbitrarily then T X , which concludes the proof. This result is sharp, as shown by the following example since Abadie CQ does not hold. Consider the problem min ∈R ) s.t. 0 ≤ 1 ⊥ 2 ≥ 0.

1 (

 1 ; ) = 0 gives that ( , * , , * ) = lim →∞ ( , , , ) ≥ 0. b) When 1 ( ; ) + 2 ( ; ) < 0, the complementarity condition in (20) gives Φ, 2 ( ; ) 2 ≤ 2 , and dividing by | ( )| yields to Φ, 2

1 ,Example 7 2 2 2 (

 1722 ) may converge to an undesirable A-stationary point without the hypothesis that= (max(| ( )|, | ( )|). Consider the problem min ∈R -1 s.t. 0 ≤ 1 ⊥ 2 ≥ 0. Let 2, = 1,2 and choose any positive sequences { 1, } and { } such that 1, , → 0. Consider the following -stationary sequence = ( , /2) , , = 0, , = 1-Φ, ( ; ) -1 ( ; )

  (a) Feasibility of the last relaxed non-linear program: ( ) := max(-( ), |ℎ( )|, -Φ( )); (b) Feasibility of the complementarity constraint:

  where the limit is assumed pointwise ;

	lim →∞	=	pointwise means that for all sequences { } with	∈	for all implies
	lim →∞	∈ and for any * ∈ there exists a sequence	with	∈	such that lim

→∞

= * .

  Moreover, lim →∞ 2, 1, ( ( )) = 0 by Lemma 4 with 2, = ( 1, ) and

							and
	lim →∞	, /	∞ = 0, ∀ ∈ I 0+ .
	Let us now check that either lim →∞	,	, /	2 ∞ = 0 or lim →∞	, /	∞ >
	0, lim →∞	, /		∞ > 0 using the contrapositive, i.e.
			lim →∞	, /	∞ < 0 =⇒ lim →∞	, /	∞ = 0,
	and the other case will be similar by symmetry.
	Let ∈ I 00 . lim
			lim →∞	Φ,	1

→∞

, / ∞ < 0 implies that ∈ I +0 ( ; ) for sufficiently large by definition of , as the function is non-decreasing. So, , = Φ, 2, 1, ( ( )) 1 ( ; ).

  +1 , 2 +1 ) := ( 1, 1 , 2, 2 ) ;

			2 ;	the minimum parameter value; the precision
		tolerance ;
	1 Begin ;
	2 Set := 0 ;
	3 while max( 2, , 1, ) > min and	( ) > do
	4	+1 solution of 1, , 2, with initial point;
	6 return:	the optimal value at the solution	or a decision of
		infeasibility or unboundedness.
	Algorithm 1: Basic Relaxation methods for (1), with a relaxed non-linear
	program	.

5

( 1

Table 1 :

 1 Parameter links among the methods last non-linear parametric program in particular by considering the complementarity constraint by the minimum component-wise. Table2provides our result with this criterion. We report elementary statistics by considering the percentage of success for each set of parameters. A problem is considered solved if criteria (a) and (b) are satisfied.

	Relaxation NL SS KS Butterfly
	0	none 2 none 2

Table 2 :

 2 Sensitivity analysis for MacMPEC test problems considering the feasibility of[START_REF] Abdallah | Solving absolute value equation using complementarity and smoothing functions[END_REF]. Results are a percentage of success. Best: percentage of success with the best set of parameters (independent of the problem), worst: percentage of success with the worst set of parameters, average: average percentage of success among the distribution of ( , ), std: standard deviation.

	2 )

Table 3 :

 3 Solver SNOPT NL SS KS( 2 = 1 ) ( 3 = 2 ,2 2 = 1 ) ( 2 = 1 3/2) Sensitivity analysis for MacMPEC test problems considering the optimality of (1). The results are percentages of success. Best: percentage of success with the best set of parameters, worst: percentage of success with the worst set of parameters, average: average percentage of success among the distribution of ( , ), std: standard deviation.

	best	92.08 94.06 96.04 96.04	97.03	96.04
	average	92.08 90.78 91.17 92.08	90.04	92.33
	worst	92.08 83.17 86.14 87.13	82.18	87.13
	std	0 3.15 2.59 2.45	2.86	2.77
	Solver MINOS NL SS KS	( 2 = 1 )	( 3 = 2 ,2 2 = 1 )	( 2 = 1 3/2 )
	best	85.15 94.06 93.07 88.11	94.06	87.13
	average	85.15 90.94 90.18 81.92	90.04	80.11
	worst	85.15 87.13 86.14 76.23	85.15	74.26
	std	0 1.50 1.62 2.65	2.31	2.95
	Solver IPOPT NL SS KS	( 2 = 1 )	( 3 = 2 ,2 2 = 1 )	( 2 = 1 3/2 )
	best	91.09 93.07 93.07 94.06	93.07	94.06
	average	91.09 91.82 89.84 89.05	88.80	89.02
	worst	91.09 90.10 86.14 84.16	84.16	81.19
	std	0 1.14 2.19 3.09	2.72	3.86

( ; ) := ( ) -2 1 ( ( )), and,

( ; ) := ( ) -2 1 ( ( )).

= ( 1 ) motivated by strong convergence properties as discussed in Section 4.1. The parametric non-linear program related to the butterfly relaxation of the complementarity constraints defined in[START_REF] Dussault | On approximate stationary points of the regularized mathematical program with complementarity constraints[END_REF], and augmented with a regularization of the non-negativity constraints parametrized by ¯ , is given by

=

2, 1, ( 1 + 2 ), 2 = , Φ, 1 ( ; ) =

( ; ) = 0, -2, 1, ( ( )) → -1.

Acknowledgements This research was partially supported by NSERC grant. This research was partially supported by a french grant from "l'Ecole des Docteurs de l'UBL" and "le Conseil Régional de Bretagne". The authors would like to thank the referees for their help and valuable comments.

{1, . . . , }

1, ( ( )) 2 ( ; ) -1 ( ; ) , if 1 ( ; ) ≥ -2 ( ; ) , + Φ, 2 ( ; ) -2, 1, ( ( )) 1 ( ; ) , if 1 ( ; ) < -2 ( ; ),

1, ( ( )) 1 ( ; ) -2 ( ; ) , if 1 ( ; ) ≥ -2 ( ; ) , + Φ, 1 ( ; ) -2, 1, ( ( )) 2 ( ; ) , if 1 ( ; ) < -2 ( ; ). [START_REF] Guo | Solving mathematical programs with equilibrium constraints[END_REF] The representation of ∇Φ ( ( ), ( ); ) immediately gives for all ∈ I 00 ( ; ) and all that ∇Φ ( ( ), ( ); ) = 0. Thus, being a stationary point for ( , ¯ ) satisfies

with ( , , ℎ, ) = ( , , ℎ, ) and , , , defined in [START_REF] Guo | Solving mathematical programs with equilibrium constraints[END_REF], and

Φ ( ( ), ( ); ) ≤ , Φ, ≥ 0,

Φ, Φ ( ( ), ( ); ) ≤ , ∀ = 1, . . . , .

In order to prove our main convergence theorem, we first prove a technical lemma.

Lemma 5 Consider the same assumptions as Theorem 6 below. Additionally, assume that for ∈ I +0 ∪ I 00 , lim

1 ( ; ) = 0 and for sufficiently large 1 ( ; ) ≥ -2 ( ; ). Then, The complementarity condition in [START_REF] Kanzow | Mathematical programs with equilibrium constraints: enhanced fritz john-conditions, new constraint qualifications, and improved exact penalty results[END_REF] gives that lim →∞ , = 0, since ↓ 0 and

As a consequence, lim

Note that we are necessarily in the case 1 ( ; ) + 2 ( ; ) ≥ 0, as 1 ( ; )+ 2 ( ; ) → ( * ) > 0 . In this case we get lim (

It should be noticed that > 1, otherwise for sufficiently large there would exist a constant such that

Another consequence is that 2 ( ; ) ∼ ( ), since 2 ( ; ) ≤ ( ) +

, so, Φ, 1 ( ; ) → 0 since > 1. Now, consider two cases either { , } tends to zero or not. In the former case, the conclusion of case a) would follow by applying Lemma 5. So, let lim →∞ , ≠ 0. Dividing by ( ) in the complementarity condition in [START_REF] Kanzow | Mathematical programs with equilibrium constraints: enhanced fritz john-conditions, new constraint qualifications, and improved exact penalty results[END_REF] gives | , (1 + ¯ / ( ))| ≤ /| ( )| and so ( ) ∼ -¯ . Besides, it can be noted that for sufficiently large there is no constant > 0 such that ( ) ≤ as this would lead to a contradiction with 1 ( ; ) + 2 ( ; ) ≥ 0. Indeed, as ( ) ≥ ( ), we would obtain

We remind that 1 ( ; ) = ( ) -2, 1, ( ( )) and 2 ( ;

1, ( ( )). Thus, lim →∞ ( 2 ( ; ) , 1 ( ; )) = ( ( * ) , 0) and ( * ) > 0.

Appendix 7 Proof of a Technical Lemma

In the of proof Theorem 4 and Theorem 5 we use the following lemma that links the gradients of and with the gradients of 1 ( ; ) and 2 ( ; ).

Lemma 6 Let ( , , -) be any partition of I 00 ( ; ). Assume that the gradients {∇ ( ) ( ∈ I ( )), ∇ℎ ( ) ( = 1, . . . , ), ∇ ( ) ( ∈ I ( ; ¯ ) ∪ I 00 ( ; ) ∪ I +0 ( ; )), ∇ ( ) ( ∈ I ( ; ¯ ) ∪ I 00 ( ; ) ∪ I 0+ ( ; ))} are linearly independent. Then, LICQ holds at for [START_REF] Fourer | Ampl[END_REF].

Proof We show that the gradients of the constraints of ( 13) are positively linearly independent. For this purpose, we prove that the trivial solution is the only solution to the equation 0 =