S Gratton
email: serge.gratton@enseeiht.fr

L N Vicente

A MERIT FUNCTION APPROACH FOR DIRECT SEARCH *

Keywords: derivative-free optimization, direct-search methods, constraints, merit function, penalty parameter, random directions, nonsmooth optimization

In this paper it is proposed to equip direct-search methods with a general procedure to minimize an objective function, possibly nonsmooth, without using derivatives and subject to constraints on the variables. One aims at considering constraints, most likely nonlinear or nonsmooth, for which the derivatives of the corresponding functions are also unavailable. The novelty of this contribution relies mostly on how relaxable constraints are handled. Such constraints, which can be relaxed during the course of the optimization, are taken care of by a merit function and, if necessary, by a restoration procedure. Constraints that are unrelaxable, when present, are treated by an extreme barrier approach. One is able to show that the resulting merit function direct-search algorithm exhibits global convergence properties for first-order stationary constraints. As in the progressive barrier method [C.

Introduction. Consider the problem min

f (x) s.t. x ∈ Ω = Ω r ∩ Ω nr . (1)
The feasible region of this problem is defined by relaxable and/or unrelaxable constraints. The nonrelaxable constraints correspond to Ω nr ⊆ R n . Such constraints have to be satisfied at all iterations in an algorithmic framework for which the objective function is evaluated. Typically they are bounds or linear constraints but they can also include hidden constraints (constraints which are not part of the problem specification/formulation and their manifestation comes in the form of some indication that the objective function could not be evaluated). In contrast, relaxable constraints need only be satisfied approximately or asymptotically. In our notation Ω r is the set of relaxable constraints, which is assumed to take the form Ω r = {x ∈ R n : c i (x) ≤ 0 ∀i ∈ I} .

Finally, the objective function f : R n → R and the relaxable constraint functions c i are only assumed to be locally Lipschitz continuous (in the sense that the convergence analysis holds if f and the c i 's are Lipschitz continuous near an accumulation point produced by the algorithm). Most of the globally convergent derivative-free approaches for handling nonlinear constrained problems have been of direct search or line search type. 1Feasible methods may be the only option when all the constraints are unrelaxable (Ω r = R n ). In addition they generate a sequence of feasible points, thus allowing the iterative process to be terminated prematurely with a guarantee of feasibility for the best point tested so far. One way of designing feasible methods is by means of the barrier function [START_REF] Audet | Nonsmooth optimization through mesh adaptive direct search and variable neighborhood search[END_REF] f Ωnr (x) = f (x) if x ∈ Ω nr , +∞ otherwise.

Following the notation in [START_REF] Audet | Mesh adaptive direct search algorithms for constrained optimization[END_REF], we refer to such a barrier function as the extreme barrier function. It is not necessary to evaluate f at infeasib le points since the value of the extreme barrier function is set to +∞ at such point s. Direct-search methods take action solely based on function values comparisons and are thus appropriate to use in conjunction with an extreme barrier function. In the c ontext of direct-search methods of directional type using such functions, there are two k nown ways of designing globally convergent algorithms. In any of the cases, one must use sets of directions whose union (after normalization if needed) is asymptotically dense in the unit sphere of R n , even if the objective function is smooth. The first approach re quires only a simple decrease to accept new iterates but imposes integer requirements throughout the algorithm (and in particular in the generation of the directions). This approach is known as mesh adaptive direct-search (MADS) and has been developed by Audet and Dennis [START_REF] Audet | Mesh adaptive direct search algorithms for constrained optimization[END_REF]. One can, however, relax such integer lattice requirements an d freely generate the directions densely in the unit sphere at the price of imposing a s ufficient decrease condition on the acceptance of new iterates (see Vicente and Custó dio [START_REF] Vicente | Analysis of direct searches for discontinuous functions[END_REF])-in practice, sufficient decrease can be imposed as not to differ much from s imple decrease. An alternative to extreme barrier when designing feasible methods is the use of projections onto the feasible set, although this might require the know ledge of the derivatives of the constraints and be expensive or unpractical in many ins tances (see Lucidi, Sciandrone, and Tseng [START_REF] Lucidi | Objective-derivative-free methods for constrained optimization[END_REF] for such an approach).

In the case where there are no unrelaxable cons traints, one can use a penalty term by adding to the objective function a measure of constraint violation multiplied by a penalty parameter, and thus allowing one to star t infeasible with respect to the relaxable constraints. In this vein, Lewis and Torczon [START_REF] Lewis | A globally convergent augmented Lagrangian pattern search algorithm for optimization with general constraints and simple bounds[END_REF] (see also [START_REF] Kolda | A Generating Set Direct Search Augmented LAgrangian Algorithm for Optimization with a Combination of General and Linear Constraints[END_REF]) suggested an approach based on an augmented Lagrangian method. They consider the solution of a sequence of subproblems where the augmented Lagrang ian function takes into account only the nonlinear constraints and is minimized subje ct to the remaining constraints (bounds on the variables or more general linear constr aints). Each problem can then be approximately solved using an appropriate directio nal direct-search method. This application of augmented Lagrangian methods yields global convergence results to first-order stationary points of the same type of thos e obtained under the presence of derivatives. Diniz-Ehrhardt, Mart´ınez, and Pedro so [START_REF] Diniz-Ehrhardt | Derivative-free methods for nonlinear programming with general lower-level constraints[END_REF] studied a more general augmented Lagrangian setting where the problem con straints imposed as subproblem constraints are not necessarily of linear type. In tur n, Liuzzi and Lucidi [START_REF] Liuzzi | A derivative-free algorithm for inequality constrained nonlinear programming via smoothing of an ℓ ∞ penalty function[END_REF] and Liuzzi, Lucidi, and Sciandrone [START_REF] Liuzzi | Sequential penalty derivative-free methods for nonlinear constrained optimization[END_REF] developed and ana lyzed algorithms for inequality constrained problems, based on nonsmooth and smooth, respectively, penalty functions. They imposed sufficient decrease and handled bound and linear constraints separately, proving that a subset of the set of limit points of the sequence of iterates satisfy the first-order necessary conditions of the original problem. Martínez and Sobral [START_REF] Martínez | Constrained derivative-free optimization on thin domains[END_REF] proposed an algorithm for problems with "thin" constraints based on relaxing feasibility and performing a subproblem restoration procedure. Filter methods may also be appropriate to handle relaxable constraints, and the first step in this direction was done by Audet and Dennis [START_REF] Audet | A pattern search filter method for nonlinear programming without derivatives[END_REF]. The filter approach of Dennis, Price, and Coope [START_REF] Dennis | Direct search methods for nonlinearly constrained optimization using filters and frames[END_REF] guarantees global convergence to a first-order stationary point by means of an envelope around the filter as means of measuring sufficient decrease.

The first general approach to consider both relaxable and unrelaxable constraints is called progressive barrier and has been suggested by Audet and Dennis [START_REF] Audet | A progressive barrier for derivative-free nonlinear programming[END_REF], exhibiting some global convergence properties. It allows the handling of both types of constraints by combining mesh adaptive direct search for unrelaxable constraints with nondominance filter type concepts for the relaxable constraints (see the consequent developments in [START_REF] Audet | Globalization strategies for mesh adaptive direct search[END_REF]). An interesting feature is that a constraint can be considered relaxable until it becomes feasible whereupon it is transferred to the set of unrelaxable constraints.

In this paper, we develop an alternative approach to progressive barrier [START_REF] Audet | A progressive barrier for derivative-free nonlinear programming[END_REF], handling the relaxable constraints by means of a merit function instead of a filter. For such a purpose, we consider a constraint violation function of the type

(3) g(x) = i∈I max(c i (x), 0)
and the merit function

(4) M (x; µ) = f (x) + µg(x),
where µ ∈ R is a positive penalty parameter. The meri t function and the corresponding penalty parameter are only used in the evaluation o f an already computed step, to decide whether it will be accepted or not. The merit f unction (4) using ( 3) is known in nonlinear programming (see [23, section 17.2]) as t he ℓ 1 penalty function and has been extensively used in implementations (see [23, sec tion 17.5]).

Our treatment of the nonrelaxable constraints wil l implicitly consider the use of extreme barrier functions of the type [START_REF] Audet | Nonsmooth optimization through mesh adaptive direct search and variable neighborhood search[END_REF]. In practice what we optimize is f Ωnr since the nonrelaxable constraints restrict the evaluation of the objective function f. For generality, one considers here that Ω nr also constrains the evaluation of the relaxable constraints, and thus implicitly consider g Ωnr instead of g in our proposed algorithm. Due to the presence of (derivative-free) unrelaxable constraints and/or of the nonsmoothness of the objective function, the directions used in the algorithm must be generated densely in the unit sphere of R n .

Our merit function approach has been designed in a simple and modular way. A successful iteration is defined by a sufficient decre ase in the constraint violation measure (3) (sufficiently away from feasibility) or a s ufficient decrease in the merit function [START_REF] Audet | A pattern search filter method for nonlinear programming without derivatives[END_REF] for an appropriate value of the penalty pa rameter. Whenever a sufficient decrease in the constraint violation measure (3) is ob served at the expense of a significant increase in the objective function, a restoratio n of feasibility mode is entered with the single purpose of minimizing (3).

This paper is organized as follows. We start by describing the merit function algorithm in section 2. The convergence theory of t he proposed approach is then divided in four sections: section 3 for the behavior of the step size parameter; section 4 for the case where restoration is only entered a finite number of times; section 5 for the case where restoration is entered but never left; section 6 for the case where restoration is entered an infinite number of times. In section 7 we discuss how the theory particularizes in the presence of smoothness. In section 8 we show a few runs of the algorithm as a proof of concept. Finally, section 9 contains some concluding remarks and Appendix A summarizes a few notions of Clarke nonsmooth calculus needed in this paper.

A merit function algorithm.

In our algorithm framework an iteration is considered successful in two situations. To describe them in some detail let us assume a given iterate x k and a step size α k > 0. Each iteration is divided in a search and a poll step, but the latter is the one responsible for the convergence properties of the algorithm (and thus we ignore the search step for most of this discussion). Also, let d be a direction considered in the poll step and ρ(α) a forcing function, i.e., a positive and nondecreasing function verifying lim α↓0 ρ(α)/α = 0. The directions used in the poll step belong to a set D k which does not necessarily have to span R n with nonnegative coefficients as it happens in traditional direct-search methods for smooth problems.

The first possibility of success is that a certain sufficient decrease in the constraint violation measure g is attained (g(x k + α k d) < g(x k ) -ρ(α k )) and one is sufficiently away from the feasible region g(x k ) > Cρ(α k ) for some constant C > 1.

The other situation where success is declared is when the merit function is sufficiently decreased (M (

x k + α k d k ; µ k ) < M (x k ; µ k ) -ρ(α k ))
for a certain choice of the penalty parameter µ k . The update of the penalty parameter follows a classical one [23, formula (18.33)] since what we use in [START_REF] Audet | Mesh adaptive direct search algorithms for constrained optimization[END_REF] below is essentially the formula

[f (x k + α k d k ) -f (x k )]/α k ρ(α k )/α k ,
where the nominator corresponds to ∇f (x k ) ⊤ d k in the classical update (where f is typically continuously differentiable) and the denominator replaces the value of g(x k ) in the classical update (and we will observe later that when ρ(α k )/α k goes to zero so does, in principle, g(x k ); see Theorems 4.1, 5.1-ii, and 6.1 and their proofs). We summarize below the definition of a successful point (to be used in both search and poll steps). Begin (successful point). Given x k and α k , a point y k (either in the search or in the poll step) is successful if

g(y k ) < g(x k ) -ρ(α k ) and g(x k ) > Cρ(α k ) or, if that is false, if M (y k ; µ k ) < M (x k ; µ k ) -ρ(α k ), where (5) µ k = max μ, f (y k ) -f (x k ) Cρ(α k )
and μ > 0 and C > 1 are constants independent of k. End (successful point). However, before measuring success, our algorithm framework considers a phase to restore feasibility or decrease the amount of constraint violation. A Restoration is entered (in the poll step) when there exists a d ∈ D k such that g(x k + α k d) < g(x k ) -ρ(α k ), g(x k ) > Cρ(α k ), and M (x k + α k d; μ) ≥ M (x k ; μ), for a sufficiently large value μ of the penalty parameter. Notice that the first and third of these conditions imply

f (x k + α k d) -f (x k ) ≥ μ[g(x k ) -g(x k + α k d)] > μρ(α k ).
Thus, when Restoration is entered it is because a direction d has been found for which g is sufficiently reduced (g(x k + α k d) < g(x k ) -ρ(α k )) at a point x k sufficiently away from being feasible (g(x k ) > Cρ(α k )) and for which f has considerably increased

(f (x k + α k d) -f (x k ) > μρ(α k ))
. Restoration can also be entered in the search step and so we define below the notion of a Restoration identifier in general terms, to be used in both search and poll steps.

Begin (Restoration identifier). Given x k and α k , a point y k is a Restoration identifier (either in the search or in the poll step) if

g(y k ) < g(x k ) -ρ(α k ) and g(x k ) > Cρ(α k ) and M (y k ; μ) ≥ M (x k ; μ),
where μ > 0 and C > 1 are constants independent of k.

End (Restoration identifier). Our merit function approach is described below in Algorithm 2.1. All directions in the sets D k for all k are considered normalized.

Algorithm 2.1 (A merit function algorithm (Main)).

Initialization Choose x 0 ∈ Ω nr , α 0 , μ > 0, C > 1, 0 < β 1 ≤ β 2 < 1, and γ ≥ 1.
For k = 0, 1, 2, . . .

. If x k + α k d / ∈ Ω nr for all d ∈ D k , the iteration is declared unsuccessful. Otherwise, remove from D k all directions d such that x k + α k d / ∈ Ω nr . If any of the points x k + α k d, with d ∈ D k , is a Restoration identifier, then enter Restoration (with k r = k). Otherwise, if there is a successful point of the form x k + α k d k with d k ∈ D k , then x k+1 = x k + α k d k
and declare the iteration and the poll step successful. Otherwise, declare the iteration unsuccessful and set

x k+1 = x k . 3.
Step size parameter update: If the iteration was successful, then maintain or increase the step size parameter:

α k+1 ∈ [α k , γα k ].
Otherwise, decrease the step size parameter:

α k+1 ∈ [β 1 α k , β 2 α k ].
As we said before, if g can be sufficiently reduced (sufficiently away from feasibility) while f is considerably increased, we need to focus totally on a reduction of the constraint violation, and such a procedure is described in Algorithm 2.2. Restoration is then left when progress in the reduction of the constraint violation cannot be further achieved and such a considerable increase in f is no longer observed (we will later see in section 5 the appropriateness of such a leaving criterion).

Algorithm 2.2 (A merit function algorithm (Restoration)).

Initialization

Start from x kr ∈ Ω nr given from the Main algorithm and consider the same parameters as in there.

For k = k r , k r + 1, k r + 2, . . . 1. Search step (optional):
Evaluate the function g at a finite number of points in Ω nr . If any of those points (say x) is such that g(x) < g(x k ) -ρ(α k ) and g(x k ) > Cρ(α k ), then set x k+1 = x, declare the iteration and the search step successful, and skip the poll step. 2. Poll step: Select a finite subset of directions

D k . If x k + α k d / ∈ Ω nr for all d ∈ D k , the iteration is declared unsuccessful. Otherwise, remove from D k all directions d such that x k + α k d /
∈ Ω nr . Declare the poll step and the iteration successful if there exists a

d k ∈ D k such that g(x k + α k d k ) < g(x k ) -ρ(α k ) and g(x k ) > Cρ(α k ).
In such a case, set

x k+1 = x k + α k d k .
Otherwise, declare the iteration unsuccessful and set x k+1 = x k . Leave Restoration and return to the Main algorithm (starting at a new (k + 1)th iteration using x k+1 and α k+1 ) if the iteration is unsuccessful and

M (x k + α k d; μ) < M (x k ; μ) for some d ∈ D k . 3.
Step size parameter update: As in Step 3 of the Main algorithm.

3.

Step size behavior. As it is classic in direct-search methods or other techniques for derivative-free optimization, we start our analysis of global convergence by showing that the step size parameter approaches zero. We will do this under the condition that Restoration is not entered an infinite number of times (and postpone to section 6 the analysis of this situation).

Theorem 3.1. Assume that f is bounded below. Assume that Restoration is entered finitely many times.

Then,

lim inf k→+∞ α k = 0.
Proof. Suppose that there exists k ∈ N and ᾱ > 0 such that α k ≥ ᾱ and the kth iteration is a Main one for every k ≥ k.

Let us assume now that there exists an infinite subsequence J 1 of successful iterations after k ¯. We thus know that x k ∈ Ω nr for all k ∈ J 1 . In the derivation below we will omit the unsuccessful iterations, since at thos e iterations the iterates do not move.

If [g(x k+1 ) < g(x k ) -ρ(α k ) and g(x k ) > Cρ(α k )] is true for sufficiently large k ∈ J 1 , then g(x k+1 ) < g(x k ) -ρ(α k ) ≤ g(x k ) -ρ(α ¯)
for those indices k, which renders a contradiction sinc e g is bounded below by 0.

Thus, there must exist an infinite subsequence J 2 ⊆ J 1 of iterates for which

M (x k+1 ; µ k ) < M (x k ; µ k ) -ρ(α k ).
Here we consider two possibilities.

In the first case, all these iterates are such that µ k = μ for sufficiently large k. In such an occurrence one has that

M (x k+1 ; μ) < M (x k ; μ) -ρ(α k ) ≤ M (x k ; μ) -ρ(ᾱ)
for all k ∈ J 2 sufficiently large. However, in the successful iterations where [g(x k+1 ) < g(x k ) -ρ(α k ) and g(x k ) > Cρ(α k )], since Restoration was not entered ( k was considered sufficiently large for this purpose), one knows that M (x k+1 ; μ) < M (x k ; μ). Thus, M (x k ; μ) tends to -∞, which is a contradiction given the boundedness from below of both f and g.

In the second possibility, there is an infinite number of iterations in J 2 such that

µ k = f (x k+1 ) -f (x k ) Cρ(α k ) .
Let us choose just one of these iterations. For such an iteration k, either g(

x k+1 ) ≥ g(x k ) -ρ(α k ) or g(x k ) ≤ Cρ(α k ). Thus, either f (x k+1 ) -f (x k ) = µ k Cρ(α k ) ≥ µ k [g(x k ) -g(x k+1 )] (since C > 1) or f (x k+1 ) -f (x k ) = µ k Cρ(α k ) ≥ µ k g(x k ) ≥ µ k [g(x k ) -g(x k+1 )], both leading to M (x k+1 ; µ k ) ≥ M (x k ; µ k ), which contradicts M (x k+1 ; µ k ) < M (x k ; µ k ) -ρ(α k ).
We have proved under the assumption of contradiction that one cannot have an infinity of successful iterations. On the other hand, if all iterations are unsuccessful after a certain order that also contradicts the assumption of contradiction.

The following corollary organizes the relevant information regarding unsuccessful iterations and step size behavior for the analysis in the next sections.

Corollary 3.2. Assume that f is bounded below. Assume that Restoration is entered finitely many times.

Then, there exists at least one refining subsequence of Main iterations (i.e., a subsequence K composed of unsuccessful Main iterations for which α k → 0 for k ∈ K).

Proof. The proof can be found, for instance, in [START_REF] Conn | Introduction to Derivative-Free Optimization[END_REF] but it is given here for completeness. From Theorem 3.1 we conclude that there must exist a subsequence J of unsuccessful iterations (or unsuccessful poll steps). Thus, from the way we update the step size parameter, there must exist a subsequence of unsuccessful iterations

K ⊂ J such that α k+1 → 0 for k ∈ K. Since, α k ≤ (1/β 1 )α k+1 for k ∈ K, we obtain α k → 0 for k ∈ K.
4. Convergence assuming restoration is never entered after a certain order. The analysis of global convergence of Algorithm 2.1 is made by inspecting the sign of appropriate Clarke directional derivatives. Let h (e.g., h = f, g) be Lipschitz continuous near x * and be restricted to Ω nr ⊆ R n . We will use the following definition of the Clarke generalized derivative of h at x * along d:

h • (x * ; d) = lim sup x → x * , x ∈ Ω nr t ↓ 0, x + td ∈ Ω nr h(x + td) -h(x) t ,
where d must be in the hypertangent T H Ωnr (x * ) cone to Ω nr at x * (i.e., d must be in the interior of the tangent cone T Cl Ωnr (x * ) to Ω nr at x * ). In Appendix A of this paper we provide the rigorous definitions of these derivatives as well as the definitions of tangent and hypertangent cones. We assume throughout this paper that the hypertangent T H Ωnr (x * ) is nonempty. The sign of the Clarke derivatives is then analyzed at limit points of refining subsequences along refining directions. As we said before, by a refining subsequence [START_REF] Audet | Analysis of generalized pattern searches[END_REF], we mean a subsequence of unsuccessful Main iterates for which the step-size parameter converges to zero. By a refining direction [START_REF] Audet | Mesh adaptive direct search algorithms for constrained optimization[END_REF] (in T H Ωnr (x * )) associated with a refining subsequence K converging to x * , one means a limit point of

{d k } (in T H Ωnr (x * ))
where k ∈ K is taken sufficiently large such that x k + α k d k ∈ Ω nr . Given that our working directions in the sets D k 's are normalized, so are the refining directions.

4.1. Results on feasibility. We start by considering the determination of feasibility. (Note that since Ω nr is not necessarily by assumption a closed set, one must assume below that the limit point of a refining subsequence verifies the nonrelaxable constraints.) Theorem 4.1. Assume that f is bounded below. Assume that Restoration is entered finitely many times.

Let {x k } k∈K be a refined subsequence converging to x * ∈ Ω nr and assume that d ∈ T H Ωnr (x * ) is a refining direction associated with K and x * . Assume that g is Lipschitz continuous near x * . Then either g(x * ) = 0 (implying x * ∈ Ω r and thus

x * ∈ Ω) or g • (x * ; d) ≥ 0.
Proof. By assumption there exists a subsequence K 1 ⊆ K and a corresponding subsequence {d k } k∈K1 of polling directions such that {d k } converges to d ∈ T H Ωnr (x * ) in K 1 and α k goes to zero in K 1 . Thus, one must necessarily have that

x k +α k d k ∈ Ω nr for k sufficiently large in K 1 . Since the iteration k ∈ K 1 is unsuccessful, g(x k + α k d k ) ≥ g(x k ) -ρ(α k ) or g(x k ) ≤ Cρ(α k )
, and then either there exists an infinite number of the first or of the second. In the latter case, it is then trivial to obtain g(x * ) = 0 from the fact that α k → 0 in K 1 and the continuity of g. In the former case, there exists a subsequence

K 2 ⊆ K 1 such that g(x k + α k d k ) -g(x k ) α k ≥ - ρ(α k ) α k ∀k ∈ K 2 .
On the other hand, from the definitions of lim sup and K 2 ,

lim sup x → x * , x ∈ Ω nr t ↓ 0, x + td ∈ Ω nr g(x + td) -g(x) t ≥ lim sup k∈K2 g(x k + α k d) -g(x k ) α k .
Since g is Lipschitz continuous near x * (with constant L g ),

g(x k + α k d k ) -g(x k ) α k -L g d k -d ≤ g(x k + α k d) -g(x k ) α k .
One then obtains g Assume that T Cl Ωnr (x * ) has a nonempty interior. Then either g(x * ) = 0 (implying x * ∈ Ω r and thus x * ∈ Ω) or if the set of refining directions associated with K ′ (where K ′ is formed by the indices in K such that g(

x k + α k d k ) ≥ g(x k ) -ρ(α k )) and x * is dense in T Cl Ωnr (x * ) ∩ {d ∈ R n : d = 1}, then g • (x * ; v) ≥ 0 for all v ∈ T Cl
Ωnr (x * ), and x * is a stationary point of the constraint violation problem [START_REF] Audet | A progressive barrier for derivative-free nonlinear programming[END_REF].

Proof. Following the proof of Theorem 4.1, if there exists an infinite number of cases where g(x k ) ≤ Cρ(α k ), then g(x * ) = 0. Now, let v be such that v ∈ T Cl Ωnr (x * ) and v = 1. Then v is the limit of a sequence D of refining directions d associated with K ′ and x * such that d ∈ T H Ωnr (x * ). For each such d one can apply the proof of Theorem 4.1 and obtain g

• (x * ; d) ≥ 0. Thus, g • (x * ; v) = lim d∈T H Ωnr (x * ),d∈D g • (x * ; d) ≥ 0.
The result then holds for nonnormalized v's given that T Cl Ωnr (x * ) is a cone and the Clarke derivatives are homogeneous in their second arguments.

Results on optimality.

We now move to an intermediate optimality result. One does not explicitly use x * ∈ Ω r in the proof, but one notes that g • (x * ; d) ≤ 0 only describes the cone of first-order linearized directions under the feasibility assumption x * ∈ Ω r .

Theorem 4.3. Assume that f is bounded below. Assume that Restoration is entered finitely many times.

Let {x k } k∈K be a refined subsequence converging to x * ∈ Ω. Assume that f and g are Lipschitz continuous near x * . Assume that d ∈ T H Ωnr (x * ) is a refining direction associated with K and x * such that g

• (x * ; d) ≤ 0. Then f • (x * ; d) ≥ 0.
Proof. By assumption there exists a subsequence K 1 ⊆ K and a corresponding subsequence {d k } k∈K1 of polling directions such that {d k } converges to d ∈ T H Ωnr (x * ) in K 1 and α k goes to zero in K 1 . Thus, one must necessarily have that

x k +α k d k ∈ Ω nr for k sufficiently large in K 1 . Since the iteration k ∈ K 1 is unsuccessful, one is sure that M (x k + α k d k ; µ k ) ≥ M (x k ; µ k ) -ρ(α k )
, where µ k is given by [START_REF] Audet | Mesh adaptive direct search algorithms for constrained optimization[END_REF].

If

µ k = [f (x k + α k d k ) -f (x k )]/[Cρ(α k )], then it is because [f (x k + α k d k ) - f (x k )]/[Cρ(α k )] ≥ μ,
and thus [START_REF] Audet | Globalization strategies for mesh adaptive direct search[END_REF] f

(x k + α k d k ) -f (x k ) α k ≥ C μ ρ(α k ) α k . If not, then M (x k + α k d k ; μ) ≥ M (x k ; μ) -ρ(α k ), and thus (8) f (x k + α k d k ) -f (x k ) α k ≥ μ g(x k ) -g(x k + α k d k ) α k - ρ(α k ) α k .
On the other hand, from the definition of lim sup a nd the assumption g

• (x * ; d) ≤ 0, lim sup k∈K1 g(x k + α k d) -g(x k ) α k ≤ lim sup x → x * , x ∈ Ω nr t ↓ 0, x + td ∈ Ω nr g(x + td) -g(x) t ≤ 0.
Since g is Lipschitz continuous near x * and the fact that d k → d (and using an argument already seen in the proof of Theorem 4.1), lim sup

k∈K1 g(x k + α k d k ) -g(x k ) α k = lim sup k∈K1 g(x k + α k d) -g(x k ) α k ≤ 0.
Thus, one can say that there exists {ǫ k }, with ǫ k → 0, such that

g(x k + α k d k ) -g(x k ) α k ≤ ǫ k ∀k ∈ K 1 ,
which then implies when (8) occurs ( 9)

f (x k + α k d k ) -f (x k ) α k ≥ -μǫ k - ρ(α k ) α k . Now we know already that lim sup x → x * , x ∈ Ω nr t ↓ 0, x + td ∈ Ω nr f (x + td) -f (x) t ≥ lim sup k∈K1 f (x k + α k d) -f (x k ) α k = lim sup k∈K1 f (x k + α k d k ) -f (x k ) α k .
The proof is completed since the right-hand sides of ( 7) and ( 9) tend to zero in K 1 . Finally, we make use of the density of the refining directions in the set

(10) T (x * ) = T H Ωnr (x * ) ∩ {d ∈ R n : d = 1, g • (x * ; d) ≤ 0}
to derive the complete optimality result. Theorem 4.4. Assume that f is bounded below. Assume that Restoration is entered finitely many times.

Let {x k } k∈K be a refined subsequence converging to x * ∈ Ω. Assume that f and g are Lipschitz continuous near x * .

Assume that T H Ωnr (x * ) ∩ {d ∈ R n : g • (x * ; d) ≤ 0} has a nonempty interior. If the set of refining directions associated with K and x * is dense in T (x * ), then f • (x * ; v) ≥ 0 for all v ∈ T Cl Ωnr (x * ) such that g • (x * ; v) ≤ 0, and x * is a stationary point of (1).

Proof. Let v be such that v ∈ T Cl Ωnr (x * ), g • (x * ; v) ≤ 0, and v = 1. Then v is the limit of a sequence D of refining directions d associated with K and x * such that d ∈ T H Ωnr (x * ) and g • (x * ; d) ≤ 0. For each such d one can apply Theorem 4.3 and obtain f

• (x * ; d) ≥ 0. Thus, f • (x * ; v) = lim d∈T H Ωnr (x * ),d∈D f • (x * ; d) ≥ 0.
The result then holds for nonnormalized v's given that T Cl Ωnr (x * ) is a cone and the Clarke derivatives are homogeneous in their second arguments.

Never leaving restoration. The analysis of an infinite run of consecutive steps inside

Restoration shows that such a behavior would lead to feasibility and optimality results similar as in the previous case. By a refining subsequence below, we now mean a subsequence of unsuccessful Restoration iterates for which the stepsize parameter converges to zero. The definition of refining direction is the same as before. (Again, since Ω nr is not necessarily by assumption a closed set, one must assume below that x * belongs to Ω nr .)

Theorem 5.1. Assume that f is bounded below. Assume that Restoration is entered and never left.

(i) Then there exists a refining subsequence.

(ii) Let {x k } k∈K be a refined subsequence converging to x * ∈ Ω nr and assume that d ∈ T H Ωnr (x * ) is a refining direction associated with K and x * . Assume that g is Lipschitz continuous near x * . Then either g(x * ) = 0 (implying x * ∈ Ω r and thus

x * ∈ Ω) or g • (x * ; d) ≥ 0.
(iii) Let {x k } k∈K be a refined subsequence converging to x * ∈ Ω and assume that d ∈ T H Ωnr (x * ) is a refining direction associated with K and x * such that g

• (x * ; d) ≤ 0. Assume that f is also Lipschitz continuous near x * . Then f • (x * ; d) ≥ 0.
Proof. (i) There must exist a refining subsequence K within this call of the Restoration (this is essentially the argument of the third paragraph of the proof of Theorem 3.1). By assumption there exists a subsequence K 1 ⊆ K and a corresponding subsequence {d k } k∈K1 of polling directions such that {d k } converges to d ∈ T H Ωnr (x * ) in K 1 and α k goes to zero in K 1 . Thus, one must necessarily have that (iii) Since at the unsuccessful iteration k ∈ K 1 , Restoration is not left, it must be because M (x k +α k d k ; μ) ≥ M (x k ; μ) for all k ∈ K 1 , and the proof follows an argument also already seen (see the fourth paragraph of the proof of Theorem 4.3).

x k +α k d k ∈ Ω nr for k sufficiently large in K 1 . (ii) Since the iteration k ∈ K 1 is unsuccessful in the Restoration, g(x k + α k d k ) ≥ g(x k ) -ρ(α k ) or g(x k ) ≤ Cρ(α k ),
By assuming density of appropriate refining directions in certain cones, we could also establish stationary results for problems (1) and ( 6) as in Theorems 4.2 and 4.4, respectively.

6. Entering and leaving restoration an infinite number of times. It remains to analyze the case when one enters (and thus leaves) Restoration an infinite number of times. In this case the conditions under which the global convergence results are derived are not the ideal ones since we will have the need to assume that the search step is not performed (or not performed when it requires restoration) and that the step size is not increased (or not increased as frequently as it is decreased). Theorem 6.1. Assume that f is bounded below. Assume that Restoration is entered and left an infinite number of times.

Assume that α k is never increased, that the search step is not applied in the Main algorithm, and that {x k } converges to x * .

Let d be a direction which is the limit point of {d k } for both the sequences where Restoration is entered and left.

Assume that f and g are Lipschitz continuous n ear x * . Then x * ∈ Ω nr and either g(x * ) = 0 (implying x * ∈ Ω r and thus

x * ∈ Ω) or g • (x * ; d) ≥ 0. Furthermore, f • (x * ; d) ≥ 0 if g • (x * ; d) ≤ 0.
Proof. Let J 1 and J 2 be two subsequences of i terations where Restoration is entered and left, respectively.

Since for k ∈ J 2 one knows that α k is reduced and the step parameter is never increased, one obtains α k → 0. Also, by assumption there exists a subsequence J 3 ⊆ J 2 and a corresponding subsequence {d k } k∈J3 of polling directions such that {d k } converges to d ∈ T H Ωnr (x * ) in J 3 and α k goes to zero in J 3 . Thus, one must necessarily have that x k +α k d k ∈ Ω nr for k sufficiently large in J 3 . Thus, from g(

x k +α k d k ) ≥ g(x k )-ρ(α k ) or g(x k ) ≤ Cρ(α k ), for all k ∈ J 3 , one concludes that g • (x * ; d) ≥ 0 or g(x * ) = 0. Now, for k ∈ J 1 , M (x k + α k d k ; μ) ≥ M (x k ; μ)
, and from this we conclude that

f • (x * ; d) ≥ 0 if g • (x * ; d) ≤ 0.
To derive a result of the form of Theorem 4.4, one would need to impose that the directions used when entering Restoration are dense in the set [START_REF] Clarke | Optimization and Nonsmooth Analysis[END_REF].

To establish Theorem 6.1 we needed to make sure that α k goes zero, and since we already had a subsequence of step size decreases, one way to ensure such a property was to rule out step size increases. Note also that we can allow search steps as long as they are skipped when they require Restoration.

An alternative to this result is to consider a certain maximum number N of Restoration calls, after which one decides to unrelax the relaxable constraints. In this approach, at the (N + 1)th call to Restoration, one enters a slightly different Restoration algorithm with the single purpose of minimizing g (i.e., Algorithm 2.2 without the condition of leaving Restoration). After such a call, if one arrives at a point where g is zero, one redefines Ω nr as the intersection of the originals Ω nr and Ω r , and start from there an approach strictly based on the minimization of the extreme barrier function f Ωnr . This procedure can be applied to the relaxable constraints c i (x) ≤ 0, i ∈ I, individually.

7. Particularization to smoother settings. When f is strictly differentiable at x * in the sense of Clarke [START_REF] Clarke | Optimization and Nonsmooth Analysis[END_REF], there exists ∇f (x * ) such that f • (x * ; d) = ∇f (x * ), d for all d. Furthermore, if the c i 's are smoother (for instance, continuously differentiable at x * ), then g in ( 3) is regular [START_REF] Clarke | Optimization and Nonsmooth Analysis[END_REF], and its Clarke directional derivatives coincide with the traditional ones, i.e., g • (x * ; d) = g ′ (x * ; d). Thus, under these smoother assumptions, the results would read as follows: (i) g ′ (x * ; d) ≥ 0 (in the relaxable constraints criticality result of Theorem 4.1); (ii) the projection of ∇f (x * ) is zero onto the set of directions v such that v ∈ T Cl Ωnr (x * ) and g ′ (x * ; v) ≤ 0 (in the optimality result of Theorem 4.4).

When f and c i , i ∈ I, are continuously differentiable and Ω nr = R n , there is no need to use sets of polling directions dense in the unit sphere. The algorithms (Main and Restoration) can then consider in this smooth setting, in their poll steps, directions belonging to positive spanning sets D k . To better extend the result of Theorem 4.1 to such a setting one would have to consider a continuously differentiable version for g, such as [START_REF] Colson | Trust-Region Algorithms for Derivative-Free Optimization and Nonlinear Bilevel Programming[END_REF] g

(x) = i∈I [max(c i (x), 0)] 2 .
Theorem 7.1. Assume that f is bounded below. Assume that Restoration is entered finitely many times.

Let {x k } k∈K be a refined subsequence converging to x * . Suppose that D k converges in K to a positive spanning set D * . Assume that Ω nr = R n , that c i , i ∈ I, are continuously differentiable at x * , and that g is given by [START_REF] Colson | Trust-Region Algorithms for Derivative-Free Optimization and Nonlinear Bilevel Programming[END_REF]. Then either g(x * ) = 0 (and thus x * ∈ Ω) or ∇g(x * ) = 0.

Proof. Since the iteration k ∈ K is unsuccessful, g(x k + α k d k ) ≥ g(x k ) -ρ(α k ) for all d ∈ D k or g(x k ) ≤ Cρ(α k )
, and then either there exists an infinite number of the first or of the second. In the latter case, it is then trivial to obtain g(x * ) = 0 from the fact that α k → 0 in K and the continuity of g. In the former case, there exists a subsequence

K 1 ⊆ K such that g(x k + α k d) -g(x k ) α k ≥ - ρ(α k ) α k ∀d ∈ D k , ∀k ∈ K 1 .
Applying the mean value theorem, for some t d k ∈ (0, 1),

∇g(x k + t d k α k d), d ≥ - ρ(α k ) α k ∀d ∈ D k , ∀k ∈ K 1 ,
which then implies ∇g(x * ), d ≥ 0 for all d ∈ D * , and thus ∇g(x * ) = 0. Theorem 4.3 can also be adapted to the continuously differentiable case. Theorem 7.2. Assume that f is bounded below. Assume that Restoration is entered finitely many times.

Let {x k } k∈K be a refined subsequence converging to x * ∈ Ω. Assume that Ω nr = R n and that f , c i , i ∈ I, are continuously differentiable at x * . Let g be given by (3) or [START_REF] Colson | Trust-Region Algorithms for Derivative-Free Optimization and Nonlinear Bilevel Programming[END_REF]. Suppose that D k converges to a set D * containing positive generators for

(12) G(x * ) = {v ∈ R n : g ′ (x * ; v) ≤ 0} = {v ∈ R n : ∇c i (x * ), v ≤ 0 when c i (x * ) = 0}.
Then the projection of ∇f (x * ) onto G(x * ) is zero.

Proof. The proof of Theorem 4.3 shows that for all limit points d of polling directions, if d ∈ G(x * ), then ∇f (x * ), d ≥ 0. Thus, for all positive generators of G(x * ) in D * , ∇f (x * ), d ≥ 0, and this implies the result.

8. Numerical illustration. We illustrate the performance of the merit function algorithm on three test problems, which were also tested in [START_REF] Audet | A progressive barrier for derivative-free nonlinear programming[END_REF] to assess the progressive barrier method. The first two problems are defined by a simple algebraic formulation whereas the third one comes from an application.

A simple implementation of Algorithm 2.1 was made in MATLAB without any parameter tuning. The step size updating parameters were set to α 0 = 1, β 1 = β 2 = 0.5, and γ = 2. The forcing function was set chosen as ρ(α) = min{10 -5 , 10 -5 α 2 k }. For the update of the penalty parameter we picked μ = max{10, g(x 0 )} and C = 100. No search step was attempted. The measure of constraint violation was the nonsmooth one [START_REF] Audet | Analysis of generalized pattern searches[END_REF]. As for the polling directions, those were randomly generated each step with norm one. We show results for |D k | = n/2, n + 1, 2n. There is no guarantee, even in the cases |D k | = n + 1, 2n, of having computed a positive spanning set, but one knows that that is not required in the convergence theory. A study of random positive spanning sets is out of the scope of this paper. The results presented are the average of 40 runs (corresponding to 40 values of the seed of the MATLAB random generator randn).

In the first problem [START_REF] Audet | Mesh adaptive direct search algorithms for constrained optimization[END_REF], one minimizes a linear function in a convex domain:

min n i=1 x i s.t. n i=1 x 2 i ≤ 3n. ( 13
)
Two starting points are considered, one feasible (0, . . . , 0) ⊤ and the other infeasible (3, . . . , 3) ⊤ . There is a single (global) solution (-√ 3, . . . , -√ 3) ⊤ , with optimal value -√ 3n. In the second problem [START_REF] Audet | A progressive barrier for derivative-free nonlinear programming[END_REF], the objective is still linear but the feasible region is nonconvex: The results for problems ( 13)-( 14) are depicted in Figures 12for the case n = 50. One can see that convergence is attained in all the cases and that the results must be considered good when compared to those r eported in [START_REF] Audet | A progressive barrier for derivative-free nonlinear programming[END_REF]. One observes the nonmonotonicity in the value of the objective fun ction (especially when starting infeasible), while reaching feasibility or within the com promise promoted by the merit function. This effect is even visible while approachin g the minimizer (which lies at the boundary) for problem [START_REF] Conn | Introduction to Derivative-Free Optimization[END_REF]. One also observes tha t most of the progress is made to be the less robust for these test problems. In addit ion, the number of iterations is much lower (most of the cases below 1000 and never exceeding 2000 for the chosen budget size) meaning that the parallelization of the alg orithm would bring significant gains in the overall computational time.

min x n s.t. n i=1 (x i -1) 2 ≤ n 2 ≤ n i=1 (x i + 1) 2 . ( 14
We also ran the code on the truth model of a probl em defined by the optimization of a styrene process production process (see [START_REF] Audet | Nonsmooth optimization through mesh adaptive direct search and variable neighborhood search[END_REF]). Th e problem has eight variables, four unrelaxable constraints (of the type yes-no), an d seven relaxable constraints. The variables have lower and upper bounds (x i ∈ [0, 100], i = 1, . . . , n), which were treated by us as unrelaxable constraints. We interfac ed the C++ code available in NOMAD [START_REF] Abramson | The NOMAD project[END_REF] for this problem to our MATLAB opti mizer. We considered the two initial points also used in [START_REF] Audet | A progressive barrier for derivative-free nonlinear programming[END_REF], namely x 0 = 100[0.54, 0.66, 0.86, 0.08, 0.29, 0.51, 0.32, 0.15] ⊤ (fe asible for the relaxable const.) x 0 = 100[0.44, 0.99, 0.76, 0.39, 0.39, 0.48, 0.43, 0.05] ⊤ (in feasible for the relaxable const.).

The plots in Figure 3 depict the performance of the a lgorithm for these two starting points when using n/2, n+1, and 2n polling directions. Again the version |D k | = n/2 appeared as the less robust one. One can see that the results for this third problem must also be considered good when compared to those reported in [START_REF] Audet | A progressive barrier for derivative-free nonlinear programming[END_REF].

Finally, we point out that, for all the instances run, the returned points were always feasible with respect to the relaxable constrain ts and that the update of the penalty parameter has never posed any problem of sca ling or magnitude. Restoration was only entered a negligible number of times. 9. Concluding remarks. We have introduced a globalization procedure to include relaxable constraints in direct-search methods, a llowing starting infeasible with respect to these constraints. The procedure introduc ed requires the evaluation of a merit function for the purposes of measuring success of an iteration. The penalty parameter present in the merit function does not, thu s, play any explicit role in the . [START_REF] Conn | Introduction to Derivative-Free Optimization[END_REF] whe n n = 50 (and a budget of 600n is given). The optimal value is approximately 86.6025. On the l eft (resp., on the right) the starting point is feasible (resp., infeasible). computation of the step. It is also important to stres s that no type of boundedness of the penalty parameter was assumed to derive the global convergence results. We included a scheme to restore feasibility associated wit h these constraints (or just to significantly reduce such a constraint violation) as it seemed to us as a potentially useful tool.

The convergence analysis is organized depending o n the number of times Restoration is entered. When Restoration is entered finitely of ten, we showed in Theorem 4.2 that the limit points of certain subsequences of iterates (called refining and composed of unsuccessful iterations for which α k goes to zero) a re either feasible or Clarke stationary for the constraint violation problem [START_REF] Audet | A progressive barrier for derivative-free nonlinear programming[END_REF]. The n, we showed in Theorem 4.4 that such limit points, when feasible to the original problem, are Clarke stationary for [START_REF] Abramson | The NOMAD project[END_REF]. Our theory provides similar results when Resto ration is entered but never left (see section 5). The remaining case is when Restoratio n is entered and left an infinite number of times (section 6). Here, to guarantee the sa me type of results, we required the algorithm to meet two additional criteria related t o the application of the search [START_REF] Dennis | Direct search methods for nonlinearly constrained optimization using filters and frames[END_REF] whe n n = 50 (and a budget of 600n is given). The optimal value is -49. On the left (resp., on the right) the starting point is feasible (resp., infeasible).

step and the update of the step size α k in successful i terations.

As a referee pointed out to us, our algorithmic fra mework could be simplified by setting µ k = µ ¯ without affecting the theoretical prop erties. Having µ k = µ ¯ would implicitly maintain the presence of a penalty parame ter. For the sake of generality and algorithmic flexibility, we maintained the more gen eral penalty parameter update.

A number of issues remain to be better investiga ted, in particular how our approach would rank in a comprehensive numerical com parison of the existing directsearch type methods for nonlinear constrained deriva tive-free optimization. The few numerical tests made until now are relatively promising and indicated the need to a better understanding of the use of random directions and random positive spanning sets in direct search, a study which we are currently undertaking. Other algorithmic options are likely to also have a significant impact like t he application of a search step, the choice of parameters such as the initial threshold µ ¯ for the penalty parameter, and the resetting of the step size before and after a cha nge in optimization state (such as the Restoration).

Appendix A. Cones and derivatives in the constrained case. A vector is said tangent to Ω nr at x if it satisfies the following definition.

Definition A.1. A vector d ∈ R n is said to be a Clarke tangent vector to the set Ω nr ⊆ R n at the point x in the closure of Ω nr if for every sequence {y k } of elements of Ω nr that converges to x and for every sequence of positive real numbers {t k } converging to zero, there exists a sequence of vectors {w k } converging to d such that y k + t k w k ∈ Ω nr .

The Clarke tangent cone to Ω nr at x, denoted by T Cl Ωnr (x), is then defined as the set of all Clarke tangent vectors to Ω nr at x. The Clarke tangent cone generalizes the tangent cone in nonlinear programming [START_REF] Nocedal | Numerical Optimization[END_REF], but one can think about the latter one for gaining the necessary geometric motivation.

Given x * ∈ Ω nr and d ∈ T Cl Ωnr (x), one is not sure that x + td ∈ Ω nr for x ∈ Ω nr arbitrarily close to x * . Thus, for this purpose, one needs to consider directions in the interior of the Clarke tangent cone. The hypertangent cone appears then as the interior of the Clarke tangent cone (when such interior is nonempty, as we assume in this paper). In what follows, B(z; r) denotes {w ∈ R n : w -z < r}.

Definition A.2. A vector d ∈ R n is said to be a hypertangent vector to the set Ω nr ⊆ R n at the point x in Ω nr if there exists a scalar ǫ > 0 such that y + tw ∈ Ω nr ∀y ∈ Ω nr ∩ B(x; ǫ), w ∈ B(d; ǫ), and 0 < t < ǫ.

The hypertangent cone to Ω nr at x, denoted by T H Ωnr (x), is then the set of all hypertangent vectors to Ω nr at x. The closure of the hypertangent cone is the Clarke tangent one (when the former is nonempty).

If we assume that h is Lipschitz continuous near x * , we can define the Clarke-Jahn generalized derivative along directions d in the hypertangent cone to Ω nr at x * , h • (x * ; d) = lim sup x → x * , x ∈ Ω nr t ↓ 0, x + td ∈ Ω nr h(x + td) -h(x) t = lim ǫ↓0 sup x ∈ B(x * ; ǫ) ∩ Ω nr t ∈ (0, ǫ), x + td ∈ Ω nr h(x + td) -h(x) t .

These derivatives are essentially the Clarke generalized directional derivatives [START_REF] Clarke | Optimization and Nonsmooth Analysis[END_REF], generalized by Jahn [START_REF] Jahn | Introduction to the Theory of Nonlinear Optimization[END_REF] to the constrained setting. Given a direction v in the tangent cone, one can consider the Clarke-Jahn generalized derivative to Ω nr at x * as the limit h • (x * ; v) = lim d∈T H Ωnr (x * ),d→v h • (x * ; d) (see [START_REF] Audet | Mesh adaptive direct search algorithms for constrained optimization[END_REF]). The point x * is considered stationary for problem [START_REF] Abramson | The NOMAD project[END_REF] when Ω = Ω nr if f • (x * ; v) ≥ 0 for all v ∈ T Cl Ωnr (x * ). When Ω r = R n , then the point x * is considered stationary for problem (1) if f • (x * ; v) ≥ 0 for all v ∈ T Cl Ωnr (x * ) ∩ {d ∈ R n : g • (x * ; d) ≤ 0}.

  and the proof follows an argument already seen (in the second paragraph of the proof of Theorem 4.1).

)

  Two starting points are also considered, one feasibl e (n, 0, . . . , 0) ⊤ and the other i n) ⊤ . There is a single (global) solution (1, . . . , 1, 1-n) ⊤ , with -

Fig. 1 .

 1 Fig.1. Two runs of Algorithm 2.1 on problem[START_REF] Conn | Introduction to Derivative-Free Optimization[END_REF] whe n n = 50 (and a budget of 600n is given). The optimal value is approximately 86.6025. On the l eft (resp., on the right) the starting point is feasible (resp., infeasible).

Fig. 2 .

 2 Fig.2. Two runs of Algorithm 2.1 on problem[START_REF] Dennis | Direct search methods for nonlinearly constrained optimization using filters and frames[END_REF] whe n n = 50 (and a budget of 600n is given). The optimal value is -49. On the left (resp., on the right) the starting point is feasible (resp., infeasible).

Fig. 3 .

 3 Fig.3. Two runs of Algorithm 2.1 on the styrene problem for a budget of 300 function evaluations. On the left (resp., on the right) the starting point is feasible (resp., infeasible) with respect to the unrelaxable constraints.

  ≥ 0 since both d k -d and ρ(α k )/α k tend to zero in K 2 .By assuming that appropriate refining directions are dense in T Cl Ωnr (x * )∩{d ∈ R n : d = 1}, one can show that the limit point x * is Clarke stationary for the constraint Theorem 4.2. Assume that f is bounded below. Assume that Restoration is entered finitely many times.Let {x k } k∈K be a refined subsequence converging to x * ∈ Ω nr . Assume that g is Lipschitz continuous near x * .

	violation problem
	(6)	min g(x) s.t. x ∈ Ω nr .

• (x * ; d)

On the model-based trust-region side of optimization witho ut derivatives, nonlinear constraints have been considered mostly in implementations (see[8, 9, 11, 12,

[START_REF] Powell | A direct search optimization method that models the objective and constraint functions by linear interpolation[END_REF]), and as far as we know no convergence theory has yet been developed.

Acknowledgments. The authors thank the two referees, in particular one of them, for their constructive comments and suggestions which led to an improved version of this paper. We are also grateful to A. Ismael F. Vaz for his help in running the application problem.

This author's research was supported by FCT under grants PTDC/MAT/116736/2010 and PEst-C/MAT/UI0324/2011 and by the Réseau Thématique de Recherche Avancée, Fondation de Coopération Sciences et Technologies pour l'Aéronautique et l'Espace, under the grant ADTAO.