Differential Stability of Two-Stage Stochastic Programs.
Two-stage stochastic programs with random right-hand side are considered. Optimal values and solution sets are regarded as mappings of the expected recourse functions and their perturbations, respectively. Conditions are identified implying that these mappings are directionally differentiable and semidifferentiable on appropriate functional spaces. Explicit formulas for the derivatives are derived. Special attention is paid to the role of a Lipschitz condition for solution sets as well as of a quadratic growth condition of the objective function.
Introduction
Two-stage stochastic programming is concerned with problems that require a here-
and-now decision on the basis of given probabilistic information on the random data
without making further observations. The costs to be minimized consist of the direct
costs of the here-and-now (or first stage) decision as well as the costs generated by the
need of taking a recourse (or second stage) decision in response to the random environ-
ment. Recourse costs are often formulated by means of expected values with respect
to the probability distribution of the involved random data. In this way, two-stage
models and their solutions depend on the underlying probability distribution. Since
this distribution is often incompletely known in applied models, or it has to be approximated
for computational purposes, the stability behaviour of stochastic programming
models when changing the probability measure is important. This problem is studied
in a number of papers. We only mention here the surveys [13], [37] and the papers [1],
This research is supported by the Deutsche Forschungsgemeinschaft
[12], [17], [24], [25], [31] and [32]. The paper [1] contains general results on continuity
properties of optimal values and solutions when perturbing the probability measures
with respect to the topology of weak convergence. Quantitative continuity results of
solution sets to two-stage stochastic programs with respect to suitable distances of
probability measures are derived in [24] and [25]. Asymptotic properties of statistical
estimators of values and solutions to stochastic programs are derived in [17], [31], [32].
They are based on directional differentiability properties of the underlying optimization
problems with respect to the parameter that carries the randomness ([17], [32]) or the
probability measure ([31]). These directional differentiability results for values (in [32])
and solutions (in [17], [31]) lead to asymptotic results via the so-called delta-method .
For a description of the delta-method we refer to Chapter 6 in [26], [32], to [33] for
an up-to-date presentation and to [15] for a set-valued variant. These papers illuminate
the importance of the Hadamard directional differentiability (for single-valued
functions) and of the semidifferentiability (for set-valued mappings) in the context of
asymptotic statistics.
The present paper aims at contributing to this line of differential stability studies. The
results in [17], [31] apply to fairly general stochastic optimization models, but impose
conditions that are rather restrictive in our context. The present paper deals with
special two-stage models and, using structural properties, avoids certain assumptions
that complicate or even prevent the applicability of those general results to two-stage
stochastic programs. Such assumptions are the (local) uniqueness of solutions and
differentiability properties of perturbed problems, which are indispensable in [17], [31].
Before discussing this in more detail, let us introduce the class of two-stage stochastic
programs, we want to consider:
is a nonempty closed convex set, A
is a (s; m)-matrix and Q - is the expected recourse function with respect to the (Borel)
probability measure - on IR s ,
Z
~
~
Here
m are the recourse costs, W is an (s; -
m)-matrix and called the recourse
matrix, and ~
corresponds to the value of the optimal second stage decision
for compensating a possible violation of the (random) constraint To have the
problem (1.1) - (1.3) well-defined, we assume
Z
first moment).
The assumptions (A1) and (A2) imply that ~
Q is finite, convex and polyhedral on
. Due to (A3) also Q - is finite and convex on IR s (cf. [14], [36]). Observe that,
in general, an expected recourse function Q - may be nondifferentiable on a certain
union of hyperplanes in IR s and that, indeed, differentiability properties of Q - depend
on the degree of smoothness induced by the measure - (cf. [14], [19], [35], [36] and
Remark 4.8). Another observation shows that the uniqueness of solutions to (1.1) is
guaranteed only if the constraint set C picks just one element from the relevant level
set of g(\Delta) +Q - \Delta). This set may be large since Q - \Delta) is constant on translates of the
null space of the matrix A (see Example 1.1 in [25]). Proposition 2.1 below provides
some more insight into the structure of the solution set to (1.1) and elucidates the role
of the set-valued mapping oe(y) yg in this respect.
Note that assumption (A1) could be relaxed by introducting the set
+1g. Then (A2) and (A3) imply that K is a closed convex polyhedron and
that Q - is convex and continuous on K (cf. [36]). Now (A1) can be replaced by the
condition K ' A(C) (relatively complete recourse), and much of the work done in this
paper carries over to this more general setting by using spaces of functions defined on
K instead of IR s .
Let K C denote the set of all convex functions on IR s which forms a convex cone in the
space C 0 (IR s ) of all continuous functions on IR s . K C will serve as the set of possible
perturbations of the given expected recourse function Q - 2 K C . We define
and regard ' and / as mappings from K C into the extended reals and the set of all
closed convex subsets of IR m , respectively.
In this paper we develop a sensitivity analysis for the mappings ' and / at some given
function Q - . The stochastic programming origin of the model (1.1) takes a back seat
and our results are stated in terms of general conditions on Q - and its perturbations
Q. We identify conditions such that the value function ' has first- and second-order
directional derivatives and the solution-set mapping / is directionally differentiable at
admissible directions. Here, admissibility means that the direction belongs to
the radial tangent cone to K C at Q - , i.e.,
ensuring that the difference quotients are well-defined. For v belonging to T r (K C
the Gateaux directional derivatives of ' and / at Q - and (Q -
tively, are defined as
if the limits exist. The third limit is understood in the sense of (Painlev'e-Kuratowski)
set convergence (e.g. [2]). Recall that the lower and upper set limits of a family (S t ) t?0
of subsets of a metric space (X; d) are defined as
lim inf
lim sup
Both sets are closed and the lower set limit is contained in the upper limit. If both limits
coincide, the family (S t ) t?0 is said to converge and its limit set is denoted by lim
For sequences of sets (S n ) n2IN the definitions of set limits are modified correspondingly.
We also derive conditions implying that the limits defining the directional derivatives
exist uniformly with respect to directions v belonging to compact subsets of certain
functional spaces. The limits are then called (first- or second-order) Hadamard directional
derivatives and semiderivatives for set-valued maps, respectively. The corresponding
directional derivatives are defined on tangent cones to the cone of convex
functions in certain functional spaces. For more information on concepts of directional
differentiability and multifunction differentiability we refer to [5], [30] and to [2], [4],
[21], [23], respectively.
Let us fix some notations used throughout the paper. k \Delta k and h\Delta; \Deltai denote the norm
and scalar product, respectively, in some Euclidean space IR n ; B(x; r) denotes the open
ball around x 2 IR n with radius r ? 0; d(x; D) denotes the distance of x 2 IR n to the
set D ' IR n ; for a real-valued function f on IR n , rf denotes its gradient in IR n and the
its Hessian; if f is locally Lipschitzian near x 2 IR n , @f(x) denotes
the Clarke subdifferential of f at x; f 0 (x; d) denotes the directional derivative of f at
x in direction d if it exists; for denotes the tangent cone to C at x, i.e.,
cl stands for closure;
for denotes the second order tangent set to C at x in
direction -, i.e., T 2 (C; x;
closed and
convex; see [10] for further properties).
In our paper, we use the following linear metric spaces of real-valued functions on
The space C 0 (IR s ) of continuous functions on IR s equipped with the distance
d1 (f; ~
f) =X
\Gamman kf \Gamma ~
, where
kyk-r
jf(y)j, for f; ~
the space C 0;1 (IR s ) of locally Lipschitzian functions on IR s with the metric
d L (f; ~
f) =X
\Gamman kf \Gamma ~
, where
y
the space C 1 (IR s ) of continuously differentiable functions on IR s with the metric d(f; ~
d1 (f; ~
and the space C 1;1 (IR s ) of functions in C 1 (IR s )
whose gradients are locally Lipschitzian on IR s equipped with the distance d(f; ~
d1 (f; ~
f) for all f 2 C 1;1 (IR s ).
The sensitivity analysis of the mappings ' and / is carried out by exploiting structural
properties of the optimization model (1.1). We obtain novel differentiability properties
of solution sets and extend our earlier results on directional differentiability of optimal
values in [12] considerably. As one might expect, the basic ingredients of our analysis
are a Lipschitz continuity result for solution sets with respect to the distance in
(Theorem 2.3) and a quadratic growth condition near solution sets (Theo-
rem 2.6). Both theorems extend earlier results in [25] to more general situations for
the first stage costs g and constraint set C. All results in the paper apply to the
linear-quadratic case, i.e., to linear or convex quadratic g and polyhedral C. Indeed,
all results are formulated as general as possible and most of them are accompanied by
illustrative examples. The second-order analysis of ' in Section 3 utilizes some ideas
from [28] and [29], but its proof is entirely different and its Gateaux differentiability
part is valid for nondifferentiable directions (Theorem 3.4). It is also elaborated that
the Hadamard directional differentiability properties require the C 0 -topology for the
first-order result and the C 1 -topology for the second-order one (Theorem 3.8), while
the C 1;1 -topology is needed for the semidifferentiability of the solution-set mapping /
(Theorem 4.7). All results on differentiability properties of / in Section 4 are new and
do not follow from recent sensitivity results (as e.g. [3], [6], [7], [16], [29]; see also the
survey [8] for further references).
The results of Sections 3 and 4 have direct implications to asymptotic properties of
values and solution sets of two-stage stochastic programs when applying nonparametric
estimation procedures to approximate Q - . For a discussion of some of the related
aspects we refer to [11], where the delta-method is utilized and a central limit theorem
for all selections belonging to a Castaing representation of the approximate solution
sets is derived. Further applications to asymptotics are beyond the scope of this paper
and will be done elsewhere.
Basic directional properties
The first step in our analysis of directional properties consists in establishing results
on the lower Lipschitz continuity of / and on the directional uniform quadratic growth
of the objective near its solution set. Both results become important for our method
of deriving directional differentiability properties for the optimal value function ' and
the solution set mapping / at some given expected recourse function Q - . Their proofs
are based on a decomposition of the program
with Q belonging to K C , into two auxiliary problems. The first one is a convex program
with decisions taken from A(C) and the second represents a parametric convex program
which does not depend on Q.
Proposition 2.1 Let Q 2 K C and /(Q) be nonempty. Then we have
Moreover, - is convex on A(C) and dom oe is nonempty.
Proof. Let -
For the converse inequality, let " ? 0 and -
be such that
Then there exists a -
"-
is arbitrary, the first statement has been shown. In particular, x 2 oe(Ax)
and Ax 2 Y (Q) for any x 2 /(Q) . Hence, it holds that /(Q) ' oe(Y (Q)). Conversely,
implying
Since the convexity of - is immediate, the proof is complete. 2
In the following, it will turn out that Lipschitzian properties of the solution set mapping
y 7! oe(y) and a quadratic growth property of g near oe(y) are essential. For the linear-quadratic
case we are in a comfortable situation in this respect. Namely, we have the
following
Proposition 2.2 Let g be linear or convex quadratic, C be convex polyhedral and assume
dom oe to be nonempty. Then oe is a polyhedral multifunction which is Hausdorff
Lipschitzian on its domain dom there exists a constant L ? 0 such that
yk; for all
where dH denotes the (extended) Hausdorff distance on subsets of IR m .
Moreover, for each r ? 0 there exists a constant j(r) ? 0 such that
(Here - and oe are defined as in Proposition 2.1).
Proof. The Lipschitz property of oe is shown in [18], Theorem 4.2. To prove the second
statement, let g be of the form positive
semidefinite and c 2 IR m . For each y 2 A(C) we fix some z(y) 2 oe(y). An elementary
characterization of solution sets to convex quadratic programs with linear constraints
yields that
Due to the Lipschitz behaviour of convex polyhedra (cf. [34]), there exists a constant
for all y 2 A(C) and x 2 C with y. Using the decomposition
2 denotes the square root of H, and the representation
one arrives at the estimate
for all y 2 A(C) and x 2 C with y.
us fix some element -
r) and a corresponding
oe(A-x). For each y 2 A(C) we now select z(y) 2 oe(y) such that
Hausdorff Lipschitzian on A(C), this
implies A(C). Hence, there exists a constant
r). Thus our estimate continues
to d(x;
and some constant -
Furthermore, the equation
implies kH 1
y.
Therefore, we finally obtain
for all x
Due to the above proposition, the main results in this section apply to the linear-quadratic
case. Although this case represents the main application of our results, the
assumptions of the following theorems are formulated in terms of general conditions on
the mapping oe in order to gain generality and clarity. The first theorem states (lower)
Lipschitz continuity of / at Q - and supplements Theorem 2.4 in [25].
Theorem 2.3 Let Q nonempty, bounded and Q - be strongly convex
on some open, convex neighbourhood of A/(Q - ). Let -
assume that there
exist a constant L ? 0 and a neighbourhood U of -
y with
Then there exist constants -
Proof. We may assume that U is open, convex and that Q - is strongly convex on U .
Let V be an open, convex, bounded subset of IR m such that /(Q -
It follows from Proposition 2.3 in [25] (where a slightly different terminology is used)
that there exists a constant
cl A(V
chosen such that cl A(V
r). Hence, we have ; 6=
Proposition 2.1 yields the relation
strongly convex
on U , there exists a constant - ? 0 such that
belongs to A(V ) ae U ,
we obtain
and, hence,
yk --
--
The proof can now be completed as follows. Let Q 2 K C be such that
Then
Remark 2.4 The proof shows that a Lipschitz modulus of / can be chosen as the
quotient of a Lipschitz constant to oe and a strong convexity constant to Q - .
From the proof it is immediate that replacing the local Lipschitz condition on oe by
stronger conditions like
sup
leads to corresponding stronger Lipschitz continuity properties of solution sets. Because
of Proposition 2.2, all of this applies to the linear-quadratic case. However, it is worth
mentioning that the theorem also applies to more general problems such that the
corresponding solution sets oe(y) enjoy Lipschitzian properties. Conditions ensuring
Lipschitz behaviour of oe can be derived from stability results for the corresponding
parametric generalized equation
which describes the first order necessary optimality condition. Here L(x; -; y) := g(x)+
is the Lagrangian function, rL(x; -;
, where g is
assumed to be continuously differentiable, and N C \ThetaIR s is the normal cone map of convex
analysis. Such stability results are presently available for broad classes of parametric
generalized equations (e.g. [16], [20], [22]). A typical recent result in this direction,
which applies to our situation for twice continuously differentiable g, is Theorem 5.1
in [20]. It says that the solution set mapping of the parametric generalized equation
(2.2) is pseudo-Lipschitzian around (-x; -
y) if the adjoint generalized equation
has only the trivial solution w
Here D   N C \ThetaIR s (-x; -; \GammarL(-x; -
y)) is the Mordukhovich coderivative ([20]) of the normal
cone multifunction at the point (-x; -; \GammarL(-x; -
belonging to the graph of
. Translating this into our framework, we obtain that the mapping oe is pseudo-
Lipschitzian around (-x; -
y) if the following two conditions are satisfied:
(a) There exists an element -
x belonging to the relative interior of C such that
y
(Slater
(b) the equations Aw
have only the trivial solution w is a solution
of (2.2) for
y.)
The next example shows that the theorem also applies to instances of two-stage stochastic
programs with nonpolyhedral convex constraint sets C.
Example 2.5 In (1.1) -
be the uniform distribution on [\Gamma 1; 1] and
x g. Then we have ~
R
jyj otherwise ,
strongly convex on (\Gamma 1; 1). For y we have
and, hence d((0; 0); . Thus Theorem 2.3 applies for -
Example 2.8 shows that Theorem 2.3 gets lost if Q - fails to be strongly convex on some
neighbourhood of A/(Q - ). Our next result establishes a sufficient condition for the
uniform quadratic growth near solution sets.
Theorem 2.6 Let Q nonempty, bounded and Q - be strongly convex
on some open convex neighbourhood U of A/(Q - ). Assume that there exists a constant
yk; for all
and, for each r ? 0 there exists a constant j(r) ? 0 such that
Then, for some open, bounded neighbourhood V of /(Q - ) and each
there exist constants c ? 0 and ffi ? 0 such that the following uniform growth condition
holds:
for all x
Proof. Let be an open, bounded subset of IR m such that
As in Theorem 2.3 we choose ffi ? 0 such that ; 6=
and, in addition, that strongly convex on U for all t 2 [0; ffi)
(with a uniform constant - ? 0). For each t 2 [0; ffi) Proposition 2.1 then yields that
is the unique minimizer of the strongly convex function
- +tv on A(C) and, moreover, we have -ky \Gammay t k 2 -(y)+(Q - +tv)(y)\Gamma'(Q - +tv),
for all y . Now, we choose r ? 0 such that V ' B(0; r) and continue for
each
Putting c
completes the proof. 2
The following examples show that the quadratic growth condition gets lost even for
the original problem, i.e. either the Lipschitz condition for oe or the strong
convexity property for Q - are violated.
Example 2.7 Consider again the set-up of Example 2.5. It holds that dH (oe(y);
oe is not Hausdorff Lipschitzian on A(C).
Supposed there exists a neighbourhood V of /(Q -
such that the growth condition
is satisfied. Since the sequence (( 1
belongs to C " V for sufficiently large n 2 IN ,
this would imply %( 1
for large n, which is a contradiction.
Example 2.8 In (1.1) -
- be the probability distribution on IR having the density
R
jyj otherwise ,
there is no neighbourhood of /(Q - ) where Q - is strongly convex.
It is clear that the quadratic growth condition fails to hold, since the inequality %x 2 -
cannot be true for some % ? 0 and all x belonging to some
neighbourhood of
With the linear function we obtain for all t 2 [0; 1] that /(Q -
f
(cf. Example 3.7). Hence, the lower Lipschitz property of / has got lost, too.
Since the strong convexity and later also the strict convexity of the expected recourse
function Q - (on certain convex subsets of IR s ) form essential conditions in most of our
results, we record a theorem (Theorem 2.2 in [27]) that provides a handy criterion to
check these properties for problem (1.1) - (1.3).
Proposition 2.9 Let V ae IR s be open convex and assume (A1), (A3). Consider the
following conditions:
absolutely continuous on IR s ;
there exist a density f - for - and a constant
Then (A2)   and (A4) imply that Q - is strictly convex on V if V is a subset of the
support of -, and (A2)   , (A4)   imply that Q - is strongly convex on V .
In addition, it is shown in [27] that under (A1) - (A4) the condition (A2)   is also
necessary for the strict convexity of Q - . For extended simple recourse models (i.e.
is equivalent to q
(componentwise), where This may be used to check
strict or strong convexity properties in the Examples 2.5 and 2.8.
Directional derivatives of optimal values
In this section, we study first- and second-order directional differentiability properties of
the optimal value function ' on its domain K C . We begin with the first-order analysis
and show that ' as a mapping from K C to the extended reals is Hadamard directionally
differentiable at some given expected recourse function Q - 2 K C . Here K C is regarded
as a subset of C 0 (IR s ). Recall that ' is Hadamard directionally differentiable at Q - on
K C iff for all sequences (v n ) converging to some v in C 0 (IR s ) and all sequences t n ! 0+
such that the elements belong to K C the limit
exists. Since the condition means that v
the limit v belongs to the tangent cone T (K C ; Q - ) to K C at Q - in C 0 (IR s ). In
[32], [33] this property is also called Hadamard directional differentiability tangentially
to K C .
Proposition 3.1 Let Q - 2 K C and assume that /(Q - ) is nonempty, bounded. Then
' is Hadamard directionally differentiable at Q - on K C and it holds for all v 2
If, in addition, Q - is strictly convex on some open convex neighbourhood of A/(Q - ),
we have
Proof. Arguing similarly as in the proof of Propostion 2.1 in [24] there exists a
neighbourhood N of Q - in C 0 (IR s ) such that /(Q) is nonempty for all Q
sequences such that t n ! 0+,
belongs to K C for all n 2 IN . Then sufficiently large n 2 IN .
upper semicontinuous at Q -
([24]), the sequence has an accumulation point x 2 /(Q - ) and we obtain
lim sup
where the last inequality follows from the uniform convergence of (v n ) to v on bounded
subsets of IR s . In order to show the reverse inequality for lim inf, let x 2 /(Q - ). Then
lim inf
This completes the proof of the first part. The second part is an immediate conclusion,
since A/(Q - ) is a singleton whenever Q - is strictly convex on some of its open, convex
neighbourhoods. 2
The preceding result can also be proved by using the methodology of Theorem 6.4.1 in
[26]. There the compactness of the constraint set is assumed and Gateaux directional
differentiability of ' at Q - together with its Lipschitz continuity is shown. Here we
prefer a direct two-sided argument, which will also be used in the subsequent second-order
analysis of '. Namely, we will first derive an upper bound for the second-order
Hadamard directional derivative of ' at some Q - 2 K C , where K C is equipped with
the C 0;1 -topology. Secondly, we identify conditions implying that the upper bound
coincides with the Gateaux directional derivative of ' at Q - for all directions taken
from T r (K C
Lemma 3.2 Let y sequence in K C such that
sequence converging to - in IR s .
Then we have lim sup
(v
Proof. Each function v n is locally Lipschitzian on IR s and, hence, Lebourg's mean
value theorem for Clarke's subdifferential ([9]) implies the existence of elements ~ y n
belonging to the segments
(v
The convergence v n ! v in C 0;1 (IR s ) implies that
n!1holds for any r ? 0. This yields
0:
Here dH denotes the Hausdorff distance and the inequality is a consequence of general
properties of the subdifferential (cf. Lemma 2.1 in [25]). Hence, there exist elements
~
belonging to @v(~y n ) such
(v
and, for some ~
lim sup
(v
Here, the identity follows from the upper semicontinuity of @v(\Delta). This completes the
proof. 2
Proposition 3.3 Let Q - 2 K C and assume that /(Q - ) is nonempty, bounded. Let g
be twice continuously differentiable, Q - be strictly convex on some open convex neighbourhood
of A/(Q - ) and twice continuously differentiable at -
y, where
sequence in K C such that v n := 1
in C 0;1 (IR s ). Then
lim sup
x) is the tangent
cone to C at -
x and T 2 (C; -
x; -) the second order tangent set to C at -
x in direction -.
Proof. Let -). Then there exists a sequence (z n ) such that
Using Proposition 3.1, this allows for
the following estimate
After dividing by t 2
n and using Lemma 3.2 the limes superior as of the right-hand
side can be bounded above by
Taking the infimum on the right-hand side yields the assertion. 2
We notice that the upper second-order Hadamard directional derivative
lim sup
nonpositive, since ' is concave on K C
and, hence, the inequality '(Q - +t n v n
We also note that the upper bound is nonpositve, since (0;
belongs to S(-x) \Theta T 2 (C; - x;
Next we consider particular perturbations Q n of Q - , namely, Q
for some Q 2 K C sufficiently large n 2 IN . Then v
In the following result we give conditions implying that the second-order
directional derivative exists and coincides with the upper bound of the
previous proposition. The result extends those in [12] although its proof parallels in
parts that of Theorem 3.6 in [12].
Theorem 3.4 Let Q - 2 K C and assume that /(Q - ) is nonempty, bounded. Let g be
twice continuously differentiable, Q - be strictly convex on some open convex neighbourhood
of A/(Q - ) and twice continuously differentiable at - y, where
assume that
(ii) the second-order set S 2 (-x; -) := fz 2 T 2 (C; -
is nonempty for each - 2 S(-x).
Then the second-order Gateaux directional derivative of ' at Q - in direction v exists
and it holds that
Moreover, the infimum is attained at some -
having the property that
-).
(Here S(-x) and T 2 (C; -
are defined as in the previous result, v 0 (-y; j) is the directional
derivative of v at -
y in direction j and O(t) denotes a real quantity such that 1
jO(t)j is
bounded as t ! 0+.)
Proof. (i) implies that there exist constants L ? 0,
expanding g and Q - and
using Proposition 3.1 we obtain
xi +2
xi
Moreover, we have that
denotes a real quantity having
the property 1
the optimality of - x implies
for any t 2 (0; ffi), we
Now take a sequence (t n ) tending to 0+ in such a way that
lim inf
and that - n := 1
-. The latter is possible since k 1
sufficiently large. Then -
x) and Proposition 3.1 yields
This implies -
From (3.1) and (3.2) we obtain
lim inf
Here we have used the fact that v is Hadamard directionally differentiable and Clarke
regular ([9]), i.e. v 0 (-y;
ji. From Proposition 3.3 we obtain
lim sup
The latter equality is due to (ii) and to the fact that the necessary optimality condition
for - x yields
Hence, the limit lim
exists and is equal to the
infimum subject to - 2 S(-x). Moreover, this infimum is attained at -
S(-x). For the
remainder of the proof we put a(-) := v 0 (-y; A-) and
Since S(-x) is a (convex) cone, we have
-)); for all - ? 0:
In case of B( -
-) ? 0, the quadratic function f vanishes at with the property
and the final assertion is shown. If B( -
the fact that
-) holds for any - ? 0, implies a( -
-) and the proof is complete. 2
The proof shows that the previous theorem remains true when replacing condition
(ii) by the condition that both infima in (3.3) coincide. Next we state a more handy
criterion implying that ' 00 (Q - ; v) exists for any direction v 2 T r (K C
Corollary 3.5 Let Q - 2 K C and assume that /(Q - ) is nonempty, bounded. Let g be
twice continuously differentiable, Q - be strongly convex on some open convex neighbourhood
of A/(Q - ) and twice continuously differentiable at -
y where
assume that
(i) 0 there exist a constant L ? 0 and a neighbourhood U of - y such that
(ii) the second-order set S 2 (-x;
is nonempty for each - 2 S(-x).
Then the second-order Gateaux directional derivative of ' at Q - exists for any direction
the formula for ' 00 (Q - ; v) in Theorem 3.4 holds true.
Moreover, condition (ii) is satisfied if C is polyhedral and (i) 0 is satisfied for any - x 2
in addition to the polyhedrality of C, g is linear or (convex) quadratic.
Proof. Let Theorem 2.3 then says that there exist constants -
Hence, the strong convexity of Q - and condition (i) 0 imply that condition (i) of the
previous theorem is satisfied and that the first part of the assertion is shown. If C
is polyhedral, we have T 2 (C; -
x). Hence, (ii) is satisfied. If C is polyhedral and g is linear or (convex)
quadratic, Proposition 2.2 implies (i) 0 to hold for any -
Let us consider two illustrative examples to provide some insight into the benefit and
limits of the previous results.
Example 3.6 We revisit Example 2.5 and know that condition (i) 0 is satisfied for
Furthermore, it holds that T (C; -
Hence, (ii) and the general assumptions of Corollary 3.5 are satisfied and ' 00 (Q - ; v)
exists for any v 2 T r (K C ; Q - ). It holds that ' 00 (Q -
IRg. Let us finally replace the function g(x) j 0
by
IR, and condition (ii) is violated. But, since we have
both infima in (3.3) coincide, the result holds true and we have
Example 3.7 Here we revisit Example 2.8, and have
For the function
2 . Hence, '
has no second-order directional derivative at Q - in direction v. Note that there is no
neighbourhood of -
strongly convex.
Finally, we aim at showing that ' is even second-order Hadamard directionally differentiable
at equipping K C with a suitable topology. To this end we need a
certain counterpart of Lemma 3.2 for the corresponding limes inferior. Since this is not
available for nonsmooth functions, it is a natural idea to consider the space C 1 (IR s ),
to restrict ' to the subset K C " C 1 and to equip K C " C 1 with the C 1 -topology. Then
we are able to show that the assumptions of Corollary 3.5 even imply the second-order
Hadamard directional differentiability of ' at Q - .
Theorem 3.8 Let Q assume that /(Q - ) is nonempty, bounded. Let g
be twice continuously differentiable, Q - be strongly convex on some open convex neighbourhood
of A/(Q - ) and twice continuously differentiable at -
y where
assume the conditions (i) 0 and (ii) of Corollary 3.5 to hold.
Then the second-order Hadamard directional derivative of ' at Q - exists in any direction
v belonging to the tangent cone T (K any such
v, and all sequences t n ! 0+ and (Q n ) in K C such that v n := 1
exists, and it holds
0g.
Proof. Let sequence in K C such that
together with Theorem 2.3 then
imply that there exist constants L ?
such that
Since the sequence (v n ) converges in C 1 (IR s ), the norms kv n k L;r are uniformly bounded
and we have
Expanding g and Q - as in the proof of Theorem 3.4
we obtain analogously to (3.1), for all n - n 0 :t 2
Putting - n := 1
and using the mean value theorem for v n we may continue
with some -
Arguing as in the proof of Theorem 3.4 and using v n ! v in C 1 (IR s ) we arrive at the
estimate
lim inf
for some element -
Furthermore, we conclude from (ii) and Proposition 3.3 that
lim sup
Hence, the desired limit exists and the proof is complete. 2
Let us finally note that all minimization problems appearing as bounds or formulas for
second-order directional derivatives represent convex programs. Those in the results
3.4, 3.5 and 3.8 have convex cone constraints, which are polyhedral if C is polyhedral.
Moreover, the solution sets of the convex minimization problems in 3.4, 3.5 and 3.8 are
nonempty. Indeed, we show next that these solution sets represent certain derivatives
of the set-valued mapping / at the pair (Q - x).
4 Differentiability of solution sets
It is well-known that second-order differentiability properties of optimal values in perturbed
optimization are intrinsic for establishing the differentiability of solutions (see
e.g. [8]). We also pursue this approach and derive conditions implying directional
differentiability properties of the solution set mapping by exploiting the results of the
previous section. Our first results in this direction concern Gateaux directional differ-
entiability, and complement Theorem 3.4 and its corollary.
Theorem 4.1 Assume that the general conditions on g, Q - and C of Theorem 3.4 are
suppose the conditions (i) and (ii) of
Theorem 3.4 to be satisfied. In addition, assume that
(iii) there exist a neighbourhood V of such that the
uniform growth condition
for all x
Then the Gateaux directional derivative of / at the pair (Q - x) into direction v exists
and it holds that
Proof. Let M(-x; v) denote the solution set in the assertion. First we show that
lim sup
x). Then there exists a sequence (t converging to
(0+; -) such that - n 2 1
Hence, analogously to the proof of Theorem 3.4 we deduce that - belongs to S(-x).
In view of Theorem 3.4 it remains to show that 1hr 2 g(-x)-i
expanding g and Q - as in the proof of Theorem 3.4, we
obtain analogously to (3.1):
After dividing by t 2
n and taking the lim
on both sides of the inequality, we obtain the
desired estimate. In a second step we show that
or, equivalently, that it holds for any - 2 M(-x; v),
lim t!0t
sequence with t n ! 0+. We have to show that
lim
there exists an element z
and a sequence (z n ) converging to z with -
suffices to show that
lim
Condition (iii) implies the following estimate for all sufficiently large n
By expanding g and Q - as in the proof of Theorem 3.4 and using the fact that - belongs
to S(-x), we may continue
After dividing by t 2
n and taking the lim sup
on both sides of the latter inequality, we
obtain
lim sup
c
where we made use of z Theorem 3.4. This completes the
proof. 2
Complementing Corollary 3.5 we provide a result on the directional differentiability of
/ at Q - into any direction v
Theorem 4.2 Assume that the general conditions on g, Q - and C of Corollary 3.5
are satisfied. Let -
assume that
(i) 00 there exists a constant L ? 0 such that
and, for each r ? 0, there exists a constant j(r) ? 0 such that
(ii) the second-order set S 2 (-x;
is nonempty for each - 2 S(-x).
Then the Gateaux directional derivative / 0 (Q -
x; v) of / at the pair (Q -
exists for
any direction v the formula in Theorem 4.1.
Moreover, condition (ii) is satisfied if C is polyhedral, and (i) 00 is satisfied if C is
polyhedral and g is linear or (convex) quadratic.
Proof. Let strongly convex on some open convex neighbourhood
of A/(Q - ), we infer from condition (i) 00 and Theorem 2.6 that condition (iii)
of Theorem 4.1 is satisfied. Moreover, condition (i) 00 implies (i) 0 and, thus, Corollary 3.5
says that the second-order directional derivative ' 00 (Q - ; v) exists. Hence, the first part
of the assertion follows from the proof of the previous theorem. If C is polyhedral,
we have 0 2 S 2 (-x; -) for any - 2 S(-x), and if, in addition, g is convex quadratic,
Proposition 2.2 implies condition (i) 00 to hold. 2
We note that Example 3.7 shows that, in general, the directional differentiability property
of / gets lost at those pairs (Q -
is not strongly convex
on some neighbourhood of A/(Q - ).
Finally, we turn to directional differentiability properties of / where the derivatives
exist uniformly with respect to directions taken from compact sets of certain functional
spaces. For our first result we consider the space C 1 (IR s ) and equip the set K
with the C 1 -topology.
Proposition 4.3 Let Q assume that the general conditions on g,
and C in Proposition 3.3 are satisfied. In addition, we suppose condition (ii) of
Theorem 3.4 to be satisfied. Let -
sequence in K C
such that v n := 1
Then the upper set limit of the sequence ( 1
of closed convex subsets
in IR m , i.e., lim sup
x)), is contained in the closed convex set
argmin
Proof. Let D n := 1
x) for all n 2 IN and let -
- belong to the upper set
limit lim sup
. Then there exist a subsequence (again denoted by (D n )) and elements
-. Since -
we have that -
As in the proof of Theorem 3.4 we deduce that hrg(-x); -
thus, -
expanding g and Q - as in the proof of Theorem 3.4, we also obtain
analogously to (3.1):
After dividing by t 2
n and taking the lim sup
on both sides of the inequality, we obtain
as in the proof of Theorem 3.8
lim sup
-i:
Hence, we may conclude from (ii) and Proposition 3.3 that -
- belongs to the set
and we are done.Remark 4.4 The upper limit of the sequence ( 1
in Proposition 4.3
is nonempty if the mapping d(-x; /(\Delta)) from K C into the extended reals has the Lipschitzian
property of Theorem 2.3 at Q - . Indeed, we may select x
for large n 2 IN , such that for some constants -
. Hence, the sequence ( 1
is bounded and
has a convergent subsequence whose limit belongs to lim sup
x). If
the Lipschitz property of d(-x; /(\Delta)) is violated, the upper set limit may be empty. This
is illustrated by Example 3.7, in which we have -
g.
In order to establish the semidifferentiability of / at a pair (Q -
x) belonging to the
graph of /, it remains to show, according to Proposition 4.3, that the solution set
argmin
is contained in the lower set limit lim inf
converges to v. To this end, a uniform quadratic
growth condition of the objective functions g(\Delta)
is significant. In view of Theorem 2.6, the uniform strong convexity of Q - and its
approximations Q n , for large n 2 IN , is decisive for the growth condition. The next
example and the following result show that the approximations Q n do not maintain
the strong convexity property of Q - in general if the sequence (Q n ) converges to Q -
in C 1 (IR s ), but that the situation is much more advantageous when considering the
C 1;1 -topology.
Example 4.5 Let Q be the following differentiable
convex functions
\Gammay \Gamman
0; y \Gamman
Note that Q
and Q n is not strongly convex for each n 2 IN ,
but (Q n ) converges to Q - in C 1 (IR s ).
strongly convex on some bounded convex set
(with some constant - ? 0).
Then there exists a neighbourhood N of Q - in C 1;1 (IR s ) such that each function Q
belonging to N is strongly convex on U with constant -Proof. The strong convexity of Q - on U (with constant - ? 0) is equivalent to the
condition
such that cl U ' B(0; r) and let N be a neighbourhood of Q - in C 1;1 (IR s ) having the
property
y. Then we
obtain for any Q 2 N ,
and, hence
This means that Q is strongly convex on U with constant -. 2
Now we are able to show that the solution set mapping / is semidifferentiable on
at some pairs (Q -
direction v from the tangent cone
in C 1;1 (IR s ). The assumptions are essentially
the same as in Theorem 4.2.
Theorem 4.7 Let Q assume that /(Q - ) is nonempty, bounded.
Let g be twice continuously differentiable, Q - be strongly convex on some open convex
neighbourhood U of A/(Q - ) and twice continuously differentiable at -
y, where
Assume that, for each r ? 0, there exist constants L ? 0 and j(r) ? 0 such
that the following condition (i) 00 is satisfied for
Then the solution set mapping / from K C " C 1;1 into IR m is semidifferentiable at any
such that S 2 (-x; -) is nonempty for each - 2 S(-x), and into
any direction v 2 T (K any such -
x and v, t n ! 0+, and (Q n ) in
exists. The semiderivative D/(Q -
x; v) is equal to the set
argmin
Moreover, / is semidifferentiable at any pair (Q -
direction
polyhedral. Condition (i) 00 is satisfied if C is polyhedral
and g is linear or (convex) quadratic.
Proof. Let be such that S 2 (-x; -) is nonempty for each - 2 S(-x),
and (Q n ) is a sequence in K C " C 1;1 . We may assume that U is bounded. Since
converges to Q - in C 1;1 (IR s ), we obtain from Lemma 4.6 that there exists an
, such that Q n is strongly convex on U for each n - n 0 with a uniform constant
sufficiently large such that /(Q n ) is nonempty, for each
Arguing as in the proof of Theorem 2.6, we obtain a constant c ? 0 and a
neighbourhood V of /(Q n ) such that the growth condition
holds for all x
be a minimizer of the function 1hr 2 g(-x)-i
subject to - 2 S(-x). Because of Proposition 4.3 it remains to show that -
belongs to the lower limit lim inf
there exists an element z
-) and a sequence (z n ) converging to z with
As in the proof of Theorem 4.1 it suffices to show
that
lim
By using the above growth condition and by expanding the function g and Q - , we
obtain as in the proof of Theorem 4.1
and
lim sup
c
This implies -
x) and the semidifferentiability of / at (Q -
in
direction v is shown. The remaining part of the assertion follows as in the proof of
Theorem 4.2. 2
For the linear-quadratic case, the essential assumptions in Theorem 4.7 are the strong
convexity of Q - , and the smoothness properties of Q - and its perturbations Q, respec-
tively. While criteria for strong convexity were already discussed in Section 2, we now
close this section by adding some comments on C 1;1 - and C 2 -properties of expected
recourse functions.
Remark 4.8 Assume (A1) - (A3) and - to have a density with respect to the Lebesgue
measure on IR s . Then the function Q - in (1.2) is continuously differentiable on IR s and
its gradient is of the form rQ -
)), for all y
are certain basis submatrices of the recourse matrix W such that the
simplicial cones B i (IR s
are linearity regions of ~
Q and d i is the gradient
of ~
Denoting by F - the distribution
function of - and using the formula
-(y +B(IR s
for any nonsingular (s; s)-matrix B, C 1;1 - and C 2 -properties of Q - may thus be formulated
in terms of Lipschitz and differentiability properties of the distribution functions
to the linear transforms - of the measure -.
The distribution function F - of a probability measure - on IR s is locally Lipschitzian
if all one-dimensional marginal distribution functions of - are locally Lipschitzian (cf.
[24], [35]). F - is continuously differentiable if - has a continuous density function and
all one-dimensional marginal distribution functions of - are continuously differentiable
(cf. [19], [35]). If - has a continuous density function, then - ffi B has a continuous density
for any nonsingular (s; s)-matrix B, too. Hence, we may conclude, for instance,
that Q - belongs to C 1;1 (IR s has a (continuous) density and the
above-mentioned conditions on the one-dimensional marginal distribution functions
for F -ffiB belonging to C 0;1 (IR s are satisfied for any nonsingular
(s; s)-matrix B. This criterion is particularly useful for probability distributions
which have the property that all one-dimensional marginal distributions of - and
all linear transforms - ffi B, for all nonsingular matrices B, belong to the same class of
measures. For instance, all multivariate normal and all logarithmic concave probability
measures (e.g. [14]) form classes having this property.

Acknowledgement

: The authors wish to thank Alexander Shapiro (Georgia Institute
of Technology, Atlanta) and Ren'e Henrion (WIAS Berlin) for beneficial discussions



--R

Stability results for stochastic programs and sen- sors

First and second order sensitivity analysis of nonlinear programs under directional constraint qualification conditions
A comparative study of multifunction differentiability with applications in mathematical programming
Directional derivatives in nonsmooth optimization
Perturbed optimization in Banach spaces I: A general theory based on a weak directional constraint qualification
Quadratic growth and stability in convex programming problems with multiple solutions
Optimization problems with perturbations
Optimization and Nonsmooth Analysis
tangent sets and second-order optimality condi- tions
Differentiable selections of set-valued mappings with application in stochastic programming
Strong convexity and directional differentiability of marginal values in two-stage stochastic programming
Stability and sensitivity analysis for stochastic programming

Generalized delta theorems for multivalued mappings and measurable selections
Sensitivity analysis for nonsmooth generalized equations
Asymptotic theory for solutions in statistical estimation and stochastic programming
bounds for solutions of linear equations and inequalities
Approximationen der Entscheidungsprobleme mit linearer Ergebnis- funktion und positiv homogener
Stability theory for parametric generalized equations and variational inequalities via nonsmooth analysis
Differentiability of relations and differential stability of perturbed optimization problems
Strongly regular generalized equations

Stability of solutions for stochastic programs with complete recourse
Lipschitz stability for stochastic programs with complete recourse
Discrete Event Systems.
Strong convexity in stochastic programs with complete recourse
Second order directional derivatives in parametric optimization prob- lems
Sensitivity analysis of nonlinear programs and differentiability properties of metric projections
On concepts of directional differentiability
On differential stability in stochastic programming
Asymptotic analysis of stochastic programs
Weak Convergence and Empirical Pro- cesses
A Lipschitzian characterization of convex polyhe- dra
Distribution sensitivity analysis for stochastic programs with complete recourse
Stochastic programs with fixed recourse: the equivalent deterministic program
in: Handbooks in Operations Research and Management Science.
--TR

--CTR
Svetlozar T. Rachev , Werner Rmisch, Quantitative Stability in Stochastic Programming: The Method of Probability Metrics, Mathematics of Operations Research, v.27 n.4, p.792-818, November 2002
semide-rivatives;sensitivity analysis;two-stage stochastic programs;directional derivatives;solution sets