Jérôme Bolte
email: jerome.bolte@tse-fr.eu.

Edouard Pauwels

Majorization-minimization procedures and convergence of SQP methods for semi-algebraic and tame programs

Keywords: SQP methods, Sℓ 1 QP, Moving balls method, Extended Sequential Quadratic Method, KKT points, KL inequality, Nonlinear programming, Converging methods, Tame optimization

In view of solving nonsmooth and nonconvex problems involving complex constraints (like standard NLP problems), we study general maximization-minimization procedures produced by families of strongly convex sub-problems. Using techniques from semi-algebraic geometry and variational analysis -in particular Lojasiewicz inequality-we establish the convergence of sequences generated by this type of schemes to critical points.

The broad applicability of this process is illustrated in the context of NLP. In that case critical points coincide with KKT points. When the data are semi-algebraic or real analytic our method applies (for instance) to the study of various SQP methods: the moving balls method, Sℓ 1 QP, ESQP. Under standard qualification conditions, this provides -to the best of our knowledge-the first general convergence results for general nonlinear programming problems. We emphasize the fact that, unlike most works on this subject, no second-order assumption and/or convexity assumptions whatsoever are made. Rate of convergence are shown to be of the same form as those commonly encountered with first order methods.

Introduction

Many optimization methods consist in approximating a given problem by a sequence of simpler problems that can be solved in closed form or computed fast, and which eventually provide a solution or some acceptable improvement. From a mathematical viewpoint some central questions are the convergence of the sequence to a desirable point (e.g. a KKT point), complexity estimates, rates of convergence. For these theoretical purposes it is often assumed that the constraints are simple, in the sense that their projection is easy to compute (i.e. known through a closed formula), or that the objective involve nonsmooth terms whose proximal operators are available (see e.g. [START_REF] Combettes | Proximal Splitting Methods in Signal Processing[END_REF][START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Lojasiewicz inequality[END_REF][START_REF] Attouch | Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods[END_REF]). An important challenge is to go beyond this prox friendly (1 ) setting and to address mathematically the issue of nonconvex nonsmooth problems presenting complex geometries.

The richest field in which these problems are met, and which was the principal motivation to this research, is probably "standard nonlinear programming" in which KKT points are generally sought through the resolution of quadratic programs of various sorts. We shall refer here to these methods under the general vocable of SQP methods. The bibliography on the subject is vast, we refer the readers to [START_REF] Bertsekas | Nonlinear Programming[END_REF][START_REF] Nocedal | Numerical Optimization[END_REF][START_REF] Gill | Sequential Quadratic Programming Methods[END_REF][START_REF] Fletcher | Global convergence of a trust-region SQP-filter algorithm for general nonlinear programming[END_REF] (for instance) and references therein for an insight.

Although these methods are quite old now -the pioneering work seems to originate in the PhD thesis of Wilson [START_REF] Wilson | Simplicial Method for Convex Programming[END_REF] in 1963-and massively used in practice, very few general convergence or complexity results are available. Most of them are local and are instances of the classical case of convergence of Newton's method (2 ) [START_REF] Fletcher | Practical Methods of Optimization[END_REF][START_REF] Bonnans | Numerical Optimization: Theoretical and Practical Aspects[END_REF][START_REF] Nocedal | Numerical Optimization[END_REF]. Surprisingly the mere question "are the limit points KKT points?" necessitates rather strong assumptions and/or long developmentssee [START_REF] Bonnans | Numerical Optimization: Theoretical and Practical Aspects[END_REF]Theorem 17.2] or [START_REF] Burke | A robust sequential quadratic programming method[END_REF][START_REF] Byrd | On the Convergence of Successive Linear-Quadratic Programming Algorithms[END_REF][START_REF] Solodov | Global convergence of an SQP method without boundedness assumptions on any of the iterative sequences[END_REF] for the drawbacks of "raw SQP" in this respect, see also [START_REF] Bertsekas | Nonlinear Programming[END_REF][START_REF] Bonnans | Numerical Optimization: Theoretical and Practical Aspects[END_REF] for some of the standard conditions/corrections/recipes ensuring that limit points are KKT. Works in which actual convergence (or even limit point convergence) are obtained under minimal assumptions seem to be pretty scarce. In [START_REF] Fukushima | A Sequential Quadratically Constrained Quadratic Programming Method for Differentiable Convex Minimization[END_REF] Fukushima-Luo-Tseng provided a general SQCQP method (3 ) together with a convergence result in terms of limit points, the results were further improved and simplified in [START_REF] Solodov | On the Sequential Quadratically Constrained Quadratic Programming Methods[END_REF]. More related to the present work is the contribution of Solodov in [START_REF] Solodov | Global convergence of an SQP method without boundedness assumptions on any of the iterative sequences[END_REF] who gave a genuinely non-trivial proof for a SQP method to eventually provide KKT limit points. More recently Auslender [START_REF] Auslender | An Extended Sequential Quadratically Constrained Quadratic Programming Algorithm for Nonlinear, Semidefinite, and Second-Order Cone Programming[END_REF] addressed the issue of the actual convergence in the convex case by modifying and somehow reversing the basic SQP protocol: "the merit function" (see [START_REF] Han | A globally convergent method for nonlinear programming[END_REF][START_REF] Powell | On search directions for minimization algorithms[END_REF]) is directly used to devise descent directions as in Fletcher's pioneering Sℓ 1 QP method [START_REF] Fletcher | An ℓ 1 penalty method for nonlinear constraints[END_REF]. In this line of research one can also quote the works of Auslender-Shefi-Teboulle [START_REF] Auslender | A moving balls approximation method for a class of smooth constrained minimization problems[END_REF] on the "moving balls" method -another instance of the class of SQCQP methods.

Apart from [START_REF] Auslender | An Extended Sequential Quadratically Constrained Quadratic Programming Algorithm for Nonlinear, Semidefinite, and Second-Order Cone Programming[END_REF][START_REF] Auslender | A moving balls approximation method for a class of smooth constrained minimization problems[END_REF], we are not aware of other results providing actual convergence for general smooth convex functions (4 ). After our own unfruitful tries, we think this is essentially due to the fact that the dynamics of active/inactive constraints is not well understood -despite some recent breakthroughs [START_REF] Lewis | Active Sets, Nonsmoothness, and Sensitivity[END_REF][START_REF] Wright | Constraint identification and algorithm stabilization for degenerate nonlinear programs[END_REF][START_REF] Hare | Identifying Active Constraints via Partial Smoothness and Prox-Regularity[END_REF] to quote a few. In any cases "usual" methods for convergence or complexity fail and to our knowledge there are very few other works on the topic. In the nonconvex world the recent advances of Cartis-Gould-Toint [START_REF] Cartis | On the complexity of finding first-order critical points in constrained nonlinear optimization[END_REF] are first steps towards a complexity theory for NLP. Since we focus here on convergence our approach is pretty different but obviously connections and complementarities must be investigated.

Let us describe our method for addressing these convergence issues. Our approach is threefold:

-We consider nonconvex, possibly nonsmooth, semi-algebraic/real analytic data; we actually provide results for definable sets. These model many, if not most, applications.

-Secondly we delineate and study a wide class of majorization-minimization methods for nonconvex nonsmooth constrained problems. Our main assumption being that the procedures involve locally Lipschitz continuous, strongly convex upper approximations. Under a general qualification assumption, we establish the convergence of the process. Once more, nonsmooth KL inequality appears as an essential tool.

-Previous results are applied to derive convergence of SQP methods (Fletcher's Sℓ 1 QP [START_REF] Fletcher | An ℓ 1 penalty method for nonlinear constraints[END_REF], Auslender [START_REF] Auslender | An Extended Sequential Quadratically Constrained Quadratic Programming Algorithm for Nonlinear, Semidefinite, and Second-Order Cone Programming[END_REF]) and SQCQP methods (moving balls method [START_REF] Auslender | A moving balls approximation method for a class of smooth constrained minimization problems[END_REF]). To the best of our knowledge, these are the first general nonconvex results dealing with possibly large problems with complex geometries -which are not "prox-friendly". Convergence rates have the form O 1 k γ with γ > 0. We describe now these results into more details which will also give an insight at the main results obtained in this paper.

Majorization-minimization procedures (MMP). These methods consist in devising at each point of the objective a simple upper (tangent) model (e.g. quadratic forms) and to minimize/update these models dynamically in order to produce minimizing/descent sequences. This principle can be traced back, at least, to [36, section 8.3.(d)] and have found many applications since then, mostly in the statistics literature [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF], but also in other branches like recently in imaging sciences [START_REF] Chouzenoux | A Majorize-Minimize Subspace Approach for ℓ 2ℓ 0 Image Regularization[END_REF]. In the context of optimization, many iterative methods follow this principle, see [START_REF] Beck | Gradient-Based Algorithms with Applications to Signal Recovery Problems[END_REF][START_REF]Optimization with First-Order Surrogate Functions[END_REF] for numerous examples -and also [START_REF] Noll | Convergence of Non-smooth Descent Methods Using the Kurdyka-Lojasiewicz Inequality[END_REF] where KL inequality is used to solve nonsmooth problems using a specific class of models. These procedures, which we have studied as tools, appeared to have an interest for their own sake. Our main results in this respect are self-contained and can be found in Sections 3 and 4. Let us briefly sketch a description of the MM models we use. Being given a problem of the form

P min f (x) : x ∈ D
where f : R n → R is a semi-algebraic continuous function and D is a nonempty closed semialgebraic set, we define at each feasible point x, local semi-algebraic convex models for f and D, respectively h(x, •) : R n → R -which is actually strongly convex-and D(x) ⊂ R n . We then iteratively solve problems of the form

x k+1 = p(x k ) := arg min h(x k , y) : y ∈ D(x k ) , k ∈ N.
An essential assumption is that of using upper approximations (5 ):

D(x) ⊂ D and h(x, •) ≥ f (•) on D(x).
When assuming semi-algebraicity of the various ingredients, convergence cannot definitely be seen as a consequence of the results in [START_REF] Attouch | Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods[END_REF][START_REF] Bolte | Proximal alternating linearized minimization for nonconvex and nonsmooth problems[END_REF]. This comes from several reasons. First we do not have a "proper (sub)gradient method" for P as required in the general protocol described in [START_REF] Attouch | Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods[END_REF]. A flavor of these difficulty is easily felt when considering SQP. For these methods there is, at least apparently, a sort of an unpredictability of future active/inactive constraints: the descent direction does not allow to forecast future activity and thus does not necessarily mimic an adequate subgradient of f + i D or of similar aggregate costs (6 ). Besides, even when a better candidate for being the descent function is identified, explicit features inherent to the method still remain to be dealt with. The cornerstone of our analysis is the introduction and the study of the value (improvement) function F (x) = h(x, p(x)). It helps circumventing the possible anarchic behavior of active/inactive constraints by an implicit inclusion of future progress within the cost. We establish that the sequence x k has a behavior very close to a subgradient method for F , see Section 4.3.

Our main result is an asymptotic alternative, a phenomena already guessed in [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Lojasiewicz inequality[END_REF]: either the sequence x k tends to infinity, or it converges to a critical point. As a consequence we have convergence of the sequence to a single point whenever the problem P is coercive.

Convergence of SQP type methods. The previous results can be applied to many algorithms (see e.g. [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Lojasiewicz inequality[END_REF][START_REF] Bolte | Proximal alternating linearized minimization for nonconvex and nonsmooth problems[END_REF][START_REF] Chouzenoux | A Majorize-Minimize Subspace Approach for ℓ 2ℓ 0 Image Regularization[END_REF]), but we concentrate on some SQP methods for which such results are novel.

In order to avoid a too important concentration of hardships, we do not discuss here computational issues of the sub-steps, the prominent role of step sizes, the difficult question of the feasibility of sub-problems, we refer the reader to [START_REF] Fletcher | Practical Methods of Optimization[END_REF][START_REF] Bertsekas | Nonlinear Programming[END_REF][START_REF] Gill | Sequential Quadratic Programming Methods[END_REF] and references therein. We would like also to emphasize that, by construction, the methods we investigate may or may not involve hessians in their second-order term but they must systematically include a fraction of the identity as a regularization parameter, à la Levenberg-Marquardt (see e.g. [START_REF] Nocedal | Numerical Optimization[END_REF]). Replacing Hessian by their regularization or by fractions of the identity is a common approach to regularize ill-posed problems; it is also absolutely crucial when facing large scale problems see e.g. [START_REF] Gill | SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization[END_REF][START_REF] Svanberg | A Class of Globally Convergent Optimization Methods Based on Conservative Convex Separable Approximations[END_REF].

The aspects we just evoked above have motivated our choice of Auslender SQP method and of the moving balls method which are both relatively "simple" SQP/SQCQP methods. To show the flexibility of our approach, we also study a slight variant of Sℓ 1 QP [START_REF] Fletcher | An ℓ 1 penalty method for nonlinear constraints[END_REF]. This method, also known as "elastic SQP", is a modification of SQP making the sub-problems feasible by the addition of slack variables. In [START_REF] Gill | SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization[END_REF] the method has been adapted and redesigned to solve large scale problems (SNOPT); a solver based on this methodology is available.

For these methods we show that a bounded sequence must converge to a single KKT point, our results rely only on semi-algebraic (definability) techniques and do not use convexity nor second order conditions. We also establish that these methods come with convergence rates similar to those observed in classical first-order method ( [START_REF] Attouch | On the convergence of the proximal algorithm for nonsmooth functions involving analytic features[END_REF]).

Organization of the paper. Section 2 presents our main results concerning SQP methods. In Section 3, we describe an abstract framework for majorization-minimization methods that is used to analyze the algorithms presented in Section 2. We give in particular a general result on the convergence of MM methods. Definitions, proofs and technical aspects can be found in Section 4. Our results on MM procedures and SQP are actually valid for the broader class of real analytic or definable data, this is explained in Section 5. The Appendix (Section 6) is devoted to the technical study of SQP methods, it is shown in particular how they can be interpreted as MM processes.

Sequential quadratic programming for semi-algebraic and tame problems

We consider in this section problems of the form:

(1)

P NLP min x∈R n f (x) s.t. f i (x) ≤ 0, i = 1, . . . , m x ∈ Q
where each f i is twice continuously differentiable and Q is a nonempty closed convex set. Q should be thought as a "simple" set, i.e. a set whose projection is known in closed form (or "easily" computed), like for instance one of the archetypal self dual cone R n + , second order cone, positive semi-definite symmetric cone (7 ) but also an affine space, an ℓ 1 ball, the unit simplex, or a box. Contrary to Q, the set

F = {x, f i (x) ≤ 0, i = 1, . . . , m},
has, in general, a complex geometry and its treatment necessitates local approximations in the spirit of SQP methods. Specific assumptions regarding coercivity, regularity and constraint qualification are usually required in order to ensure correct behavior of numerical schemes, we shall make them precise for each method we present here. Let us simply recall that under these assumptions minimizers x of P NLP must satisfy the famous KKT conditions:

x ∈ Q, f 1 (x) ≤ 0, . . . , f m (x) ≤ 0, (2) ∃ λ 1 ≥ 0, . . . , λ m ≥ 0, (3) ∇f (x) + λ i ∇f i (x) + N Q (x) ∋ 0, (4)
λ i f i (x) = 0, ∀i = 1, . . . , m, (5)
where N Q (x) is the normal cone to Q at x (see Section 4.1).

SQP methods assume very different forms, we pertain here to three "simple models" with the intention of illustrating the versatility of our approach (but other studies could be led):

-Moving balls method: an SQCQP method, -ESQP method a merit function approach with ℓ ∞ penalty, -Sℓ 1 QP method a merit function approach with ℓ 1 penalty.

A sequentially constrained quadratic method: the moving balls method

This method was introduced in [START_REF] Auslender | A moving balls approximation method for a class of smooth constrained minimization problems[END_REF] for solving problems of the form of (1) with Q = R n . The method enters the framework of sequentially constrained quadratic problems. It consists in approximating the original problem by a sequence of quadratic problems over an intersection of balls. Strategies for simplifying constraints approximation, computations of the intermediate problems are described in [START_REF] Auslender | A moving balls approximation method for a class of smooth constrained minimization problems[END_REF], we only focus here on the convergence properties and rate estimates. The following assumptions are necessary.

Regularity: [START_REF] Auslender | A moving balls approximation method for a class of smooth constrained minimization problems[END_REF] The functions f, f 1 , . . . , f m : R n → R are C 2 , with Lipschitz continuous gradients. For each i = 1, . . . , m, we denote by L i > 0 some Lipschitz constants of ∇f i and by L > 0 a Lipschitz constant of ∇f .

Mangasarian-Fromovitz Qualification Condition (MFQC): For x in F , set I(x) = {i = 1, . . . , m : f i (x) = 0}. MFQC writes [START_REF] Beck | Gradient-Based Algorithms with Applications to Signal Recovery Problems[END_REF] ∀x ∈ F , ∃d ∈ R n such that ∇f i (x), d < 0, ∀i ∈ I(x).

Compactness: There exists a feasible x 0 ∈ F such that

(8) {x ∈ R n : f (x) ≤ f (x 0 )} is bounded.
The moving balls method is obtained by solving a sequence of quadratically constrained problems.

Moving balls method

Step 1 x 0 ∈ F .

Step 2 Compute x k+1 solution of min

y∈R n f (x k ) + ∇f (x k ), y -x k + L 2 ||y -x k || 2 s.t. f i (x k ) + ∇f i (x k ), y -x k + L i 2 ||y -x k || 2 ≤ 0, i = 1 . . . m
The algorithm can be proven to be well defined and to produce a feasible method provided that x 0 is feasible, i.e.

x k ∈ F , ∀k ≥ 0.

These aspects are thoroughly described in [START_REF] Auslender | A moving balls approximation method for a class of smooth constrained minimization problems[END_REF].

Theorem 2.1 (Convergence of the moving balls method) Recall that Q = R n and assume that the following conditions hold -The functions f, f 1 , . . . , f m are semi-algebraic, -Lipschitz continuity conditions (6),

-Mangasarian-Fromovitz qualification condition (8),

-boundedness condition [START_REF] Beck | Gradient-Based Algorithms with Applications to Signal Recovery Problems[END_REF],

-feasibility of the starting point x 0 ∈ F .

Then, (i) The sequence {x k } k∈N defined by the moving balls method converges to a feasible point x ∞ satisfying the KKT conditions for the nonlinear programming problem P NLP .

(ii) Either convergence occurs in a finite number of steps or the rate is of the form:

(a) x k -x ∞ = O(q k ), with q ∈ (0, 1), (b) x k -x ∞ = O 1 k γ , with γ > 0.

Extended sequential quadratic method

ESQM method (and Sℓ 1 QP) grounds on the well-known observation that an NLP problem can be reformulated as an "unconstrained problem" involving an exact penalization. Set f 0 = 0 and consider

min x∈Q f (x) + β max i=0,...,m f i (x) (9)
where β is positive parameter. Under mild qualification assumptions and for β sufficiently large, critical points of the above are KKT points of the initial nonlinear programming P NLP . Building on this fact ESQM is devised as follows:

• At a fixed point x (non necessarily feasible), form a model of (9) such that:

-complex terms f, f 1 , . . . , f m are linearized, -a quadratic term β 2 ||y -x|| 2 is added both for conditioning and local control, • minimize the model to find a descent direction and perform a step of size λ > 0,

• both terms λ, β are adjusted online:

λ is progressively made smaller to ensure a descent condition, β is increased to eventually reach a threshold for exact penalization.

We propose here a variation of this method which consists in modifying the quadratic penalty term instead of relying on a line search procedure to ensure some sufficient decrease. For a fixed x in R n , we consider a local model of the form:

h β (x, y) = f (x) + ∇f (x), y -x + β max i=0,...,p {f i (x) + ∇f i (x), y -x } + (λ + βλ ′ ) 2 ||y -x|| 2 + i Q (y),
where β is a parameter and λ, λ ′ > 0 are fixed.

As we shall see this model is to be iteratively used to provide descent directions and ultimately KKT points. Before describing into depth the algorithm, let us state our main assumptions (recall that

F = {x ∈ R n : f i (x) ≤ 0, ∀i = 1, . . . ,

m}).

Regularity: The functions [START_REF] Bolte | The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems[END_REF] f, f 1 , . . . , f m : R n → R are C 2 , with Lipschitz continuous gradients. For each i = 1, . . . , m, we denote by L i > 0 some Lipschitz constants of ∇f i and by L > 0 a Lipschitz constant of ∇f . We also assume that the step size parameters satisfy

(11) λ ≥ L and λ ′ ≥ max i=1,...,m L i .
Qualification condition: The function max i=1,...,m

f i + i Q has no critical points on the set x ∈ Q : ∃i = 1, . . . , m, f i (x) ≥ 0 . Equivalently, ∀x ∈ {x ∈ Q : ∃i = 1, . . . , m, f i (x) ≥ 0}, there cannot exist {u i } i∈I such that (12) u i ≥ 0, i∈I u i = 1, i∈I u i ∇f i (x), z -x ≥ 0, ∀z ∈ Q, where I = j > 0, f j (x) = max i=1,...,m {f i (x)} .
Remark 1 (a) Set J = {1, . . . , m}. The intuition behind this condition is simple:

max i∈J f + i Q is assumed to be (locally) "sharp" and thus β max i∈J (0, f i ) + i Q resembles i Q∩F for big β. (b)
The condition [START_REF] Bonnans | Numerical Optimization: Theoretical and Practical Aspects[END_REF] implies the generalized Mangasarian-Fromovitz condition (sometimes called Robinson condition):

∀x ∈ Q ∩ F , ∃y ∈ Q \ {x}, ∇f i (x), y -x < 0, ∀i = 1, . . . , m, such that f i (x) = 0.
(c) Observe that qualification condition [START_REF] Bonnans | Numerical Optimization: Theoretical and Practical Aspects[END_REF] implies that the feasible set is connected which is a natural extension of the more usual convexity assumption. [Connectedness follows from a contradiction argument and the application of the mountain pass theorem. The latter ensures indeed the existence of a non feasible critical point to max{f i : i = 1, . . . , m} + i Q which contradicts our qualification assumption.]

Compactness: For all real numbers µ 1 , . . . , µ m , the set

(13) {x ∈ Q, f i (x) ≤ µ i , i = 1, . . . , m} is compact.
Boundedness:

(14) inf x∈Q f (x) > -∞.
Let us finally introduce feasibility test functions

(15) test i (x, y) = f i (x) + ∇f i (x), y -x
for all i = 1, . . . , m and x, y in R n .

Remark 2 (Online feasibility test) We shall use the above functions for measuring the quality of β k . This test function will also be applied to the analysis of Sℓ 1 QP. Depending on the information available in the method, other choices could be done like for instance

test i (x, y) = f i (x) + ∇f i (x), y -x + L f i 2 y -x or simply test i (x, y) = f i (y).
We proceed now to the description of the algorithm.

Extended Sequential Quadratic Method (ESQM)

Step 1 Choose

x 0 ∈ Q, β 0 , δ > 0
Step 2 Compute the unique solution x k+1 of min y∈R n h β k (x k , y), i.e. solve for y (and s) in: min

y,s f (x k ) + ∇f (x k ), y -x k + β k s + (λ+β k λ ′ ) 2 ||y -x|| 2 s.t. f i (x k ) + ∇f i (x k ), y -x k ≤ s, i = 1 . . . m, s ≥ 0 y ∈ Q. Step 3 If test i (x k , x k+1 ) ≤ 0 for all i = 1, . . . , m, then β k+1 = β k , otherwise β k+1 = β k + δ
Remark 3 (a) Working with quadratic terms involving Hessians in h β k is possible provided that local models are upper approximations (one can work for instance with approximate functions à la Levenberg-Marquardt [START_REF] Nocedal | Numerical Optimization[END_REF]).

(b) The algorithm presented in [START_REF] Auslender | An Extended Sequential Quadratically Constrained Quadratic Programming Algorithm for Nonlinear, Semidefinite, and Second-Order Cone Programming[END_REF] is actually slightly different from the one above. Indeed, the quadratic penalty term was there simply proportional to β and the step sizes were chosen by line search. Original ESQP could thus be seen as a kind of backtracking version of the above method.

(c) Let us also mention that many updates rules are possible, in particular rules involving upper bounds of local Lagrange multipliers. The essential aspect is that exact penalization is reached in a finite number of iterations.

(d) Observe that the set Q of simple constraints is kept as is in the sub-problems.

The convergence analysis carried out in [START_REF] Auslender | An Extended Sequential Quadratically Constrained Quadratic Programming Algorithm for Nonlinear, Semidefinite, and Second-Order Cone Programming[END_REF] can be extended to our setting, leading to the following theorem (note we do not use the semi-algebraicity assumptions). -boundedness assumptions (13), ( 14), then the sequence of parameters β k stabilizes after a finite number of iterations k 0 and all cluster points of the sequence {x k } k∈N are KKT points of the nonlinear programming problem P NLP .

The application of the techniques developed in this paper allow to prove a much stronger result: (ii) Either convergence occurs in a finite number of steps or the rate is of the form:

(a) x kx ∞ = O(q k ), with q ∈ (0, 1),

(b) x k -x ∞ = O 1 k γ , with γ > 0.
This result gives a positive answer to the "Open problem 3" in [5, Section 6] (with a slightly modified algorithm).

Sℓ 1 QP aka "elastic sequential quadratic method"

The Sℓ 1 QP is an ℓ 1 version of the previous method. It seems to have been introduced in the eighties by Fletcher [START_REF] Fletcher | An ℓ 1 penalty method for nonlinear constraints[END_REF]. Several aspects of this method are discussed in [START_REF] Fletcher | Practical Methods of Optimization[END_REF]; see also [START_REF] Gill | SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization[END_REF] for its use in the resolution of large size problems (SNOPT algorithm). The idea is based this time on the minimization of the ℓ 1 penalty function:

min x∈Q f (x) + β m i=0 f + i (x) ( 16
)
where β is a positive parameter and where we have set a + = max(0, a) for any real number a.

Local models are of the form:

h β (x, y) = f (x) + ∇f (x), y -x + β m i=1 (f i (x) + ∇f i (x), y -x ) + + (λ + βλ ′ ) 2 ||y -x|| 2 + i Q (y), ∀x, y ∈ R n ,
where as previously λ, λ ′ > 0 are fixed parameters. Using slack variables the minimization of h β (x, .) amounts to solve the problem

min f (x) + ∇f (x), y -x + β m i=1 s i + (λ+βλ ′ ) 2 ||y -x|| 2 s.t. f i (x) + ∇f i (x), y -x ≤ s i , i = 1 . . . m s 1 , . . . , s m ≥ 0 y ∈ Q.
Once again, the above is very close to the "usual" SQP step, the only difference being the elasticity conferred to the constraints by the penalty term.

The main requirements needed for this method are quasi-identical to those we used for ESQP: we indeed assume [START_REF] Bolte | The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems[END_REF], ( 12), ( 13), [START_REF] Byrd | On the Convergence of Successive Linear-Quadratic Programming Algorithms[END_REF], while [START_REF] Bolte | Proximal alternating linearized minimization for nonconvex and nonsmooth problems[END_REF] is replaced by:

(17) λ ≥ L and λ ′ ≥ m i=1 L i .
The latter is more restrictive in the sense that smaller step lengths are required, but on the other hand this restriction comes with more flexibility in the relaxation of the constraints.

In the description of the algorithm below, we make use the test functions (15) described in the previous section.

Sℓ 1 QP Step 1 Choose x 0 ∈ Q, β 0 , δ > 0 Step 2 Compute the unique solution x k+1 of min y∈R n h β k (x k , y),
i.e. solve for y (and s) in:

min f (x) + ∇f (x), y -x + β k m i=1 s i + (λ+β k λ ′ ) 2 ||y -x|| 2 s.t. f i (x) + ∇f i (x), y -x ≤ s i , i = 1 . . . m s 1 , . . . , s m ≥ 0 y ∈ Q. Step 3 If test i (x k , x k+1 ) ≤ 0 for all i = 1, . . . , m, then β k+1 = β k , otherwise β k+1 = β k + δ
The convergence in terms of limit points and for the sequence β k is similar to that of previous section. In this theorem semi-algebraicity is not necessary. -boundedness assumptions (13), ( 14), then the sequence of parameters β k stabilizes after a finite number of iterations k 0 and all cluster points of the sequence {x k } k∈N are KKT points of the nonlinear programming problem P NLP .

We obtain finally the following result: -boundedness assumptions (13), [START_REF] Byrd | On the Convergence of Successive Linear-Quadratic Programming Algorithms[END_REF].

Then, (i) The sequence {x k } k∈N generated by (ESQM) converges to a feasible point x ∞ satisfying the KKT conditions for the nonlinear programming problem P NLP .

(ii) Either convergence occurs in a finite number of steps or the rate is of the form:

(a) x k -x ∞ = O(q k ), with q ∈ (0, 1), (b) x k -x ∞ = O 1 k γ , with γ > 0.
3 Majorization-minimization procedures In what follows we study the properties of majorization-minimization methods. At each feasible point, x, local convex models for f and D are available, say h(x, •) : R n → R and D(x) ⊂ R n ; we then iteratively solve problems of the form

x k+1 ∈ arg min h(x k , y) : y ∈ D(x k ) .
In order to describe the majorization-minimization method we study, some elementary notions from variational analysis and semi-algebraic geometry are required. However, since the concepts and notations we use are quite standard we have postponed their formal introduction in Section 4.1 page 16. We believe this contributes to a smoother presentation of our results.

Majorization-minimization procedures

For the central problem at stake

P min f (x) : x ∈ D
we make the following standing assumptions

S        f : R n → R is locally Lipschitz continuous, subdifferentially regular and semi-algebraic, inf f (x) : x ∈ D > -∞,
D ⊂ R n is nonempty, closed, regular and semi-algebraic.

Remark 4 (Role of regularity) The meaning of the terms subdifferential regularity/regularity is recalled in the next section. It is important to mention that these two assumptions are only used to guarantee the good behavior of the sum rule (and thus of KKT conditions)

∂ (f + i D ) (x) = ∂f (x) + N D (x), x ∈ D.
One could thus use alternative sets of assumptions, like: f is C 1 and D is closed (not necessarily regular).

A critical point x ∈ R n for P is characterized by the relation ∂(f + i D )(x) ∋ 0, i.e. using the sum rule:

∂f (x) + N D (x) ∋ 0 (Fermat's rule for constrained optimization).
When D is a non empty intersection of sublevel sets, as in Section 2, it necessarily satisfies the assumptions S (see Appendix). Besides, by using the generalized Mangasarian-Fromovitz qualification condition at x, one sees that Fermat's rule exactly amounts to KKT conditions (see Proposition 4.1).

Inner convex constraints approximation

Constraints are locally modeled at a point x ∈ R n by a subset D(x) of R n . One assumes that

D : R n ⇒ R n satisfies (19)        dom D ⊃ D, D(x) ⊂ D and N D(x) (x) ⊂ N D (x), ∀x ∈ D, D has closed convex values, D is continuous (in the sense of multivalued mappings).
Local strongly convex upper models for f Fix µ > 0.

(20)

                                          
The family of local models

h : R n × R n -→ R (x, y) -→ h(x, y)
satisfies:

(i) h(x, x) = f (x) for all x in D, (ii) ∂ y h(x, y)| y=x ⊂ ∂f (x) for all x in D, (iii) For all x in D, h(x, y) ≥ f (y), ∀y ∈ D(x), (iv) h is continuous. For each fixed x in D, the function h(x, •) is µ strongly convex.
Example 1 (a) A typical, but important, example of upper approximations that satisfy these properties comes from the descent lemma (Lemma 4.4). Given a C 1 function f with L f -Lipschitz continuous gradient we set

h(x, y) = f (x) + ∇f (x), y -x + L f 2 x -y 2 .
Then h satisfies all of the above (with D = D(x) = R n for all x). (b) SQP methods of the previous section provide more complex examples.

A qualification condition for the surrogate problem

We require a relation between the minimizers of y → h(x, y) and the general variations of h. Set ĥ(x, y) = h(x, y) + i D(x) (y), for all x, y in R n , and ĥ(x, y) = +∞ whenever D(x) is empty.

For, any compact C ⊂ R n , there is a constant K(C), such that, We set for all x in D,

p(x) = P D x - 1 L f ∇f (x) .
With these simple instances for h and D, we recover the gradient projection iteration mapping. Note also that for this example ∂ ĥ(x, y) = (v, 0) implies that

v = (LI n -∇ 2 f (x))(x -p(x)).
Thus the qualification assumption is trivially satisfied whenever f is C 2 .

Our general procedure can be summarized as:

Majorization-minimization procedure (MMP)

Assume the local approximations satisfy the assumptions:

• inner constraints approximation [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF],

• upper objective approximation (20),

• qualification conditions [START_REF] Van Den Dries | Geometric categories and o-minimal structures[END_REF], Let x 0 be in D and define iteratively

x k+1 = p(x k ),
where p is the iteration mapping [START_REF] Fletcher | Practical Methods of Optimization[END_REF].

Example 2 Coming back to our model example, (MMP) reduces simply to the gradient projection method

x k+1 = P D x k - 1 L f ∇f (x k ) , x 0 ∈ D.

Main convergence result

Recall the standing assumptions S on P , our main "abstract" contribution is the following theorem. (II) In addition, when x k converges, either it converges in a finite number of steps or the rate of convergence is of the form:

(a) x k -x ∞ = O(q k ), with q ∈ (0, 1), (b) x k -x ∞ = O 1 k γ , with γ > 0.
Remark 6 (Coercivity/Divergence) (a) If in addition [f ≤ f (x 0 )] ∩ D is bounded, the sequence x k cannot diverge and converges thus to a critical point. (b) The divergence property (I) -(i) is a positive result, a convergence result, which does not correspond to a failure of the method but rather to the absence of minimizers in a given zone.

Theorem 3.1 draws its strength from the fact that majorization-minimization schemes are ubiquitous in continuous optimization (see [START_REF] Beck | Gradient-Based Algorithms with Applications to Signal Recovery Problems[END_REF]). This is illustrated with SQP methods but other applications can be considered.

The proof (to be developed in the next section) is not trivial but the ideas can be briefly sketched as follows:

• Study the auxiliary function, the "value improvement function":

F = val : D → R x → h(x, p(x)).
• Show that there is a non-negative constants K 1 such that sequence of iterates satisfies:

F (x k ) + K 1 ||x k -x k+1 || 2 ≤ f (x k ) ≤ F (x k-1 )
• Show that for any compact C, there is a constant

K 2 (C) such that if x k ∈ C, we have: dist 0, ∂F (x k ) ≤ K 2 (C)||x k+1 -x k ||
• Despite the explicit type of the second inequality, one may use KL property (see Section 4.1) and techniques akin to those presented in [START_REF] Bolte | Proximal alternating linearized minimization for nonconvex and nonsmooth problems[END_REF][START_REF] Attouch | Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods[END_REF] to obtain convergence of the iterative process.

Convergence analysis of majorization-minimization procedures

This section is entirely devoted to the exposition of the technical details related to the proof of Theorem 3.1.

Some concepts for nonsmooth and semi-algebraic optimization

We hereby recall a few definitions and concepts that structure our main results. In particular, we introduce the notion of a subdifferential and of a KL function, which are the most crucial tools used in our analysis.

Nonsmooth functions and subdifferentiation

A detailed exposition of these notions can be found in [START_REF] Rockafellar | Variational analysis[END_REF]. In what follows, g denotes a proper lower semi-continuous function from R n to (-∞, +∞] whose domain is denoted and defined by dom g = x ∈ R n : g(x) < +∞ . Recall that g is called proper if dom g = ∅.

Definition 1 (Subdifferentials) Let g be a proper lower semicontinuous function from R n to (-∞, +∞].

1. Let x ∈ dom g, the Fréchet subdifferential of g at x is the subset of vectors v in R n that satisfy lim inf y→x, y =x g(y)g(x)v, yx ||x -y|| ≥ 0.

When x ∈ dom g, the Fréchet subdifferential is empty by definition. The Fréchet subdifferential of g at x is denoted by ∂g(x).

2. The limiting subdifferential, or simply the subdifferential of g at x, is defined by the following closure process:

∂g(x) = {v ∈ R n : ∃x j → x, g(x j ) → g(x), u k ∈ ∂g(x j ), u j → v as j → ∞}.
3. Assume g is finite valued and locally Lipschitz continuous. The function g is said to be subdifferentially regular, if ∂g(x) = ∂g(x) for all x in R n .

Being given a closed subset C of R n its indicator function i C : R n → (-∞, +∞] is defined as

follows i C (x) = 0 if x ∈ C, i C (x) = +∞ otherwise.
C is said to be regular if ∂i C (x) = ∂i C (x) on C. In this case, the normal cone to C is defined by the identity

N C (x) = ∂i C (x), ∀x ∈ R n .
The distance function to C is defined as dist (x, C) = min xy : y ∈ C .

We recall the two following fundamental results. (i) When x is a local minimizer of g, then 0 ∈ ∂g(x). Conversely a point x is a critical point of g, if 0 ∈ ∂g(x).

(ii) If x is a solution to P , under assumption S , then:

∂f (x) + N D (x) ∋ 0.
(iii) Assume further that D is of the form

D = {x ∈ Q : f 1 (x) ≤ 0, . . . , f m (x) ≤ 0},
where Q is closed, convex and nonempty and f 1 , . . . , f m : R n → R are C 1 functions. For x in D, set I(x) = {i : f i (x) = 0} and assume that there exists y ∈ Q such that,

(Robinson QC) ∇f i (x), y -x < 0, ∀i ∈ I(x).
Then D is regular,

N D (x) =    i∈I(x) λ i ∇f i (x) : λ i ≥ 0, i ∈ I(x)    + N Q (x),
and critical points for P are exactly KKT points of P .

Proof. (i) is [START_REF] Rockafellar | Variational analysis[END_REF]Theorem 10.1]). (ii) is obtained by using the sum rule [38, Corollary 10.9]. For (iii), regularity and normal cone expression follow from [38, Theorem 6.14] (Robinson condition appears there in a generalized form).

Recall that a convex cone L ⊂ R n + is a nonempty convex set such that R + L ⊂ L. Being given a subset S of R n , the conic hull of S, denoted cone S is defined as the smallest convex cone containing S. Since a cone always contains 0, cone ∅ = {0}. Proposition 4.2 (Subdifferential of set-parameterized indicator functions) Let n 1 , n 2 , m be positive integers and g 1 , . . . , g m : R n 1 × R n 2 → R continuously differentiable functions. Set

C(x) = {y ∈ R n 2 : g i (x, y) ≤ 0, ∀x ∈ R n 1 , ∀i = 1, . . . , m} ⊂ R n 2
and for any y ∈ C(x) put I(x, y) = {i = 1, . . . , m : g i (x, y) = 0}, the set I(x, y) is empty otherwise. Assume that the following parametric Mangasarian-Fromovitz qualification condition holds:

∀(x, y) ∈ R n 1 × R n 2 , ∃d, ∇g i (x), d < 0, ∀i ∈ I(x, y).
Consider the real extended-valued function

H : R n 1 × R n 2 → (-∞, +∞] defined through H(x, y) =      i C(x) (y) whenever C(x) is nonempty + ∞ otherwise.
Then the subdifferential of H is given by

(25) ∂H(x, y) = cone ∇g i (x, y) : i ∈ I(x, y) . Proof. For (x, y) in dom H, set G(x, y) = (g 1 (x, y), . . . , g m (x, y)). Then H(x, y) = i R n -(G(x, y)).
Observe that G(x, y) ≤ 0 and set I = I(x, y). Denoting by G ′ (x, y) * the adjoint of the Jacobian of G at (x, y). The abstract qualification constraint required in [START_REF] Rockafellar | Variational analysis[END_REF]Theorem 10.6] is equivalent to λ i ≥ 0, i∈I λ i ∇g i (x, y) = 0 ⇒ λ i = 0. Using Hahn-Banach separation theorem this appears to be equivalent to the parametric MFQC condition. We thus obtain

∂H(x, y) = G ′ (x, y) * ] N R m -(G(x, y)) = i∈I λ i ∇g i (x, y) : λ i ≥ 0 .

Multivalued mappings

A multivalued mapping

F : R n ⇒ R m maps a point x in R n to a subset F (x) of R m . The set dom F := x ∈ R n : F (x) = ∅
is called the domain of F . For instance the subdifferential of a lsc function defines a multivalued mapping ∂f : R n ⇒ R n . Several regularity properties for such mappings are useful in optimization; we focus here on one of the most natural concept: set-valued continuity (see e.g. [20, Section 3.B, p. 142]).

Definition 2 (Continuity of point-to-set mappings) Let F : R n ⇒ R m and x in dom F . (i) F is called outer semi-continuous at x, if for each sequence x j → x and each sequence y j → y with y j ∈ F (x j ), we have y ∈ F (x). (ii) F is called inner semi-continuous at x, if for all x j → x and y ∈ F (x) there exists a sequence y j ∈ F (x j ), after a given term, such that y j → y. (iii) F is called continuous at x if it is both outer and inner semi-continuous.

4.1.3

The KL property and some facts from real semi-algebraic geometry KL is a shorthand here for Kurdyka-Lojasiewicz. This property constitutes a crucial tool in our convergence analysis. We consider the nonsmooth version of this property which is given in [START_REF] Bolte | Clarke subgradients of stratifiable functions[END_REF]Theorem 11] -precisions regarding concavity of the desingularizing function are given in [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Lojasiewicz inequality[END_REF]Theorem 14].

Being given real numbers a and b, we set [a (i) The function g is said to have the Kurdyka-Lojaziewicz (KL) property at x ∈ dom ∂g if there exists α ∈ (0, +∞], a neighborhood V of x and a function ϕ ∈ Φ α such that

≤ g ≤ b] = {x ∈ R n : a ≤ g(x) ≤ b}.
(26) ϕ ′ (g(x) -g(x)) dist (0, ∂g(x)) ≥ 1 for all x ∈ V ∩ [g(x) < g(x) < α].
(ii) The function g is said to be a KL function if it has the KL property at each point of dom ∂g.

KL property basically asserts that a function can be made sharp by a reparameterization of its values. This appears clearly when g is differentiable since [START_REF] Gill | SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization[END_REF] writes:

∇ ϕ • f (x) ≥ 1, ∀x ∈ V ∩ [g(x) < g(x) < α].
The function ϕ used in this parameterization is a called a desingularizing function. As we shall see such functions are ubiquitous in practice, see [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Lojasiewicz inequality[END_REF][START_REF] Attouch | Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods[END_REF]. When ϕ is of the form ϕ(s) = cs 1-θ with c > 0 and θ ∈ [0, 1), the number θ is called a Lojasiewicz exponent. Definition 4 (Semi-algebraic sets and functions) (i) A set A ⊂ R n is said to be semi-algebraic if there exists a finite number of real polynomial functions g ij , h ij : R n → R such that

A = p i=1 q j=1 {y ∈ R n : g ij (y) = 0, h ij (y) > 0} (ii) A mapping G : R n ⇒ R m is a said to be semi-algebraic if its graph graph G = (x, y) ∈ R n+m : y ∈ G(x) is a semi-algebraic subset of R n+m .
Similarly a real extended-valued function g : R n → (-∞, +∞] is semi-algebraic if its graph (x, y) ∈ R n+1 : y = g(x) is semi-algebraic.

Lemma 4.9 (Semi-algebraicity of the value function) If f , h, D are semi-algebraic then F is semi-algebraic.

Let D ′ denote the domain where F is differentiable. By standard stratification results, this set contains a dense finite union of open sets (a family of strata of maximal dimension, see e.g. [START_REF] Van Den Dries | Geometric categories and o-minimal structures[END_REF]) and thus one has: [START_REF]Optimization with First-Order Surrogate Functions[END_REF] int D ′ is dense in D.

We now have the following estimates As a consequence

(33) dist (0, ∂F (x)) ≤ K||p(x) -x||, ∀x ∈ D ∩ C.
Proof. Fix x in int D ′ ∩ C and let δ and µ be in R n . Then ĥ(x + δ, p(x)

+ µ)) = h(x + δ, p(x) + µ) + i D(x+δ) (p(x) + µ) ≥ h(x + δ, p(x + δ)) = h(x, p(x)) + ∇F (x), δ + o(||δ||) = ĥ(x, p(x)) + ∇F (x), δ + o(||δ||).
This implies that (∇F (x), 0) ∈ ∂ ĥ(x, p(x)). Since C is bounded, the qualification assumption of Section 3.2 yields [START_REF] Maratos | Exact penalty function algorithms for finite dimensional and control optimization problems[END_REF].

To obtain [START_REF] Nesterov | Introductory lectures on convex optimization: A basic course[END_REF] it suffices to use the definition of the subdifferential, the continuity of p and the fact that int D ′ is dense in D.

We have the following property for the sequence generated by the method Proposition 4.11 (Hidden gradient steps) Let {x k } k=1,2,... be the sequence defined through x k+1 = p(x k ) with x 0 ∈ D. Then x k lies in D and

F (x k ) + µ 2 ||x k -x k+1 || 2 ≤ f (x k ) ≤ F (x k-1 ), ∀k ≥ 1. (34)
Moreover, for all compact subset C of R n , there exists [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF]. We only need to prove the second item (34) since the third one immediately follows from [START_REF] Nesterov | Introductory lectures on convex optimization: A basic course[END_REF]. Using inequality [START_REF] Gill | Sequential Quadratic Programming Methods[END_REF] and the fact that h(x, y) ≥ f (y) for all y in D(x), we have

K 2 (C) > such that dist (0, ∂F (x k )) ≤ K 2 (C)||x k+1 -x k ||, whenever x k ∈ C. Proof. The sequence x k lies in D since p(x k ) ∈ D(x k ) ⊂ D by
F (x) = h(x, p(x)) ≥ f (p(x)) = h(p(x), p(x)) ≥ F (p(x)) + µ 2 ||p(x) -p(p(x))|| 2 , therefore F (x k-1 ) ≥ f (x k ) ≥ F (x k ) + µ 2 ||x k -x k+1 || 2
which proves (34).

An abstract convergence result

The following abstract result is similar in spirit to [START_REF] Attouch | Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods[END_REF] and to recent variations [START_REF] Bolte | Proximal alternating linearized minimization for nonconvex and nonsmooth problems[END_REF]. However, contrary to previous works it deals with conditions on a triplet {x k-1 , x k , x k+1 } and the subgradient estimate is of explicit type (like in [START_REF] Absil | Convergence of the iterates of descent methods for analytic cost functions[END_REF] and even more closely [START_REF] Noll | Convergence of Non-smooth Descent Methods Using the Kurdyka-Lojasiewicz Inequality[END_REF]).

Proposition 4.12 (Gradient sequences converge) Let F : R n → (-∞, +∞] be proper, lower semi-continuous, semi-algebraic function. Suppose that there exists a sequence {x k } k∈N such that,

(a) ∃K 1 > 0 such that F (x k ) + K 1 ||x k+1 -x k || 2 ≤ F (x k-1 ) (b) For all compact subset C of R n , there exists K 2 (C) > such that dist (0, ∂F (x k )) ≤ K 2 (C)||x k+1 -x k ||, whenever x k ∈ C. (c) If x k has a cluster point x, ie there exists x k j → x, then F (x k j ) → F (x).
Then, (I) The following asymptotic alternative holds

(i) Either the sequence {x k } k∈N satisfies x k → +∞ (ii) or it converges to a critical point of F .
As a consequence each bounded sequence is a converging sequence.

(II) When x k converges, we denote by x ∞ its limit and we take θ ∈ [0, 1) a Lojasiewicz exponent of F at x ∞ . Then, (i) If θ = 0, the sequence (x k ) k∈N converges in a finite number of steps, (ii) If θ ∈ (0, 1 2 ] then there exist c > 0 and q ∈ [0, 1) such that

x k -x ∞ ≤ c q k , ∀k ≥ 1.
(iii) If θ ∈ ( 1 2 , 1) then there exists c > 0 such that

x k -x ∞ ≤ c k -1-θ 2θ-1 , ∀k ≥ 1.
Proof. We first deal with (I). Suppose that there exists k 0 ≥ 0 such that x k 0 +1 = x k 0 . This implies by (a) that x k 0 +l = x k 0 for all l > 0. Thus the sequence converges and the second inequality (b) implies that we have a critical point of F . We now suppose that ||x k+1x k || > 0 for all k ≥ 0. Definition of a KL neighborhood. Suppose that (I)(i) does not hold. There exists therefore a cluster point x of x k . Combining (a) and (c) we obtain that

(35) lim k→+∞ F (x k ) = F (x).
With no loss of generality we assume that F (x) = 0. Since F is semi-algebraic, it is a KL function (Theorem 4.3). There exist δ > 0, α > 0 and ϕ ∈ ϕ α such that

ϕ ′ (F (x)) dist (0, ∂F (x)) ≥ 1,
for all x such that xx ≤ δ and x ∈ [0 < F < α]. In view of assumption (b), set

K 2 = K 2 B(x, δ) .
Estimates within the neighborhood. Let r ≥ s > 1 be some integers and assume that the points x s-1 , x s . . . , x r-1 belong to B(x, δ) with F (x s-1 ) < α. Take k ∈ {s, . . . , r}, using (a), we have

F (x k ) ≤ F (x k-1 ) -K 1 ||x k+1 -x k || 2 = F (x k-1 ) -K 1 ||x k+1 -x k || 2 ||x k -x k-1 || ||x k -x k-1 || ≤ F (x k-1 ) - K 1 K 2 ||x k+1 -x k || 2 ||x k -x k-1 || dist (0, ∂F (x k-1 )).
From the monotonicity and concavity of ϕ, we derive

ϕ • F (x k ) ≤ ϕ • F (x k-1 ) -ϕ ′ • F (x k-1 ) K 1 K 2 ||x k+1 -x k || 2 ||x k -x k-1 || dist (0, ∂F (x k-1 )),
thus by using KL property, for k ∈ {s, . . . , r},

• F (x k ) ≤ ϕ • F (x k-1 ) - K 1 K 2 ||x k+1 -x k || 2 ||x k -x k-1 || . (36) ϕ
We now use the following simple fact: for a > 0 and b ∈ R,

2(a -b) - a 2 -b 2 a = a 2 -2ab + b 2 a = (a -b) 2 a ≥ 0, thus for a > 0 and b ∈ R (37) 2(a
-b) ≥ a 2 -b 2 a .
We have therefore, for k in {s, . . . , r},

||x k -x k-1 || = ||x k -x k-1 || 2 ||x k -x k-1 || = ||x k+1 -x k || 2 ||x k -x k-1 || + ||x k -x k-1 || 2 -||x k+1 -x k || 2 ||x k -x k-1 || (37)
≤ ||x k+1 -x k || 2 ||x k -x k-1 || + 2(||x k -x k-1 || -||x k+1 -x k ||) (36)
≤ K 2 K 1 (ϕ • F (x k-1 ) -ϕ • F (x k )) + 2(||x k -x k-1 || -||x k+1 -x k ||).
Hence by summation (38)

r k=s ||x k -x k-1 || ≤ K 2 K 1 ϕ • F (x s-1 ) -ϕ • F (x r ) + 2 (||x s -x s-1 || -||x r+1 -x r ||) .
The sequence remains in the neighborhood and converges. Assume that for N sufficiently large one has

x N -x ≤ δ 4 , (39)
K 2 K 1 ϕ • F (x N ) ≤ δ 4 , (40)
K -1 1 F (x N -1 ) < min δ 4 , K -1 1 α . (41)
One can require [START_REF] Solodov | Global convergence of an SQP method without boundedness assumptions on any of the iterative sequences[END_REF] and ( 41) because ϕ is continuous and F (x k ) ↓ 0. By (a), one has [START_REF] Wilson | Simplicial Method for Convex Programming[END_REF] x

N +1 -x N ≤ K -1 1 F (x N -1 ) < δ 4 .
Let us prove that x r ∈ B(x, δ) for r ≥ N + 1. We proceed by induction on r. By (39),

x N ∈ B(x, δ) thus the induction assumption is valid for r = N + 1. Since by [START_REF] Svanberg | A Class of Globally Convergent Optimization Methods Based on Conservative Convex Separable Approximations[END_REF] one has F (x N ) < α, estimation (38) can be applied with s = N + 1. Suppose that r ≥ N + 1 and x N , . . . , x r-1 ∈ B(x, δ), then we have the following

x r -x ≤ x r -x N + x N -x (39) ≤ r k=N +1 x k -x k-1 + δ 4 (38) ≤ K 2 K 1 ϕ • F (x N ) + 2||x N +1 -x N || + δ 4 (40), (42)
< δ.

Hence x N , . . . , x r ∈ B(x, δ) and the induction proof is complete. Therefore, x r ∈ B(x, δ) for any r ≥ N . Using (38) again, we obtain that the series x k+1x k converges, hence x k also converges by Cauchy criterion.

The second part (II) is proved as in [2, Theorem 2]. First, because of the semi-algebraicity of the data, ϕ can be chosen of the form ϕ(s) = c.s 1-θ with c > 0 and θ ∈ [0, 1). In this case, [START_REF] Rockafellar | Variational analysis[END_REF] combined with KL property and (b) yields a similar result as formula [START_REF] Bolte | Proximal alternating linearized minimization for nonconvex and nonsmooth problems[END_REF] in [START_REF] Attouch | On the convergence of the proximal algorithm for nonsmooth functions involving analytic features[END_REF], which therefore leads to the same estimates.

Remark 7 (1) (Coercivity implies convergence) Quite often in practice F has bounded level sets. In that case the alternative reduces to convergence because of assumption (a).

(2) (Assumption (c)) Assumption (c) is very often satisfied in practice: for instance when F has a closed domain and is continuous on its domain or when F is locally convex up to a square (locally semi-convex).

At last, Propositions 4.11 and 4.12 can be combined to prove Theorem 3.1.

Beyond semi-algebraicity: MMP and NLP with real analytic data

Many concrete and essential problems involve objectives and constraints defined through real analytic functions -which are not in general semi-algebraic functions-and this raises the question of the actual scope of the results described previously. We would thus like to address here the following question: Can we deal with nonlinear programming problems involving real analytic data? A convenient framework to capture most of what is needed to handle real analytic problems, and of an even larger class of problems, is the use of o-minimal structures. These are classes of sets and functions whose stability properties and topological behavior are the same as those encountered in the semi-algebraic world.

We give below some elements necessary to understand what is at stake and how our results enter this larger framework.

Definition 5 (O-minimal structures, see [START_REF] Van Den Dries | Geometric categories and o-minimal structures[END_REF]) An o-minimal structure on (R, +, .) is a sequence of families O = (O p ) p∈N with O p ⊂ P(R p ) (the collection of subsets of R p ), such that for each p ∈ N:

(i) Each O p contains R p and is stable by finite union, finite intersection and complementation;

(ii) if A belongs to O p , then A × R and R × A belong to O p+1 ;

(iii) if Π : R p+1 → R p is the canonical projection onto R p then for any A in O p+1 , the set Π(A) belongs to O p ;

(iv) O p contains the family of real algebraic subsets of R p , that is, every set of the form

{x ∈ R p : g(x) = 0},
where g : R p → R is a real polynomial function ;

(v) the elements of O 1 are exactly the finite unions of intervals.

Examples of such structures are given in [START_REF] Van Den Dries | Geometric categories and o-minimal structures[END_REF]. We focus here on the class of globally subanalytic sets which allows us to deal with real analytic NLP in a simple manner. Thanks to Gabrielov's theorem of the complement, the class of globally subanalytic subsets can be seen as the smallest o-minimal structure containing semi-algebraic sets and the graphs of all real analytic functions of the form: f : [-1, 1] n → R, see e.g. [START_REF] Van Den Dries | Geometric categories and o-minimal structures[END_REF]. As a consequence any real analytic function defined on an open neighborhood of a box is globally subanalytic.

Note that a real analytic function might not be globally subanalytic (take sin whose graph intersects the x-axis infinitely many times, and thus (iv) is not fulfilled for (graph sin) ∩ (Ox), however it follows from the definition that the restriction of a real analytic function to a compact set included in its (open) domain is globally subanalytic.

We come now to the results we need for our purpose. For any o-minimal structure, one can assert that:

(a) The KL property holds -i.e. one can replace the term "semi-algebraic" by "definable" in Theorem 4.3, see [START_REF] Bolte | Clarke subgradients of stratifiable functions[END_REF].

(b) The stratification properties [START_REF]Optimization with First-Order Surrogate Functions[END_REF] used to derive the abstract qualification condition hold, see [START_REF] Van Den Dries | Geometric categories and o-minimal structures[END_REF].

As a consequence, and at the exception of convergence rates, all the results announced in the paper are actually valid for an arbitrary o-minimal structure instead of the specific choice of the class of semi-algebraic sets.

To deal with the case of real analytic problems, we combine the use of compactness and of the properties of globally subanalytic sets. This leads to the following results. -Lipschitz continuity assumptions (10), 8 subanalytic is actually enough, see [START_REF] Van Den Dries | Geometric categories and o-minimal structures[END_REF] -steplength condition [START_REF] Bolte | Proximal alternating linearized minimization for nonconvex and nonsmooth problems[END_REF], -qualification assumptions [START_REF] Bonnans | Numerical Optimization: Theoretical and Practical Aspects[END_REF], -boundedness assumptions (13), [START_REF] Byrd | On the Convergence of Successive Linear-Quadratic Programming Algorithms[END_REF], Then, (i) the sequence {x k } k∈N generated by (ESQM) (resp. Sℓ 1 QP) converges to a feasible point

x ∞ satisfying the KKT conditions for the nonlinear programming problem P NLP .

(ii) Either convergence occurs in a finite number of steps or the rate is of the form: (ii) Either convergence occurs in a finite number of steps or the rate is of the form:

(a) x k -x ∞ = O(q k ), with q ∈ (0, 1), (b) x k -x ∞ = O 1 k γ , with γ > 0.
(a) x kx ∞ = O(q k ), with q ∈ (0, 1),

(b) x k -x ∞ = O 1 k γ , with γ > 0.
Proof. The "proofs" of both theorems are the same. We observe first that in both cases the sequences are bounded. Let thus a > 0 be such that x k ∈ [-a, a] n for all nonnegative k. Now the initial problem can be artificially transformed to a definable problem by including the constraints x i ≤ a and -x i ≤ a without inducing any change for the sequences. This imposes restrictions to real analytic function making them globally subanalytic hence definable. The fact that the rate of convergence are of the same nature is well known and comes from the fact that Puiseux Lemma holds for subanalytic functions (see [START_REF] Van Den Dries | Geometric categories and o-minimal structures[END_REF]).

6 Appendix: convergence proofs for SQP methods

Convergence of the moving balls method

The local model of f is given at a feasible x by

h MB (x, y) = f (x) + ∇f (x), y -x + L 2 ||y -x|| 2 , x, y ∈ R n ,
while the constraint approximation is given by

D(x) = y ∈ R n : f i (x) + ∇f i (x), y -x + L i 2 ||y -x|| 2 ≤ 0 .
The fact that for all x in F , D(x) ⊂ F is ensured by Lemma 4.4. As an intersection of a finite number of balls containing x the set D(x) is a nonempty compact (hence closed) convex set. The proof of the continuity of D is as in [6,

g i (y) = f (x) + ∇f i (x), y -x + L i 2 y -x 2 , y ∈ R n , i = 1, . . . , m.
Suppose that (x, y) is such that g i (y) ≤ 0, i = 1 . . . m. Then the only solution u = (u 1 , . . . , u m ) to m i=1 u i ∇g i (y) = 0, u i ≥ 0 and u i g i (y) = 0 for 1 ≤ i ≤ m is the trivial solution u = 0.

Proof. When J = {i = 1, . . . , m : g i (y) = 0} is empty, the result is trivial. Suppose that J is not empty and argue by contradiction. This means that 0 is in the convex envelope of ∇g j (y), j ∈ J and thus one cannot have Mangasarian-Fromovitz condition for P(x) at y (recall that P(x) involves constraints of the form g i ≤ 0). This contradicts the fact that Slater condition holds for P(x), since Slater condition classically implies Mangasarian-Fromovitz condition at each point. Proof. Observe that, at this stage, we know that p is continuous. We argue by contradiction and assume that the supremum is not finite. One can thus assume, by compactness, that there exists a point x in F together with a sequence z j → x such that at least one of the λ j (z j ) tends to infinity. Writing down the optimality conditions one derives Lagrange relations

1 m i=1 λ i (x) (∇f (z j ) + L(p(z j ) -z j )) + m i=1 λ i (z j ) m i=1 λ i (z j ) (∇f i (z j ) + L i (p(z j ) -z j )) = 0
and complementary slackness

λ j (z j ) f i (z j ) + ∇f i (z j ), p(z j ) -z j ) + L i 2 p(z j ) -z j 2 = 0.
Up to an extraction one can assume that the sequence of p-uplet

λ i (z j ) m i=1 λ i (z j ) i=1,...,m j
converges to u = (u 1 , . . . , u m ) in the unit simplex and that, for all i, the limit of λ i (z j ) exists and is either finite or infinite. Passing to the limit, one obtains that

m i=1 u i ∇g i (p(x)) = 0, g i (p(x)) ≤ 0 and u i g i (p(x)) = 0 for 1 ≤ i ≤ m, (44)
where g 1 , . . . , g m are as defined in Lemma 6.2. But Lemma 6.2 asserts that the unique solution to such a set of equations is u = 0 which contradicts the fact that u is a point of the unit simplex.

Recall that for all x, y ∈ R n , we set ĥMB (x, y) = h MB (x, y) + i D(x) (y). Fix x ∈ F and y in D(x) set

I(x, y) = i ∈ {1, . . . , m} : f i (x) + ∇f i (x), y -x + L i 2 ||y -x|| 2 = 0 .
Combining Proposition 4.2 with Corollary 6.2, one has that the subdifferential of ĥMB is given by

∂ ĥMB (x, y) (45)
= L(x -y) -∇ 2 f (x)(x -y) ∇f (x) + L(y -x) + cone L i (x -y) -∇ 2 f i (x)(x -y) ∇f i (x) + L i (y -x) , i ∈ I(x, y) .
The only assumption of Section 3.2 that needs to remain established is the qualification assumption [START_REF] Van Den Dries | Geometric categories and o-minimal structures[END_REF]. The desired bound on v follows from the bound on the the Lagrange multipliers in (46) obtained in Corollary 6.3

The assumptions for applying Theorem 3.1 are now gathered and Theorem 5.2 follows. The fact that we eventually obtain a KKT point is a consequence of the qualification condition and Proposition 4.1.

6.2 Convergence of Extended SQP and Sℓ 1 QP 6.2.1 Sketch of proof of Theorem 2.2

The proof arguments are adapted from [5, Theorem 3.1, Proposition 3.2]. Set l = inf Q f and recall that l > -∞ by [START_REF] Byrd | On the Convergence of Successive Linear-Quadratic Programming Algorithms[END_REF]. Use first regularity assumptions [START_REF] Bolte | The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems[END_REF], [START_REF] Bolte | Proximal alternating linearized minimization for nonconvex and nonsmooth problems[END_REF]

f i (x k+1 ) ≤ 1 β k (h β k (x k+1 , x k ) -l) ≤ 1 β k (h β k (x k , x k ) -l - λ + β k λ ′ 2 ||x k+1 -x k || 2 ) ≤ 1 β k (f (x k ) -l) + max i=0,...,m f i (x k ) - λ ′ 2 ||x k+1 -x k || 2 ,
where the first inequality follows from the monotonicity of β k and the fact that f (x k+1 )l ≥ 0, the second inequality is due to the descent lemma while the third one is a consequence of the strong convexity of the local model. The above implies that 1 β k+1 (f (x k+1 )l) + max i=0,...,m f i (x k+1 ) ≤ 1 β 0 (f (x 0 )l) + max i=0,...,m f i (x 0 ), thus max i=0,...,m f i (x k+1 ) is bounded for all k and the compactness assumption (13) ensures the boundedness of x k . Since 1 β k (f (x k )l) + max i=0,...,m f i (x k ) ≥ 0, a standard telescopic sum argument gives that ||x k+1x k || → 0. Set J k = {i = 0, . . . , m : test i (x k , x k+1 ) = max j=0...m test j (x k , x k+1 )}, and suppose that β k → ∞. This means that, up to a sub-sequence, there exists a nonempty set I ⊂ {1, . . . , m} such that

J k = I (47) ∀t ∈ N, ∀i ∈ I, f i (x k ) + ∇f i (x k ), x k+1 -x k > 0.
Recall that the optimality condition for the local model minimization ensures that, for all k, there exists dual variables u i ≥ 0, i ∈ J k such that i∈J k u i = 1 and

1 β k ∇f (x k ) + (λ + λ ′ β k )(x k+1 -x k ) + i∈J k u i ∇f i (x k ), z -x k+1 ≥ 0, (48)
for any z ∈ Q. Using the boundedness properties of x k and u i , up to another sub-sequence, we can pass to the limit in equations ( 47), (48) to find x ∈ Q, ūi , i ∈ I such that ūi ≥ 0 i∈I ūi = 1 f i (x) ≥ 0, i ∈ I i∈I ūi ∇f i (x), zx ≥ 0, z ∈ Q, which contradicts qualification assumption (12) (lim x k+1x k = 0). Therefore, for k sufficiently large, we have

β k = β > 0, f i (x k ) + ∇f i (x k ), x k+1 -x k ≤ 0, 0 ∈ J k .
Given that x k+1x k → 0, any accumulation point is feasible. Furthermore, given an accumulation point x, set Ī = {0 ≤ i ≤ m, f i (x) = 0}. It must holds that (up to a sub-sequence) J k = Ī for a sufficiently large k. The fact that x is a stationary point follows by passing to the limit in (48).

Proof of convergence of ESQM

As granted by Theorem 2.2, there exists k 0 such that β k = β for all integer k ≥ k 0 . Since our interest goes to the convergence of the sequence, we may assume with no loss of generality that β k is equal to β. Therefore we only need to consider the behavior of the sequence {x k } with respect to the function The assumptions [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF] for D are obviously fulfilled; as for [START_REF] Dontchev | Implicit functions and solution mappings[END_REF] it follows essentially from the descent lemma, which is itself applicable thanks to assumptions [START_REF] Bolte | The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems[END_REF], [START_REF] Bolte | Proximal alternating linearized minimization for nonconvex and nonsmooth problems[END_REF] (see also previous subsection). Assumption S is also fulfilled (Q is convex, hence regular and so is Ψ β ).

Once more the only point that needs to be checked more carefully is the qualification assumption [START_REF] Van Den Dries | Geometric categories and o-minimal structures[END_REF]. For all x, y ∈ Q, let I(x, y) be the active indices in the definition of h ESQM (x, y). The subdifferential of ĥESQM is given by ∂ ĥESQM (x, y) = µ(xy) -∇ 2 f (x)(xy) ∇f (x) + µ(yx) + co -∇ 2 f i (x)(xy) ∇f i (x) : i ∈ I(x, y) + 0 N Q (y) ,

where co denotes the convex hull. The result follows from the fact that the f i is C 2 and that the hessian are bounded on bounded sets. Theorem 3.1 applies and gives the desired conclusion. The fact that we eventually obtain a KKT point of P is a consequence of Theorem 2.2.

Convergence of Sℓ 1 QP

The proof is quasi-identical to that of ESQP, it is left to the reader.

Theorem 2 . 2 (

 22 [START_REF] Auslender | An Extended Sequential Quadratically Constrained Quadratic Programming Algorithm for Nonlinear, Semidefinite, and Second-Order Cone Programming[END_REF]) Assume that the following properties hold -Lipschitz continuity conditions (10), -steplength conditions (11), -qualification assumption (12),

Theorem 2 . 3 (

 23 Convergence of ESQM) Assume that the following conditions hold -The functions f, f 1 , . . . , f m and the set Q are real semi-algebraic. -Lipschitz continuity condition (10), -steplength condition (11), -qualification assumption (12), -boundedness assumptions (13), (14), Then, (i) The sequence {x k } k∈N generated by (ESQM) converges to a feasible point x ∞ satisfying the KKT conditions for the nonlinear programming problem P NLP .

Theorem 2 . 4

 24 Assume that the following properties hold -Lipschitz continuity conditions (10), -steplength conditions (17), -qualification assumption (12),

Theorem 2 . 5 (

 25 Convergence of Sℓ 1 QP) Assume that the following conditions hold -The functions f, f 1 , . . . , f m and the set Q are semi-algebraic, -Lipschitz continuity condition (10), -steplength condition (17), -qualification assumption (12),

3. 1

 1 Sequential model minimizationWe consider a general problem of the form (18)P min f (x) : x ∈ Dwhere f : R n → R is a continuous function and D is a nonempty closed set.

( 21 )

 21 x ∈ D ∩ C, y ∈ D(x) ∩ C and (v, 0) ∈ ∂ ĥ(x, y) =⇒ ||v|| ≤ K(C)||x -y|| The iteration mapping and the value function For any fixed x in D, we define the iteration mapping as the solution of the sub-problem (22) P(x) min h(x, y) : y ∈ D(x) that is (23) p(x) := arg min h(x, y) : y ∈ D(x) .

  ) = value of P(x) = h(x, p(x)), and val (x) = +∞ otherwise Remark 5 (a) The restriction "x belongs to D" is due to the fact that our process is based on upper approximations and thus it is a feasible model (i.e. generating sequences in D). Note however that this does not mean that non feasible methods cannot be studied with this process (see ESQP and Sℓ 1 QP in the previous section) . (b) Recalling Example 1, assuming further that D(x) = D for all x, and denoting by P D the projection onto D, the above writes

Theorem 3 . 1 (

 31 Convergence of MMP for semi-algebraic problems) Assume that the local model pair h, D(•) satisfies: -the inner convex constraints assumptions (19), -the upper local model assumptions (20), -the qualification assumptions (21) -the tameness assumptions: f, h and D are real semi-algebraic. Let x 0 ∈ D be a feasible starting point and consider the sequence {x k } k=1,2,... defined by x k+1 = p(x k ). Then, (I) The following asymptotic alternative holds (i) either the sequence {x k } k=1,2,... diverges, i.e. x k → +∞, (ii) or it converges to a single point x ∞ such that ∂f (x ∞ ) + N D (x ∞ ) ∋ 0.

Proposition 4 . 1 (

 41 Fermat's rule, critical points, KKT points) We have the following extensions of the classical Fermat's rule:

  The sets [a < g < b], [g < a]... are defined similarly.For α ∈ (0, +∞], we denote by Φ α the class of functions ϕ : [0, α) → R that satisfy the following conditions (a) ϕ(0) = 0;(b) ϕ is positive, concave and continuous;(c) ϕ is continuously differentiable on (0, α), with ϕ ′ > 0.Definition 3 (KL property) Let g be a proper lower semi-continuous function from R n to (-∞, +∞].

Lemma 4 . 10 (

 410 Subgradient bounds) Let C ⊂ D be a bounded set. Then there exists K ≥ 0 such that ∀x ∈ D ′ ∩ C (32) ||∇F (x)|| ≤ K||p(x) -x||.

Theorem 5 . 1 (

 51 Convergence of ESQM/Sℓ 1 QP for analytic functions) Assume that the following properties hold -The functions f, f 1 , . . . , f m are real analytic and Q is globally subanalytic ( 8 )

Theorem 5 . 2 (

 52 Convergence of the moving balls method) Recall that Q = R n and assume that the following properties hold -The functions f, f 1 , . . . , f m are real analytic, -Lipschitz continuity assumptions (6), -Mangasarian-Fromovitz qualification condition (8), -boundedness condition (7), -feasibility of the starting point x 0 ∈ F .Then, (i) The sequence {x k } k∈N defined by the moving balls method converges to a feasible point x ∞ satisfying the KKT conditions for the nonlinear programming problem P NLP .

Corollary 6 . 3 (

 63 Lagrange multipliers of the subproblems are bounded) For each x in F , we denote by Λ(x) ⊂ R m + the set of Lagrange multipliers associated to P(x). Then for any compact subset B of F ,[START_REF] Wright | Constraint identification and algorithm stabilization for degenerate nonlinear programs[END_REF] sup max i=1,...,m λ i (x) : (λ 1 (x), . . . , λ m (x)) ∈ Λ(x), x ∈ B < +∞.

Lemma 6 . 4

 64 The qualification assumption[START_REF] Van Den Dries | Geometric categories and o-minimal structures[END_REF] holds for h MB . Proof. (v, 0) ∈ ∂ ĥMB (x, y) implies that y = arg min z {h MB (x, z) : z ∈ D(x)}in other words that y = p(x). In view of (45) one has the existence of non-negative λ i (x), i = 1, . . . , m such thatL.I n -∇ 2 f (x) + p i=1 λ i (x) L i I n -∇ 2 f i (x) (xp(x)) = v ∇f (x) + L(yx) + p i=1 λ i (x) (∇f i (x) + L i (p(x)x)) = 0 (46)

Ψ

  β (x) = f (x) + β max i=0,...,m(f i (x)) + i Q (x),whose minimization defines problem P . Set µ = λ + βλ ′ , the local model we shall use to study (ESQM) is given byh ESQM (x, y) = f (x) + ∇f (x), yx + β max i=0,...,m (f i (x) + ∇f i (x), yx ) + µ||y -x|| 2while the constraints inner approximations reduce to a constant multivalued mapping D(x) = Q.

  Proposition A1 & A2].Let us also recall that Mangasarian-Fromovitz condition implies that

Lemma 6.1 (Slater condition for P(x)) [6, Proposition 2.1] The set D(x) satisfies the Slater condition for each x in F . Corollary 6.2 For a given feasible x, set

A term we borrow from Cox-Judistskii-Nemirovskii recent developments[START_REF] Cox | Dual subgradient algorithms for large-scale nonsmooth learning problems[END_REF]

Under second-order assumptions and assuming that no Maratos effect[START_REF] Maratos | Exact penalty function algorithms for finite dimensional and control optimization problems[END_REF] troubles the process

Sequential quadratically constrained quadratic programming.

We focus here on SQP methods but alternative methods for treating complex constraints are available, see e.g.[START_REF] Cox | Dual subgradient algorithms for large-scale nonsmooth learning problems[END_REF] and references therein.

Hence the wording of majorization-minimization method

iD denotes the indicator function as defined in Section 4.1.1

Computing the projection in that case requires to compute eigenvalues which may be very hard for large size problems

Effort sponsored by the Air Force Office of Scientific Research, Air Force Material Command, USAF, under grant number FA9550-14-1-0056. This research also benefited from the support of the "FMJH Program Gaspard Monge in optimization and operations research". The author is supported by an award of the Simone and Cino del Duca foundation of Institut de France.

For this class of functions, we have the following result which provides an important field of applications for our method. This is discussed in the last section. Theorem 4.3 ([9,[START_REF] Bolte | The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems[END_REF]) Let g be a proper lower semi-continuous function from R n to (-∞, +∞]. If g is semi-algebraic, then g is a KL function.

An auxiliary Lyapunov function: the value function

Basic estimations Lemma 4.4 (Descent lemma) Let g : R n → R be a differentiable function with L-Lipschitz continuous gradient. Then for all x and y in R n ,

The proof is elementary, see e.g. [ Proof. Since y → h(x, y) is µ strongly convex, the function 2 . This follows by writing down the first order optimality condition for p(x) (convex setting) and by using the convexity of y → h(x, y)-µ 2 ||y -p(x)|| 2 . The inequality follows readily.

Lemma 4.6 (Descent property) For all x in D,

Proof. From Lemma 4.5, we have for all x in D that

Therefore from the fact that h(x, •) is an upper model for f on D(x), we infer

Iteration mapping

For any fixed x in D, we recall that the iteration mapping is defined through: p(x) := arg min h(x, y) : y ∈ D(x)}. Proof. Let x be a point in D and let x j ∈ D be a sequence converging to x. Fix y ∈ D(x) and let y j be a sequence of points such that y j ∈ D(x j ) and y j → y (use the inner semi-continuity of D). We prove first that p(x j ) is bounded. To this end, observe that [START_REF] Hare | Identifying Active Constraints via Partial Smoothness and Prox-Regularity[END_REF] h(x j , p(x j )) + µ 2 y jp(x j ) 2 ≤ h(x j , y j ).

Recall that h(x j , p(

and p(x j ) is bounded by continuity of h. Denote by π a cluster point of p(x j ). Observe that since p(x j ) ∈ D(x j ), the outer semi-continuity of D implies that π ∈ D(x). Passing to the limit in (29) above, one obtains

Since this holds for arbitrary y in D(x), we have established that π minimizes h(x, •) on D(x), that is π = p(x). This proves that p is continuous. By assumption (20) (ii) we have ∂ y h(x, p(x)) = ∂ y h(x, x) ⊂ ∂f (x). On the other hand D(x) ⊂ D and N D(x) (x) ⊂ N D (x), by [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF]. Using these inclusions in (30) yields the result.

Value function

We consider here

x -→ h x, p(x) .

the value function. Being given x and a value f (x) = h(x, x), it measures the progress made not on the objective f but on the value of the model. Due to its construction F is clearly semi algebraic by quantifier elimination.