Sensitivity Analysis of Optimization Problems Under Second Order Regular Constraints.
We present a perturbation theory for finite dimensional optimization problems subject to abstract constraints satisfying a second order regularity condition. This is a technical condition that is always satisfied in the case of semi-definite optimization. We derive Lipschitz and Holder expansions of approximate optimal solutions, under a directional constraint qualification hypothesis and various second order sufficient conditions that take into account the curvature of the set defining the constraints of the problem. We show how the theory applies to semi-infinite programs in which the contact set is a smooth manifold and the quadratic growth condition in the constraint space holds, and discuss the differentiability of metric projections as well as the Moreau-Yosida regularization. Finally we show how the theory applies to semi-definite optimization.
Introduction
In this paper we present a theory that allows to compute the asymptotic expansions of the
optimal value function v(u), as well as the optimal or "nearly optimal" solutions x(u) of
parametric optimization problems of the form
f(x; u) subject to G(x; u) 2 K:
While the theory is fairly complete in the framework of mathematical programming where
the set K is polyhedral, the question is far from being settled in general, particularly when
dealing with infinite dimensional problems.
The differentiability properties of v(u) and x(u) strongly depend on the second order behavior
of the unperturbed optimization problem, namely, quadratic growth and second order
optimality conditions. Therefore, an essential difficulty in the general setting comes from the
curvature (in a properly defined sense) that may appear with non-polyhedral constraint sets
K. A number of generalized notions of polyhedricity have permitted to develop a perturbation
theory for some relevant classes of infinite dimensional optimization problems [3, 13, 18].
Nevertheless, the curvature terms seem unavoidable for such problems as semi-infinite programming
(i.e. minimization problems with an infinite number of inequality constraints) or
semi-definite optimization. The latter is the particular case of (P u is the
space of p \Theta p symmetric matrices, and
is the cone of positive semi-definite matrices.
When f and G are affine functions, the semi-definite optimization problem is known as the
linear matrix inequalities (LMI) problem
(LMI) Min
where A - 0 is used to denote A 2 S p
. This is an important particular case which has been
recognized in the past few years as a very convenient framework for optimization problems
arising in various fields [7, 8]. However, relatively few papers have considered sensitivity
analysis of such problems. The best results obtained so far, which are due to [26], provide
explicit formulas for the expansion of the value function, solution and multiplier, under
rather restrictive hypothesis which permit the use of the implicit function theorem.
An alternative approach for treating these difficult problems by taking into account the
curvature of K, has emerged recently [3, 4, 9, 14, 15]. The novelty in this approach is the use
of second order tangent sets and a second order property of the set K, called (inner) second
order regularity, introduced in [3]. In [4] we discussed the weaker condition of outer second
order regularity, under which there is no gap between second order necessary and sufficient
optimality conditions. In the present paper we explore the implications and limitations of
inner regularity in connection with sensitivity analysis of optimal solutions of perturbed
optimization problems.
RR n-2989
4 J. Fr'ed'eric Bonnans , Roberto Cominetti , Alexander Shapiro
We begin by studying the sensitivity results in the abstract setting (P u ). We then show
how they apply in the framework of semi-infinite programming, and particularly for semi-definite
optimization problems. Before proceeding with the abstract results, let us illustrate
some of them through an elementary example where the computations can be carried out
explicitly.
Example. Consider the family of convex semi-definite problems
Min
where ff is a given nonnegative constant, and u 2 IR is a real parameter. When the
above problem has a unique optimal solution -
which satisfies Slater's condition.
Moreover, there exists a unique Lagrange multiplier
and the second order growth condition (hence the strong second order sufficient
holds. The linearized problem, which captures the first order behavior of the optimal value
function, is given by
Min
with unique optimal solution -
ff) if ff ? 0, and no solution if
When ff ? 0 Theorem 4.1 (see section 4) applies: since the linearized problem has a
unique optimal solution, the same holds for the auxiliary second order approximating problem
and we get
When Theorem 5.1 applies, leading to an expansion of the form
u).
We will discuss this case in section 7.
Our perturbation analysis is based on: (i) a concept of second order regularity, (ii)
second order sufficient optimality conditions, and (iii) the directional constraint qualification
introduced in [3]. We distinguish between three basic cases, in the spirit of [3, 5]. The first
and second cases, illustrated in the example above, are when the strong and weak (second
sufficient optimality conditions hold, leading respectively to Lipschitz and H-older
stability of optimal trajectories. The third case is when the set of Lagrange multipliers is
empty, and the optimal solutions are once again H-older stable of degree 1=2. The derived
results are similar to those obtained for nonlinear programming problems, except for the
additional terms related to the curvature of the set K.
The paper follows the method of upper and lower estimates of the objective function
[3, 5, 12, 14, 22, 23]. The upper estimates are those obtained in [3]. The novelty lies in the
theory of lower estimates and the expansion of approximate solutions.
INRIA
Sensitivity analysis of optimization problems under second order regular constraints 5
Preliminaries
In this section we review some known results on first order sensitivity analysis and second
order optimality conditions, that are needed in the sequel. We also fix the notations used
throughout the paper.
2.1 Basic notation
We consider the parametrized family of optimization problems (P u
mappings of class C 2 . The space of "decisions" X is assumed to be
finite dimensional, U is a topological vector space of "parameters", and the "constraint" set
K is a nonempty closed convex subset of the Banach space Y with topological dual Y   . The
feasible set, optimal value, and set of optimal solutions of (P u ) are denoted respectively
Similarly, given an optimization problem (P ), we denote by \Phi(P ), v(P ) and S(P ), the
feasible set, the optimal value, and the set of optimal solutions of (P ).
For we view the corresponding optimization problem (P 0 ) as unperturbed and
assume that it has an optimal solution x We shall consider perturbations along a
fixed direction d 2 U , that is to say, we investigate the local behavior of the optimal value
and optimal solutions of the problems (P td we say that a point
is an "-optimal solution of (P u ". For a nonnegative
valued function "(t) we shall also consider trajectories x(t) of "(t)-optimal solutions of (P td ).
The support function of T ae Y at y   2 Y   is oe(y
Tg is the distance function to T . The tangent and normal
cones to the set K at the point y 2 K are defined as
fy
Finally, for a function IR, we denote by h 0 (y; d) its directional derivative
If h 0 (y; d) exists for every d 2 Y we say that h is directionally differentiable at y, and we
define (when it exists) the parabolic second order directional derivative
RR n-2989
6 J. Fr'ed'eric Bonnans , Roberto Cominetti , Alexander Shapiro
2.2 First order analysis
Optimality conditions for (P u ) are usually stated in terms of the associated Lagrangian and
generalized Lagrangian
The Fritz John necessary conditions for a local minimum x of (P u ) are
The set   g
u (x) of generalized Lagrange multipliers (ff; -) 6= (0; may be
empty when Y is a general Banach space. However   g
in two important cases: when
Y is finite dimensional and also when K has a non empty interior [17, 28].
If the multiplier ff in (2.3) is non zero, then we can take and the corresponding
first order necessary conditions become
The set   u (x) of Lagrange multipliers satisfying (2.4) is non empty and bounded [19, 28],
whenever the following constraint qualification, due to Robinson [20], holds
Let us summarize the first order differentiability properties of the optimal value function
v(u) and the optimal solutions. To this end, for the given perturbation direction d 2 U and
the (unperturbed) optimal solution x we consider the following linearization of the
family of problems (P td ),
together with its dual (cf. [1, 27])
(DL d ) Max
The directional constraint qualification at the point x 0 in the direction d, which is essentially
Robinson's constraint qualification for (PL d ), is (cf. [1] and [3, Part I])
It is clear that (CQ) implies (DCQ), and that both conditions are equivalent if
INRIA
Sensitivity analysis of optimization problems under second order regular constraints 7
Theorem 2.1 Suppose that (DCQ) holds. Then there is no duality gap between problems
lim sup
Moreover, the common value v(PL d which
case the set S(DL d ) of optimal solutions of (DL d ), is a non empty weak   compact subset of
Furthermore, if there exists an o(t)-optimal trajectory -
x(t) of (P td ) such that k-x(t)\Gammax 0
O(t), then the directional derivative v 0 (0; d) exists and v 0 (0; d) = v(DL d ). In the latter case
coincides with the set of accumulation points of the differential quotients (x(t)\Gammax 0 )=t
where x(t) ranges over the set of all possible o(t)-optimal trajectories of (P td ).
For a discussion of this result and relevant references, the reader is referred to [6].
2.3 Second order optimality conditions
Let us briefly state the theory of second order optimality conditions for the unperturbed
problem (P 0 ). To this end we skip the argument u, and all derivatives are understood with
respect to x only.
Recall that the second order tangent set to K at the point y 2 K in the direction
z 2 TK (y) is defined as
and that (under some first order qualification conditions) a second order necessary optimality
condition is given by (see [4, 9, 15])
sup
is the critical cone
Unfortunately, for sufficient conditions it is not enough to change the weak inequality in
(2.7) into a strict one, but one needs the following concept (see [4]),
Definition 2.1 A set A ae Y is an upper second order approximation set for K at the point
in the direction z 2 TK (y) with respect to a linear mapping
sequence
being a convergent
sequence in Y and fq k g ae X satisfying t k q k ! 0, the following condition holds
lim
RR n-2989
8 J. Fr'ed'eric Bonnans , Roberto Cominetti , Alexander Shapiro
If this holds for any M , i.e. (2.8) is satisfied for any sequence y
that t k # 0 and t k r k ! 0, we say that A is an upper second order approximation set for K
at y in the direction z.
A sufficient condition for x 0 to be a local optimum is (see [4])
sup
where A(h) is any upper second order approximation set for K at the point G(x 0 ) in the
direction DG(x 0 )h with respect to the linear mapping DG(x As a matter of
implies the following quadratic growth condition at x 0 : there exist a constant
c ? 0 and a neighborhood N of x 0 such that
Notice that (2.9) requires the set   g (x 0 ) to be nonempty, i.e. it implies that the corresponding
first order necessary conditions hold at x 0 . We refer to (2.9) as the
generalized second order sufficient condition, and to the term oe(-; A(h)) appearing in (2.9)
as the sigma term.
K (y; z) is contained in every upper second order approximation set A, the gap
between (2.7) and (2.9) reduces to a change from weak to strict inequality whenever one can
take
K (h). This remark leads to the following concept (see [4])
Definition 2.2 We say that the set K is second order regular at a point y 2 K in a direction
z 2 TK (y) with respect to a linear mapping the second order tangent set
K (y; z) is an upper second order approximation set to K at y in the direction z with respect
to M . If this holds for every linear mapping M and every direction z, we simply say that
K is second order regular at y.
Various conditions ensuring this second order regularity are discussed in [4]. In particular
it is shown that the cone S p
of p \Theta p symmetric positive semi-definite matrices is second
order regular at every point y
.
Remark. Let us point out that the second order regularity used in [4] concerns the
outer second order tangent sets, so that the above concept should rather be called inner
second order regularity. Since in this paper we deal exclusively with the inner version, we
shall omit the term "inner".
3 Lipschitzian and H-older directional stability of optimal
solutions
In this section we discuss quantitative stability of optimal or "nearly optimal" trajectories
for (P td ). We start our discussion with Lipschitzian stability where perturbations of optimal
INRIA
Sensitivity analysis of optimization problems under second order regular constraints 9
solutions are of the same order as perturbations of parameters. For that purpose we need
to strengthen the second order sufficient conditions (2.9) in the following way
sup
where A(h) is an upper second order approximation set for K at the point G(x in the
direction D x G(x with respect to the linear mapping
We refer to (3.1) as the strong second order sufficient conditions. These conditions were
formulated for nonlinear programming problems (i.e., without the "sigma" term) in [23]. In
the Banach space framework they were used in [27], also without the "sigma" term.
Let us remark that (3.1) can only hold if the set S(DL d ) of optimal solutions of the
problem (DL d ) is non empty, which implies of course that the set   0
multipliers is non empty. Clearly the strong second order sufficient conditions depend on
the chosen direction d, unless the set   0 singleton or the constraint mapping G(x; u)
does not depend on u. When K is second order regular at G(x 0 ; 0), we can take
Theorem 3.1 Let - x(t) be an O(t 2 )-optimal trajectory of (P td ) converging, as t # 0, to a
point satisfying the (DCQ). Suppose that
and that the strong second order sufficient conditions (3.1) hold. Then - x(t) is Lipschitz
stable at x 0 , i.e. for t - 0,
Proof. We argue by a contradiction. Suppose that (3.3) is false and choose a sequence
and the space X is finite dimensional, we can assume
by passing to a subsequence if necessary, that h k converges to a point h 2 X n f0g.
)-optimal and under (DCQ) we have v(td) -
I]), we get
the left hand side in the previous inequality is - k D x f(x
hence we obtain D x f(x
get
We can write x k in the form x
(D x G(x
RR n-2989
J. Fr'ed'eric Bonnans , Roberto Cominetti , Alexander Shapiro
Since A(h) is a second order approximation set to K at the point G(x in the direction
and with respect to the linear mapping (D x G(x since
(D x G(x
denotes the unit ball in Y .
Let us now use the strong second order sufficient conditions (3.1) to select - 2 S(DL d )
such that
for some - ? 0. It follows from (3.5) that
(D x G(x
By using the second order expansion
(D x f(x
together with (3.6) and (3.7), and since D x L(x
Since v(PL d last inequality contradicts (3.2), and hence the
proof is complete.
Remarks. Assumption (3.2) holds under the (DCQ) and if the following conditions are
satisfied ([3, 24]): the linearized problem (PL d ) has an optimal solution - h(d) such that
In case the optimal solution - h exists, condition (3.9) holds if the second order tangent set
empty. If the space X is reflexive (in particular finite
dimensional), then existence of an optimal solution of (PL d ) is a necessary condition for
Lipschitzian stability (3.3), [3]. As we shall see in the next section, second order sufficient
conditions of the type (3.1), with
are "almost" necessary
for having the Lipschitzian stability (3.3). For nonlinear programming, where the sigma term
vanishes, this was already observed in [23].
INRIA
Sensitivity analysis of optimization problems under second order regular constraints 11
As we already mentioned, the generalized second order sufficient conditions (2.9) do not
guarantee Lipschitzian stability of optimal solutions. Nevertheless these conditions imply
H-older stability of degree 1=2. The proof of the following result is similar to the previous
one and is based on the upper estimate v(td) - instead of the stronger bound
(3.2) (cf. [3]).
Theorem 3.2 Let -
x(t) be an O(t)-optimal trajectory of (P td ) converging, as t # 0, to a
point satisfying the (DCQ). Suppose that the generalized second order sufficient
conditions (2.9) hold. Then for t - 0,
4 Second order expansions of the first kind
In this section we obtain a quadratic expansion for the optimal value function v(td) and a
first order expansion for optimal solutions. To obtain an upper estimate of v(td) we consider
paths of the form
If the path x(t) is feasible, an expansion of G(x(t); td) leads to (cf. [3])
and
where
A similar expansion of the objective function leads to the following optimization problem
By minimizing it further with respect to h 2 S(PL d ) we obtain (see [3] for details),
Proposition 4.1 Let x be an optimal point satisfying (DCQ) and suppose   0
;. Then for t - 0,
lim sup
The dual problem of (PQ d;h ) can be written in the form,
RR n-2989
J. Fr'ed'eric Bonnans , Roberto Cominetti , Alexander Shapiro
It is possible to show by methods of convex analysis that under (DCQ) and assuming that
the sets T 2
K (h; d) and   0 are non empty, for all h 2 S(PL d ) there is no duality gap
between (PQ d;h ) and (DQ d;h ) and their common value is finite (cf. [21],[3]).
The upper estimate (4.5) has the following lower counterpart in which the set T 2
is replaced by an upper second order approximation.
Proposition 4.2 Let x (DCQ). For each h 2 S(PL d ), let A(h; d) be
an upper second order approximation set for K at in the direction DG(x 0 ; 0)(h; d)
with respect to D x G(x 0 ; 0). Suppose that   0 empty and that there exists an
lim inf
where v(Q d ) is the optimal value of the problem
Proof. The proof is similar to the one of Theorem 3.1. Consider a sequence t k # 0 and
stable at x 0
we have that h k are bounded so that, passing to a subsequence if necessary, we may assume
that h k ! h for some h 2 X , for which it is not difficult to show that h 2 S(PL d ) (see [3]).
We can write x
using the second order expansion
(D x G(x
we may deduce
Similarly we also get
It follows from (4.8) that
h-; D x G(x
where the term o(1) can be taken independently of - since S(DL d ) is bounded. By adding
half times t 2
k of the above term to the right hand side of (4.9), and since D x L(x
we obtain
INRIA
Sensitivity analysis of optimization problems under second order regular constraints 13
arbitrary and h 2 S(PL d ), we obtain (4.6) as claimed.
Recall that sufficient conditions for Lipschitzian stability of optimal solutions are discussed
in Theorem 3.1. The lower estimate (4.6) coincides with the upper estimate (4.5) if for
every h 2 S(PL d ) the second order tangent set T 2
K (h; d) can serve as an upper second order
approximation set, that is, under the additional condition of second order regularity. Thus
we deduce the following second order expansion of the optimal value function.
Theorem 4.1 Let x (DCQ). Suppose that   0 empty, that
there exists an o(t 2 )-optimal trajectory -
x(t) of (P td ) such that
that for every h 2 S(PL d ) the set K is second order regular at G(x 0 ; 0) in the direction
d) with respect to D x G(x
(i) For t - 0,
where v(Q d is the optimal value of the problem
(ii) Every accumulation point - h of being an o(t 2 )-optimal
trajectory of (P td ), is an optimal solution of the problem (Q d ). If in addition -(t) is a
Lagrange multiplier associated with x(t), then every weak   accumulation point of -(t) belongs
to S(DL d ).
be an optimal solution of (Q d ) and let -
w be a corresponding optimal solution of
(assuming that such optimal solutions exist). Then there exists an o(t 2 )-optimal
trajectory for (P td ) of the form -
Proof. From propositions 4.1 and 4.2 it follows that
lim inf
From the computation in the proof of proposition 4.2, it follows that any limit point of
solution of (Q d ). As oe(-; T 2
This proves (i).
If - h is an accumulation point of then as we mentioned in the proof of
proposition 4.2, - h 2 S(PL d ) and the first part of statement (ii) follows from (4.11) and
(4.5). Let - be a weak   accumulation point of -(t), where -(t) is a Lagrange multiplier
associated with x(t). It is easily proved that - is a Lagrange multiplier associated with x 0 .
From the inequalities h -
and a first order expansion of G(x(t); td) \Gamma G(x As
- h is feasible for (PL d ), and - is feasible for the dual problem (DL d ), statement (ii) follows.
Because of (DCQ), it follows by [3, Part I, Theorem B.2] that there exists a feasible path
- x(t) of (P td ) of the form specified in (iv). Moreover, f(-x(t);
statement (iv) follows.
The following is an immediate consequence of the assertion (ii) in the above theorem.
RR n-2989
14 J. Fr'ed'eric Bonnans , Roberto Cominetti , Alexander Shapiro
Corollary 4.1 Suppose that, in addition to the assumptions of theorem 4.1, problem (Q d )
possesses a unique optimal solution h   . Let -
x(t) be an o(t 2 )-optimal trajectory of (P td ) such
that O(t). Then - x(t) is right side differentiable at and the corresponding
right side derivative is equal to h   .
Let us give a sufficient condition for uniqueness of the optimal solution of the problem
(Q d ). Let us observe first that for any -, the function /(z) := \Gammaoe(-; T 2
K (y; z)) is convex.
Indeed, consider z
convexity of K, we have that
and hence
were arbitrary elements of the corresponding second order tangent sets,
we obtain that the function oe(-; T 2
K (y; \Delta)) is concave, and hence /(\Delta) is convex. It follows
that if, for every - 2 S(DL d ), the Hessian D 2
positive definite over the linear
space generated by the (convex) set S(PL d ), then the max-function of the problem (Q d ) is
strictly convex over this linear space and hence S(Q d ) is a singleton.
The right side derivative of -
x(t), at can be viewed as the directional derivative, in
the direction d, of the corresponding o(kuk 2 )-optimal solution -
x(u) of (P u ). Note also that
if there exists an O(t 2 )-optimal trajectory -
x(t) of (P td ) which is Lipschitz stable at x 0 , then
The above inequality and (4.5) can hold together only if inf h2S(PLd
is the recession cone of S(PL d ) (provided S(PL d ) is non empty), and since under
(DCQ) we have v(PQ d;h that under these assumptions the following
second order conditions
sup
are necessary for Lipschitzian stability of optimal
solutions. Note the similarity of (4.15) with the strong second order conditions (3.1).
Theorem 4.1 extends previous results obtained in the framework of nonlinear programming
[1, 5, 23]. The main difference between the results presented in Theorem 4.1 and those
obtained in the nonlinear programming setting is the additional curvature term ("sigma"
term) and the assumption of nonemptiness of S(PL d ). The condition (DCQ) and the existence
of Lagrange multipliers (which follows from the strong second order sufficient condi-
tions) imply that (PL d ) has a finite value and that its dual (DL d ) has an optimal solution.
INRIA
Sensitivity analysis of optimization problems under second order regular constraints 15
In the nonlinear programming setting, the corresponding optimization problem (PL d ) is
linear and it has optimal solutions as soon as its optimal value is finite. However, for general
non polyhedral sets K we have to postulate that S(PL d ) is non empty. If this is not true,
then as we mentined earlier, o(t)-optimal trajectories are not Lipschitz stable. In that case
we may apply the analysis of the second kind that follows.
5 Expansion of the second kind
In this section we discuss situations where approximate optimal solutions are H-older stable
of degree 1=2 (see Theorem 3.2) and the set of Lagrange multipliers is non empty. Then it
is convenient to consider paths of the form
It follows that
Expanding G(x(t); td) in a similar way we obtain that if the path x(t) is feasible, then
and
where
We need an additional assumption. We say that the strong directional constraint qualification
(SDCQ) holds if (DCQ) is satisfied and, given a path x(t) of the form (5.1) and such that
(5.3) and (5.4) hold, then for close to 1 one can find z z, and a
feasible path x fl (t) satisfying
x
In [3, Part II], where this assumption was introduced, it was proved that (SDCQ) is a
consequence of (DCQ) whenever the set K has a nonempty interior, which is the case for
semi-definite and semi-infinite optimization. Note also that (SDCQ) is satisfied whenever
(CQ) holds.
Consider the problem
ae
Min z2X 2Df(x
oe
and its dual
(D 2
f2D
RR n-2989
J. Fr'ed'eric Bonnans , Roberto Cominetti , Alexander Shapiro
Theorem 5.1 Let - x(t) be an o(t)-optimal trajectory for (P td ) converging to a point x
Suppose that the set of Lagrange multipliers   0
that for every h 2 C(x 0 ) the set K is second order regular at G(x 0 ; 0) in the direction
with respect to D x G(x and that the following (weak) second order conditions
hold
sup
Then:
x(t) is H-older stable of degree 1/2, i.e.
(ii) There is no duality gap between problems (Q 2
d ) and (D 2
d ), and their common value
d ) is less than or equal to 2v(PL d ).
(iii) The optimal value function can be expanded as
(iv) If h 2 X is an accumulation point of t \Gamma1=2
(v) If (Q 2
d ) has an optimal solution
z) and (CQ) holds, then there exists an o(t)-optimal
trajectory x(t) of (P td ) such that
Proof. By the second order conditions (5.7) and the second order regularity of the set
statement (i) follows from Theorem 3.2. Assertion (ii) and the upper estimate
are consequences of [3, Part II, Theorem 3.1]. To prove the converse inequality in (5.9) let
be an arbitrary sequence. Letting x k := - x(t k ) and using part (i), by passing to a
subsequence if necessary, we may assume that t \Gamma1=2
Hence we may write x
An expansion of G(x d)
similar to (5.2) and the second order regularity of K lead to D x G(x
and
Since
we have D x f(x
Using D x L(x
INRIA
Sensitivity analysis of optimization problems under second order regular constraints 17
This being true for any - 2   0
f2D
Together with (5.9) this proves (5.8), i.e. (iii), as well as h 2 S(D 2
It remains to prove (v). It follows from (CQ) that there exists a feasible path of the form
o(t). Computing the expansion of f(x(t); td), we find that x(t) is
an o(t)-optimal trajectory, and the proof is complete.
It may be surprising to observe that under quite natural assumptions (directional constraint
qualification and the standard second order sufficient conditions), the first order expansion
(5.8) of the optimal value function involves the second order information, included
in the problem (D 2
d ), and perturbed optimal solutions are not Lipschitz stable. This is already
true for nonlinear programming problems. In that case the above theorem reduces
to results presented in [12] and [5]. The upper estimate (5.9) was obtained in the Banach
space framework in [3].
Note that if the second order conditions (4.15) hold, then are
optimal solutions of the problem (D 2
d ) and hence v(D 2
Therefore we obtain
the following
Corollary 5.1 Suppose that the assumptions of Theorem 5.1 hold as well as the second
order conditions (4.15). Then for t - 0,
6 Expansion of the third kind
In this section we discuss a situation similar to the one considered in the previous section
except that the set of Lagrange multipliers is assumed to be empty. We consider a point
satisfying the Fritz John optimality conditions, i.e. we assume that the set   g
generalized Lagrange multipliers is non empty. These two conditions,   0
imply that if (ff; -) 2   g
We consider again paths of the form
(5.1). The main difference from the previous case is that now variations of the optimal value
function are of order O(t 1=2 ), and for can be negative. Consider the
following subset of the critical cone
It is worth pointing out that when   0
assuming (SDCQ), a
point h belongs to C 2 only if (see [3, Part II])
RR n-2989
J. Fr'ed'eric Bonnans , Roberto Cominetti , Alexander Shapiro
Theorem 6.1 Let -
x(t) be an o(t)-optimal trajectory of (P td ) converging to a point x
satisfying the Fritz John optimality conditions (2.3) and the (SDCQ). Suppose that
the set of Lagrange multipliers   0 empty, that for every h 2 C(x 0 ) the set K is second
order regular at G(x 0 ; 0) in the direction D x G(x with respect to D x G(x 0 ; 0), and that
the generalized second order sufficient conditions (2.9) hold with
K (h). Then:
x(t) is H-older stable of degree 1/2, i.e.
(ii) The optimal value function may be expanded as
where v(Q 3
d ) is the optimal value of the problem
(iii) If h is an accumulation point of t \Gamma1=2
The proof of this theorem is similar to that of Theorem 5.1 and will be omitted (see
also [3, Part II]). Theorem 6.1 extends similar results obtained for nonlinear programming
problems in [2].
7 Applications and examples
In this section we discuss some applications and particular examples of the developed theory.
7.1 Second order regularity in semi-infinite programming
Let us first show that Theorem 4.1 itself can be used to verify second order regularity of a
set defined by an infinite number of inequalities. Suppose that for every x 2 X the function
concave and that the mapping G(x) does not depend on u, and consider
the set
\Theta := fu
where \Phi := fx Kg. Since the functions f(x; \Delta) are concave, the set \Theta is
convex. Clearly the set \Theta can be also defined in the form \Theta
v(u) := inf x2\Phi f(x; u) is the corresponding optimal value function.
Consider a point u 0g the set of minimizers
of f(\Delta; and in the later case the set \Delta 0 is the set
of minimizers of f(\Delta; Suppose that there exists a compact set \Sigma such that for all
u in a neighborhood of u 0 and some ff ? v(u 0 ),
INRIA
Sensitivity analysis of optimization problems under second order regular constraints 19
We refer to this assumption as the inf-compactness condition. By Danskin theorem [11],
under the inf-compactness condition, the optimal value function v(u) is directionally differentiable
at its directional derivative is given by
We assume that \Delta 0 is non empty and denote
We also assume that the following second order growth condition holds for the function
there exist a neighborhood N of \Delta 0 and c ? 0 such that
Theorem 7.1 Suppose that the Slater condition holds, i.e. there is - u such that f(x; - u) ? 0
for all x 2 \Phi, that the set \Delta 0 is non empty and finite, that the inf-compactness condition
and the second order growth condition (7.3) hold, that for every x the (CQ) holds and
for every h 2 C(x 0 ) the set K is second order regular at G(x 0 ) in the direction DG(x 0 )h
with respect to DG(x 0 ). Then the set \Theta is second order regular at u 0 and, if in addition
\Theta
d) is the optimal value of the problem
Min
Proof. Consider a point x As we mentioned earlier, x 0 is a minimizer of f(\Delta;
subject to the constraint G(\Delta) 2 K and hence can be viewed as an optimal solution of the
corresponding (unperturbed) problem (P u0 ). Note that in the present case the constraint
mapping G(\Delta) does not depend on u. By restricting the optimization problem to a neigh-
borhhod of x 0 , we obtain from Theorem 4.1 that the corresponding optimal value function
- v(u) can be expanded as
where - x0 (d; w) is the optimal solution of the problem
Min
fD
The additional term D u in the above expansion appears since the optimal value
function is expanded now along the parabolic curve (with the additional term 1t 2 w), and
this term is equal to D u since G(\Delta) does not depend on u. Note also that the set
RR n-2989
J. Fr'ed'eric Bonnans , Roberto Cominetti , Alexander Shapiro
of the corresponding Lagrange multipliers is non empty because of the (CQ) and
that existence of Lipschitz stable optimal solutions is ensured by the second order growth
and inf-compactness conditions. Such analysis can be performed at every point of the set \Delta 0
and the optimal value function v(u) is given by the minimum of the optimal value functions
corresponding to points x Consequently we obtain that the optimal value function
v(u) is second order directionally differentiable and its second order directional derivative
given by the minimum of functions - x0 (d; w), x Because of the
Slater condition this implies (7.4), as proved in [4].
Note that, under the Slater condition, T \Theta (u 0 0g. Therefore if
\Theta d) is empty. Also if v 0
\Theta d) is the whole
space U . Consequently, in order to show second order regularity of \Theta, we have to consider
only the case when v 0 Consider a sequence u
r k such that
Consider also a point x and a path
using the second order expansion of
G(x(t)), it is not difficult to see that such a path can be feasible, for small t - 0, only if
By the Robinson-Ursescu stability theorem, because of the (CQ), the above condition is
also sufficient for existence of such feasible path. Let x k := x(t k
z k be
such that G(x k
where the term o(t 2
k ) can be taken uniformly in z for z in a bounded subset of X . Moreover,
where \Xi is the set formed by those z 2 X satisfying (7.7). By duality the minimum in (7.9)
is equal to the maximum in (7.5) and hence
Since the above inequality holds for any x by the Slater condition and (7.4) it
follows that r k 2 T 2
\Theta which proves the second order regularity assertion.
7.2 Differentiability of metric projections
As an another application of Theorem 4.1, let us consider the question of directional differentiability
of metric projections. Let K be a convex closed subset of IR n and for a point
denote by PK (u) the point in K closest to u (with respect to the Euclidean norm
can be defined as the optimal solution of the problem
Min
INRIA
Sensitivity analysis of optimization problems under second order regular constraints 21
and is called the metric projection of u onto K. There are examples of a convex set K
in IR 3 (and even in IR 2 ) such that the corresponding metric projection is not directionally
differentiable at a point u 0 62 K ([16, 25]).
The vector u in (7.10) can be viewed as a perturbation parameter in a neighborhood of
a given point u 0 . Let us observe that all assumptions of Theorem 4.1 hold, provided the
set K is second order regular at the point x 0 := PK (u 0 ). For a given direction d 2 IR n , the
auxiliary problem (Q d ) can be written in the form
Min
By the discussion following Corollary 4.1, we have that the objective function in (7.11)
is strongly convex. Since it is assumed that the set K is second order regular at x 0 , the
second order tangent set T 2
we have that oe(-; T 2
valued for all h 2 C(x 0 ). It
follows that the objective function in (7.11) is also finite valued for h 2 C(x 0 ) , and hence the
optimization problem (7.11) possesses a unique optimal solution. We obtain the following
result (see Corollary 4.1).
Theorem 7.2 Suppose that the convex set K ae IR n is second order regular at the point
directionally differentiable at
where h   is the optimal solution of the problem (7.11).
7.3 An application to semi-definite programming
Consider, for example, the space S p of p \Theta p symmetric matrices equipped with the scalar
product and the corresponding (Frobenius) norm kAk :=
ij . It is shown in [4] that the set S p
of positive semi-definite matrices
is (inner) second order regular at every point. Therefore the theory presented in this paper
can be applied in a straightforward manner to semi-definite programming problems.
Consider the cone K := S p
and a point
. If B is positive definite,
then B belongs to the interior of S p
and in that case TK singular, then
is an n \Theta s matrix whose columns
an orthonormal basis of the null space of B. Furthemore, consider H 2 TK (B).
If the matrix E T HE is positive definite, then the second order tangent set T 2
K
K
is the Moore-Penrose pseudo inverse of B, and being
an orthonormal basis of the null space of the s \Theta s matrix E T HE (see [26] for a discussion
and derivation of these formulas).
RR n-2989
22 J. Fr'ed'eric Bonnans , Roberto Cominetti , Alexander Shapiro
For example, consider the metric projection PK (\Delta) onto the set K := S p
. It is well
known that PK
i is the spectral decomposition
of A (i.e. ff i and e i are eigenvalues and corresponding orthonormal eigenvectors of A),
I 0g. It follows from Theorem 7.2
that PK (\Delta) is directionally differentiable at every point A 2 S p even if A has several zero
eigenvalues. Suppose that A 62 S p
. The directional derivative P 0
K (A; D) is then given by
the optimal solution of the corresponding auxiliary problem which we now calculate.
We have that the corresponding Lagrange multipler is given by
If I + is empty, i.e. the matrix A is negative semi-definite, then
K
i and it follows from (7.13)
that (cf. [26])
Therefore the auxiliary problem can be written in the form
Min
where
\Gamma2 tr
hi P
and is the corresponding critical cone given by
is the matrix whose columns are the vectors e i , is the matrix whose
columns are e i ,
. Alternatively the cone C can
be written in the form
We see that the objective function in (7.14) is quadratic and that C is a linear space iff the
set I 0 is empty, i.e. iff A does not have zero eigenvalues. Therefore we obtain that PK (\Delta) is
differentiable at A 62 K iff A does not possess zero eigenvalues.
Example. Consider the example discussed in the introduction. When ff ? 0 all calculations
are simple, as computing second order terms is not necessary. When Theorem
INRIA
Sensitivity analysis of optimization problems under second order regular constraints 23
5.1 applies. The critical cone is
-, and the
Lagrangian simplifies to L(x; -;
, The auxiliary problem (D 2
d ) reduces to
Min
"'
The cost function of this subproblem is the sum of two nonnegative functions. Therefore it
has the unique optimal solution -
It follows that any o(u)-optimal
trajectory x(u), u - 0, satisfies
u). As a matter of fact, by direct computation
we find that the perturbed problem has a unique optimal solution -



--R

First and second order sensitivity analysis of nonlinear programs under directional constraint qualification conditions
Directional derivatives of optimal solutions in smooth nonlinear pro- gramming
Perturbed optimization in Banach spaces I: a general theory based on a weak directional constraint qualification
Second order necessary and sufficient optimality conditions under abstract constraints
D'eveloppement de solutions exactes et approch'ees en programmation non lin'eaire
Optimization problems with perturbations
Linear Matrix inequa- lities

tangent sets and second order optimality conditions
Tangent sets to unilateral convex sets
The Theory of Max-Min and Its Applications to Weapons Allocation Problems
Directional behavior of optimal solutions in nonlinear mathematical programming
How to differentiate the projection on a convex set in Hilbert space.
On sensitivity analysis of nonlinear programs in Banach spaces
An envelope-like effect of inifinitely many inequality constraints on second order necessary conditions for minimization problems
a discontinuous envelope function and a non-differentiable nearest point mapping
On the existence and nonexistence of Lagrange multipliers in Banach spaces

First order conditions for general nonlinear optimization
Stability theorems for systems of inequalities
Conjugate Duality and Optimization
Perturbation theory of nonlinear programs when the set of optimal solutions is not a singleton
Sensitivity analysis of nonlinear programs and differentiability properties properties of metric projections
On Lipschitzian stability of optimal solutions of parametrized semi-infinite programs
Directionally nondifferentiable metric projection
First and second order analysis of nonlinear semidefinite programs
Sensitivity analysis of parametrized programs under cone constraints
Regularity and stability for the mathematical programming problem in Banach spaces
--TR

--CTR
Jong-Shi Pang , Defeng Sun , Jie Sun, Semismooth homeomorphisms and strong stability of semidefinite and Lorentz complementarity problems, Mathematics of Operations Research, v.28 n.1, p.39-63, February
Defeng Sun, The Strong Second-Order Sufficient Condition and Constraint Nondegeneracy in Nonlinear Semidefinite Programming and Their Implications, Mathematics of Operations Research, v.31 n.4, p.761-776, November 2006
parametric optimization;semi-definite programming;directional constraint qualification;semi-infinite programming;directional differentiability;sensitivity analysis;metric projection;optimal value function;second order optimality conditions