# Aubin Property and Uniqueness of Solutions in Cone

## Transcript Of Aubin Property and Uniqueness of Solutions in Cone

Preprint manuscript No. (will be inserted by the editor)

Aubin Property and Uniqueness of Solutions in Cone Constrained Optimization

Diethard Klatte · Bernd Kummer

submitted 6 January 2012, revised 11 June 2012

Abstract We discuss conditions for the Aubin property of solutions to perturbed cone constrained programs, by using and reﬁning results given in [10]. In particular, we show that constraint nondegeneracy and hence uniqueness of the multiplier is necessary for the Aubin property of the critical point map. Moreover, we give conditions under which the critical point map has the Aubin property if and only if it is locally single-valued and Lipschitz. Keywords Cone constrained optimization · Aubin property · Critical points · Constraint nondegeneracy · Locally single-valued solutions Mathematics Subject Classiﬁcation (2000) 49K40 · 90C31 · 49J53 · 90C22

1 Introduction

In this paper we consider the canonically perturbed cone constrained program P(p), p = (a, b) : minx f (x) − a, x subject to g(x) − b ∈ K, (1)

where f : IRn → IR, g : IRn → IRm, K ⊂ IRm is a closed convex set, ·, · is the Euclidean inner product (with induced norm · ), and the parameter vector p = (a, b) varies near the origin. Put (P) = P(0). Note that the results of this paper remain true if f and g also vary in a suitable way in some function space or by certain parameterizations but we avoid this (i) because of size restrictions for this paper and (ii) for an intrinsic reason: the stability characterizations given below depend crucially on the canonical perturbations f − a, · and g − b.

Diethard Klatte Institut fu¨r Betriebswirtschaftslehre, Professur Mathematik fu¨r O¨ konomen, Universita¨t Zu¨rich, Moussonstr. 15, CH-8044 Zu¨rich, Switzerland. E-mail: [email protected] Bernd Kummer Institut fu¨r Mathematik, Humboldt–Universita¨t zu Berlin, Unter den Linden 6, D-10099 Berlin, Germany. E-mail: [email protected]

2

Diethard Klatte, Bernd Kummer

We speak here of cone constraints, since K is often a cone in applications. Note that K may be a set of symmetric matrices. In this case, the standard reformulation of a symmetric (d, d)-matrix A as a vector svec(A) ∈ IRd(d+1)/2 leads to a problem of type (1). Thus, problem (1) particularly covers standard nonlinear programs, secondorder cone programs and semi-deﬁnite programs under perturbations.

The Lagrange function of problem (1) is given by

L(x, λ ) = f (x) + λ , g(x) .

If f and g are C1 functions, and x¯ is a feasible point of P(p) satisfying a constraint

qualiﬁcation, then there is some λ such that (x¯, λ ) fulﬁls the Karush-Kuhn-Tucker

(KKT) conditions

DxL(x¯, λ ) = a , λ ∈ NK(g(x¯) − b),

(2)

where NK(y¯) = {z ∈ IRm | z, y − y¯ ≤ 0 ∀y ∈ K} is the normal cone of K at y¯ ∈ K. Note that by deﬁnition NK(y¯) = 0/ if y¯ ∈ K. In this sense, the feasibility condition g(x¯) − b ∈ K is included when saying that (x¯, λ ) fulﬁls (2). For ﬁrst-order optimality conditions and the theory of cone constrained programs at all we refer e.g. to Bonnans

and Shapiro [1]. For p = (a, b), denote by Σ (p) the set of all solutions (x¯, λ ) to the system (2).

A point (x¯, λ ) ∈ Σ (p) will be called critical point of problem P(p). By Λ (x¯, p) = {λ | (x¯, λ ) ∈ Σ (p)} we denote the set of multipliers associated with some x¯ in the set S(p) = {x | ∃λ : (x, λ ) ∈ Σ (p)} of stationary solutions of P(p).

The focus of our paper is to study situations in which the critical point multifunction Σ (resp. Λ or S) is in fact a locally single-valued and Lipschitz function, provided it has some multi-valued Lipschitz behavior called Aubin property. We say that a multifunction Γ from IRd to IRs has the Aubin property at some point (p¯, z¯) ∈ gphΓ = {(p, z) | z ∈ Γ (p)} (or, synonymously, the inverse multifunction Γ −1 is metrically regular at (z¯, p¯)), if there are neighborhoods U of p¯ and V of z¯ as well as some constant c > 0 such that for all p, p ∈ U and all z ∈ Γ (p) ∩V

there exists some z ∈ Γ (p ) such that z − z ≤ c p − p .

It is immediate from the deﬁnition that the Aubin property of Γ at (p¯, z¯) implies that Γ

has the Aubin property also at (p, z) ∈ gphΓ near (p¯, z¯). If Γ (p) ∩V is single-valued

on U then it becomes a locally Lipschitz function under the Aubin property. In this

case, Γ is called locally single-valued and Lipschitz around (p¯, z¯), or, synonymously, Γ −1 is strong regular at (z¯, p¯). For a detailed discussion of relations between different

stability and regularity notions we refer, e.g., to [17, 10, 6]. If F : IRd → IRd is a locally Lipschitz and directionally differentiable function,

then the Aubin property of Γ = F−1 at (z¯, p¯) gives that z¯ is an isolated (i.e., locally

unique) solution of the equation F(z) = p¯, see Fusek [7]. Of course, this applies to the critical point map Σ (a) = (D f )−1(a) of the unconstrained problem (1) for F = D f . Unfortunately, this does not mean that D f −1 is locally single-valued in this case, see Kummer’s example of a piecewise quadratic C1 function f in [12, Ex. 3] (cf. also [10, Ex. BE.4]). In contrast, if f is a C2 function then D f −1 becomes locally single-valued

under the Aubin property, by standard calculus arguments.

Aubin Property and Uniqueness of Solutions in Cone Constrained Optimization

3

What about constrained problems? For global minimizers, uniqueness follows from the Aubin property for general optimization problems, we refer to [10] and section 4 below. For critical points, the situation is much more involved. Dontchev and Rockafellar [5] studied a variational inequality F(z,t) − p ∈ NC(z) for a polyhedral convex set C and a C1 function F : IRd × IRκ → IRd with perturbation (t, p). They proved the equivalence of metric and strong regularity at solutions for this model, see Proposition 1 below. This result applies to the critical point map of a perturbed nonlinear program with C2 data, i.e., in our context, to the problem (1) with convex polyhedral set K and f , g ∈ C2.

Kummer [12] (see also [10, §7]) extended this results to the solution map of a socalled generalized Kojima system (cf. section 5 below) which covers the DontchevRockafellar model. In a recent paper, Outrata and Ram´ırez [14] show the equivalence of the Aubin property and strong regularity for the stationary solution set map of a second-order cone program under constraint nondegeneracy at a local minimizer of the initial problem. They use essentially the characterization of strong regularity for such problems given by Bonnans and Ram´ırez [2], however some ”weak” strict complementarity condition has to be supposed.

The paper is structured as follows. Section 2 is devoted to some preliminaries and basic notation. In section 3 we prove that nondegeneracy of a stationary solution and uniqueness of the multiplier for (1) necessarily follow from the Aubin property for the critical point map Σ . This has been known before only for special cases, cf. [5, 12, 10]. In section 4 we recall from [10, Ch. 4] the result on single-valuedness under the Aubin property for abstract global minimizing set mappings and apply this to convex cone constrained programs. Finally, section 5 is concerned with the equivalence of strong and metric regularity for critical point systems of (1) in the case of K being described by a ﬁnite system of nonlinear inequalities. This extends the well-known results for a convex polyhedral set K, cf. [5, 10].

2 Preliminaries

In this section we introduce further notation and terminology of this paper, and we

provide some basic tools and results which are needed in the next sections. Let C ⊂ IRm be a convex set. The relative interior of C is denoted by riC, while

spanC is the linear hull of C. A function g : IRn → IRm is called convex with respect

to C if the graph of the multifunction g(x) +C is convex.

If C is a convex closed cone, linC denotes the largest subspace in C, C− = {y∗ ∈ IRm | y∗, y ≤ 0 ∀y ∈ C} is the polar of C, and one has, by classical convex analysis, (C−)− = C and

(linC)⊥ = span(C−) ,

(3)

where ⊥ refers to the orthogonal complement. Given a linear subspace X of IRm, and writing A∗ for the adjoint of a linear operator A : IRn → IRm, we obviously have

AIRn + X = IRm if and only if Au∗∈u =X⊥0 ⇒ u = 0 . (4)

4

Diethard Klatte, Bernd Kummer

Given a closed convex set K ⊂ IRm, then TK(y¯) = NK(y¯)− denotes the tangent cone of K at y¯, where NK(y¯) is the normal cone as above. Again, TK(y¯) is empty by deﬁnition if y¯ ∈ K.

If K is a closed convex cone, one has λ ∈ NK(y) if and only if y ∈ NK− (λ ), i.e., in this case (2) is equivalent to

DxL(x¯, λ ) = a, g(x¯) − b ∈ NK− (λ ) ,

(5)

where obviously NK− (λ ) = K ∩ {µ ∈ IRm | µ, λ = 0}. We will refer in this paper at some places to a basic theorem on the equivalence of

metric and strong regularity given in [5]. Consider the perturbed generalized equation

0 ∈ p + F(z,t) + NC(z),

(6)

where C ⊂ IRd is a nonempty, polyhedral, convex set, F : IRd × IRκ → IRd is a locally Lipschitz function which is continuously differentiable w.r. to z, and q = (p,t) is a parameter vector varying around some initial point q0 = (p0,t0). Denote the solution set of (6) by S(q). Given (q0, z0) ∈ gph S, a linearized version of the generalized

equation (6) is given by

0 ∈ π + DzF(z0,t0)z + NC(z),

(7)

where the canonical parameter π varies around π0 = p0 + F(z0,t0) − DzF(z0,t0)z0. Let L(π) denote the solution set of (7).

Proposition 1 (Dontchev and Rockafellar [5, Thm. 3]) Given z0 ∈ S(q0) = L(π0),

the following properties are equivalent: 1. the solution map S of (6) has the Aubin property at (q0, z0), 2. the solution map S of (6) is locally single-valued and Lipschitz around (q0, z0), 3. the solution map L of the linearization (7) has the Aubin property at (π0, z0),

4. the solution map L of the linearization (7) is locally single-valued and Lipschitz around (π0, z0).

Note that property 4 is the concept of strong regularity in Robinson’s [15] sense.

Proposition 1 applies to the KKT system (2) of the cone constrained program (1) if

K is a convex polyhedral set: this is obvious if K is in addition a cone, due to (5),

otherwise a suitable transformation is needed, for details see [5].

In section 5 we will apply some basic result on persistence of metric or strong regularity of a continuous function F : IRd → IRs with respect to small Lipschitz perturbations F − g. Given a solution z¯ of the equation F(z) = 0, let Ω ⊂ IRd be some neighborhood of z¯ and let g : Ω → IRs be Lipschitz on Ω . We put

sup(g, Ω ) = sup{ g(z) | z ∈ Ω },

Lip(g, Ω ) = inf{r > 0 | g(z) − g(z ) ≤ r z − z ∀z, z ∈ Ω },

where · and · are given norms in IRd and IRs, respectively. Lip(g, Ω ) is called the Lipschitz rank of g. The space G = C0,1(Ω , IRs) of our (locally) Lipschitz variations g is supposed to be equipped with the norm

|g| = max{sup(g, Ω ), Lip(g, Ω )}.

(8)

Aubin Property and Uniqueness of Solutions in Cone Constrained Optimization

5

Persistence of strong regularity for generalized equations was originally studied by Robinson [15] for small C1-functions g. The following proposition was given by Kummer [13] (see also [10, §4.1]) in the more general context of perturbed inclusions, in our special form it already follows from Cominetti [4].

Proposition 2 (Klatte and Kummer [10, Cor. 4.4]) Let F be a continuous function from IRd to IRs. Suppose that g ∈ G satisﬁes sup(g, z¯+rB) = o(r) and Lip(g, z¯+rB) = O(r). Then F is metrically (resp. strongly) regular regular at z¯ if and only if so is F − g.

Here 0(·) and o(·) denote as usual functions of the type 0(t) → 0 and o(t)/t → 0 for t → 0 with 0(0) = 0 and o(0) = 0, while B is the unit ball in IRd.

3 Constraint nondegeneracy under Aubin property

In this section, we assume that f and g are C1 functions and that K ⊂ IRm is a closed

convex set. We shall show the Aubin property of the critical point map Σ implies that

the Lagrange multiplier is unique.

According to [1, 18] a point x¯ satisfying g(x¯) ∈ K is called nondegenerate with

respect to g and K if

Dg(x¯)IRn + lin TK(g(x¯)) = IRm.

(9)

This means surjectivity of Dg(x¯) whenever the cone is pointed. By (3) and (4), condition (9) is equivalent to

[ Dg(x¯)∗u = 0 ∧ u ∈ span NK(g(x¯)) ] ⇒ u = 0 ,

(10)

cf. [1, §4.6]. For a convex polyhedral cone K, (9) (and hence (10)) coincides with Robinson’s [16] deﬁnition of nondegeneracy; in the standard NLP case K = IRk− × {0m−k} this is the linear independence constraint qualiﬁcation (LICQ).

It is well-known (cf. e.g. [18, Thm. 2.1]) that

(x¯, λ¯ ) ∈ Σ (0) ∧ x¯ nondegenerate w.r. to g and K ⇒ Λ (x¯} = {λ¯ }, (11)

and conversely, Λ (x¯, 0) = {λ } and λ ∈ ri NK(g(x¯)) together imply that x¯ is nondegenerate w.r. to g and K.

To see (11) immediately, let λ 1, λ 2 ∈ Λ (x¯, 0). Then Dg(x¯)∗λ i = −D f (x¯) and λ i ∈ NK(g(x¯)) for i = 1, 2, hence Dg(x¯)∗(λ 1 − λ 2) = 0 and λ 1 − λ 2 ∈ span NK(g(x¯)), which implies λ 1 = λ 2 because of (10) and we are done.

Theorem 1 Given a critical point (x¯, λ¯ ) ∈ Σ (0), suppose Σ has the Aubin property at (0, (x¯, λ¯ )). Then x¯ is nondegenerate with respect to g and K, and so Λ (x¯, 0) = {λ¯ }.

Proof : Let (x¯, λ¯ ) ∈ Σ (0) and u ∈ IRm such that

Dg(x¯)∗u = 0 ∧ u ∈ span NK(g(x¯)).

We have to show that u = 0. If NK(g(x¯)) = {0} there is nothing to prove. Suppose NK(g(x¯)) = {0} and choose any w ∈ ri NK(g(x¯)) with w = 1. Deﬁne for any ε, δ > 0

a(ε) = εDg(x¯)∗w, b(δ ) = δ u.

6

Diethard Klatte, Bernd Kummer

Then we have λ¯ + εw ∈ NK(g(x¯)) from λ¯ , w ∈ NK(g(x¯)), and Dx f (x¯) + Dg(x¯)∗λ¯ = 0 implies Dx f (x¯) + Dg(x¯)∗(λ¯ + εw) = a(ε). Thus,

(x¯, λ¯ + εw) ∈ Σ (a(ε), 0).

For small ﬁxed ε, and for all δ ↓ 0, there are such elements (x, λ ) ∈ Σ (a(ε), b(δ )) which satisfy with some Lipschitz constant L the inequality of the Aubin property,

(x, λ ) − (x¯, λ¯ + εw) ≤ Lδ u .

(12)

By construction, λ¯ + εw ∈ ri NK(g(x¯)) and u ∈ span NK(g(x¯)), hence we can choose some small, but ﬁxed t > 0 such that

λ¯ + εw − tu ∈ NK(g(x¯)).

This implies, together with g(x) − b(δ ) = g(x) − δ u ∈ K,

0 ≥ λ¯ + εw − tu, g(x) − δ u − g(x¯) = λ¯ + εw − tu − λ , g(x) − δ u − g(x¯) + λ , g(x) − δ u − g(x¯) ≥ λ¯ + εw − λ − tu, g(x) − g(x¯) − δ u ,

where the last inequality follows from λ ∈ NK(g(x) − δ u) and g(x¯) ∈ K. Continuing this, we obtain, with µ = λ¯ + εw − λ ,

tδ u 2 ≤ µ, g(x¯) − g(x) + t u, g(x) − g(x¯) + δ µ, u .

(13)

By applying the mean-value theorem to the components gi of g, one has gi(x) − gi(x¯) = Dgi(ξ i)(x − x¯) with some ξ i between x and x¯.

Now the three terms in the right-hand side sum of (13) can be estimated as follows, recall that µ = λ¯ + εw − λ and x − x¯ fulﬁl the Lipschitz estimate (12). Indeed,

µ, g(x¯) − g(x) = ∑ µiDgi(ξ i)(x − x¯) ≤ ∑ |µi| Dgi(ξ i) x − x¯ = o(δ )

i

i

is obtained after applying the Lipschitz estimate (12) twice. Again by (12), δ µ, u ≤ δ µ u ≤ Lδ 2 u 2 = o(δ ).

Finally, we have Dgi(ξ i) → Dgi(x¯) , since Dg is continuous and ξ i → x¯ as δ ↓ 0, i.e.

u, g(x) − g(x¯) = t ∑ uiDgi(ξ i)(x − x¯) i

with ∑i uiDgi(ξ i) tending to Dg(x¯)∗u = 0 as δ ↓ 0. This yields

t u, g(x) − g(x¯) ≤ t ∑ uiDgi(ξ i) x − x¯ = o(δ ). i

Thus, (13) says, because of t > 0, δ u 2 = o(δ )

for arbitrarily small δ . This implies u = 0 and we are done.

Aubin Property and Uniqueness of Solutions in Cone Constrained Optimization

7

Remark 1 (Generalized equations). Theorem 1 similarly holds for the generalized

equation

F(x) + Dg(x)∗λ = a , λ ∈ NK(g(x) − b),

(14)

with g, K as above and some continuous function F. Its proof and that of (11) made nowhere use of the special form F(x) = D f (x) in (2). If K is a convex polyhedral set and F and Dg are continuously differentiable, then Theorem 1 is a special consequence of Proposition 1.

Remark 2 (Generalized Kojima systems). If the generalized equation (14) can be reformulated in equation form with a so-called (generalized) Kojima function, then Theorem 1 is Thm. 7.1 in [10], cf. also [12]. Note that this reformulation becomes possible if K itself is described by a system of smooth inequalities (under some constraint qualiﬁcation for this system), for details see [10, Chapt. 7]. Finally, in the context of nonlinear semideﬁnite programs, Fusek [8] has shown the uniqueness of the multiplier under the Aubin property of critical points.

4 Aubin property versus uniqueness for global minimizers

In this section, we recall a basic result on uniqueness of global minimizers to abstract optimization problems under the Aubin property and apply this to convex cone constrained programs of the form (1).

For the moment, we consider the abstract perturbed optimization problem

min ϕ(x,t) − a, x s.t. x ∈ M(t) ⊂ M (ϕ : M × T → IR), (15)

0/ = M ⊂ X, (X, ·, · ) Hilbert space, (T, d(·, ·)) metric space,

where t¯ ∈ T is an initial parameter, and (a,t) varies in X × T near (0,t¯) ∈ X × T measured by ρ((a,t), (a ,t )) = a − a + d(t,t ). Deﬁne by

Ψ (a,t) = argminx{ϕ(x,t) − a, x | x ∈ M(t)} the set of (global) optimal solutions of problem (15), and let Φ(a) = Ψ (a,t¯).

Lemma 1 [10, Lemma 4.6]. Given x¯ ∈ Φ(0), suppose that dist(x¯, Φ(a)) converges to zero for each sequence a → 0, i.e., Φ is lower semicontinuous at (0, x¯). Then Φ(0) = {x¯}.

Inspecting the proof of Lemma 4.6 in [10], one sees that the ”rich” (”tilt”) perturbation a, x in the objective function is crucial. Then one immediately has the following result which is a modiﬁcation of Corollary 4.7 in [10].

Theorem 2 (Aubin property and locally single-valued solutions). In the setting (15), the solution mapping Ψ has the Aubin property at ((0,t¯), x¯) ∈ gphΨ only if it is single-valued near (0,t¯).

Proof It follows from the Aubin property at ((0,t¯), x¯) that for certain neighborhoods U of (0,t¯) and V of x¯ and for all (a,t) ∈ U and x ∈ V with x ∈ Ψ (a,t),

Ψ (a,t) ∩V = 0/ and dist(x,Ψ (a ,t )) → 0 as (a ,t ) → (a,t).

Then Lemma 1 yields Ψ (a,t) = {x(a,t)} for all (a,t) ∈ U and some x(a,t) ∈ V .

8

Diethard Klatte, Bernd Kummer

Next we consider the perturbed cone constrained optimization problem (1) and suppose in addition to the general assumptions for (1) that f and g are continuously differentiable, f is a convex function and g is convex with respect to the set −K. Let us speak in this case of the convex problem (1) with C1 data.

Hence, by standard convex optimization (cf. e.g. [1, Prop. 3.3]), one has: if some (x¯, λ ) satisﬁes the KKT conditions (2), then x¯ is a global minimizer of the optimization problem P(p). Recall that Σ (p) (resp. S(p)) is the set of critical points (resp.stationary solutions) of P(p).

Corollary 1 (Single-valued solutions for convex programs). Consider the convex problem (1) with C1 data, and let (0, (x¯, λ¯ )) ∈ gph Σ . Then the critical point map Σ is single-valued and Lipschitz on a neighborhood of p = 0 if and only if Σ has the Aubin property at (0, (x¯, λ¯ )).

Proof The only-if direction follows from the deﬁnition of the Aubin property. To show the if-direction, we ﬁrst observe that the stationary point map S has the Aubin property at (0, x¯): Since Σ has the Aubin property, so also its component S at x¯. Thus, S is single-valued, say S(p) = {x(p)}, by convexity and Theorem 2.

Further, by deﬁnition, the Aubin property of Σ at (0, (x¯, λ¯ )) implies that Σ has the Aubin property at each (p, (x, λ )) ∈ gph Σ near (0, (x¯, λ¯ )). Hence, by Theorem 1, we have that p → Λ (x(p), p) is single-valued near p = 0, and so, Σ is also single-valued near p = 0.

Remark 3 (Strong regularity). Corollary 1 allows the application of conditions for strong regularity in the convex setting, when looking for the Aubin property of Σ . So, for example, strong regularity for linear semi-deﬁnite programs (i.e., a special convex cone constrained problem) was characterized in [3]. Further, characterizations of strong regularity of the KKT system at local minimizers were given for nonlinear problems of the type (1) with C2 data, by combining nondegeneracy of solutions with strong second-order optimality conditions: The case of standard nonlinear programs is classic, cf. e.g. [11, 15, 5, 1, 10], for semi-deﬁnite programs see e.g. [1, 19], for second-order cone programs we refer to [2]. In the convex setting, this gives also characterizations for the Aubin property of the KKT mapping.

5 Aubin property and locally single-valued critical points

Now we assume that the set K in the problem (1),

P(p), p = (a, b) : minx f (x) − a, x subject to g(x) − b ∈ K,

is deﬁned by ﬁnitely many inequalities,

K = {y ∈ IRm | h j(y) ≤ 0, j = 1, . . . , r} , h j : IRm → IR ,

(16)

write h = (h1, . . . , hr). We suppose throughout that f , g, h are C2 functions. Convexity of K is not required. Smooth equations could be added, we avoid this for simplicity.

In this section, we will discuss consequences of the Aubin property of the solution map Σ of the KKT system (2) if K is described by (16).

Aubin Property and Uniqueness of Solutions in Cone Constrained Optimization

9

For y ∈ K and under some constraint qualiﬁcation for the system h(y) ≤ 0 (e.g., under the Mangasarian-Fromovitz constraint qualiﬁcation (MFCQ)), the normal cone NK(y) has the representation, cf. e.g. [10, §7.2],

λ ∈ NK(y) ⇔ [ ∃µ ∈ IRr : λ = Dh(y)∗µ+ ∧ h(y) = µ− ] ,

(17)

where µ+j = max{µ j, 0} and µ−j = min{µ j, 0}. This is simply a brief description of

the cone of the active gradients Dh j(y), j ∈ I(y), with I(y) = { j | h j(y) = 0}.

For the rest of this section, let x¯ be a stationary solution of the problem (P)=P(0),

and put g¯ = g(x¯). Suppose that MFCQ is satisﬁed for the system h(y) ≤ 0 at y = g¯.

Setting

G(x) = h(g(x)), which gives DG(x)∗ = Dg(x)∗Dh(g(x))∗,

(18)

formula (17) allows to write the KKT system (2) for the initial problem (P) at x = x¯ and y = g¯ in the following equivalent (Kojima [11]) form

D f (x) + DG(x)∗µ+

F(x, µ) = G(x) − µ−

= 0 , λ from (17) .

(19)

System (19) is the Kojima system for the optimization problem

min f (x) such that G(x) ≤ 0 ∈ IRr.

(20)

With canonical perturbations (a, c), the equation

F(x, µ) = a ∈ IRn+r

(21)

c

describes (equivalently) the KKT-points of

min f (x) − a, x such that G(x) ≤ c.

(22)

For the classical perturbations (22), the Aubin property and strong regularity are

equivalent at the reference point by applying Proposition 1 to a standard nonlinear program with C2 data f , g.

We also know (Thm. 1) that for both properties LICQ (i.e., rank DG(x¯) = r) is a necessary condition, which does not hold, e.g. if r > n. However, LICQ is needed as long as all parameters c ∈ IRr are taken into account which does not happen here.

Indeed, we have

g(x) − b ∈ K ⇔ h(g(x) − b) ≤ 0;

g(x), b ∈ IRm

h : IRm → IRr, g : IRn → IRm G : IRn → IRr

(23)

Setting r(x, b) = G(x) − h(g(x) − b), the constraints h(g(x) − b) ≤ 0 or g(x) − b ∈ K

coincide with

G(x) ≤ cˆ := r(x, b).

(24)

Denote by ker A and im A the kernel and the image of a linear operator A, respectively. Recall that nondegeneracy (9) required Dg(x¯)IRn + lin TK(g¯) = IRm and that

lin TK(g¯) = ker Dh(g¯). So (9) means, in the current context,

Dg(x¯)IRn + ker Dh(g¯) = IRm.

(25)

This has consequences for uniqueness of the Lagrange multipliers µ+ in (19) (µ− as slack variable is always unique).

10

Diethard Klatte, Bernd Kummer

Lemma 2 Under nondegeneracy (9), the Lagrange multiplier µ+ at the reference point x¯ is uniquely deﬁned up to the orthogonal space (im Dh(g¯))⊥ of im Dh(g¯). Hence, supposing µ+ ∈ im Dh(g¯) in (19), µ+ is unique at the reference point.

Proof Assume that µ is not unique at x¯, i.e.,

λ = ∑ α jDG j(x¯) = ∑ β jDG j(x¯), α = β , α, β ≥ 0

j∈J(x¯)

j∈J(x¯)

holds for some λ ∈ NK(g¯), where J(x¯) = { j | G j(x¯) = h j(g(x¯)) = 0}. This implies

0 = ∑ (α j − β j)Dh j(g¯)Dg(x¯).

(26)

j∈J(x¯)

Using (25) we know: For any y ∈ IRm there are u ∈ IRn and w ∈ ker Dh(g¯) with Dg(x¯)u + w = y. Multiplying in (26) with u, then yields

0 = ∑ (α j − β j)Dh j(g¯)(y − w) = ∑ (α j − β j)Dh j(g¯)y.

j∈J(x¯)

j∈J(x¯)

This holds for all y ∈ IRm. Thus (26) implies that α − β , with zero-components for j ∈/ J(x¯), is necessarily orthogonal to Dh(g¯)IRm = im Dh(g¯). Conversely, if (α −

β ) ⊥ im Dh(g¯) then (26) is evident.

Next we suppose nondegeneracy (9). F can be written in product form as in [10, §7.1], namely, with identity matrix I,

D f (x) DG(x)∗ 0 1

F(x, µ) =

µ+ = M (x) V (µ).

(27)

G(x) 0 −I µ−

With the (partial) linearization of F at x¯

FL(x, µ) = [M (x¯) + DM (x¯)(x − x¯)] V (µ)

(28)

let us study the parametrization

FL(x, µ) = a ∈ IRn+r for c, µ ∈ im Dh(g¯) only.

(29)

c

Notice that

c ∈ im Dh(g¯) and DG(x¯)(x − x¯) ∈ im Dh(g¯)

yield µ− = DG(x¯)(x − x¯) − c ∈ im Dh(g¯) .

Hence µ = µ+ + µ− ∈ im Dh(g¯) holds exactly if µ+ ∈ im Dh(g¯). For the polyhedral system (29), metric and strong regularity at ((x¯, µ¯ ), (0, 0)) coincide by Proposition 1.

Now it follows from Proposition 2 that metric and strong regularity at (x¯, µ¯ ) also coincide for the (not linearized) system

F(x, µ) = a ∈ IRn+r for c, µ ∈ im Dh(g¯) .

(30)

c

Aubin Property and Uniqueness of Solutions in Cone Constrained Optimization

Diethard Klatte · Bernd Kummer

submitted 6 January 2012, revised 11 June 2012

Abstract We discuss conditions for the Aubin property of solutions to perturbed cone constrained programs, by using and reﬁning results given in [10]. In particular, we show that constraint nondegeneracy and hence uniqueness of the multiplier is necessary for the Aubin property of the critical point map. Moreover, we give conditions under which the critical point map has the Aubin property if and only if it is locally single-valued and Lipschitz. Keywords Cone constrained optimization · Aubin property · Critical points · Constraint nondegeneracy · Locally single-valued solutions Mathematics Subject Classiﬁcation (2000) 49K40 · 90C31 · 49J53 · 90C22

1 Introduction

In this paper we consider the canonically perturbed cone constrained program P(p), p = (a, b) : minx f (x) − a, x subject to g(x) − b ∈ K, (1)

where f : IRn → IR, g : IRn → IRm, K ⊂ IRm is a closed convex set, ·, · is the Euclidean inner product (with induced norm · ), and the parameter vector p = (a, b) varies near the origin. Put (P) = P(0). Note that the results of this paper remain true if f and g also vary in a suitable way in some function space or by certain parameterizations but we avoid this (i) because of size restrictions for this paper and (ii) for an intrinsic reason: the stability characterizations given below depend crucially on the canonical perturbations f − a, · and g − b.

Diethard Klatte Institut fu¨r Betriebswirtschaftslehre, Professur Mathematik fu¨r O¨ konomen, Universita¨t Zu¨rich, Moussonstr. 15, CH-8044 Zu¨rich, Switzerland. E-mail: [email protected] Bernd Kummer Institut fu¨r Mathematik, Humboldt–Universita¨t zu Berlin, Unter den Linden 6, D-10099 Berlin, Germany. E-mail: [email protected]

2

Diethard Klatte, Bernd Kummer

We speak here of cone constraints, since K is often a cone in applications. Note that K may be a set of symmetric matrices. In this case, the standard reformulation of a symmetric (d, d)-matrix A as a vector svec(A) ∈ IRd(d+1)/2 leads to a problem of type (1). Thus, problem (1) particularly covers standard nonlinear programs, secondorder cone programs and semi-deﬁnite programs under perturbations.

The Lagrange function of problem (1) is given by

L(x, λ ) = f (x) + λ , g(x) .

If f and g are C1 functions, and x¯ is a feasible point of P(p) satisfying a constraint

qualiﬁcation, then there is some λ such that (x¯, λ ) fulﬁls the Karush-Kuhn-Tucker

(KKT) conditions

DxL(x¯, λ ) = a , λ ∈ NK(g(x¯) − b),

(2)

where NK(y¯) = {z ∈ IRm | z, y − y¯ ≤ 0 ∀y ∈ K} is the normal cone of K at y¯ ∈ K. Note that by deﬁnition NK(y¯) = 0/ if y¯ ∈ K. In this sense, the feasibility condition g(x¯) − b ∈ K is included when saying that (x¯, λ ) fulﬁls (2). For ﬁrst-order optimality conditions and the theory of cone constrained programs at all we refer e.g. to Bonnans

and Shapiro [1]. For p = (a, b), denote by Σ (p) the set of all solutions (x¯, λ ) to the system (2).

A point (x¯, λ ) ∈ Σ (p) will be called critical point of problem P(p). By Λ (x¯, p) = {λ | (x¯, λ ) ∈ Σ (p)} we denote the set of multipliers associated with some x¯ in the set S(p) = {x | ∃λ : (x, λ ) ∈ Σ (p)} of stationary solutions of P(p).

The focus of our paper is to study situations in which the critical point multifunction Σ (resp. Λ or S) is in fact a locally single-valued and Lipschitz function, provided it has some multi-valued Lipschitz behavior called Aubin property. We say that a multifunction Γ from IRd to IRs has the Aubin property at some point (p¯, z¯) ∈ gphΓ = {(p, z) | z ∈ Γ (p)} (or, synonymously, the inverse multifunction Γ −1 is metrically regular at (z¯, p¯)), if there are neighborhoods U of p¯ and V of z¯ as well as some constant c > 0 such that for all p, p ∈ U and all z ∈ Γ (p) ∩V

there exists some z ∈ Γ (p ) such that z − z ≤ c p − p .

It is immediate from the deﬁnition that the Aubin property of Γ at (p¯, z¯) implies that Γ

has the Aubin property also at (p, z) ∈ gphΓ near (p¯, z¯). If Γ (p) ∩V is single-valued

on U then it becomes a locally Lipschitz function under the Aubin property. In this

case, Γ is called locally single-valued and Lipschitz around (p¯, z¯), or, synonymously, Γ −1 is strong regular at (z¯, p¯). For a detailed discussion of relations between different

stability and regularity notions we refer, e.g., to [17, 10, 6]. If F : IRd → IRd is a locally Lipschitz and directionally differentiable function,

then the Aubin property of Γ = F−1 at (z¯, p¯) gives that z¯ is an isolated (i.e., locally

unique) solution of the equation F(z) = p¯, see Fusek [7]. Of course, this applies to the critical point map Σ (a) = (D f )−1(a) of the unconstrained problem (1) for F = D f . Unfortunately, this does not mean that D f −1 is locally single-valued in this case, see Kummer’s example of a piecewise quadratic C1 function f in [12, Ex. 3] (cf. also [10, Ex. BE.4]). In contrast, if f is a C2 function then D f −1 becomes locally single-valued

under the Aubin property, by standard calculus arguments.

Aubin Property and Uniqueness of Solutions in Cone Constrained Optimization

3

What about constrained problems? For global minimizers, uniqueness follows from the Aubin property for general optimization problems, we refer to [10] and section 4 below. For critical points, the situation is much more involved. Dontchev and Rockafellar [5] studied a variational inequality F(z,t) − p ∈ NC(z) for a polyhedral convex set C and a C1 function F : IRd × IRκ → IRd with perturbation (t, p). They proved the equivalence of metric and strong regularity at solutions for this model, see Proposition 1 below. This result applies to the critical point map of a perturbed nonlinear program with C2 data, i.e., in our context, to the problem (1) with convex polyhedral set K and f , g ∈ C2.

Kummer [12] (see also [10, §7]) extended this results to the solution map of a socalled generalized Kojima system (cf. section 5 below) which covers the DontchevRockafellar model. In a recent paper, Outrata and Ram´ırez [14] show the equivalence of the Aubin property and strong regularity for the stationary solution set map of a second-order cone program under constraint nondegeneracy at a local minimizer of the initial problem. They use essentially the characterization of strong regularity for such problems given by Bonnans and Ram´ırez [2], however some ”weak” strict complementarity condition has to be supposed.

The paper is structured as follows. Section 2 is devoted to some preliminaries and basic notation. In section 3 we prove that nondegeneracy of a stationary solution and uniqueness of the multiplier for (1) necessarily follow from the Aubin property for the critical point map Σ . This has been known before only for special cases, cf. [5, 12, 10]. In section 4 we recall from [10, Ch. 4] the result on single-valuedness under the Aubin property for abstract global minimizing set mappings and apply this to convex cone constrained programs. Finally, section 5 is concerned with the equivalence of strong and metric regularity for critical point systems of (1) in the case of K being described by a ﬁnite system of nonlinear inequalities. This extends the well-known results for a convex polyhedral set K, cf. [5, 10].

2 Preliminaries

In this section we introduce further notation and terminology of this paper, and we

provide some basic tools and results which are needed in the next sections. Let C ⊂ IRm be a convex set. The relative interior of C is denoted by riC, while

spanC is the linear hull of C. A function g : IRn → IRm is called convex with respect

to C if the graph of the multifunction g(x) +C is convex.

If C is a convex closed cone, linC denotes the largest subspace in C, C− = {y∗ ∈ IRm | y∗, y ≤ 0 ∀y ∈ C} is the polar of C, and one has, by classical convex analysis, (C−)− = C and

(linC)⊥ = span(C−) ,

(3)

where ⊥ refers to the orthogonal complement. Given a linear subspace X of IRm, and writing A∗ for the adjoint of a linear operator A : IRn → IRm, we obviously have

AIRn + X = IRm if and only if Au∗∈u =X⊥0 ⇒ u = 0 . (4)

4

Diethard Klatte, Bernd Kummer

Given a closed convex set K ⊂ IRm, then TK(y¯) = NK(y¯)− denotes the tangent cone of K at y¯, where NK(y¯) is the normal cone as above. Again, TK(y¯) is empty by deﬁnition if y¯ ∈ K.

If K is a closed convex cone, one has λ ∈ NK(y) if and only if y ∈ NK− (λ ), i.e., in this case (2) is equivalent to

DxL(x¯, λ ) = a, g(x¯) − b ∈ NK− (λ ) ,

(5)

where obviously NK− (λ ) = K ∩ {µ ∈ IRm | µ, λ = 0}. We will refer in this paper at some places to a basic theorem on the equivalence of

metric and strong regularity given in [5]. Consider the perturbed generalized equation

0 ∈ p + F(z,t) + NC(z),

(6)

where C ⊂ IRd is a nonempty, polyhedral, convex set, F : IRd × IRκ → IRd is a locally Lipschitz function which is continuously differentiable w.r. to z, and q = (p,t) is a parameter vector varying around some initial point q0 = (p0,t0). Denote the solution set of (6) by S(q). Given (q0, z0) ∈ gph S, a linearized version of the generalized

equation (6) is given by

0 ∈ π + DzF(z0,t0)z + NC(z),

(7)

where the canonical parameter π varies around π0 = p0 + F(z0,t0) − DzF(z0,t0)z0. Let L(π) denote the solution set of (7).

Proposition 1 (Dontchev and Rockafellar [5, Thm. 3]) Given z0 ∈ S(q0) = L(π0),

the following properties are equivalent: 1. the solution map S of (6) has the Aubin property at (q0, z0), 2. the solution map S of (6) is locally single-valued and Lipschitz around (q0, z0), 3. the solution map L of the linearization (7) has the Aubin property at (π0, z0),

4. the solution map L of the linearization (7) is locally single-valued and Lipschitz around (π0, z0).

Note that property 4 is the concept of strong regularity in Robinson’s [15] sense.

Proposition 1 applies to the KKT system (2) of the cone constrained program (1) if

K is a convex polyhedral set: this is obvious if K is in addition a cone, due to (5),

otherwise a suitable transformation is needed, for details see [5].

In section 5 we will apply some basic result on persistence of metric or strong regularity of a continuous function F : IRd → IRs with respect to small Lipschitz perturbations F − g. Given a solution z¯ of the equation F(z) = 0, let Ω ⊂ IRd be some neighborhood of z¯ and let g : Ω → IRs be Lipschitz on Ω . We put

sup(g, Ω ) = sup{ g(z) | z ∈ Ω },

Lip(g, Ω ) = inf{r > 0 | g(z) − g(z ) ≤ r z − z ∀z, z ∈ Ω },

where · and · are given norms in IRd and IRs, respectively. Lip(g, Ω ) is called the Lipschitz rank of g. The space G = C0,1(Ω , IRs) of our (locally) Lipschitz variations g is supposed to be equipped with the norm

|g| = max{sup(g, Ω ), Lip(g, Ω )}.

(8)

Aubin Property and Uniqueness of Solutions in Cone Constrained Optimization

5

Persistence of strong regularity for generalized equations was originally studied by Robinson [15] for small C1-functions g. The following proposition was given by Kummer [13] (see also [10, §4.1]) in the more general context of perturbed inclusions, in our special form it already follows from Cominetti [4].

Proposition 2 (Klatte and Kummer [10, Cor. 4.4]) Let F be a continuous function from IRd to IRs. Suppose that g ∈ G satisﬁes sup(g, z¯+rB) = o(r) and Lip(g, z¯+rB) = O(r). Then F is metrically (resp. strongly) regular regular at z¯ if and only if so is F − g.

Here 0(·) and o(·) denote as usual functions of the type 0(t) → 0 and o(t)/t → 0 for t → 0 with 0(0) = 0 and o(0) = 0, while B is the unit ball in IRd.

3 Constraint nondegeneracy under Aubin property

In this section, we assume that f and g are C1 functions and that K ⊂ IRm is a closed

convex set. We shall show the Aubin property of the critical point map Σ implies that

the Lagrange multiplier is unique.

According to [1, 18] a point x¯ satisfying g(x¯) ∈ K is called nondegenerate with

respect to g and K if

Dg(x¯)IRn + lin TK(g(x¯)) = IRm.

(9)

This means surjectivity of Dg(x¯) whenever the cone is pointed. By (3) and (4), condition (9) is equivalent to

[ Dg(x¯)∗u = 0 ∧ u ∈ span NK(g(x¯)) ] ⇒ u = 0 ,

(10)

cf. [1, §4.6]. For a convex polyhedral cone K, (9) (and hence (10)) coincides with Robinson’s [16] deﬁnition of nondegeneracy; in the standard NLP case K = IRk− × {0m−k} this is the linear independence constraint qualiﬁcation (LICQ).

It is well-known (cf. e.g. [18, Thm. 2.1]) that

(x¯, λ¯ ) ∈ Σ (0) ∧ x¯ nondegenerate w.r. to g and K ⇒ Λ (x¯} = {λ¯ }, (11)

and conversely, Λ (x¯, 0) = {λ } and λ ∈ ri NK(g(x¯)) together imply that x¯ is nondegenerate w.r. to g and K.

To see (11) immediately, let λ 1, λ 2 ∈ Λ (x¯, 0). Then Dg(x¯)∗λ i = −D f (x¯) and λ i ∈ NK(g(x¯)) for i = 1, 2, hence Dg(x¯)∗(λ 1 − λ 2) = 0 and λ 1 − λ 2 ∈ span NK(g(x¯)), which implies λ 1 = λ 2 because of (10) and we are done.

Theorem 1 Given a critical point (x¯, λ¯ ) ∈ Σ (0), suppose Σ has the Aubin property at (0, (x¯, λ¯ )). Then x¯ is nondegenerate with respect to g and K, and so Λ (x¯, 0) = {λ¯ }.

Proof : Let (x¯, λ¯ ) ∈ Σ (0) and u ∈ IRm such that

Dg(x¯)∗u = 0 ∧ u ∈ span NK(g(x¯)).

We have to show that u = 0. If NK(g(x¯)) = {0} there is nothing to prove. Suppose NK(g(x¯)) = {0} and choose any w ∈ ri NK(g(x¯)) with w = 1. Deﬁne for any ε, δ > 0

a(ε) = εDg(x¯)∗w, b(δ ) = δ u.

6

Diethard Klatte, Bernd Kummer

Then we have λ¯ + εw ∈ NK(g(x¯)) from λ¯ , w ∈ NK(g(x¯)), and Dx f (x¯) + Dg(x¯)∗λ¯ = 0 implies Dx f (x¯) + Dg(x¯)∗(λ¯ + εw) = a(ε). Thus,

(x¯, λ¯ + εw) ∈ Σ (a(ε), 0).

For small ﬁxed ε, and for all δ ↓ 0, there are such elements (x, λ ) ∈ Σ (a(ε), b(δ )) which satisfy with some Lipschitz constant L the inequality of the Aubin property,

(x, λ ) − (x¯, λ¯ + εw) ≤ Lδ u .

(12)

By construction, λ¯ + εw ∈ ri NK(g(x¯)) and u ∈ span NK(g(x¯)), hence we can choose some small, but ﬁxed t > 0 such that

λ¯ + εw − tu ∈ NK(g(x¯)).

This implies, together with g(x) − b(δ ) = g(x) − δ u ∈ K,

0 ≥ λ¯ + εw − tu, g(x) − δ u − g(x¯) = λ¯ + εw − tu − λ , g(x) − δ u − g(x¯) + λ , g(x) − δ u − g(x¯) ≥ λ¯ + εw − λ − tu, g(x) − g(x¯) − δ u ,

where the last inequality follows from λ ∈ NK(g(x) − δ u) and g(x¯) ∈ K. Continuing this, we obtain, with µ = λ¯ + εw − λ ,

tδ u 2 ≤ µ, g(x¯) − g(x) + t u, g(x) − g(x¯) + δ µ, u .

(13)

By applying the mean-value theorem to the components gi of g, one has gi(x) − gi(x¯) = Dgi(ξ i)(x − x¯) with some ξ i between x and x¯.

Now the three terms in the right-hand side sum of (13) can be estimated as follows, recall that µ = λ¯ + εw − λ and x − x¯ fulﬁl the Lipschitz estimate (12). Indeed,

µ, g(x¯) − g(x) = ∑ µiDgi(ξ i)(x − x¯) ≤ ∑ |µi| Dgi(ξ i) x − x¯ = o(δ )

i

i

is obtained after applying the Lipschitz estimate (12) twice. Again by (12), δ µ, u ≤ δ µ u ≤ Lδ 2 u 2 = o(δ ).

Finally, we have Dgi(ξ i) → Dgi(x¯) , since Dg is continuous and ξ i → x¯ as δ ↓ 0, i.e.

u, g(x) − g(x¯) = t ∑ uiDgi(ξ i)(x − x¯) i

with ∑i uiDgi(ξ i) tending to Dg(x¯)∗u = 0 as δ ↓ 0. This yields

t u, g(x) − g(x¯) ≤ t ∑ uiDgi(ξ i) x − x¯ = o(δ ). i

Thus, (13) says, because of t > 0, δ u 2 = o(δ )

for arbitrarily small δ . This implies u = 0 and we are done.

Aubin Property and Uniqueness of Solutions in Cone Constrained Optimization

7

Remark 1 (Generalized equations). Theorem 1 similarly holds for the generalized

equation

F(x) + Dg(x)∗λ = a , λ ∈ NK(g(x) − b),

(14)

with g, K as above and some continuous function F. Its proof and that of (11) made nowhere use of the special form F(x) = D f (x) in (2). If K is a convex polyhedral set and F and Dg are continuously differentiable, then Theorem 1 is a special consequence of Proposition 1.

Remark 2 (Generalized Kojima systems). If the generalized equation (14) can be reformulated in equation form with a so-called (generalized) Kojima function, then Theorem 1 is Thm. 7.1 in [10], cf. also [12]. Note that this reformulation becomes possible if K itself is described by a system of smooth inequalities (under some constraint qualiﬁcation for this system), for details see [10, Chapt. 7]. Finally, in the context of nonlinear semideﬁnite programs, Fusek [8] has shown the uniqueness of the multiplier under the Aubin property of critical points.

4 Aubin property versus uniqueness for global minimizers

In this section, we recall a basic result on uniqueness of global minimizers to abstract optimization problems under the Aubin property and apply this to convex cone constrained programs of the form (1).

For the moment, we consider the abstract perturbed optimization problem

min ϕ(x,t) − a, x s.t. x ∈ M(t) ⊂ M (ϕ : M × T → IR), (15)

0/ = M ⊂ X, (X, ·, · ) Hilbert space, (T, d(·, ·)) metric space,

where t¯ ∈ T is an initial parameter, and (a,t) varies in X × T near (0,t¯) ∈ X × T measured by ρ((a,t), (a ,t )) = a − a + d(t,t ). Deﬁne by

Ψ (a,t) = argminx{ϕ(x,t) − a, x | x ∈ M(t)} the set of (global) optimal solutions of problem (15), and let Φ(a) = Ψ (a,t¯).

Lemma 1 [10, Lemma 4.6]. Given x¯ ∈ Φ(0), suppose that dist(x¯, Φ(a)) converges to zero for each sequence a → 0, i.e., Φ is lower semicontinuous at (0, x¯). Then Φ(0) = {x¯}.

Inspecting the proof of Lemma 4.6 in [10], one sees that the ”rich” (”tilt”) perturbation a, x in the objective function is crucial. Then one immediately has the following result which is a modiﬁcation of Corollary 4.7 in [10].

Theorem 2 (Aubin property and locally single-valued solutions). In the setting (15), the solution mapping Ψ has the Aubin property at ((0,t¯), x¯) ∈ gphΨ only if it is single-valued near (0,t¯).

Proof It follows from the Aubin property at ((0,t¯), x¯) that for certain neighborhoods U of (0,t¯) and V of x¯ and for all (a,t) ∈ U and x ∈ V with x ∈ Ψ (a,t),

Ψ (a,t) ∩V = 0/ and dist(x,Ψ (a ,t )) → 0 as (a ,t ) → (a,t).

Then Lemma 1 yields Ψ (a,t) = {x(a,t)} for all (a,t) ∈ U and some x(a,t) ∈ V .

8

Diethard Klatte, Bernd Kummer

Next we consider the perturbed cone constrained optimization problem (1) and suppose in addition to the general assumptions for (1) that f and g are continuously differentiable, f is a convex function and g is convex with respect to the set −K. Let us speak in this case of the convex problem (1) with C1 data.

Hence, by standard convex optimization (cf. e.g. [1, Prop. 3.3]), one has: if some (x¯, λ ) satisﬁes the KKT conditions (2), then x¯ is a global minimizer of the optimization problem P(p). Recall that Σ (p) (resp. S(p)) is the set of critical points (resp.stationary solutions) of P(p).

Corollary 1 (Single-valued solutions for convex programs). Consider the convex problem (1) with C1 data, and let (0, (x¯, λ¯ )) ∈ gph Σ . Then the critical point map Σ is single-valued and Lipschitz on a neighborhood of p = 0 if and only if Σ has the Aubin property at (0, (x¯, λ¯ )).

Proof The only-if direction follows from the deﬁnition of the Aubin property. To show the if-direction, we ﬁrst observe that the stationary point map S has the Aubin property at (0, x¯): Since Σ has the Aubin property, so also its component S at x¯. Thus, S is single-valued, say S(p) = {x(p)}, by convexity and Theorem 2.

Further, by deﬁnition, the Aubin property of Σ at (0, (x¯, λ¯ )) implies that Σ has the Aubin property at each (p, (x, λ )) ∈ gph Σ near (0, (x¯, λ¯ )). Hence, by Theorem 1, we have that p → Λ (x(p), p) is single-valued near p = 0, and so, Σ is also single-valued near p = 0.

Remark 3 (Strong regularity). Corollary 1 allows the application of conditions for strong regularity in the convex setting, when looking for the Aubin property of Σ . So, for example, strong regularity for linear semi-deﬁnite programs (i.e., a special convex cone constrained problem) was characterized in [3]. Further, characterizations of strong regularity of the KKT system at local minimizers were given for nonlinear problems of the type (1) with C2 data, by combining nondegeneracy of solutions with strong second-order optimality conditions: The case of standard nonlinear programs is classic, cf. e.g. [11, 15, 5, 1, 10], for semi-deﬁnite programs see e.g. [1, 19], for second-order cone programs we refer to [2]. In the convex setting, this gives also characterizations for the Aubin property of the KKT mapping.

5 Aubin property and locally single-valued critical points

Now we assume that the set K in the problem (1),

P(p), p = (a, b) : minx f (x) − a, x subject to g(x) − b ∈ K,

is deﬁned by ﬁnitely many inequalities,

K = {y ∈ IRm | h j(y) ≤ 0, j = 1, . . . , r} , h j : IRm → IR ,

(16)

write h = (h1, . . . , hr). We suppose throughout that f , g, h are C2 functions. Convexity of K is not required. Smooth equations could be added, we avoid this for simplicity.

In this section, we will discuss consequences of the Aubin property of the solution map Σ of the KKT system (2) if K is described by (16).

Aubin Property and Uniqueness of Solutions in Cone Constrained Optimization

9

For y ∈ K and under some constraint qualiﬁcation for the system h(y) ≤ 0 (e.g., under the Mangasarian-Fromovitz constraint qualiﬁcation (MFCQ)), the normal cone NK(y) has the representation, cf. e.g. [10, §7.2],

λ ∈ NK(y) ⇔ [ ∃µ ∈ IRr : λ = Dh(y)∗µ+ ∧ h(y) = µ− ] ,

(17)

where µ+j = max{µ j, 0} and µ−j = min{µ j, 0}. This is simply a brief description of

the cone of the active gradients Dh j(y), j ∈ I(y), with I(y) = { j | h j(y) = 0}.

For the rest of this section, let x¯ be a stationary solution of the problem (P)=P(0),

and put g¯ = g(x¯). Suppose that MFCQ is satisﬁed for the system h(y) ≤ 0 at y = g¯.

Setting

G(x) = h(g(x)), which gives DG(x)∗ = Dg(x)∗Dh(g(x))∗,

(18)

formula (17) allows to write the KKT system (2) for the initial problem (P) at x = x¯ and y = g¯ in the following equivalent (Kojima [11]) form

D f (x) + DG(x)∗µ+

F(x, µ) = G(x) − µ−

= 0 , λ from (17) .

(19)

System (19) is the Kojima system for the optimization problem

min f (x) such that G(x) ≤ 0 ∈ IRr.

(20)

With canonical perturbations (a, c), the equation

F(x, µ) = a ∈ IRn+r

(21)

c

describes (equivalently) the KKT-points of

min f (x) − a, x such that G(x) ≤ c.

(22)

For the classical perturbations (22), the Aubin property and strong regularity are

equivalent at the reference point by applying Proposition 1 to a standard nonlinear program with C2 data f , g.

We also know (Thm. 1) that for both properties LICQ (i.e., rank DG(x¯) = r) is a necessary condition, which does not hold, e.g. if r > n. However, LICQ is needed as long as all parameters c ∈ IRr are taken into account which does not happen here.

Indeed, we have

g(x) − b ∈ K ⇔ h(g(x) − b) ≤ 0;

g(x), b ∈ IRm

h : IRm → IRr, g : IRn → IRm G : IRn → IRr

(23)

Setting r(x, b) = G(x) − h(g(x) − b), the constraints h(g(x) − b) ≤ 0 or g(x) − b ∈ K

coincide with

G(x) ≤ cˆ := r(x, b).

(24)

Denote by ker A and im A the kernel and the image of a linear operator A, respectively. Recall that nondegeneracy (9) required Dg(x¯)IRn + lin TK(g¯) = IRm and that

lin TK(g¯) = ker Dh(g¯). So (9) means, in the current context,

Dg(x¯)IRn + ker Dh(g¯) = IRm.

(25)

This has consequences for uniqueness of the Lagrange multipliers µ+ in (19) (µ− as slack variable is always unique).

10

Diethard Klatte, Bernd Kummer

Lemma 2 Under nondegeneracy (9), the Lagrange multiplier µ+ at the reference point x¯ is uniquely deﬁned up to the orthogonal space (im Dh(g¯))⊥ of im Dh(g¯). Hence, supposing µ+ ∈ im Dh(g¯) in (19), µ+ is unique at the reference point.

Proof Assume that µ is not unique at x¯, i.e.,

λ = ∑ α jDG j(x¯) = ∑ β jDG j(x¯), α = β , α, β ≥ 0

j∈J(x¯)

j∈J(x¯)

holds for some λ ∈ NK(g¯), where J(x¯) = { j | G j(x¯) = h j(g(x¯)) = 0}. This implies

0 = ∑ (α j − β j)Dh j(g¯)Dg(x¯).

(26)

j∈J(x¯)

Using (25) we know: For any y ∈ IRm there are u ∈ IRn and w ∈ ker Dh(g¯) with Dg(x¯)u + w = y. Multiplying in (26) with u, then yields

0 = ∑ (α j − β j)Dh j(g¯)(y − w) = ∑ (α j − β j)Dh j(g¯)y.

j∈J(x¯)

j∈J(x¯)

This holds for all y ∈ IRm. Thus (26) implies that α − β , with zero-components for j ∈/ J(x¯), is necessarily orthogonal to Dh(g¯)IRm = im Dh(g¯). Conversely, if (α −

β ) ⊥ im Dh(g¯) then (26) is evident.

Next we suppose nondegeneracy (9). F can be written in product form as in [10, §7.1], namely, with identity matrix I,

D f (x) DG(x)∗ 0 1

F(x, µ) =

µ+ = M (x) V (µ).

(27)

G(x) 0 −I µ−

With the (partial) linearization of F at x¯

FL(x, µ) = [M (x¯) + DM (x¯)(x − x¯)] V (µ)

(28)

let us study the parametrization

FL(x, µ) = a ∈ IRn+r for c, µ ∈ im Dh(g¯) only.

(29)

c

Notice that

c ∈ im Dh(g¯) and DG(x¯)(x − x¯) ∈ im Dh(g¯)

yield µ− = DG(x¯)(x − x¯) − c ∈ im Dh(g¯) .

Hence µ = µ+ + µ− ∈ im Dh(g¯) holds exactly if µ+ ∈ im Dh(g¯). For the polyhedral system (29), metric and strong regularity at ((x¯, µ¯ ), (0, 0)) coincide by Proposition 1.

Now it follows from Proposition 2 that metric and strong regularity at (x¯, µ¯ ) also coincide for the (not linearized) system

F(x, µ) = a ∈ IRn+r for c, µ ∈ im Dh(g¯) .

(30)

c