Journal of Convex Analysis Volume 2 (1995), No.1/2, 41–57

Quadratic Growth and Stability in Convex Programming Problems with Multiple Solutions

J. Frédéric Bonnans

INRIA-Rocquencourt, Domaine de Voluceau, B.P. 105, 78153 Rocquencourt, France. e-mail: frederic.bonnans@inria.fr

Alexander D. Ioffe^{1}

Department of Mathematics, Technion Israel Institute of Technology, Haifa 3200 - Israel. e-mail: ioffe@techunix.technicon.ac.il

Received 9 June 1994 Revised manuscript received 23 February 1995

Dedicated to R. T. Rockafellar on his 60th Birthday

Given a convex program with C2 functions and a convex set S of solutions to the problem, we give a second order condition which guarantees that the problem does not have solutions outside of S. This condition is interpreted as a characterization for the quadratic growth of the cost function. The crucial role in the proofs is played by a theorem describing a certain uniform regularity property of critical cones in smooth convex programs. We apply these results to the discussion of stability of solutions of a convex program under possibly nonconvex perturbations.

Keywords : Convexity, Lagrangian, composite functions, critical cone, quadratic growth, stability, multiple solutions.

1. Introduction

It is well known that in nonlinear programming problems with qualified constraints the standard second order sufficient condition is equivalent to the following estimate for the cost function f_{0} on the feasible set:

f_{0}(x) ≥ f_{0}(x) + r · dist^{2}(x, x_{∗}), ∀x in a neighborhood of x_{∗}

where r > 0 and x_{∗} is the solution (e.g. [2]). The latter property which we call the second order growth condition can easily be extended to problems without constraint qualification and with multiple non–isolated solutions. In either case the second order growth condition

1 Supported by the US–Israel Binational Science Foundation grant no. 90–00455

ISSN 0944-6532 / $ 2.50 ◯^{c} Heldermann Verlag

42 J. F. Bonnans, A. D. Ioffe / Quadratic growth and stability

is instrumental in obtaining many important results of sensitivity analysis (e.g. estimates for directional derivatives of the value function or for Hölder stability of solutions) [3, 4, 10, 15]. However, if the problem has a solution set with non-isolated points, no simple characterization of the growth condition is known (see [2] for details), except in the case of linearly independent gradients of active constraints [18]. The purpose of this paper is to show that at least for one important class of problems, namely problems of smooth convex programming, a simple second order characterization of the growth condition can be given. This characterization seems to be new and of an interest. It is well known furthermore that to get Lipschitz stability of solutions of the perturbed problem a strengthening of the standard second order sufficient condition is needed in the regular case (qualified constraints and an isolated solution) [5, 15]. It was shown in [10] that this strengthened second order condition can also be expressed in terms of a “strong” second order growth condition that can be likewise extended to non–qualified problems with non–isolated solutions. We show further in this paper that in smooth convex problems (with arbitrary, not necessarily convex, dependence on the parameter) a simple second order characterization exists also for the strong growth condition. As in [2] we start with the problem of minimizing the function

f(x) := max_{1≤i≤m} f_{i}(x),

where x ∈ IR^{n}. Let S denote a compact set of minimum points of f : S ⊂ argmin f. We assume that S ≠ ∅ and denote by c the minimal value of f. We say that f satisfies the quadratic growth condition on S if

∃β > 0 : f(x) ≥ c + β dist(x, S)^{2}, ∀x in a neighborhood of S.  (QGC)

Of course, if (QGC) holds, then, at least locally, S coincides with the set of minima of f. The main result (Theorem 2.3) gives a complete characterization of (QGC) in case when all functions are convex and twice continuously differentiable. The theorem is stated in section 2 and proved in section 5. In section 3 we consider problems depending on a parameter and prove Theorem 3.4 containing a characterization for the strong growth condition. In section 4, on the way to the proof of Theorem 2.3, we establish an estimate to the set of solution of a system of linear inequalities a_{i}(x) · h ≤ 0 in case when a_{i}(x) are gradients of convex C^{1} functions. This result, for this specific case, extends the well known Robinson’s estimate for the distance to a parametrically dependent set of solutions of linear inequalities [13] in the sense that no regularity (Mangasarian-Fromovitz, or Slater) assumption at the reference point is made. Finally in section 6 we consider constrained optimization problems and state the analogues of the two main theorems in this case.

2. Characterization of quadratic growth

From now on we assume that S is a convex compact set and that f_{i}(x), i = 1, ⋯, m are convex. We denote by φ′(x; d) the directional derivative of φ at x along the direction d and by S^{m} the standard simplex of IR^{m}, i.e.

S^{m} := {λ ∈ IR_{+}^{m} ; ∑_{i=1}^{m} λ_{i} = 1}.

We start by introducing some basic notation and recalling some known facts. With each x ∈ S, we associate the collection of active indices

I(x) := {i = 1, ⋯, m : f_{i}(x) = f(x)},

the critical cone at x

C(x) := {d ∈ R^{n} : f′_{i}(x; d) ≤ 0, ∀i ∈ I(x)},

the contingent cone to S at x (the lim sup is taken in the sense of Painlevé-Kuratowski)

T_{S}(x) := lim sup_{t↓0} t^{−1}(S − x),

and the set of Lagrange multipliers:

Λ(x) := {λ ∈ S^{m} : λ_{i} = 0, i ∉ I(x), ∑_{i=1}^{m} λ_{i}f′_{i}(x; d) ≥ 0, ∀d ∈ IR^{n}}.

The Lagrangian associated with f is

L(x, λ) := ∑_{i=1}^{m} λ_{i}f_{i}(x).

As S is convex, the set T_{S}(x) coincides with the tangent cone to S at x in the sense of convex analysis, which is the collection of vectors d such that dist(x + td, S) = o(t) when t ↘ 0. As all functions f_{i} are convex, the condition ∑ λ_{i}f′_{i}(x; d) ≥ 0, ∀d ∈ IR^{n}, is equivalent to the fact that L(., λ) attains its minimum at x. For any convex set D we denote by aff D and ri D the affine hull and relative interior of D, and by rbD its relative boundary : rbD := D\ ri D. The two propositions that follow contain known facts. We prove them mainly because the proofs are short and useful for further discussions.

Proposition 2.1. (e.g. [12]) Let D be a convex set on which the convex function φ is constant. If x ∈ ri D, then ∂φ(x) ⊂ ∂φ(u) for any u ∈ D. In particular, ∂φ(x) is constant over ri D.

Proof. Given x ∈ ri D, y ∈ ∂φ(x) and u ∈ D, we have φ(u) − φ(x) ≥ y · (u − x), i.e. y · (u − x) ≤ 0. This being valid for all u ∈ D, as x ∈ ri D, we must have y · u = y · x. It follows that, for any x′ ∈ IR^{n}

φ(x′) − φ(u) = φ(x′) − φ(x) ≥ y · (x′ − x) = y · (x′ − u),

i.e. y ∈ ∂φ(u). We have proved that ∂φ(x) ∈ ∂φ(u). As x ∈ D, it follows that ∂φ(x) = ∩_{u∈D}∂φ(u) is constant over ri D.

Proposition 2.2. Let the functions f_{i} be convex and let S be a convex set on which f is constant. Then there are sets I, C and T such that, for all x ∈ ri S:

I(x) = I, C(x) = C, T_{S}(x) = T.

Proof. We first prove that when x ∈ ri S, then I(x) = ∩_{x′∈S}I(x′). Indeed, assume that i ∈ I(x) and i ∉ I(x′) for some x′ ∈ S, then f′_{i}(x, x′ − x) ≤ f_{i}(x′) − f_{i}(x) < 0. It follows that f′_{i}(x, x − x′) > 0, in contradiction to the fact that f(x) = max_{i≤1≤n} f_{i}(x) is constant on some segment [x, x + ϵ(x − x′)] with ϵ > 0. We prove that C(x) is constant on ri S. Pick i ∈ I, it follows from Proposition 2.1 that ∂f_{i}(x) is constant over ri S. Consequently, f′_{i}(x; .) is constant over ri S, whence C(x) is itself constant over ri S. For T_{S}(x) the statement is trivial: at every x ∈ ri S this is the linear subspace parallel to aff S.

It is well known (e.g. [14]) that Λ(x) does not actually depend on x, that is, there exists Λ such that, for all x ∈ S

Λ(x) ≡ Λ.

This can be easily verified if all functions f_{i} are continuously differentiable. Indeed, by Propositions 2.1 and 2.2 this is true for x ∈ ri S. It is clear furthermore that x ↦ Λ(x) is an u.s.c. set-valued map, so it remains to check that λ_{j} = 0 whenever x ∈ S and j ∈ I(x)\I. Pick x′ ∈ ri S : we have f′_{j}(x, x′−x) ≤ f_{j}(x′)−f_{j}(x) < 0. As f′_{i}(x, x′−x) = 0 for i ∈ I, we conclude that the inequality ∑ λ_{i}f′_{i}(x, x′ −x) ≥ 0 may hold for a λ = (λ_{1}, ⋯, λ_{m}) ∈ Λ(x) only if λ_{j} = 0 for j ∈ I(x)\I.

We can now formulate the main theorem. Set

φ_{x}(d) := max_{λ∈Λ} ∇_{x}^{2}L(x, λ)(d, d).

This function is strongly related to the second-order variation of the cost along a critical direction (see Section 4). Define the normal cone to S at x, which is the polar of T_{S}(x), and (for ε > 0) the set of approximate normal and critical directions as

N_{S}(x) := {v : v · d ≤ 0, ∀d ∈ T_{S}(x)},
N_{S}^{ε}(x) := {v : dist(v, N_{S}(x)) ≤ ε∥v∥},
C^{ε}(x) := {h : dist(h, C(x)) ≤ ε∥h∥}.

Theorem 2.3. Let S be a non–empty convex compact set on which f attains its minimum. Assume that all functions f_{i} are convex and twice continuously differentiable. Then the following properties are equivalent:

(i) (QGC) holds. (ii) There exists β > 0 such that

φ_{x}(d) ≥ β dist(d, T_{S}(x))^{2}, ∀x ∈ S, ∀d ∈ C(x)\T_{S}(x);

(iii) There exists β > 0 such that, for all ε ∈ (0, 1)

φ_{x}(d) ≥ (1 − ε)^{2}β∥d∥^{2}, ∀x ∈ S, ∀d ∈ C(x) ∩ N_{S}^{ε}(x).

(iv) There exist β > 0, ε > 0 such that

φ_{x}(d) ≥ β∥d∥^{2}, ∀x ∈ S, ∀d ∈ C^{ε}(x) ∩ N_{S}(x).

By Theorem 2.3, the condition below is necessary for quadratic growth:

φ_{x}(d) > 0, ∀d ∈ C(x)\T_{S}(x), ∀x ∈ S.  (2.1)

This condition, in turn, implies a first-order geometric condition on S, which is therefore itself a necessary condition for quadratic growth.

Proposition 2.4. Under the assumption of Theorem 2.3 except for the compactness of S, the condition (2.1) implies

(i) C(x)\T_{S}(x) ⊂ C\T, ∀x ∈ S. (ii) I(x)\I ≠ ϕ on rb S.

Proof. (i) Assuming the contrary, we find x ∈ S and d ∈ C(x)\T_{S}(x) with d ∉ C\T. As C(x) ⊂ C, it follows that d must belong to T \T_{S}(x). Take a sequence of x^{k} ∈ ri S converging to x. As d ∈ T, we have φ_{x^{k}}(d) = 0, hence φ_{x}(d) = lim φ_{x^{k}}(d) = 0 in contradiction with (2.1). (ii) If S is a singleton, then the relation is trivially true as rb S is empty. Otherwise pick u ∈ ri S, x ∈ rb S, and set d := x − u. It is clear that d ∈ T \T_{S}(x); hence d ∉ C\T. If I(x) = I, then C(x) = C ⊃ T, whence d ∈ C(x)\T_{S}(x), in contradiction with (i).

From (ii) we deduce in particular that if f is a C^{2} function, and its set of minima S satisfies the quadratic growth condition, then rb S is empty, which means that S is an affine space.

3. Parametric problems

We consider the family of problems

min_{x∈IR^{n}} f(x, θ)  (P_{θ})

where x ∈ IR^{n}, θ ∈ IR_{+} and f(x, θ) := max_{i=1,···,m} f_{i}(x, θ), with each f_{i}, i = 1, ⋯, m of class

C^{2}. We view (P_{θ}), for θ > 0, as a perturbation of the original problem (P_{0}). With (P_{θ}) is associated the Lagrangian

L(λ, x, θ) := ∑_{i=1}^{n} λ_{i}f_{i}(x, θ).

We denote by v(θ), S(θ) the value function and the set of solutions of (P_{θ}).

We say that a mapping θ ↦ x(θ) : IR_{+} → IR^{n}, is an ε(θ)-optimal path if f(x(θ), θ) ≤ v(θ) + ε(θ). Here ε(θ) may take the value o(ε), O(ε^{2}), etc.. Similarly, we say that a sequence {x_{n}} is ε(θ_{n})-optimal, where θ_{n} ↘ 0, if f(x_{n}, θ_{n}) ≤ v(θ_{n}) + ε(θ_{n}). Denote

μ := min_{x∈S} max_{λ∈Λ} L_{θ}(λ, x, 0),

Λ̄(x) := {λ ∈ Λ : L_{θ}(λ, x, 0) ≥ μ},

where L_{θ} is the derivative of L with respect to the parameter. Let further S̄ be the collection of points at which the above minimum is attained, that is

\overline{S} := argmin_{x∈S} max_{λ∈Λ} L_{θ}(λ, x, 0).

As \overline{S} is the set of minima of a continuous function over a compact set, it is nonempty and compact.

Proposition 3.1. (Gol’stein [6]) Assume that S(θ) is non empty and uniformly bounded for θ close to 0. Then the value function v(θ) := inf_{x∈IR^{n}} f(x, θ) has a right derivative at 0 that is equal to μ. In addition, every ε(θ_{n})-optimal sequence {x_{n}} is bounded and all its limit points belong to \overline{S}.

The following standard estimate will be useful later.

\{ \begin{matrix}There exists a > 0 such that, if θ > 0 is small enough \\ v(θ) ≤ v(0) + μθ + aθ^{2}. \end{matrix}  (3.2)

We say (cf. [10]) that the strong quadratic growth condition is satisfied if

\{ \begin{matrix}There exists β > 0, γ > 0 such that, if (x, θ) \\ is sufficiently close to \overline{S} × \{0\}, θ ≥ 0, then \\ f(x, θ) ≥ v(0) + μθ + β dist^{2}(x, S) − \frac{γ}{2} θ^{2}. \end{matrix}  (SQG)

Proposition 3.2. [10] If the strong quadratic growth condition holds, then any O(θ^{2})- optimal path x_{θ} satisfies dist(x_{θ}, S) = O(θ).

Proof. Combining (SQG) and (3.2), we get

β dist^{2}(x_{θ}, S) ≤ (a + γ)θ^{2} + O(θ^{2}) = O(θ^{2}),

from which the conclusion follows.

We observe that (SQG) can be interpreted as a quadratic growth condition for an auxiliary problem. Indeed, (SQG) is obviously equivalent to

f(x, θ) − μθ + γθ^{2} − v(0) ≥ βdist^{2}(x, S) + \frac{γ}{2} θ^{2}.

It follows that S := S ×{0} is the set of local minima of the quantity at the left-hand-side of the above inequality over IR^{n} × [0, ∞[ or, equivalently, S is the set of local minima of

f(x, θ) := max(f(x, θ) − μθ + γθ^{2} − v(0), −θ).

In order to state second order conditions we compute the critical cone and set of Lagrange multipliers associated with the problem of minimizing f.

Lemma 3.3. The set S := S × {0} is a set of local minima of the function f(x, θ) with common value zero. The critical cone associated with (x, 0) ∈ S is is defined by

C(x) = {(d, η); f′(x, 0)(d, η) − μη = 0; η ≥ 0},  (3.3)

and the set of Lagrange multipliers Λ(x) is defined by

Λ(x) = {(αλ̂, 1 − α) : λ̂ ∈ Λ̄(x) ; α = (L_{θ}(λ̂, x) − μ + 1)^{−1} ∈ (0, 1]}.

Proof. The critical cone is the set of directions in which the directional derivative of the cost is null, and is easily checked to be characterized by (3.3). Writing the optimality system, we find that the Lagrange multipliers satisfy

\{ \begin{matrix}Σ_{i=1}^{m}λ_{i}∇_{x}f_{i}(x, 0) = 0, \\ Σ_{i=1}^{m}λ_{i} ( \frac{∂f_{i}}{∂θ} (x, 0) − μ ) − ξ = 0, \\ Σ_{i=1}^{m}λ_{i} + ξ = 1, \\ λ ≥ 0, ξ ≥ 0, λ_{i}(f_{i}(x_{i}, 0) − v_{0}) = 0, \end{matrix}  (3.4)

where ξ is the multiplier associated with the constraint −θ ≤ 0. Set α := Σ_{i=1}^{m}λ_{i}. It follows from the second and third relations above that 0 < α ≤ 1. Rewrite the three first relation as

\{ \begin{matrix}∇_{x}L(λ, x) = 0, \\ L_{θ}(λ, x) − μα = ξ, \\ α + ξ = 1. \end{matrix}  (3.5)

Then ξ = 1 − α and

λ̂ := λ/α ∈ Λ and α(L_{θ}(λ̂, x) − μ) = ξ ≥ 0,

i.e. in fact λ̂ ∈ Λ̄(x); the result follows.

Note that for all x ∈ S, C(x) ⊃ C(x) × {0} and

\begin{matrix}x ∈ \overline{S} ⇒ & Λ(x) = Λ̄(x) × \{0\}, \\ x ∈ S\\overline{S} ⇒ & C(x) = C(x) × \{0\}. \end{matrix}

Our next result gives a characterization of (SQG) in terms of the second-order expansion of the data, even if the data are not jointly convex with respect to x and θ. Define

φ̄_{x}(d) := max_{λ∈Λ̄(x)} ∇_{x}^{2}L(λ, §, ′)(⌈, ⌈).

We say that the strong second-order condition is satisfied if

\{ \begin{matrix}There exist β > 0, ε > 0 such that \\ φ̄_{x}(d) ≥ β∥d∥^{2}, ∀x ∈ S̄^{ε}, ∀d ∈ C^{ε}(x) ∩ N_{S}(x), \end{matrix}  (SSOC)

where \overline{S}^{ε} = \{x ∈ S : d(x, \overline{S}) ≤ ε\}. We observe that, as φ̄_{x}(d) ≤ φ_{x}(d), (SSOC) implies (QGC). If S is a singleton, then (SSOC) reduces to the strong second-order condition of Shapiro [15].

Theorem 3.4. Conditions (SSOC) and (SGQ) are equivalent.

Proof. We prove first that (SSOC) implies (SGQ). If (SQG) does not hold, then there exists x_{n} → x ∈ \overline{S}, θ_{n} ↓ 0 with

f(x_{n}, θ_{n}) < v(0) + μθ_{n} + \frac{1}{n}dist(x_{n}, S)^{2} − nθ_{n}^{2}.  (3.6)

Let u_{n} be the projection of x_{n} onto S and d_{n} := θ_{n}^{−1}(x_{n} − u_{n}). Case 1. θ_{n} = o(dist(x_{n}, S)), for a subsequence. Extracting this subsequence if necessary we may assume that this relation holds for the entire sequence so that ∥d_{n}∥ → ∞. From Theorem 4.1 we deduce that given any ε > 0, d_{n} ∈ C^{ε}(u_{n}), u_{n} ∈ S^{ε} for n large. As ∥d_{n}∥ → ∞ we have for all λ ∈ Λ̄(u_{n})

f(x_{n}, θ_{n}) ≥ L(λ, x_{n}, θ_{n})
= L(λ, u_{n}, 0) + θ_{n}L_{θ}(λ, u_{n}, 0)

+ \frac{θ_{n}^{2}}{2} ∇_{x}^{2}L(λ, u_{n}, 0)d_{n}d_{n} + o(θ_{n}^{2}∥d_{n}∥^{2}).

As λ ∈ Λ̄(u_{n}) we have L_{θ}(λ, u_{n}, 0) ≥ μ, so that

f(x_{n}, θ_{n}) ≥ v(0) + θ_{n}μ + \frac{θ_{n}^{2}}{2} ∇_{x}^{2}L(λ, u_{n}, 0)d_{n}d_{n} + o(θ_{n}^{2}∥d_{n}∥^{2}).

Maximizing over λ ∈ Λ̄(u_{n}) we get with (3.6), as dist(x_{n}, S)/θ_{n} = ∥d_{n}∥,

φ̄_{u_{n}}(d_{n}) ≤ \frac{1}{n}∥d_{n}∥^{2} − n + o(∥d_{n}∥^{2}),

a contradiction with (SSOC).

Case 2. θ_{n} = O(dist(x_{n}, S)). Then

f_{i}(x_{n}, θ_{n}) = f_{i}(u_{n}, 0) + θ_{n} \frac{∂f_{i}}{∂θ} (u_{n}, 0)(d^{n}, 1) + O(θ_{n}^{2}),

hence

f(x_{n}, θ_{n}) ≥ max_{λ∈Λ} L(x, λ, θ_{n}),
≥ v(0) + θ_{n} max_{λ∈Λ} L′(u_{n}, λ, 0)(d^{n}, 1) + O(θ_{n}^{2}),
≥ v(0) + θ_{n}μ + O(θ_{n}^{2}),

in contradiction with (3.6) (in which we use dist(x_{n}, S) = O(θ^{n})).

This proves the implication. To prove the inverse implication (SGQ) ⇒ (SSOC) we apply the second order necessary condition for quadratic growth (Theorem 3 of [2]) to the problem of minimizing f. As C(x) ⊃ C(x) × {0} for all x ∈ S, we deduce, using Lemma 3.3, that whenever x ∈ S is sufficiently close to \overline{S}, then for small ε > 0

∃β > 0; max_{λ∈Λ̄(x)} ∇_{x}^{2}L(λ, x, 0)dd ≥ β∥d∥^{2}, ∀d ∈ C(x) ∩ N_{S}^{ε}(x),

which is equivalent to (SSOC).

We end this section by some remarks. The strong quadratic growth condition is sufficient for Lipschitz stability of solutions by Proposition 3.2. On the other hand, a necessary condition for Lipschitz stability is

φ̄_{x}(d) ≥ 0, ∀x ∈ \overline{S}, d ∈ C(x),

as observed by [17] (in the case of an isolated solutions, but the argument is obviously valid for nonisolated solutions). This means that (SQG) is, up to a second order analysis, the weakest possible sufficient condition for Lipschitz stability of solutions.

When the set of solutions is a singleton, it is possible to deduce from the Lipschitz stability of solutions the second-order expansion of the cost and the first-order expansion of pathes of approximate solutions ([1, 3, 4, 15]). In the case of nonisolated solutions, no similar theory has been developed yet.

The above necessary condition for Lipschitz stability is contingent in the sense that it depends of the perturbation also. A simple (though rather rough) structural (depending on unperturbed data only) sufficient condition for Lipschitz stability is the following. Define

\underline{φ}_{x}(d) := min_{λ∈Λ} L_{xx}(λ, x, 0)(d, d).

Then, as an easy consequence of Theorem 3.4, we obtain

Theorem 3.5. A sufficient condition for Lipschitz stability is

∃ε > 0; ∃β > 0; \underline{φ}_{x}(d) ≥ β∥d∥^{2} ; d ∈ C^{ε}(x) ∩ N_{S}(x) ; x ∈ S.

We end by a remark on the case when the data are jointly convex with respect to (x, u). Then, because of Proposition 2.1, L_{θ}(λ, x, 0) is constant over S. It follows that \overline{S} = S and Λ̄(x) = Λ for all x ∈ S. As a consequence, condition (SSOC) coincide with condition (iv) of Theorem 2.3. It follows by Theorems 2.3 and 3.4 that (QGC) and (SQG) coincide in that case.

4. Studying the critical cone

Our purpose in this section is to prove the following fact closely related to the celebrated Hoffmann’s lemma [7] and Robinson’s stability theorem [13]. We denote α^{+} := max(0, α).

Theorem 4.1. Under the assumptions of Theorem 2.3, there exists γ > 0 such that

dist(d, C(x)) ≤ γf′(x; d)^{+}, ∀x ∈ S, ∀d ∈ IR^{n}.

The novelty of this result lies primarily in the fact that neither f′(x; d) nor the set-valued map C(x) are, in general, continuous.

Proof. We shall prove the theorem in several steps. Step 1. We analyse the set C. Denote a_{i} := ∇f_{i}(x) for x ∈ ri S. By Proposition 2.1, a_{i} does not depend on the choice of x ∈ ri S. Define A := (a_{i})_{i∈I}. Given d ∈ IR^{n}, by A·d we mean (a_{i}·d)_{i∈I}. Then

C = {d ∈ IR^{n} : A·d ≤ 0}.

Let us look closer into the inequalities defining C. Set

I_{0} := {i ∈ I : a_{i}·d = 0, ∀d ∈ C}, and I_{1} := I\I_{0}.

Define similarly A_{0} := (a_{i})_{i∈I_{0}}, and A_{1} := (a_{i})_{i∈I_{1}}, so that A = A_{0} ∪ A_{1}. We claim that there exists d^{0} ∈ C such that A_{1}·d^{0} < 0. Indeed, with each i ∈ I_{1} is associated d^{i} ∈ C such that a_{i}·d^{i} < 0, so that d^{0} := ∑_{i∈I_{1}} d^{i} is the desired vector. We observe that I_{0} cannot be empty. Otherwise d^{0} would satisfy A·d^{0} < 0, which means that f′(x; d^{0}) < 0 whenever x ∈ ri S: a contradiction to the optimality of x. By Hoffmann’s lemma [7] there exists γ_{0} > 0 such that

dist(d, C) ≤ γ_{0}∥(A·d)^{+}∥.  (4.1)

Step 2. We now analyse C(x) when x ∈ rb S. Define

J(x) := I(x)\I, B(x) := (∇f_{i}(x))_{i∈J(x)}.

As in the proof of Proposition 2.1, we conclude that ∇f_{i}(x)·(x′ − x) < 0 if x′ ∈ riS and i ∈ J(x). The vector d := x′ − x belongs to T_{S}(x), and hence to C(x). Thus, if J(x) ≠ ∅, then

C(x) = {d : A·d ≤ 0, B(x)·d ≤ 0}

and there exists d^{1} ∈ C(x) such that B(x)·d^{1} < 0.

By Step 1 and the relation C(x) ⊂ C, there exists ϵ > 0 such that d^{2} := d^{1} + ϵd^{0} satisfies both A_{1}·d^{2} < 0 and B(x)·d^{2} < 0. For any J ⊂ J(x), set B_{J}(x) := (∇f_{i}(x))_{i∈J} and

H_{J}(x) := {d : A_{0}·d = 0, A_{1}·d ≤ 0, B_{J}(x)·d ≤ 0}.

We know that d^{2} ∈ H_{J}(x) satisfies A_{1}·d^{2} < 0 and B_{J}(x)·d^{2} < 0. We may assume that A_{0} is a set of independent vectors, for dropping linear dependent ones will not change its kernel. We observe that B_{J}(u) depends continuously on u. It follows now from Robinson’s stability theorem [13] that there exist a neighborhood U of x and a δ > 0 such that

dist(d, H_{J}(u)) ≤ δ(∥A_{0}·d∥ + ∥(A_{1}·d)^{+}∥ + ∥(B_{J}(u)·d)^{+}∥),  (4.2)

for all d ∈ R^{n} and all u in a neighbourhood u of x.

We observe further that ∥A_{0}·d∥ ≤ γ′dist(d, ker A_{0}) for some γ′ > 0, and (4.7), (4.3) imply together with the obvious inclusion C ⊂ ker A_{0} that, for a certain γ = γ(x, J):

dist(d, H_{J}(u)) ≤ γ(∥(A·d)^{+}∥ + ∥(B_{J}(u)·d)^{+}∥), ∀d, ∀u ∈ U.  (4.3)

Step 3. To conclude the proof we first recall that f′(x; d) = max{∇f_{i}(x) · d ; i ∈ I(x)}. Assuming that the theorem is wrong, we shall find a sequence of x^{k} ∈ S and a sequence of vectors d^{k} ∈ R^{n} such that

dist(d^{k}, C(x^{k})) ≥ kf′(x^{k}; d^{k})^{+}.  (4.4)

Extracting if necessary a subsequence,we may assume that x^{k} converges to a certain x ∈ S and that J(x^{k}) is equal to some J. Furthermore, as all C(x) are cones and f(x; ·) is homogeneous of degree one, we may likewise assume that ∥d^{k}∥ = 1 for all k and d^{k} → d. It follows from (4.3) that there is a γ > 0 such that for sufficiently big k we have

dist(d^{k}, H_{J}(x^{k})) ≤ γ(∥A·d)^{+}∥ + ∥(B_{J}(x^{k})·d^{k})^{+}∥).

But as J = J(x^{k}), we have I ∪ J = I(x^{k}), H_{J}(x^{k}) = C(x^{k}), and (4.3) implies that for some γ_{1} > 0

dist(d^{k}, C(x^{k})) ≤ γ_{1} max_{i∈I(x^{k})}(∇f(x^{k}) · d^{k})^{+}

in contradiction with (4.4). This completes the proof of Theorem 3.4.

5. Proof of Theorem 2.3

The implication (i) ⇒ (ii) is valid even for the non-convex case, see [2]. For the implication (ii) ⇒ (iii) we note that any d ∈ IR^{n} can be decomposed as d = d_{T} + d_{N}, where d_{T} (resp. d_{N}) is the projection onto T_{s}(x) (resp. N_{s}(x)), and ∥d∥^{2} = ∥d_{T} ∥^{2} + ∥d_{N}∥^{2}. It follows that

dist(d, T_{S}(x)) = ∥d_{N}∥ ≥ (1 − ε)∥d∥ if d ∈ N_{S}^{ε}(x),

52 J. F. Bonnans, A. D. Ioffe / Quadratic growth and stability

so that (ii) implies (iii) with the same parameter β. To prove that (iii) ⇒ (iv), we only have to note that if d ∈ C^{ε}(x) ∩ N_{S}(x), there exists d̂ ∈ C(x) with ∥d − d̂∥ ≤ ε∥d∥ so that ∥d̂∥ ≥ (1 − ε)∥d∥ and

dist(d̂, N_{S}(x)) ≤ ∥d − d̂∥ ≤ ε∥d∥ ≤ \frac{ε}{1 − ε}∥d̂∥,

whence d ∈ N_{S}^{ε′}(x) with ε′ := ε/(1 − ε). We may take ε so small that

|φ_{x}(d) − φ_{x}(d̂)| ≤ \frac{β}{8} ∥d̂∥^{2}, if ∥d − d̂∥ ≤ ε∥d̂∥.

We may also assume ε < \frac{1}{2}. Then with (iii), using ∥d∥ ≥ (1 − ε)∥d̂∥ ≥ \frac{1}{2}∥d̂∥, we obtain

φ_{x}(d̂) ≥ φ_{x}(d) − \frac{β}{8} ∥d̂∥^{2} ≥ \frac{β}{8} ∥d̂∥^{2}.

It remains to prove that (iv) ⇒ (i). Assuming that the implication does not hold, we find a sequence u^{k} ∉ S converging to a certain x ∈ Sand such that

f(u^{k}) ≤ f(x^{k}) + \frac{1}{k}∥u^{k} − x^{k}∥^{2},  (5.1)

where x^{k} is the projection of u^{k} onto S, i.e. x^{k} ∈ S and ∥x^{k} − u^{k}∥ = dist(u^{k}, S). Set d^{k} := (u^{k} − x^{k})/∥u^{k} − x^{k}∥. Then ∥d^{k}∥ = 1 and d^{k} ∈ N_{S}(x^{k}). As f is convex, we have f(u^{k}) ≥ f(x^{k}) + ∥u^{k} − x^{k}∥f′(x^{k}; d^{k}). So with (5.1)

f′(x^{k}; d^{k}) ≤ k^{−1}∥u^{k} − x^{k}∥ → 0.

Theorem 4.1 now implies that ε_{k} := dist(x^{k}, C(x^{k})) → 0. Using (iv), we get for sufficiently large k

φ_{x}(d^{k}) ≥ \frac{β}{2} > 0.  (5.2)

Setting t_{k} := ∥u^{k} − x^{k}∥ we have

f(u^{k}) ≥ max_{λ∈Λ} L(u^{k}, λ),

= f(x^{k}) + max_{λ∈Λ}(∑_{i=1}^{m} λ_{i}∇f_{i}(x^{k}) · d^{k} + \frac{t_{k}^{2}}{2} ∇^{2}f_{i}(x^{k})(d^{k}, d^{k})) + r_{k}(t_{k})),

= f(x^{k}) + t_{k}^{2}φ_{x}(d^{k}) + r_{k}(t_{k}) ≥ f(x^{k}) + \frac{t_{k}^{2}}{4} β′ + r_{k}(t_{k}),

where, as x^{k} → x and Λ is bounded, the functions r_{k}(t) are o(t^{2}) uniformly in k, so for sufficiently large k we have with (5.2)

f(u^{k}) ≥ f(x^{k}) + \frac{β}{8} ∥u^{k} − x^{k}∥^{2},

in contradiction with (5.1). The proof is completed.

6. Constrained optimization

We now consider an optimization problem of the form

min f_{0}(x); f_{i}(x) ≤ 0, i = 1, ⋯, m.  (P)

with f_{i}(x), i = 0, ⋯, m convex and C^{2}. We say that x ∈ IR^{n} is feasible if f_{i}(x) ≤ 0, i = 1, ⋯, m. Assume that (P) has solutions and let c be the value of f_{0}(x) over the set of solutions. Changing f_{0} into f_{0} − c if necessary, we may assume that this optimal value is null. Then x is solution of (P) iff it minimizes the function

f(x) := max_{0≤i≤m} f_{i}(x).

We now define two concepts of quadratic growth, and study the relations between them. First, we define quadratic growth for (P) as

∃β > 0 : f_{0}(x) ≥ β dist(x, S)^{2}, for all feasible x in a neighborhood of S. (QGC)

Taking in account a penalization of unfeasibilities, we define generalized quadratic growth for (P) as

∃β > 0 : f(x) ≥ β dist(x, S)^{2}, for all x in a neighborhood of S.  (GQGC)

It is obvious that (GQGC) implies (QGC). The converse is not true, as shown by the following example: min x^{4}; x^{4} ≤ 0. The Slater qualification hypothesis is:

∃x^{∗} ∈ IR^{n}; f_{i}(x^{∗}) < 0, i = 1, ⋯, m.

If the set of solutions of (P) is nonempty, and the Slater hypothesis holds, we know (see e.g. [8]) that there exists r > 0 such that the set of solutions of (P) coincides with the set of points that minimize the so-called exact penalty function

θ_{r}(x) := f_{0}(x) + r ∑_{i=1}^{m} max(0, f_{i}(x)).

Define

\begin{aligned}f̂_{i}(x) & := f_{0}(x) + rf_{i}(x), i = 1, ⋯, m. \\ f̂_{0}(x) & := f_{0}(x). \end{aligned}

Then θ_{r} can be written as

θ_{r}(x) := max_{i=0,···,m} f̂_{i}(x).

Define the collection of active indices

Ī(x) := {i = 1, ⋯, m : f_{i}(x) = 0},

the critical cone at x

C(x) := {d ∈ IR^{n} : f_{0}(x; d) ≤ 0, f′_{i}(x; d) ≤ 0, ∀i ∈ Ī(x)},

the set of Lagrange and generalized multipliers (the components of z ∈ IR^{m+1} are denoted z_{0}, ⋯, z_{m} ) :

\begin{matrix}Λ_{0}(x) := & \{λ ∈ S^{m+1} ; λ_{i} = 0, i ∉ Ī(x) ; ∑_{i=0}^{m} λ_{i}∇f_{i}(x) = 0\}, \\ Λ_{1}(x) := & \{λ ∈ IR_{+}^{m} ; λ_{i} = 0, i ∉ Ī(x) ; ∇f_{0}(x) + ∑_{i=1}^{m} λ_{i}∇f_{i}(x) = 0\}, \end{matrix}

the ordinary and the generalized Lagrangian

L(x, λ) := f_{0}(x) + ∑_{i=1}^{m} λ_{i}f_{i}(x) ; L̂(x, λ) := ∑_{i=0}^{m} λ_{i}f_{i}(x),

and the associated functions

φ_{x}(d) := max_{λ∈Λ_{1}} ∇_{x}^{2}L(x, λ)(d, d) ; φ̂_{x}(d) := max_{λ∈Λ_{0}} ∇_{x}^{2}L̂(x, λ)(d, d).

Theorem 6.1. Assume that all functions f_{i}, i = 0, ⋯, m are convex and twice continuously differentiable. Let S be a non empty convex compact set of solutions of (P). Then the following properties are equivalent:

(i) (GQGC) holds. (ii) There exists β > 0 such that

φ̂_{x}(d) ≥ β dist(d, T_{S}(x))^{2}, ∀x ∈ S, ∀d ∈ C(x)\T_{S}(x);

(iii) There exists β > 0, such that for all ε ∈ (0, 1)

φ̂_{x}(d) ≥ (1 − ε)^{2}β∥d∥^{2}, ∀x ∈ S, ∀d ∈ C(x) ∩ N_{S}^{ε}(x).

(iv) There exist β′ > 0, ε > 0 such that

φ̂_{x}(d) ≥ β′∥d∥^{2}, ∀x ∈ S, ∀d ∈ C^{ε}(x) ∩ N_{S}(x).

If, in addition, the Slater qualification hypothesis holds, the following properties are equivalent:

(v) (QGC) holds. (vi) There exists β > 0 such that

φ_{x}(d) ≥ β dist(d, T_{S}(x))^{2}, ∀x ∈ S, ∀d ∈ C(x)\T_{S}(x);

(vii) There exists β > 0, such that for all ε ∈ (0, 1)

φ_{x}(d) ≥ (1 − ε)^{2}β∥d∥^{2}, ∀x ∈ S, ∀d ∈ C(x) ∩ N_{S}^{ε}(x).

(viii) There exists β′ > 0, ε > 0 such that

φ_{x}(d) ≥ β′∥d∥^{2}, ∀x ∈ S, ∀d ∈ C^{ε}(x) ∩ N_{S}(x).

Proof. The equivalence between conditions (i) to (iv) is an immediate consequence of Theorem 2.3 applied to f(x). Applying now Theorem 2.3 to θ_{r}(x), we find that after some simple computations that properties (vi) to (viii) are equivalent to

∃β > 0 ; θ_{r}(x) ≥ β dist(x, S)^{2}, in a neighborhood of S.  (6.1)

To end the proof it suffices to check that, thanks to the Slater hypothesis, that (6.1) is equivalent to (QGC) when r is large enough. That (6.1) implies (QGC) is obvious. We now prove that the converse holds.

Given x ∈ IR^{n}, α ∈ [0, 1], we consider

x(α) := αx^{∗} + (1 − α)x

where x^{∗} is given by the Slater condition. Set γ^{∗} := − max_{1≤i≤m} f_{i}(x^{∗}) > 0, and γ(x) :=

max(0, max_{1≤i≤m} f_{i}(x)). By convexity

\begin{matrix}f_{i}(x(α)) ≤ & αf_{i}(x^{∗}) + (1 − α)f_{i}(x) \\ ≤ & − αγ^{∗} + (1 − α)γ(x) \\ ≤ & − αγ^{∗} + γ(x). \end{matrix}

We deduce that for

α(x) := min(1, γ(x)/γ^{∗}),

the point y(x) := α(x)x^{∗} + (1 − α(x))x is feasible, and

∥y(x) − x∥ = α(x)∥x^{∗} − x∥ ≤ \frac{γ(x)}{γ^{∗}}∥x^{∗} − x∥.

Let U be a compact convex neighborhood of S containing x^{∗} and L the Lipschitz constant of f_{0} on U. Set

r := max_{x∈U} \{\frac{∥x^{∗} − x∥}{γ^{∗}}(L + 2β dist(x, S))γ(x))\} .

Then

θ_{r}(x) =f_{0}(y(x)) + f_{0}(x) − f_{0}(y(x)) + rγ(x),
≥β dist(y(x), S)^{2} − L∥y(x) − x∥ + rγ(x),
≥β dist(y(x), S)^{2} + ( r − L\frac{∥x^{∗}−x∥}{γ^{∗}} ) γ(x).

On the other hand,

dist(y(x), S) ≥ dist(x, S) − ∥y(x) − x∥ ≥ dist(x, S) − \frac{∥x^{∗} − x∥}{γ^{∗}}γ(x),

so that

θ_{r}(x) ≥β dist(x, S)^{2}

+ [r − L\frac{∥x^{∗} − x∥}{γ^{∗}} − 2β \frac{∥x^{∗} − x∥}{γ^{∗}} dist(x, S) + β \frac{∥x^{∗} − x∥^{2}}{(γ^{∗})^{2}} γ(x)] γ(x),

≥β dist(x, S)^{2} + [r − \frac{∥x^{∗} − x∥}{γ^{∗}}(L + 2β dist(x, S)] γ(x),
≥β dist(x, S)^{2},

as was to be proved.

References

[1] A. Auslender, R. Cominetti: First and second order sensitivity analysis of nonlinear programs under directional constraint qualification condition. Optimization 21, 1990, 351–363.

[2] J.F. Bonnans, A.D. Ioffe: Second-order sufficiency and quadratic growth for non isolated minima. Inria Report 1853. Mathematics of Operations Research, 1993, to appear.

[3] J.F. Bonnans, A.D. Ioffe, A. Shapiro: Expansion of exact and approximate solutions in nonlinear programming. In Lecture Notes in Economics and Mathematical Systems 382, W. Oettli and P. Pallaschke eds., Springer Verlag, 1993, 103–117.

[4] J.F. Bonnans, A.D. Ioffe, A. Shapiro: Développement de solutions exactes et approchées en programmation non linéaire. Comptes Rendus Acad. Sci. Paris Ser. I, 1992, 119–123.

[5] J. Gauvin, R. Janin: Directional behavior of optimal solutions in nonlinear mathematical programming. Mathematics of Operation Research 13, 1988, 629–649.

[6] E.G. Gol’stein: Theory of convex programming. Nauka, Moscow, 1970; Transl. Math. Monographs 36, Amer. Mathematics Soc., Providence, R.I., 1972.

[7] A. Hoffmann: On approximate solutions of systems of inequalities, J. Res. National Bureau Standards, Sect. B 49, 1952, 263–265.

[8] A.D. Ioffe: Necessary and sufficient conditions for a local minimum. SIAM J. Control Optimization 17, 1979, 245–288.

[9] A.D. Ioffe: Variational analysis of a composite function : a formula for the lower second order epi-derivative, Mathematics of Analysis Applications 160, 1991, 379–405.

[10] A.D. Ioffe: On sensitivity analysis of nonlinear program in Banach spaces : the approach via composite unconstrained optimization, SIAM J. Optimization, 4, 1994, 1–43.

[11] E.S. Levitin, A.A. Miljutin, N.P. Osmolowski: On conditions for a local minimum in problems with constraints, in Mathematical Economics and Functional Analysis, B.S. Mitiagin ed., Nauka, Moscow, 1974, 139–202 (In Russian).

[12] O.L. Mangasarian: A simple characterization of solution sets of convex programs. Oper. Res. Letters 7, 1988, 21–26

[13] S.M. Robinson: Stability theory for systems of inequalities, part 2, SIAM J. Numerical Analysis, 13, 1976, 487–513.

[14] R.T. Rockafellar: Convex Analysis, Princeton University Press 1970.

[15] A. Shapiro: Sensitivity analysis of nonlinear programs and differentiability properties of metric projections. SIAM J. Control Optimization 26, 1988, 628–645.

[16] A. Shapiro: Perturbation theory of nonlinear programs when the set of solution is not a singleton. J. Applied Mathematics of Optimization 18, 1988, 215–229.

[17] A. Shapiro: Perturbation analysis of optimization problems in Banach spaces. Numerical Functional Analysis and Optimization 13, 1992, 97–116.

[18] D. Klatte: On quantitative stability for non-isolated minima. Control and Cybernetics 23, 58 J. F. Bonnans, A. D. Ioffe / Quadratic growth and stability

HIER :

Leere Seite