Jean Charles

MAINTAINING THE POSITIVE DEFINITENESS OF THE MATRICES IN REDUCED SECANT METHODS FOR EQUALITY CONSTRAINED OPTIMIZATION *

Keywords: Positive reduced matrices in optimization Augmented Lagrangian, Constrained Optimization, Exact Penalty Function, Global Convergence, Optimization Algorithm, Reduced Secant Method, Superlinear Convergence, Wolfe's Step-size Selection. Subject classification AMS (MOS). 49D05, 49D30, 65K05

We propose an algorithm for minimizing a function f on IR n in the presence of m equality constraints c that locally is a reduced secant method. The local method is globalized using a nondifferentiable augmented Lagrangian whose decrease is obtained by both a longitudinal search that decreases mainly f and a transversal search that decreases mainly c . Our main objective is to show that the longitudinal path can be designed to maintain the positive definiteness of the reduced matrices by means of the positivity of γ k T δ k , where γ k is the change in the reduced gradient and δ k is the reduced longitudinal displacement.

Introduction

We consider here the problem of minimizing a real-valued function f , defined on an open convex set ω in IR n , subject to m (m < n ) nonlinear equality constraints c : min { f (x ) : x ∈ ω , c (x ) = 0 } .

(1.1)

We shall suppose that the m × n Jacobian matrix of the constraints at a point x in ω, namely A (x ), is surjective, i.e. has full rank m . Then, if x * is a local solution of (1.1), there exists a unique Lagrange multiplier λ * in IR m , such that the following first order optimality conditions are satisfied for x = x * and λ = λ * (see [START_REF] Fletcher | Practical methods of optimization[END_REF], for example):

∇f (x ) + A (x ) T λ = 0 . c (x ) = 0 , (1.2)
We have denoted by ∇f (x ) the gradient vector of f at x .

Locally, the faster methods for solving (1.1) tackle the problem by trying to solve directly the system (1.2), whose solutions correspond to stationary points of the original problem. Two classes of local methods may be distinguished.

The first class is formed of those algorithms whose step is an approximation of the Newton step for solving (1.2). Among them are the quasi-Newton methods, which may be introduced as follows. The Jacobian matrix of (1.

J k . . = L k A (x k ) A (x k ) T O ,
where L k is a symmetric matrix of order n and if we denote by ∇ x l (x k ,λ k ) the gradient according to x of the Lagrangian, quasi-Newton methods consist in calculating approximations (x k ,λ k ) of (x * ,λ * ), by using the following scheme:

λ k +1 x k +1 = λ k x k -J k -1 ∇ x l (x k ,λ k ) c (x k ) .
Note that if L k is positive definite, or only positive definite in Ker A (x k ), the kernel of A (x k ), i.e. ξ T L k ξ > 0 for all nonzero ξ in Ker A (x k ), then J k is non singular and the previous iteration is well defined. This method is called the Successive Quadratic Programming (SQP) method because x k +1 = x k + d k SQP , where d k SQP is obtained by solving successively in d the following quadratic programs:

s.t. d ∈ IR n , c (x k ) + A (x k ) d = 0 min ∇f (x k ) T d + 2 1 d T L k d , (1.3)
and λ k +1 = λ k +1 SQP , the associated multiplier. In this algorithm, L k is updated at each iteration. This method has been extensively studied since the papers by [START_REF] Wilson | A simplicial algorithm for concave programming[END_REF], [START_REF] Han | Superlinearly convergent variable metric algorithms for general nonlinear programming problems[END_REF] and Powell (1978,a,b,c) and we refer to [START_REF] Powell | Methods for nonlinear constraints in optimization calculations[END_REF] for a state of the art on the subject.

The second class of methods is based on the fact that the dimension of problem (1.1) is not n but n -m , which is the dimension of the manifold M (x while the convergence of the former has been proved to be superlinear (in one step) (see [START_REF] Byrd | On the convergence of constrained optimization methods with accurate Hessian information on a subspace[END_REF] and Gilbert (1986,a,b)), that is to say:

x k +1 -x * / x k -x * → 0 .
(1.5) This is a better rate of convergence than the rate (1.4). Note that this rate of convergence can also be obtained by using the SQP method but with the necessity of updating a matrix of order n . Therefore, reduced secant methods become competitive and sometimes the only ones usable when the number m of constraints is large while the number n -m of parameters remains reasonable.

In this work, we shall focus on some aspects of the method proposed by Coleman and Conn. But first, what is this method?

The presentation of the algorithm given below has been developed in Gilbert (1986,a and[START_REF] Ch | Mise a `jour de la me ´trique dans les me ´thodes de quasi-Newton re ´duites en optimisation avec contraintes d'e ´galite ´[END_REF] and differs noticeably from the one given by Coleman and Conn (1982,a). In particular, the formalism used here, which is due to Gabay (1982,a), allows us to group together a set of methods that differ only by a choice of operators. The main idea is to build, at each point y in ω, a decomposition of IR n in two complementary subspaces and to do this smoothly in y . The first subspace is Ker A (y ), the tangent space to M (y ) .

. = c -1 (c (y )) at y , for which a basis Z (y ) -is chosen. This is to say that Z (y ) -is an n × (n -m ) matrix whose columns form a basis of Ker A (y ). Therefore, for all y in ω, we have:

A (y ) Z (y ) -= 0 , (1.6)
and Z (y ) -is injective, i.e. u ∈ IR n -m and Z (y ) -u = 0 imply u = 0. The complementary subspace to Ker A (y ) depends on the choice of a right inverse A (y ) -of A (y ) and is given by R (A (y ) -), the range of A (y ) -. Then, there exists a unique (n -m ) × n matrix Z (y ) satisfying:

Z (y ) Z (y ) -= I in IR (n -m )×(n -m ) ,
(1.7) Z (y ) A (y ) -= 0 in IR (n -m )×m .

(1.8)

One way to introduce the algorithm is to say that it tries to solve the system of optimality (1.2) by considering both equations separately and successively. Therefore, starting from an estimate (x k ,λ k ) of (x * ,λ * ), the next iterate (x k +1 ,λ k +1 ) is calculated in two steps:

y k . . = x k -R k c (x k ) = . . x k + r k , (1.9) x k +1 . . = y k -Z (y k ) -H k g (y k ) = . . y k + t k , (1.10) λ k +1 . . = -A (y k ) -T ∇f (y k ) + A (y k ) -T L k Z (y k ) -H k g (y k ) .
(1.11)

In (1.9), r k is the restoration step and R k is the restoration operator, an n × m injective matrix, asymptotically close to A (x * ) -. Here, we shall take R k . . = A (x k ) -, although R k . . = A (y k -1 ) -, which avoids the linearization of the constraints at x k , is also possible without destroying superlinear convergence, but this is more difficult to analyze. In (1.10), t k is the tangent step and H k is a symmetric matrix of order n -m that should be updated so as to remain positive definite (the main concern of this paper) and so as to have

(G k -G * ) Z (y k ) t k = o ( t k ) , (1.12)
where

G k . . = H k -1 and G *
is the reduced Hessian of the Lagrangian. This is defined by

G * . . = Z (x * ) -T L * Z (x * ) -.
(1.13)

Condition (1.12) is a sufficient (but not necessary) condition of superlinear convergence for (x k ) (see [START_REF] Byrd | On the convergence of constrained optimization methods with accurate Hessian information on a subspace[END_REF]), Gilbert (1986,a,b)). Usually, it is satisfied in practice (see [START_REF] Coleman | On the local convergence of a quasi-Newton method for the nonlinear programming problem[END_REF] and Gilbert ( 1988)). In (1.10), g (y k ) is the reduced gradient of f at y k and is defined by

g (y ) . . = Z (y ) -T ∇f (y ) . Finally, in (1.11), L k is an approximation of L * .
Algorithm (1.9)-(1.10) differs from the one proposed by Coleman and Conn (1982,a) because of their particular choice of operators. In their algorithm, A (y ) -is the Moore-Penrose pseudo-inverse of A (y ), i.e. A (y ) -.

. = A (y ) T (A (y ) A (y ) T ) -1 , and Z (y ) -is an orthogonal basis of Ker A (y ). However, the local analysis of the method has shown that this particular choice of operators has no influence on the superlinear convergence of the method (see [START_REF] Hoyer | Variants of the reduced Newton method for nonlinear equality constrained optimization problems[END_REF] and Gilbert (1986,a)). This means that it is possible to use this freedom of choice for other purposes.

Algorithm (1.9)-(1.11) calls for some comments. First, note that λ k does not intervene in the calculation of x k +1 and λ k +1 . Therefore, from the superlinear convergence of the sequence (x k ,λ k ) (together), we can deduce the superlinear convergence of (x k ), while for (λ k ) we get

λ k +1 -λ * / x k -x * → 0 .
(1.14)

We also see that the sequence (x k ) can be generated by (1.9)-(1.10) independently of the sequence (λ k ). We shall see, indeed, that the update of H k does not require the knowledge of (λ k ). Therefore, algorithm (1.9)-(1.10) is a reduced method for (x k ), because the only matrix to update is H k , which is of order n -m . On the other hand, the n × n matrix L k intervenes in the calculation (1.11) of λ k +1 . We have said that, locally, this calculation is not necessary. However, in a global framework, some estimate of λ * is useful. Therefore, we shall avoid the need of generating L k by taking the following estimate:

λ(y ) . . = -A (y ) -T ∇f (y ) , (1.15) whose value at y = x * is λ * .
The local algorithm (1.9)-(1.10) may be globalized by using a penalty function θ of the form:

θ(x ) . . = f (x ) + φ(c (x )) , (1.16)
where φ : IR m → IR + satisfies φ(0) = 0. If φ is convex, one may calculate θ ′ (x ; t ), the directional derivative of θ at x in a direction t . In particular, one finds:

θ ′ (y k ; t k ) = ∇f (y k ) T t k + φ ′ (c (y k ); A (y k ) t k
) and because t k ∈ Ker A (y k ), we have:

θ ′ (y k ; t k ) = ∇f (y k ) T t k = -g (y k ) T H k g (y k ) = g (y k ) T Z (y k ) t k .
(1.17)

This shows that it is useful to maintain H k positive definite in order that t k will be a descent direction of θ at y k .

Our main objective in this paper is to design a globally and superlinearly convergent algorithm that locally reduces to the method (1.9)-(1.10) and that maintains the matrices H k positive definite. To obtain this last property, we shall update the matrices H k by the inverse BFGS formula (see e.g. [START_REF] Dennis | Quasi-Newton methods, motivation and theory[END_REF]):

H k +1 = I - γ k T δ k δ k γ k T H k I - γ k T δ k γ k δ k T + γ k T δ k δ k δ k T , (1.18)
which we shall refer to by

H k +1 = BFGS (H k ,γ k ,δ k ).
In this formula, γ k will be the change in the reduced gradient (a vector in IR n -m ) when making a certain displacement and δ k is the corresponding "reduced" displacement (also a vector in IR n -m ). Then, it is well known that H k transmits its positive definiteness to H k +1 if and only if

γ k T δ k > 0 . (1.19)
For us, this property will play a major part because we shall maintain the positive definiteness of H k , precisely by trying to satisfy condition (1.19) at each iteration of the algorithm. In this paper, we shall not use other particular properties of the BFGS update. Therefore, other update formulae having the same property, such as those of the restricted Broyden's class, could be used.

This way of maintaining the positive definiteness of the generated matrices by realizing condition (1.19) is standard in unconstrained optimization. There, the vector γ k is the change in the gradient of the objective function when the displacement δ k = ρ k d k is done. Condition (1.19) is then tried to be satisfied by determining a suitable step-size ρ k in the direction d k . Wolfe's step-size selection criteria are relevant for this determination. So, in order to realize (1.19) in our problem, we shall propose a generalization of Wolfe's criteria, which will require a particular design of the search path.

The fact that this strategy for maintaining H k positive definite succeeds for reduced secant methods is rather comforting because it does not for SQP methods, in general. The reason for this is that, for these methods, the local analysis forces γ k to be the change in the gradient of the Lagrangian for the displacement ρ k d k SQP , ρ k is the step-size. But, the Lagrangian is not necessarily bounded from below and may have a negative curvature in the direction d k SQP , even locally. Therefore, γ k T δ k may be negative for any step-size ρ k (see Powell (1978,b and1984)).

The papers analyzing the update of matrices in reduced methods are due to [START_REF] Coleman | On the local convergence of a quasi-Newton method for the nonlinear programming problem[END_REF], [START_REF] Nocedal | Projected Hessian updating algorithms for nonlinearly constrained optimization[END_REF] and Gilbert (1986,b). In the first paper the analysis is local and, as we shall see, (1.19) is automatically satisfied close to optimal points satisfying the usual second order optimality conditions, if the vectors γ k and δ k are correctly chosen (see below). The analysis of Nocedal and Overton, which concerns the algorithm studied by Gabay (1982,b), is also local. Finally, the analysis in Gilbert (1986,b) is global but the reduced matrix is not updated if condition (1.19) is not satisfied. This does not prevent superlinear convergence from occurring because asymptotically (1.19) may be satisfied. However, even far from the solution it may be interesting to update the matrix in order to improve convergence. So one possibility would be to use Powell's (1978,b) modification of γ k (as for SQP methods), another one is proposed in this paper.

The paper is organized as follows. In Section 2, we specify the notation and state the hypotheses. In Section 3, we discuss the solutions adopted to realize condition (1.19) along the longitudinal displacement governed by the tangent step t k . On the one hand, it is detailed how Wolfe's step-size selection procedure can be used to obtain (1.19) when the displacement is done on the manifold M (y k ). On the other hand, a counter-example will show that a simple search along the direction t k cannot assure Wolfe's criteria to be satisfied in general. However, a median solution can be obtained by extending to our problem an algorithm proposed by [START_REF]A view of line-searches[END_REF] to find a Wolfe point in unconstrained optimization. Here, a change in the direction of search is made each time an unfruitful attempt to realize (1.19) is done. Therefore, the longitudinal search path becomes piecewise linear, approximating roughly an "ideal" path on the manifold M (y k ). The analysis in Section 3 is done using a penalty function having the general form (1.16). In Section 4, however, we insert the longitudinal search of Section 3 in a globally convergent algorithm by using tools that have been well developed in the specific literature since the paper by [START_REF] Han | A globally convergent method for nonlinear programming[END_REF]. In particular, we motivate our choice of a nondifferentiable augmented Lagrangian

l p (x ,µ) . . = f (x ) + µ T c (x ) + p c (x ) , (1.20)
where . is a norm on IR m , as a merit function by the necessity to have a unit longitudinal step-size asymptotically, being inspired in this respect by the work of [START_REF] Bonnans | Asymptotic admissibility of the unity stepsize in exact penalty methods I: equalityconstrained problems[END_REF]. We shall also be more specific about the transversal displacement which consists of a simple linear search from x k in the direction r k , using Armijo's technique on the same penalty function (1.20). Finally, we give a theorem showing a global convergence result for the algorithm.

Hypotheses and notation

We shall suppose that ω is a convex open set of IR n . The convexity of ω is not essential but it is assumed to discard technical problems when Taylor's theorem is used. On the other hand, assuming ω open is essential because we do not consider here a problem with general constraints or inequality constraints. ω will be the set where f and c have nice properties. Usually, it will not be possible to take ω = IR n .

We shall suppose that on ω, f and c are sufficiently smooth, three times continuously differentiable will be enough, and that their derivatives are bounded, which can be satisfied if ω is bounded and small enough. Later, we shall suppose that the sequences (x k ) and (y k ) remain in ω, so, this supposes implicitly the boundedness of these sequences. We shall also suppose that c is a submersion on ω, i.e. that A (y ) is surjective for all y in ω. This is a rather strong hypothesis but a useful one because it allows to make the decomposition of IR n at each point y of ω in Ker A (y ) = R (Z (y ) -) (see (1.6)) and Ker Z (y ) = R (A (y ) -) (see (1.8)). Using (1.6), (1.7) and (1.8), we get

I = A (y ) -A (y ) + Z (y ) -Z (y ) in IR n ×n .
(2.1)

We shall also suppose that this decomposition is made in a smooth way. More precisely, the function

y → (A (y ) -,Z (y ) -)
will be supposed twice continuously differentiable on ω and, as well as its derivatives, bounded on ω.

Because

Z (y ) = 0 I n -m A (y ) -Z (y ) --1
, the function y → Z (y ) will have the same property. This may also appear as a strong hypothesis if ω is large, but it can be satisfied in a neighborhood of a solution x * if some qualification hypothesis (A (x * ) surjective) is satisfied. On this question, we refer to [START_REF] Byrd | Continuity of the null space basis and constrained optimization[END_REF].

We shall denote by x * a solution of problem (1.1), i.e. a local minimizer satisfying the standard second order sufficient conditions of optimality (see [START_REF] Fletcher | Practical methods of optimization[END_REF], for instance). Therefore we shall suppose the existence of a Lagrange multiplier λ given in (1.13) will be supposed positive definite.

We shall denote by . any norm on IR n or IR m (and not necessarily the same norms on both spaces) and by . D the dual norm for the Euclidean scalar product, i.e.

v D . . = sup { v T u : u ≤ 1 }. The norm .
2 will denote the l 2 norm. Matrix norms will be supposed subordinated to the vector norms, i.e. A .

.

= sup { Au : u ≤ 1 }. If (u k ) k ≥0 is a sequence of vectors and (α k ) k ≥0 is a sequence of positive numbers, we shall write u k = O (α k ) when ( u k /α k ) k ≥0 is bounded and u k = o (α k ) when ( u k /α k ) k ≥0 converges to zero.
The i -th component of a vector u will be denoted by u (i ) .

The longitudinal displacement

In this section, we shall suppose that y k is a point given in ω with g (y k ) ≠ 0 (if t k = 0, there will be no longitudinal displacement) and that H k is positive definite. Therefore, if θ is given by (1.16) with φ convex, we see by (1.17) that θ ′ (y k ; t k ) is negative.

In unconstrained minimization (min ψ(u )), quasi-Newton methods locally try to approximate the Hessian of ψ at a solution u * . Therefore, the change in the gradient of ψ between two successive iterates u k and u k +1 gives some information on this Hessian. So, the vectors γ k and δ k used in the update formulae are usually taken as follows:

γ k . . = ∇ψ(u k +1 ) -∇ψ(u k ) , δ k . . = u k +1 -u k = τ k v k .
where τ k is some step-size in a descent direction v k of ψ at u k . Wolfe's step-size selection procedure consists in finding a step-size τ = τ k such that the following inequalities are satisfied:

ψ(u k +τv k ) ≤ ψ(u k ) + α 1 τ ∇ψ(u k ) T v k , (3.1) ∇ψ(u k +τv k ) T v k ≥ α 2 ∇ψ(u k ) T v k , (3.2)
where 0 < α 1 < α 2 < 1 . A step-size τ satisfying both inequalities will be called serious. Condition (3.1) ensures a sufficient decrease of ψ, while condition (3.2) prevents the step-size τ from being too small. A global convergence result can be obtained with these conditions, see [START_REF] Wolfe | Convergence conditions for ascent methods[END_REF]. An important advantage of this way of selecting the step-size in the framework of quasi-Newton methods is that condition (3.2) automatically ensures the positivity of γ k T δ k and, as a result, the positive definiteness of the updated matrices.

In reduced methods for constrained optimization, an approximation G k of G * , the projected Hessian of the Lagrangian, is updated. Here, it is the change in the reduced gradient that gives information on G * , as suggested by the following formula (see [START_REF] Stoer | Principles of sequential quadratic programming methods for solving nonlinear programs[END_REF], [START_REF] Nocedal | Projected Hessian updating algorithms for nonlinearly constrained optimization[END_REF]):

∇g (x * ) = ∇ (Z (x ) -T (∇f (x ) + A (x ) T λ * )) (x * ) = Z (x * ) -T L * , (3.3)
where we used (1.6) and the second optimality condition in (1.2). Comparing (1.13) and (3.3), we see that

G * is a part of ∇g (x *
). This is essentially due to the unfeasibility of the method, because in this case, the successive iterates do not belong to a particular manifold of dimension n -m , and any function used to get information on G * has to be defined on all IR n . Hence, if, like g , this function takes its values in IR n -m , its Jacobian is a matrix of dimension (n -m ) × n and not of order n -m , like G * . Therefore accurate information is obtained on G * if, asymptotically, the change in the reduced gradient is given for a displacement along the tangent space R (Z (x reduced secant methods, as those proposed independently by [START_REF] Nocedal | Projected Hessian updating algorithms for nonlinearly constrained optimization[END_REF] and Gilbert (1986,b and[START_REF] Ch | Mise a `jour de la me ´trique dans les me ´thodes de quasi-Newton re ´duites en optimisation avec contraintes d'e ´galite ´[END_REF]. The scheme proposed by [START_REF] Coleman | On the local convergence of a quasi-Newton method for the nonlinear programming problem[END_REF] is related, but requires the use of a multiplier estimate. Following this strategy, when the unit step-size is accepted (and it will be asymptotically), the matrix H k will be updated by the BFGS formula (1.18), with

γ k = γ k 1 and δ k = δ k 1 , where γ k 1 . . = g (x k +1 ) -g (y k ) , δ k 1 . . = Z (y k ) t k = Z (y k ) (x k +1 -y k ) .
The step δ k 1 is called the reduced longitudinal displacement. Note that another choice is possible but needs the use of an update criterion: see [START_REF] Nocedal | Projected Hessian updating algorithms for nonlinearly constrained optimization[END_REF] for the algorithm of Gabay (1982,b), and Gilbert (1986,b and 1988) for algorithm (1.9)-(1.10).

Let us show now that the condition (γ k 1

) T δ k 1 > 0 is usually satisfied asymptotically. Using (3.3) and supposing that the sequence (y k ) converges to a solution x * of (1.1) with t k → 0, we have (we use

t k = Z (y k ) -δ k 1 ): γ k 1 = Z (x * ) -T L * t k + o ( t k ) = G * δ k 1 + o ( δ k 1 ) . Hence, (γ k 1 ) T δ k 1 is positive for large k if G *
is positive definite. However, this condition (1.19) is not necessarily satisfied when y k is far from x * , even if a step-size τ is introduced to scale the tangent step t k :

γ k τ . . = g (y k +τt k ) -g (y k ) , δ k τ . . = τ Z (y k ) t k .
The following counter-example confirms this claim. . The hypotheses of Section 2 are satisfied on ω β for any β > 1. We have g (y ) =y (1) , t (y ) = H y (1) y ∼ and g (y +τt (y )) =y (1) (1+τHy (2) ). As δ τ = τ H y (1) , if we suppose y (1) and H positive, the positivity of (γ τ ) T δ τ is equivalent to g (y +τt (y )) > g (y ) , i.e.

Suppose that n = 2, m = 1, f (y ) . . = y (2) , c (y ) . . = ( y 2 2 -1)
-τ H y (1) y (2) > 0, which is never satisfied for any positive step-size τ when y (2) is also positive.

On the other hand, Wolfe's conditions may be satisfied for a certain step-size τ along a search path y k M starting from y k and belonging to the manifold M (y k ) .

. = c -1 (c (y )) (this submanifold of ω exists because c is a submersion). Let us consider, indeed, the search trajectory y k M , defined by the following ordinary differential equation (where the dot stands for a derivative according to τ): , where θ is given in (1.16) with φ convex. We obtain, by a calculation similar to the one in (1.17):

y k M (0) = y k . y . k M (τ) = Z (y k M (τ)) -Z (y k ) t k , ( 3
∇ψ(τ) = θ ′ (y k M (τ); Z (y k M (τ)) -Z (y k )t k ) = g (y k M (τ)) T Z (y k ) t k , ∇ψ(0) = θ ′ (y k ; t k ) = g (y k ) T Z (y k ) t k .
Then, rewriting Wolfe's conditions (3.1)-(3.2) with this ψ, u k .

. = 0 ∈ IR and v k . . = 1 ∈ IR , we obtain:

θ(y k M (τ)) ≤ θ(y k ) + α 1 τ θ ′ (y k ; t k ) , (3.5) g (y k M (τ)) T Z (y k ) t k ≥ α 2 g (y k ) T Z (y k ) t k . (3.6)
Considering the function τ ∈ IR → ψ(τ) ∈ IR , it is clear that there exists a positive step-size τ k such that (3.5)-(3.6) are satisfied at τ = τ k , if the solution of (3.4) exists for sufficiently large τ and if, for example, f is bounded from below on M (y k ) (see the argument in [START_REF] Wolfe | Convergence conditions for ascent methods[END_REF]). Writing inequality (3.6) at τ = τ k , we see that condition (1.19) is satisfied with γ k = γ k M and δ k given by

γ k M . . = g (y k M (τ k )) -g (y k ) , δ k . . = τ k Z (y k ) t k .
In view of the counter-example and the success of the path y k M , a possible direction of investigation could be to try to build an approximation of the path y k M , using an approximation scheme for the differential equation (3.4). But, on the one hand, it is very expensive to have an accurate approximation and, on the other hand, for any τ for which (3.6) would not be satisfied the question of the sharpness of the approximation would arise as a leitmotiv: as shown by the counter-example, the linear approximation (y k +τt k ) is sometimes inadequate, so, what about the current one? Fortunately, the situation can be sorted out by trying to satisfy both inequalities (3.5) and (3.6) in the following way.

Let us remark first that inequality (3.5) is satisfied for small positive τ along the linear path

y k 0 (τ) . . = y k +τt k (τ > 0) instead of y k M (τ): θ(y k 0 (τ)) ≤ θ(y k ) + α 1 τ θ ′ (y k ; t k ) . (3.7)
Indeed, θ ′ (y k ; t k ) is negative and α 1 is less than 1. On the other hand, by continuity and because α 2 is less than 1, the inequality corresponding to (3.6),

g (y k 0 (τ)) T Z (y k ) t k ≥ α 2 g (y k ) T Z (y k ) t k , (3.8)
is not satisfied for small positive τ along y k 0 (τ). Therefore, we may define τ k

1 . . = sup { τ ′ > 0 : \/ -τ ∈ [0 , τ ′ [ , y k 0 (τ) ∈ ω, (3.7) is satisfied and (3.8) is not satisfied }. If τ k 1 is infinite, which is not possi- ble if θ is bounded from below -see (3.7), or if y k 1 . . = y k 0 (τ k 1
) ∈ / ω, we shall consider that the algorithm has failed. Otherwise, (3.7) is satisfied at y k 1 (by continuity). Then, if (3.8) is satisfied at y k 1 (which is the only possibility in the unconstrained case), τ k 1 is a serious step-size. Otherwise, this means, by continuity,

that (3.7) is not satisfied for τ > τ k 1 in a neighborhood of τ k 1 . In this last case, θ(y k 1 ) = θ(y k ) + α 1 τ k 1 θ ′ (y k ; t k
) and the search to satisfy (3.7) and (3.8) may be pursued from y k 1 in the direction

Z (y k 1 ) -Z (y k ) t k . To see this, it is enough to remark that, if y k 1 (τ) is defined by y k 1 (τ) . . = y k 0 (τ) for 0 ≤ τ ≤ τ k 1 and y k 1 (τ) . . = y k 1 + (τ-τ k 1 ) Z (y k 1 ) -Z (y k ) t k for τ > τ k 1
, the following inequality holds:

θ(y k 1 (τ)) ≤ θ(y k ) + α 1 τ θ ′ (y k ; t k ) , for τ > τ k 1 in a neighborhood of τ k 1
. This is true because, on the contrary, we would have a sequence of

τ > τ k 1 , converging to τ k 1 , with θ(y k 1 (τ)) -θ(y k 1 ) > α 1 (τ-τ k 1 ) θ ′ (y k ; t k ) .
Dividing by (τ-τ k 1

) and taking the limit as τ tends to τ k 1 would give: ). Now, we can continue and define τ k

(θ ο y k 1 ) ′ (τ k 1 ; 1) ≥ α 1 θ ′ (y k ; t k ) > α 2 θ ′ (y k ; t k ) = α 2 g (y k ) T Z (y k ) t k . But (θ ο y k 1 ) ′ (τ k 1 ; 1) = ∇f (y k 1 ) T Z (y k 1 ) -Z (y k )t k + φ ′ (c (y k 1 ); A (y k 1 )Z (y k 1 ) -Z (y k )t k ) = g (y k 1 ) T Z (y k ) t k , because of (1.6). So, g (y k 1 ) T Z (y k ) t k > α 2 g (y k ) T Z (y k ) t k ,
2 . . = sup {τ ′ > τ k 1 : \/ -τ ∈ [τ k 1 , τ ′ [ , y k 1 (τ) ∈ ω, θ(y k 1 (τ)) ≤ θ(y k ) + α 1 τ θ ′ (y k ; t k ) and g (y k 1 (τ)) T Z (y k ) t k < α 2 g (y k ) T Z (y k ) t k }, y k 2 . . = y k 1 (τ k 2
), and so on. Therefore, the search can be pursued along a piecewise linear path, as long as a serious step-size is not met.

To obtain an implementable version of this algorithm, two questions, which constitute our program up to the end of this section, have to be clarified:

(i) the values τ k i of the step-size at which the search is reoriented are not attainable by calculation and should be redefined,

(ii) the algorithm should be shown to terminate in a finite number of iterations.

The last question will be the subject of Theorem 3.3, while for the first question, we may refer to what is done in unconstrained optimization to find a serious step-size in the sense of Wolfe. Indeed, in this case as well, if the step-size corresponding to our τ k 1 solves the problem, it is never calculated but only approximated and this is possible because there must exist a left neighborhood of τ k 1 constituted of serious step-sizes. For example, [START_REF]A view of line-searches[END_REF] has proposed an algorithm to find a serious step-size in unconstrained optimization (see also, Fletcher (1980, Section 2.6), and Dennis and Schnabel (1983, Algorithm A 6.3.1 mod, p. 328)). Let us recall it here in terms of the function ψ introduced at the beginning of the section.

Line-search Algorithm:

(3.9) 1.

τ

. . = 0 ; τ . . = ∞ ; choose ( τ > 0 ) ; 2. repeat 2.1. if ( (3.1) is not satisfied ) 2.2. then { τ . . = τ ; τ . . = INTERPOL (τ , τ ) } 2.3. else { 2.4. if ( (3.2) is satisfied ) then exit / * τ is serious * / 2.5. else { 2.6. τ . . = τ ; 2.7. if ( τ = ∞ ) then τ . . = EXTRAPOL (τ ) 2.8. else τ . . = INTERPOL (τ , τ ) 2.5. } 2.3. } ;
So, the algorithm tries to trap a step-size like τ k 1 in an interval [τ , τ ]. The step-size τ is said to be too large because it does not satisfy (3.1), hence some step-size like τ k 1 must exist in [0 , τ ]. The step-size τ is said to be too small because it is less than τ and satisfies (3.1) but not (3.2), hence some step-size like τ k 1 must exist in [τ , τ ]. The algorithm uses two functions: INTERPOL gives a step-size τ between the two finite values τ and τ and EXTRAPOL gives a step-size τ greater than τ . Some conditions on these functions are required in order to ensure the global convergence of methods using such line-search algorithm.

We shall adapt this algorithm to our situation by modifying the direction of search each time a step-size is recognized as too small. These step-sizes will constitute our new τ k i 's. Note that this change in the direction of search at a point y k i is free of charge because an inequality like (3.6) or (3.8) has to be tested at y k i and therefore the new basis Z (y k i ) -is available and the new search direction Z (y k i ) -Z (y k ) t k , as well. However, the fact to have to linearize the constraints and to compute the basis of the tangent space at each point y k i can be rather expensive for certain applications. It is therefore important to show that the unit step-size is usually accepted asymptotically. This will be done in Section 4. Then, according to our experience with the line-search algorithm (3.9) in unconstrained optimization, it is not unrealistic to expect that the unit step-size will be accepted at almost all iterations. Now, even if such is the case, the algorithm still requires two linearizations of the constraints per iteration (at y k and x k +1 ), which is more expensive than implementing an arc-search from y k to y k +1 on the penalty function using Armijo's rule as we would find in Gabay (1982,b) or Gilbert (1986,a). This technique does not however guarantee the positivity of (g (x k +1) -g (y k )) T Z (y k )t k . Therefore, it is important to generalize the algorithm presented here to reduced secant methods that require only one linearization of the constraints per iteration.

Before stating our algorithm we need to define precisely the search path and to give the properties required for the interpolation and extrapolation functions.

Being given l positive numbers: 0 = .

.

τ k 0 < τ k 1 < . . . < τ k l , (3.10)
we define by induction the points y k i and the piecewise linear trajectories y k i (τ), τ ≥ 0 for 0 ≤ i ≤ l . For i = 0, we define

y k 0 . . = y k , (3.11) y k 0 (τ) . . = y k + τ t k = y k + τ Z (y k ) -Z (y k ) t k , for τ ≥ 0 (3.12)
and for 1 ≤ i ≤ l , we define

y k i . . = y k i -1 (τ k i ) , (3.13) y k i (τ) . . = y k i + (τ-τ k i ) Z (y k i ) -Z (y k ) t k , for τ > τ k i . y k i -1 (τ) , for 0 ≤ τ ≤ τ k i , (3.14)
Therefore, if the dot stands for a right derivative, we have

y . k l (τ k i ) = Z (y k i ) -Z (y k ) t k , 0 ≤ i ≤ l .
So, the path y k l ( . ) may be seen as an explicit Euler approximation of the solution

y k M of (3.4) on [0 , τ k l ]
for the discretization (3.10) in τ. Proof. For l ≥ 1, we have y k l = y k + S l , with

S l . . = i =0 Σ l -1 (τ k i +1 -τ k i ) Z (y k i ) -Z (y k ) t k .
Because

y k i ∈ ω, (Z (y k i ) -) i ≥0 is bounded. Hence, for l 2 > l 1 , S l 2 -S l 1 ≤ C (τ k l 2 -τ k l 1 )
, where C is a positive constant independent of l 1 and l 2 . As (τ k l ) l ≥0 converges, (S l ) l ≥1 is a Cauchy sequence, hence converges in IR n . And so does (y k l ) l ≥0 .

Wolfe's criteria are then generalized as follows: find a non negative integer l , l +1 positive numbers (τ k i ) 0≤i ≤l verifying (3.10) and a τ > τ k l such that:

θ(y k l (τ)) ≤ θ(y k ) + α 1 τ θ ′ (y k ; t k ) , (3.15) g (y k l (τ)) T Z (y k ) t k ≥ α 2 g (y k ) T Z (y k ) t k , (3.16)
where 0 < α 1 < α 2 < 1 are given. See (1.17), for the value of θ ′ (y k ; t k ).

We shall need an interpolation function J :

ω × IR + → IR + . . = [0 , ∞[ such that: (y ,τ) → J (y ,τ) is continuous on ω × IR + , (3.17) \/ -y ∈ ω , \/ -τ > 0 : J (y ,τ) ∈ ]0 , τ[ , (3.18) \/ -y ∈ ω , \/ -τ > 0 : J y p (τ) → 0 as p → ∞ , (3.19)
where J y p (τ) . . = (J y ο . . (p times) . . ο J y )(τ) and J y (τ) . . = J (y ,τ). This function will be used when we shall need a new trial step-size between, say, τ k l and τ > τ k l . Then, we shall take τ ′ . .

= τ k l + J (y k l , τ-τ k l ).
By condition (3.18), τ ′ ∈ ]τ k l , τ[ (interpolation) and condition (3.19) guarantees that if the operation is repeated, the new step-sizes will be closer and closer to τ k l . We can deduce from (3.17) and (3.18), that for y ∈ ω and τ ≥ 0, J (y ,τ) = 0 if and only if τ = 0.

We shall also need an extrapolation function E : ω → IR + such that:

y → E (y ) is continuous on ω , (3.20) \/ -y ∈ ω : E (y ) > 0 . (3.21)
This function will be used when we shall need a new trial step-size greater than, say, τ k l . Then, we shall take

τ k l + E (y k l ) > τ k l .
Lemma 3.2. If (y l ) l ≥0 is a converging sequence in ω and (τ l ) l ≥0 is a bounded sequence of positive numbers such that J (y l ,τ l ) converges to zero, then τ l converges to zero.

Proof. Let y in ω be the limit point of (y l ) and (τ l ′ ) be a subsequence of (τ l ) that converges to some τ. Then, by (3.17), J (y l ′ ,τ l ′ ) → J (y ,τ) = 0, hence τ = 0 and all the sequence (τ l ) l ≥0 converges to zero.

We can now state the Longitudinal Search Algorithm:

(3.22) 1. if ( t k = 0 ) then exit ; 2. l . . = 0 ; τ k 0 . . = 0 ; choose ( τ > 0 ) ; 3. repeat 3.1. if ( ( y k l (τ) ∈ / ω ) or ( (3.15) is not satisfied ) ) 3.2. then τ . . = τ k l + J (y k l ,τ-τ k l )
converges to some y k in IR n . According to the suppositions, y k is in ω.

Let us show that

θ(y k ) = θ(y k ) + α 1 τ k θ ′ (y k ; t k ) = θ(y k ) + α 1 τ k g (y k ) T Z (y k ) t k . (3.25)
In view of (3.23) and by continuity, it is enough to prove that the left hand side of (3.25) is not less than the right hand side. For this, let us remark that there exists an integer l 0 such that for l ≥ l 0 , we have for some τ k l > τ k l +1

:

τ k l +1 = τ k l + J (y k l ,τ k l -τ k l ) . (3.26)
Indeed, for sufficiently large l , τ k l +1 is given by (3.26), i.e. by interpolation. Otherwise, we would have

τ k l +1 = τ k l + E (y k l
) for some subsequence of l 's and at the limit on those l 's, we would have, by (3.20), E (y k ) = 0, which is in contradiction with hypothesis (3.21). Now, by construction,

τ k l ≤ τ k l + E (y k l ). So (τ k l
) l ≥l 0 is also bounded. Then, the limit in (3.26) and Lemma 3.2 show that (τ k l ) l ≥l 0 converges to τ k . As

y k l (τ k l ) = y k l + (τ k l -τ k l ) Z (y k l ) -Z (y k ) t k converges to y k ∈ ω, y k l (τ k l ) ∈ ω for large l . Therefore, (3.26) means that (3.15) is not satisfied at y k l (τ k l ), i.e. θ(y k l (τ k l )) > θ(y k ) + α 1 τ k l θ ′ (y k ; t k ) .
The equality (3.25) is proved by taking the limit on l in this last inequality.

Taking the limit on l in (3.24) and using 0 < α 1 < α 2 , we see that there will be a contradiction (and therefore we shall have proved the theorem) if we show that

g (y k ) T Z (y k ) t k ≥ α 1 g (y k ) T Z (y k ) t k .
(3.27)

For this, we build a sequence (η p ) p ≥0 of positive numbers converging to zero and a sequence (z k p ) p ≥0 of points in IR n of the form (3.28) such that:

z k p . . = y k + η p Z (y k ) -Z (y k ) t k ,
z k p ∈ ω ⇒ θ(z k p ) ≥ θ(y k ) + α 1 (τ k +η p ) g (y k ) T Z (y k ) t k . (3.29)
As z k p ∈ ω for large p , (3.29) and (3.25) give for large p :

η p θ(z k p ) -θ(y k ) ≥ α 1 g (y k ) T Z (y k ) t k .
Hence, (3.27) will follow by taking the limit on p in this inequality.

The sequences (η p ) p ≥0 and (z k p ) p ≥0 are built by induction together with an increasing sequence of indices (l p ) p ≥0 such that for p ≥ 0 and l ≥ l p , either

z k p ,l . . = y k l (τ k l +η p ,l ) = y k l + η p ,l Z (y k l ) -Z (y k ) t k ∈ / ω,
where η p ,l . . = J y k l p (E (y k l )), or (3.15) is not satisfied at z k p ,l , i.e. for τ = τ k l + η p ,l . In other words, for p ≥ 0 and l ≥ l p :

z k p ,l ∈ ω ⇒ θ(z k p ,l ) > θ(y k ) + α 1 (τ k l +η p ,l ) g (y k ) T Z (y k ) t k . (3.30)
We begin with η 0 , z k 0 and l 0 . We have already seen in getting (3.26) that we may find a positive index l 0 such that for l ≥ l 0 , τ k l is obtained by interpolation, which means that either z k 0,l = y k l (τ k l +η 0,l ) ∈ / ω or (3.15) is not satisfied at z k 0,l . This is precisely (3.30) for p = 0. Similarly, for p ≥ 1, we may find an index l p ≥ l p -1 (defined by induction) such that for all l ≥ l p , either z k p ,l ∈ / ω or (3.15) is not satisfied at z k p ,l . Indeed, otherwise, l p being greater than l p -1 , we would have for a subsequence of l 's:

τ k l +1 = τ k l + J y k l p (E (y k l ))
and the limit on l , would give

(J y k ο . . (p times) . . ο J y k )(E (y k )) = 0 .
This would imply E (y k ) = 0, in contradiction with (3.21). Therefore, for l ≥ l p , (3.30) is still satisfied. As (z k p ,l ) l ≥0 converges to z k p given by (3.28) with

η p . . = J y k p (E (y k )) ,
the limit in (3.30) gives (3.29). Moreover, (η p ) p ≥0 converges to zero because of property (3.19).

Remarks 3.4. A consequence of Theorem 3.3 is that if θ is bounded below, ω = IR n and the hypotheses of the theorem are satisfied, then the longitudinal search algorithm (3.22) will find a point

x k +1 . . = y k l k (τ k )
x k +1 -y k ≤ C τ k t k , (3.31)
where C is a positive constant that depends only on a bound of Z ( . ) and Z ( . ) -on ω.

Proof. We have

x k +1 -y k = i =0 Σ l k -1 (τ k i +1 -τ k i ) Z (y k i ) -Z (y k ) t k ,
from which (3.31) follows.

The algorithm

In secant methods, it is commonly considered that a globalizing technique is successful if the unit stepsize is asymptotically accepted by the search algorithm, because then the superlinear convergence of the local method is not prevented from occurring. This means that the longitudinal search algorithm (3.22) should set l k = 0 and τ k = 1 for all sufficiently large k . In fact, this depends on three factors: the search direction t k , i.e. the matrix H k , the penalty function θ and the constants α 1 and α 2 in (3.15)-(3.16).

Because G k is updated to be a good approximation of the projected Hessian of the Lagrangian, which is a condition imposed by the local analysis, the point (y k +t k ) will be asymptotically a good approximation of a minimizer of the Lagrangian in the tangent plane y k +R (Z (y k ) -). Note, indeed, that if

G k = Z (y k ) -T L (y k ,λ) Z (y k ) -, we have t k . . = argmin { l (y k ,λ) + ∇ x l (y k ,λ) T t + t T L (y k ,λ) t /2 : t ∈ R (Z (y k ) -) }
, for any λ. Therefore, the unit step-size has some chance of being accepted if θ is close to the Lagrangian. Finally, in addition to 0 < α 1 < α 2 < 1, we need to impose the condition α 1 < 1/2, because then condition (3.15) accepts the minimum of a quadratic function.

We choose as penalty function the nondifferentiable augmented Lagrangian:

l p (x ,µ) . . = f (x ) + µ T c (x ) + p c (x ) , (4.1)
where . is a norm on IR m . This penalty function is exact, i. x ∈ ω , c (x ) = 0 }, which is equivalent to problem (1.1) or it may be directly obtained as in [START_REF] Bonnans | Asymptotic admissibility of the unity stepsize in exact penalty methods I: equalityconstrained problems[END_REF], where the penalty function (4.1) has been used in connection with the SQP method to obtain the admissibility of the unit stepsize.

Another possibility could have been to use the differentiable augmented Lagrangian, obtained by replacing p c (x ) by (p /2) c (x ) 2 2 in (4.1), which is exact if µ = λ * and if p is greater than some positive threshold p (see [START_REF] Bertsekas | Constrained optimization and Lagrange multiplier methods[END_REF], for example). The advantage of l p defined by (4.1) is that it can be exact with µ different from λ * and that the threshold for p is easy to calculate. This is important, because, as we have said it, we shall need to make l p close to the Lagrangian function. With the penalty function (4.1), this will be done simply by improving the estimate µ of λ * as the iterates progress to a solution x * and by decreasing p if necessary and if the requirement p > µ-λ * D allows it. The path from y k to x k +1 , given by Theorem 3.3, may be obtained by using l p ( . ,µ) as penalty function in algorithm (3.22). From (1.17), the directional derivative of l p with respect to x in the direction t k is given at (y k ,µ) by:

l p ′ (y k ,µ; t k ) = ∇f (y k ) T t k = g (y k ) T Z (y k ) t k . (4.2) When H k is non singular, g (y k ) = -G k Z (y k ) t k , where G k . . = H k -1
. In this case, we shall also use:

∇f (y k ) T t k = g (y k ) T Z (y k ) t k = -t k T Z (y k ) T G k Z (y k ) t k . (4.3)
Now, it remains to give conditions for the feasibility of a linear search on l p starting at x k in the direction r k . The directional derivative of l p with respect to x in the direction r k .

.

= -A (x k ) -c (x k ) is
given at (x k ,µ) by:

l p ′ (x k ,µ; r k ) = (λ(x k )-µ) T c (x k ) -p c (x k ) , (4.4)
where we used the multiplier estimate λ(x ) given in (1.15). Remark that for the derivative of the last term of (4.1), noting ν(z

) . . = z , we have (ν ο c ) ′ (x k ; r k ) = ν ′ (c (x k ); -c (x k )) = -ν(c (x k ))
, by definition of the directional derivative. Therefore, from (4.4), r k is a descent direction of l p ( . ,µ) at x k , if p > λ(x k )-µ D . This shows that p will have to be adapted sometimes in order to preserve this inequality before doing the transversal step. We shall denote by p k the value of the penalty parameter at iteration k . In the same way, we shall see that µ will have to be modified at some iterations and we shall denote by µ k its value at iteration k . Therefore, a condition to satisfy at each iteration (from x k to x k +1 ) is:

p k ≥ λ(x k )-µ k D + p k , (4.5) for 0 < a ≤ a < ∞ , S ([a , a ]) is finite , (4.11) S (a ) → 0 as a → 0+ . (4.12)
This function S will be used again in the adaptation rules for p k , p k and µ k and these properties will be useful to prove a global convergence result for the algorithm. For example, we may follow [START_REF] Bonnans | Asymptotic admissibility of the unity stepsize in exact penalty methods I: equalityconstrained problems[END_REF] and take S (a ) . . = min { 10 q : a ≤ 10 q , q integer }. Statement 4 will always succeed because inequality (4.5) will be guaranteed by the adaptation rules for p k , p k and µ k (statements 9 and 10) and because if statement 5 succeeds, the point x k is in ω. Note that if r k = 0, ρ k = 1 is always accepted in statement 4! On the other hand, statement 5 may not succeed, as described in Theorem 3.3 (ii) and commented in Remark 3.4. In order not to prevent superlinear convergence from occurring we suppose that the initial τ in the longitudinal search algorithm is chosen equal to 1. In statement 7, the inverse BFGS formula (1.18) is always well defined because, by construction, γ k T δ k is positive.

Before stating the adaptation rules for p k , p k and µ k in statements 9 and 10, we need to examine under what conditions the unit step-sizes ρ k and τ k are accepted in both the transversal and longitudinal displacements. These are the contents of the following two propositions.

Proposition 4.1. Suppose that Algorithm RSA (4.9) produces bounded sequences (µ k ) and (p k ) and a sequence (x k ) in ω that converges to a solution x * of problem (1.1). Then, we have for large k :

l p k (x k +r k ,µ k ) -l p k (x k ,µ k ) -α l p k ′ (x k ,µ k ; r k ) = (1-α) l p k ′ (x k ,µ k ; r k ) + o ( r k ) . (4.13)
Proof. For large k , the segment [x k , x k +r k ] is in ω. Then, f and c being twice differentiable on ω, Taylor's expansions give

f (x k +r k ) = f (x k ) + λ(x k ) T c (x k ) + o ( r k )
and c (x k +r k ) = o ( r k ) . Consequently, (p k ) and (µ k ) being bounded, we get (4.13).

Proposition 4.2. Suppose that Algorithm RSA (4.9) produces a bounded sequence (p k ), a sequence (x k ) in ω that converges to a solution x * of problem (1.1), a sequence (µ k ) that converges to the associated multiplier λ * and a bounded sequence of non singular reduced matrices (H k ) such that (1.12) is satisfied with G k = H k -1

. Then, we have for large k :

l p k (y k +t k ,µ k ) -l p k (y k ,µ k ) -α 1 l p k ′ (y k ,µ k ; t k ) ≤ ( 2 1 -α 1 ) l p k ′ (y k ,µ k ; t k ) + p k O ( t k 2 ) + o ( t k 2 ) , (4.14) α 2 g (y k ) T Z (y k ) t k -g (y k +t k ) T Z (y k ) t k = α 2 g (y k ) T Z (y k ) t k + o ( t k 2 ) . (4.15)
Proof. As the sequence (y k ) converges also to x * and (H k ) is bounded, the segment [y k , y k +t k ] is in ω for large k . Then, f and c being C 2 on ω, Taylor's expansions give:

f (y k +t k ) = f (y k ) + ∇f (y k ) T t k + 2 1 f ′′ (x * ) . t k 2 + o ( t k 2 ) , c (y k +t k ) = c (y k ) + 2 1 c ′′ (x * ) . t k 2 + o ( t k 2 ) .
Hence, using µ k → λ * and the boundedness of (p k ), we get

l p k (y k +t k ,µ k ) ≤ l p k (y k ,µ k ) + ∇f (y k ) T t k + 2 1 t k T L * t k + p k O ( t k 2 ) + o ( t k 2 ) .
But, as y → Z (y ) -is continuous,

t k = Z (y k ) -Z (y k ) t k = Z (x * ) -Z (y k ) t k + o ( t k
). So, with (4.3), the last inequality becomes

l p k (y k +t k ,µ k ) -l p k (y k ,µ k ) -α 1 ∇f (y k ) T t k ≤ ( 2 1 -α 1 ) ∇f (y k ) T t k -2 1 t k T Z (y k ) T (G k -G * ) Z (y k ) t k + p k O ( t k 2 ) + o ( t k 2 ) .
From this inequality, (4.2) and (1.12), we deduce (4.14).

On the other hand, as y → Z (y ) -is C 1 on ω and f is C 2 on ω, g is C 1 on ω and, by a Taylor's expansion and (3.3), we get

g (y k +t k ) = g (y k ) + Z (x * ) -T L * t k + o ( t k ) = g (y k ) + G * Z (y k ) t k + o ( t k ) .
Hence, using again (4.3) and (1.12), we obtain

g (y k +t k ) T Z (y k ) t k = g (y k ) T Z (y k )t k + t k T Z (y k ) T G * Z (y k )t k + o ( t k 2 ) = -t k T Z (y k ) T (G k -G * ) Z (y k ) t k + o ( t k 2 ) = o ( t k 2 ) ,
hence (4.15).

Propositions 4.1 and 4.2 enable us to give conditions on the admissibility of the unit step-sizes ρ k and τ k , i.e. on the non positivity of the left hand side of (4.13), (4.14) and (4.15). These conditions will guide us in the design of the adaptation rules for p k , p k and µ k .

We have r k = O ( c (x k ) ) and inequality (4.5) implies that l p k ′ (x k ,µ k ; r k ) ≤p k c (x k ) . Under this condition (4.5) and α < 1, the estimate (4.13) becomes

l p k (x k +r k ,µ k ) -l p k (x k ,µ k ) -α l p k ′ (x k ,µ k ; r k ) ≤ -(1-α) [ p k -η k ] c (x k ) ,
where η k → 0. Therefore, the step-size ρ k = 1 will be accepted asymptotically if, in addition to the hypotheses of Proposition 4.1, α < 1, (4.5) is satisfied at each iteration and (p k ) is bounded away from zero.

To exploit the estimates (4.14) and (4.15), let us remark that, under the hypotheses of Proposition 4.2, there exists constants C 1 , C 2 and C 3 (independent of k ), such that H k 2 ≤ C 1 and t k ≤ C 2 H k g (y k ) ≤ C 3 Z (y k ) t k 2 . Therefore, using (4.3) and the positive definiteness of G k , we obtain

g (y k ) T Z (y k ) t k ≤ -H k 2 -1 Z (y k ) t k 2 2 ≤ -C 1 -1 C 3 -2 t k 2 .
This shows that the left hand side of (4.15) will be negative asymptotically if, in addition to the hypotheses of Proposition 4.2, α 2 > 0 and H k is positive definite. Whereas, the left hand side of (4.14) will be negative asymptotically if, in addition to the hypotheses of Proposition 4.2, we have α 1 < 1/2, H k positive definite and p k sufficiently small. But, because p k has to satisfy inequality (4.5), this means that p k must be small enough, although nonzero as we have just seen.

On the other hand, by modifying µ k and p k , we change the merit function at each iteration, which can prevent convergence. So, we have to proceed with caution, and, as in [START_REF] Bonnans | Asymptotic admissibility of the unity stepsize in exact penalty methods I: equalityconstrained problems[END_REF], we shall change µ k and p k only when the convergence progresses sufficiently. To test convergence, we shall need (ε k is defined in statement 6 of Algorithm RSA):

ε ∼ k . . = min { ε i : 0 ≤ i ≤ k } . (4.16)
We can now make precise statements 9 and 10 of Algorithm RSA. Indices k , i and j are initialized in statement 3 of the algorithm. Index k is updated in statement 11, while indices i and j are updated in statements 9 and 10 respectively (see below).

Adaptation of p k

p k (statement 9 of Algorithm RSA): (4.17)

if ( ( ε ∼ k ≤ ε ∼ i /a 1 ) and ( ( l k ≠ 0 ) or ( τ k ≠ 1 ) ) ) then { i . . = k ; p k +1 . . = p k /
(4.20) if ( ε ∼ k ≤ ε ∼ j /a 3 ) then { j . . = k ; µ k +1 . . = λ(x k +1 ) ; p k +1 . . = S (p k +1 ) } (4.21) else { µ k +1 . . = µ k ; p k +1 . . = max (p k , S ( λ(x k +1 )-µ k +1 D +p k +1 ) } . (4.22)
We recall that the properties of function S have been given in (4.10)-(4.12). We see that, as long as ε ∼ k does not decrease sufficiently, p k and µ k are not changed; only p k can be increased by (4.22) so as to satisfy (4.5). This procedure is recommended by [START_REF] Mayne | A superlinearly convergent algorithm for constrained optimization problems[END_REF] for the globalization of SQP methods using the l ∞ exact penalty function. In our case, however, we have seen that it is necessary to have the penalty function close to the Lagrangian. Therefore, if ε ∼ k decreases sufficiently, we adapt µ k and p k in (4.21), and we decrease p k in (4.18) if, furthermore, the unit step-size is not accepted.

The next theorem shows how these rules work in case of convergence of (x k ).

Theorem 4.3. Suppose that Algorithm RSA (4.9) with the adaptation rules (4.17) and (4.20) produces a sequence (x k ) in ω converging to a solution x * of problem (1.1) and a bounded sequence of positive definite matrices (H k ). Suppose, as well, that condition (1.12) is satisfied with G k .

. = H k -1

. Then, we have ρ k = 1, l k = 0 and τ k = 1 for k large enough.

Proof. As

x k → x * , we have c (x k ) → 0, hence y k → x * , g (y k ) → 0, ε k → 0 and, by (4.21), µ k → λ *
Hence, l k = 0 and τ k = 1 for large k and from (4.19) we see that p k = p > 0, for large k . By using Proposition 4.1 (and the comments after the proof of Proposition 4.2), we see that the left hand side of (4.13) becomes negative for large k , hence ρ k = 1.

We now prove a global convergence result for Algorithm RSA.

Theorem 4.4. Suppose that Algorithm RSA (4.9) with the adaptation rules (4.17) and (4.20) produces sequences (x k ) and (y k ) in ω and a bounded sequence of positive definite matrices (H k ) with bounded inverses. Then, one of the following situations occurs:

(i) lim ε ∼ k = 0 , (ii) µ k = µ for large k , (p k ) is unbounded and λ(x k ) D → ∞ when k → ∞ in { k : p k > p k -1 } , (iii) µ k = µ for large k , p k = p for large k and either l p (x k ,µ) → -∞ or for some subsequence dist (x k ,ω c ) → 0 .
Remarks 4.5. Because the sequences (x k ) and (y k ) are generated by the algorithm, it is implicitly supposed that the longitudinal search algorithm succeeds at each iteration, which will occur if, for instance, l p is bounded below and ω = IR n (see Remarks 3.4). The situation (i) means that for a subsequence of indices k , c (x k ) → 0 and g (y k ) → 0. Therefore, if ω is bounded, there exists a subsequence of (x k ) that converges to a solution of problem (1.1). The situation (ii) means that either { x k : p k > p k -1 } is unbounded or has accumulation points x on the boundary of ω at which λ(x ) is not well defined by (1.15), for instance, because A (x ) has not full rank. In (iii), dist (x k ,ω c ) is the distance from x k to the complementary set of ω.

λ(x k ) D → + ∞ for k → ∞ in { k : p k > p k -1 } ,
which is the conclusion (ii) of the theorem.

On the other hand, if (p k ) is bounded, (4.22) and (4.11) show that p k changes finitely often. So, p k = p for large k . We prove the rest of (iii) by contradiction, supposing that l p (x k ,µ) is bounded from below and that (x k ) remains away from ω c . We have from Theorem 3.3, (4.8) and (4.5):

l p (x k +1 ,µ) ≤ l p (y k ,µ) ≤ l p (x k ,µ) .
Therefore, the sequences (l p (x k ,µ)) and (l p (y k ,µ)) converge to the same value.

According to the longitudinal displacement (i.e. to inequalities (3.15) and (3.16)), (4.2), the positive definiteness of H k and the boundedness of (H k -1 ), we have Here and below, C denotes a positive constant independent of k . From (4.23) and the convergence of (l p (y k ,µ)) and (l p (x k ,µ)) to the same value, we deduce that τ k g (y k ) 2 → 0. From (4.24), the boundedness of (H k ), the Lipschitz continuity of g (with the hypotheses of Section 2, g ′ is bounded on the convex set ω) and Proposition 3.5, we get

g (y k ) 2 ≤ C x k +1 -y k g (y k ) ≤ C τ k g (y k ) 2 .
Hence, g (y k ) → 0 . Now, from the transversal search (i.e. from (4.8)), (4.4) and (4.5), we have

l p (y k ,µ) -l p (x k ,µ) ≤ α ρ k [ (λ(x k ) -µ) T c (x k ) -p c (x k ) ] ≤ -α p ρ k c (x k ) .
Hence, ρ k c (x k ) → 0 . We are going to show that (ρ k ) is bounded away from zero. This will prove (iii) because then c (x k ) → 0 and, with g (y k ) → 0, we have ε k → 0, which gives the expected contradiction with the initial assumption (ε ∼ k ≥ ε ∼ ∞ > 0). Again, we set about it by contradiction. So, let us suppose ρ k < 1 and ρ k → 0 for k in a subsequence IK . We may consider that ρ k /β is not accepted by the line search because Armijo's criterion (4.8) is not satisfied. Indeed, otherwise it would mean that for a subsequence IK ′ of IK , x Therefore, with (4.25) and (4.5), this leads to

(1-α) β ρ k p c (x k ) < C ρ k 2 c (x k ) 2 .
Therefore ρ k c (x k ) is positive for k in IK and dividing by this factor in this inequality, we obtain a contradiction with the fact that ρ k c (x k ) → 0.

Remark 4.6. The fact that, in situation (i) of the theorem, only a subsequence of (ε k ) converges to 0 (instead of all the sequence) does not come from the hypotheses of the theorem that are rather strong. The boundedness of (H k ) and (H k -1 ) is usually enough to imply the convergence of all the sequence (ε k )

to zero, as this may be also observed in unconstrained optimization, see Wolfe (1969, Theorem 1). But it comes from the way the convergence is checked in statements 9 and 10 of the algorithm, using the nonincreasing sequence (ε ∼ k ) k ≥0 defined in (4.16). Indeed, suppose that, instead of being calculated by (4.16), ε ∼ k is given by ε ∼ k . . = Φ ( { ε i : 0 ≤ i ≤ k } ) , (4.26)

The technique used here to maintain the positive definiteness of the matrices H k may be seen as a generalization to equality constrained optimization of Wolfe's step-size selection procedure in unconstrained optimization. It is well known that this technique cannot be used in the framework of quasi-Newton or SQP methods. As the technique works well in unconstrained optimization, this may be seen as an advantage of the reduced framework over the SQP methods. However, the algorithm proposed here always requires at least two (and exactly two, asymptotically) linearizations of the constraints for each superlinear step, which can be an important overcost in some applications. Therefore, the developed technique should be extended to those reduced methods that require only one linearization of the constraints per iteration.

As mentioned in the text, a weak point of the algorithm lies in the way the multipliers and the penalty parameters are adapted to improve the penalty function. Indeed, it requires from the algorithm to feel the closeness of a solution and therefore impoverishes the global convergence result (see Remark 4.6). We think that some progress might be obtained on this topic as well.

  according to x of the Lagrangian l (x ,λ) . . = f (x ) + λ T c (x ) evaluated at (x

  /2 and take ω = ω β . . = βB \ β -1 B with β > 1; B denotes the unit open ball. For these data, the unique solution of problem (1.1) is y * (1) = 0 and y * (2) = -1. We have A (y ) = y T . At any point in ω β , we may use the following orthogonal decomposition of IR 2 : A (y ) -. . = y / y 2 2 , Z (y ) -. . = y ∼ , where y ∼ (1) . . = y (2) and y ∼ (2) . . =y (1) . To these choices corresponds a unique matrix Z (y ) satisfying (1.7) and (1.8): it is given by Z (y ) = y ∼T / y 2 2

  .4) If we multiply to the left both sides of (3.4) by A (y k M (τ)), we see that y k M (τ) ∈ M (y k ). Let us introduce the function ψ . . = θ ο y k M

Lemma 3. 1 .

 1 If (τ k l ) l ≥1 is an increasing sequence of positive numbers that converges to some τ k and if (y k l ) l ≥0 , defined by(3.11)-(3.14), remains in ω, then (y k l ) l ≥0 converges in IR n .

  satisfying both inequalities (3.15) and (3.16). The situations in which the longitudinal search algorithm fails are similar to those posing problem to algorithm (3.9) for finding Wolfe points in unconstrained optimization. The first situation of Theorem 3.3 (ii) corresponds to the case where a local minimum of an unbounded from below function f is searched. With the notation from the beginning of the section, the second situation of Theorem 3.3 (ii) corresponds to the case where the objective function ψ : ]0 , ∞[ → IR has positive derivative and negative curvature on, say ]0 , 1[. If u k ∈ ]0 , 1[, algorithm (3.9) will search in ]0 , u k [, where no Wolfe point can be found(Lemare ´chal (1984)). The algorithm we propose cannot face correctly such situations, either.Below, we shall need the following inequality. Proposition 3.5. With the hypotheses of Theorem 3.3, if starting from a point y k in ω, the longitudinal search algorithm (3.22) gives a point x k +1 in ω and a step-size τ k , we have

  e. a solution x * of problem (1.1) is a local minimizer (here strict) of l p ( . ,µ), if p > µ-λ * D , where λ * is the multiplier associated to x * and . D is the dual norm of . on IR m . This result may be derived as a variant of a result of Han and Mangasarian (1979) by considering the problem min { f (x ) + µ T c (x ) :

  Proof of Theorem 4.4. Let us suppose that situation (i) does not occur. Then, lim ε ∼ k . . = ε ∼ ∞ > 0 and, by (4.19) and (4.22), p k = p for large k , µ k = µ for large k and (p k ) is a nondecreasing sequence for large k . Then, either (p k ) is unbounded or (p k ) is bounded! In the first case, this means by (4.22) and (4.10) that ( λ(x k ) D ) is unbounded, and more precisely,

  l p (x k +1 ,µ)l p (y k ,µ) ≤ α 1 τ k l p ′ (y k ,µ; t k ) = -α 1 τ k g (y k ) T H k g (y k ) ≤ -α 1 τ k H k -1 2 -1 g (y k ) 2 2 ≤ -α 1 τ k C g (y k ) 2 , (4.23) (g (x k +1 )g (y k )) T Z (y k ) t k ≥ (1-α 2 ) g (y k ) T H k g (y k ) ≥ (1-α 2 ) C g (y k ) 2 .(4.24)

  ∼ k . . = x k + (ρ k /β) r k ∈ / ω for k ∈ IK ′ . But ρ k c (x k ) → 0 implies that (ρ k /β) r k → 0 ((A (x k ) -) is bounded) and therefore (x k ) k ∈ IK ′ would go closer and closer to a point x ∼ k not in ω, a situation that has been discarded by hypothesis. So, for k in IK , we havel p (x k + β ρ k r k ,µ)l p (x k ,µ) > α β ρ k [ (λ(x k )-µ) T c (x k )p c (x k ) ] . (4.25) Expanding l p (x k + β ρ k r k ,µ) about x k gives l p (x k + β ρ k r k ,µ) ≤ f (x k ) + β ρ k λ(x k ) T c (x k ) + ρ k 2 C r k 2 + µ T c (x k )β ρ k µ T c (x k ) + p (1β ρ k ) c (x k ) ≤ l p (x k ,µ) + β ρ k [ (λ(x k )-µ) T c (x k )p c (x k ) ] + ρ k 2 C r k 2 .

.

We begin with the longitudinal displacement. Suppose that l k ≠ 0 or τ k ≠ 1 infinitely often. Then, by (4.18), we would have p k → 0 and by (4.21), (4.22) and (4.12), p k → 0. Therefore, using Proposition 4.2 (and the comments after its proof), we see that the left hand sides of (4.14) and (4.15) become negative for large k , and therefore l k = 0 and τ k = 1 for large k : a contradiction.

Acknowledgment

It is a pleasure for me to thank C. Lemare ´chal and J. F. Bonnans for various helpful conversations and the referees for their very careful reading of the manuscript and for their valuable comments and suggestions.

* Work supported by the FNRS (Fonds National de la Recherche Scientifique) of Belgium.

3.3.

else { 3.4.

if ( (3.16) is satisfied ) 3.5.

then { τ k . . = τ ; l k . . = l ; exit } / * τ is serious * / 3.6. else { l . . = l +1 ; τ k l . . = τ ; τ . . = τ k l + E (y k l ) }

} ;

In statement 2, the choice τ = 1 is recommended if the algorithm is used within the context of secant methods because in this case the unit step-size is essential to obtain superlinear convergence. We have added in statement 3.1 another reason to decrease τ: the points y k l must belong to ω. Therefore a serious step-size may not be found because ω is too small and the algorithm may loop in statement 3. This is one of two reasons for looping (see the other one in the theorem below).

Let us remark that the algorithm will not cycle between statement 3.1 and 3.

We have seen that the search path y k l ( . ) is an Euler approximation of the solution of (3.4). From the way the discretization points τ k i are built by the algorithm above, we see that this approximation will be accurate if τ in statement 2 is chosen "small" and if \/ y ∈ ω, E (y ) is "small". However, doing this is expensive and, in fact, useless because building a good approximation of y k M is not the aim of the algorithm.

We now give the main result of this section, which shows that, apart from some pathological situations, a serious step-size is found in a finite number of iterations. Proof. Clearly, by the remark preceding the theorem, if a finite number l k of points y k l are calculated, this means that a step-size τ k has been found in statement 3.5 and that y k l k (τ k ) satisfies (3.15) and

(3.16). So let us suppose the contrary, i.e. that a sequence (y k l ) l ≥0 is built in ω. Let us suppose also that the sequence (θ(y k l )) l ≥0 is bounded from below and that (y k l ) l ≥0 does not converge to a point on the boundary of ω. We have to prove that these suppositions give a contradiction.

For all l , we have by construction: where p k is some positive number.

Let ρ k denote the step-size along the transversal displacement r k :

We shall determine ρ k by [START_REF] Armijo | Minimization of functions having Lipschitz continuous first partial derivatives[END_REF] procedure. Two parameters, α and β, are chosen in ]0 , 1[ and ρ k is taken in the form

where b k is the smallest non negative integer such that We can now outline our reduced secant algorithm.

Algorithm RSA: (4.9) 1.

Choose the constants:

Choose a point x 0 in ω and H 0 , a symmetric positive definite matrix of order n -m . 3.

Calculate λ(x 0 ) by (1.15), choose p 0 > 0, set µ 0 . . = λ(x 0 ) and p 0 . . = S (p 0 ) and set the indices k .

. = 0 (iterations), i . . = 0 (adaptation of p k ), j . . = 0 (adaptation of p k and µ k ).

4.

Select a transversal step-size ρ k by Armijo's procedure (4.7)-(4.8) and set y k . . = x k + ρ k r k .

5.

Execute the longitudinal search algorithm (3.22), starting with τ = 1 and using the penalty function l p k ( . ,µ k ) instead of θ( . ) in (3.15) to determine a step-size τ k and a point x k +1 , if possible.

6.

Calculate

Calculate λ(x k +1

) by (1.15). 9.

Adapt

. = k +1 and go to statement 4.

The algorithm calls for some comments. In statement 1, ε is a positive convergence threshold and is used in statement 6. The positive constants a 1 , a 2 and a 3 will be used in the adaptation rules for p k , p k and µ k (statements 9 and 10) given below. In statement 2, H 0 can be chosen as the identity matrix but this does not take into account the scaling of the problem. Therefore, a possible choice is to take H 0 = I in the first longitudinal search (statement 5) and to calculate H 1 by updating h 0 I rather than I , where h 0 .

. = γ 0 T δ 0 / γ 0 T γ 0 . This term minimizes in h the condition number of BFGS (hI ,γ 0 ,δ 0 ), the inverse BFGS update of h I (see [START_REF] Oren | Optimal conditioning of self-scaling variable metric algorithms[END_REF]), and seems to give good numerical results (see Shanno and Phua (1978)). In statement 3, p 0 should be taken large enough and the function S : ]0 , ∞[ → ]0 , ∞[ is supposed to satisfy the following properties: (4.10) where the function Φ is such that, for any sequence

The function min in (4.16) is just an example of such Φ. Then, it can be shown that Theorems 4.3 and 4.4 remain true. Therefore, we would have a better convergence result in Theorem 4.4 (i), if it were possible to find a function Φ such that we have also

Unfortunately, this is not possible. To see this, let us consider the following algorithm where

}

Let us show that if Φ satisfies (4.27), the sequences (ε k ) and (ε ∼ k ) generated by this algorithm are such that (ε k ) does not converge to zero and ε ∼ k → 0. Therefore, Φ does not satisfy (4.28). The sequence (ε ∼ k ) converges to zero, because, otherwise, (ε ∼ k ) being nonincreasing, there would exist a positive integer l 0 such that ε ∼ k ≥ 1/l 0 , \/ k ≥ 0, which would mean that statement 2.4 is executed at most l 0 times. Therefore, for large k , statement 2.3 would be executed and ε k → 0, which would be in contradiction with (4.27). Therefore, ε ∼ k → 0. But then, statement 2.4 is executed infinitely often, so (ε k ) does not converge to zero.

Conclusion

We have presented an algorithm for equality constrained optimization of the reduced type in which the projected Hessian of the Lagrangian is approximated by updating at each iteration a matrix H k using the BFGS formula and two vectors: γ k , the change in the reduced gradient, and δ k , the corresponding reduced displacement.

The main purpose of the paper has been to show the possibility of obtaining the positivity of γ k T δ k , which is essential to guarantee the positive definiteness of the reduced matrices H k . This feature is due to a particular design of the longitudinal displacement which minimizes the objective function f while roughly maintaining constant the value of the constraint function c . For this, we introduce a step-size τ k scaling the reduced displacement in IR n -m , while the longitudinal displacement in IR n becomes piecewise linear. Wolfe's criteria are used to determine the step-size τ k .

The algorithm is made globally convergent by using a nondifferentiable augmented Lagrangian function. Another feature of the algorithm is to separate completely the longitudinal and transversal displacements: the step-sizes of both displacements are determined by two different searches on the penalty function.