On Risk-Averse Stochastic Semidefinite Programs with Continuous Recourse

Abstract

The vast majority of the literature on stochastic semidefinite programs (stochastic SDPs) with recourse is concerned with risk-neutral models. In this paper, we introduce mean-risk models for stochastic SDPs and study structural properties as convexity and (Lipschitz) continuity. Special emphasis is placed on stability with respect to changes of the underlying probability distribution. Perturbations of the true distribution may arise from incomplete information or working with (finite discrete) approximations for the sake of computational efficiency. We discuss extended formulations for stochastic SDPs under finite discrete distributions, which turn out to be deterministic (mixed-integer) SDPs that are (almost) block-structured for many popular risk measures.

1 Introduction

Stochastic semidefinite programs with recourse were first considered by Ariyawansa and Zhu in [1], where, for finite discrete distributions, the authors reformulate the risk-neutral stochastic SDP as a block-structured deterministic SDP and discuss an application to the stochastic version of the minimum-volume covering ellipsoid problem (cf. [23, 25]). In [29], the same authors give a multitude of other applications, including problems in geometry, location aided routing, RC circuit design and structural optimization.

Some approaches to the algorithmic treatment of risk neutral programs with linear recourse carry over to expectation based stochastic SDPs. Extending the results of Zhao (cf. [27]), Mehrotra and Özevin derive a polynomial logarithmic barrier algorithm employing Bender’s decomposition (cf. [15]). Using the volumetric barrier of Vaidya (cf. [24]), Ariyawansa and Zhu construct algorithms of similar complexity in [2]. Furthermore, in [13], Jin, Ariyawansa and Zhu propose homogeneous self-dual algorithms with complexities comparable to the ones of the methods mentioned before. Motivated by an application in multi-antenna wireless networks, Gaujal and Mertikopoulos establish a stochastic approximation algorithm in [9].

Chance constrained SDP models are introduced by Ariyawansa and Zhu in [28, Chapter 3], where an application to the stochastic minimum-volume covering ellipsoid problem is considered. A different approach towards risk-aversion is taken by Schultz and Wollenberg [20], who consider stochastic mixed-integer semidefinite programs arising from unit commitment problems in AC transmission systems. Based on Lagrangian relaxation of the nonanticipativity constraint, a decomposition algorithm for minimizing a weighted sum of the expectation and the probability of exceeding a certain threshold is proposed.

The present work extends the models of [20] and [2] by considering more general risk measures. Instead of focussing on a certain application, we discuss structural properties as convexity and (Lipschitz) continuity of the resulting objective functions. Furthermore, we establish sufficient conditions for differentiability in the risk neutral setting.

Consequences for quantitative stability of the stochastic SDP models under perturbations of the underlying distribution are pointed out. Such perturbations may arise from incomplete information about the distribution or the choice to work with a simpler (possibly finite discrete) approximation for reasons of computational efficiency.

Finally, for finite discrete distributions, we establish equivalent almost block-structured SDPs for various risk measures. For instance, these results allow to adopt the well-known L-shaped method by Slyke and Wets (cf. [22]) to various risk-averse stochastic SDP models. Wollenberg has demonstrated how block structures can be exploited to solve large stochastic SDPs in the risk neutral setting (cf. [26]).

2 Two-Stage Stochastic SDPs with Continuous Recourse

Let $\mathcal {S}^{k}_{+}$ denote the cone of symmetric positive semidefinite matrices in $\mathbb {R}^{k \times k}$. The componentwise Frobenius product of $A = (a_{1}, \ldots , a_{s})^{\top } \in (\mathcal {S}^{k}_{+})^{s}$ and $x \in \mathcal {S}^{k}_{+}$ is defined as $A \bullet x := \left (\text {tr}(a_{1} x), \ldots , \text {tr}(a_{s} x) \right )^{\top } \in \mathbb {R}^{s}$, where tr denotes the trace of a quadratic matrix. Furthermore, the Frobenius norm on $\mathcal {S}^{k}_{+}$ is given by

$$ \|x\| := \sqrt{x \bullet x}. $$

We shall consider the parametric SDP

$$ (\textbf{P}(z))\qquad\qquad \min_{x,y} \{c \bullet x + q \bullet y | T \bullet x + W \bullet y = z, x \in X, y \in \mathcal{S}^{m}_{+}\}, $$

where $z \in \mathbb {R}^{s}$ enters as a parameter. The data is comprised of $c \in \mathcal {S}^{n}_{+}$, $q \in \mathcal {S}^{m}_{+}$, $T \in (\mathcal {S}^{n}_{+})^{s}$, $W \in (\mathcal {S}^{m}_{+})^{s}$ and a nonempty, closed, convex set $X \subseteq \mathcal {S}^{n}_{+}$. The set X is usually given as a spectrahedron, i.e., the intersection of the solution sets of a finite number of affine matrix inequalities with the cone of positive semidefinite matrices.

Let z = Z(ω) be the realization of a random vector $Z: {\Omega } \to \mathbb {R}^{s}$ on some probability space $({\Omega }, \mathcal {F}, \mathbb {P})$. A two-stage stochastic SDP arises from (P(z)) if the decision x has to be taken without knowledge of the particular realization Z(ω), while y can be chosen after observing the previously unknown parameter. In this setting, the optimal decision y is governed by the recourse problem

$$ \min_{y} \{q \bullet y | W \bullet y = Z(\omega) - T \bullet x, y \in \mathcal{S}^{m}_{+} \}. $$

(1)

Let $\varphi : \mathbb {R}^{s} \to \overline {\mathbb {R}}$ denote the optimal value function of (1) with respect to the right-hand side of the system of matrix equations in its constraints, i.e.,

$$ \varphi(t) := \min_{y} \{q \bullet y | W \bullet y = t,~y \in \mathcal{S}^{m}_{+} \}. $$

Introducing the function $f: \mathcal {S}^{n}_{+} \times \mathbb {R}^{s} \to \overline {\mathbb {R}}$, f(x,z) := c ∙ x + φ(z − T ∙ x) we may rewrite (P(Z(⋅)) as

$$ \min_{x} \lbrace f(x,Z(\cdot)) | x \in X \rbrace. $$

(2)

Due to the assumed interplay between decision and observation, problem (2) is not well-defined without further modelling choices. For any x, f(x,Z(⋅)) belongs to the space $L^{0}({\Omega }, \mathcal {F}, \mathbb {P})$ of extended real-valued random variables on the underlying probability space. We thus may fix any functional $\mathcal {R}: \mathcal {X} \to \mathbb {R}$ satisfying

$$ \{f(x, Z(\cdot)) | x \in X \} \subseteq \mathcal{X} \subseteq L^{0}({\Omega}, \mathcal{F}, \mathbb{P}) $$

and consider the optimization problem

$$ \min_{x} \{ Q_{\mathcal{R}}(x) | x \in X \}, $$

(3)

where the mapping $Q_{\mathcal {R}}: \mathcal {S}^{n}_{+} \to \mathbb {R}$ is given by $Q_{\mathcal {R}}(x) = \mathcal {R}[f(x,Z(\cdot ))]$.

We shall work with the following assumptions:

• A1 (Relatively complete recourse) $W \bullet \mathcal {S}^{m}_{+} \supseteq \text {supp} \mathbb {P} \circ Z^{-1}$.

• A2 (Strict dual feasibility) There is some $u \in \mathbb {R}^{s}$ such that q − W^⊤u is positive definite.

Similar, yet more restrictive assumptions are also made in [15].

Lemma 1

Assume A2, then A1 holds if and only if $M_{D} := \{u \in \mathbb {R}^{s} | q - W^{\top } u \in \mathcal {S}^{m}_{+} \}$ is compact.

Proof

M_D is closed due to the closedness of $S^{m}_{+}$. Suppose that M_D is unbounded, i.e., that there exists a sequence $\{u_{k}\}_{k \in \mathbb {N}} \subseteq M_{D}$ with $\lim _{k \to \infty } \|u_{k}\| = \infty$. Define v_k := u_k/∥u_k∥, then ∥v_k∥ = 1 holds for all $k \in \mathbb {N}$. Therefore, the sequence $\{v_{k} \}_{k \in \mathbb {N}}$ can be assumed to converge to some v≠ 0 without loss of generality. By u_k ∈ M_D we have $q -W^{\top } u_{k} \in \mathcal {S}^{m}_{+}$ for all $k \in \mathbb {N}$. Thus,

$$ -W^{\top} v = \lim_{k \to \infty} - W^{\top} v_{k} = \lim_{k \to \infty} \frac{1}{\|u_{k}\|} \left( q - W^{\top} u_{k} \right) \in \mathcal{S}^{m}_{+}. $$

Now select any u₀ ∈ M_D. Then u₀ + αv ∈ M_D holds for any α ≥ 0 and we have

$$ \lim_{\alpha \to \infty} v^{\top} (u_{0} + \alpha v) = \lim_{\alpha \to \infty} v^{\top} u_{0} + \alpha \| v \|^{2} = \infty, $$

verifying $\sup \{v^{\top } u | q - W^{\top } u \in \mathcal {S}^{m}_{+} \} = \infty$. By duality, the set $\{y \in \mathcal {S}^{m}_{+} | W \bullet y = v \}$ has to be empty, which contradicts A1.

Let M_D be compact, then once again by duality for arbitrary $t \in \mathbb {R}^{s}$, there exists u ∈ M_D with ${\min \nolimits } \{q \bullet y | W \bullet y = t, y \in \mathcal {S}^{m}_{+} \} = t^{\top } u$, which implies $t \in W \bullet \mathcal {S}^{m}_{+}$ and thus A1. □

The lemma above shows that $\sup \{t^{\top } u | q - W^{\top } u \in \mathcal {S}^{m}_{+} \}$ is attained for any $t \in \mathbb {R}^{s}$ whenever A1 and A2 hold true.

Lemma 2

Assume A1 and A2, then φ is finite, convex and Lipschitz continuous on $\mathbb {R}^{s}$ .

Proof

Due to A1 and A2, strong duality holds true for the SDP defining φ. We thus have

$$ \varphi(t)= \max_{u} \{t^{\top} u | u \in M_{D} \} \quad \forall t \in \mathbb{R}^{s}. $$

As M_D is nonempty and compact by Lemma 1, φ is finite on $\mathbb {R}^{s}$.

Furthermore, for arbitrary λ ∈ [0,1] and $t_{1}, t_{2} \in \mathbb {R}^{s}$, strong duality implies

$$ \begin{array}{@{}rcl@{}} \varphi(\lambda t_{1}+ (1-\lambda)t_{2}) &=&\max_{u \in M_{D}} (\lambda t_{1}+ (1-\lambda)t_{2})^{T}u \\ & \leq& \lambda \max_{u \in M_{D}} {t_{1}^{T}}u + (1-\lambda) \max_{u \in M_{D}} {t_{2}^{T}}u \\ &=& \lambda \varphi(t_{1})+ (1-\lambda) \varphi(t_{2}), \end{array} $$

which proves the asserted convexity of φ.

To establish Lipschitz continuity, let $t_{1}, t_{2} \in \mathbb {R}^{s}$ be arbitrary and fixed. Then by strong duality and the compactness of M_D, there exists u₁,u₂ ∈ M_D such that $\varphi (t_{1}) = t_{1}^{\top } u_{1}$ and $\varphi (t_{2}) = t_{2}^{\top } u_{2}$. By $t_{1}^{\top } u_{1} \geq t_{1}^{\top } u_{2}$ and $t_{2}^{\top } u_{2} \geq t_{2}^{\top } u_{1}$ we have

$$ - \|u_{2}\| \cdot \|t_{1}-t_{2}\| \leq t_{1}^ \top u_{2} - t_{2}^{\top} u_{2} \leq \varphi(t_{1}) - \varphi(t_{2}) \leq t_{1}^ \top u_{1} - t_{2}^{\top} u_{1} \leq \| u_{1} \| \cdot \|t_{1}-t_{2} \| $$

and thus $|\varphi (t_{1})-\varphi (t_{2})| \leq \max \nolimits \{\|u_{1}\|,\|u_{2}\| \} \|t_{1}-t_{2}\|$. Set $L_{\varphi } := \max \nolimits \nolimits _{u\in M_{D}}\|u\| < \infty$, then

$$ |\varphi(t_{1})-\varphi(t_{2})| \leq L_{\varphi} \cdot \|t_{1}-t_{2}\| $$

holds for all $t_{1}, t_{2} \in \mathbb {R}^{s}$, which completes the proof. □

Remark 1

Under assumptions A1 and A2, φ is finite and convex, which implies directional differentiability by [18, Theorem 25.4]. Furthermore, the subdifferential of φ is convex, compact and admits the representation

$$ \partial \varphi(t) = \text{Argmax} \{u^{\top} t | u \in M_{D} \}. $$

By [18, Theorem 25.1], φ is differentiable at t if and only if ∂φ(t) is a singleton. In that case, we have ∂φ(t) = {∇φ(t)}.

Remark 2

In two-stage stochastic linear programming, the counterpart of φ is the optimal value function of a linear program:

$$ \varphi_{l}: \mathbb{R}^{s} \to \overline{\mathbb{R}}, \quad \varphi_{l}(t) := \min \{q_{l}^{\top} y_{l} | W_{l} y_{l} = t,~y_{l} \in \mathbb{R}^{m}_{+} \} $$

with $q_{l} \in \mathbb {R}^{m}$ and $W_{l} \in \mathbb {R}^{s \times m}$. By linear programming theory, φ_l is finite on $\mathbb {R}^{s}$ iff $W_{l} (\mathbb {R}^{m}_{+}) =\mathbb {R}^{s}$ and $M_{D_{l}} = \{u \in \mathbb {R}^{s} | W_{l}^{\top } u \leq q\} \neq \emptyset$. In this situation, φ_l admits the representation

$$ \varphi_{l}(t) = \max_{j=1,\dots, N} d_{j}^{\top} t, $$

where $d_{1},\dots ,d_{N}$ denote the vertices of the polytope $M_{D_{l}}$. In particular, φ_l is piecewise linear, convex and Lipschitz continuous.

The following example shows that the assumptions A1 and M_D≠∅ are not sufficient to ensure that the optimal value in the problem defining φ(t) is attained for all $t \in \mathbb {R}^{s}$.

Example 1

For $t \in \mathbb {R}$, consider the SDP

$$ \min \left\{ \left[\begin{array}{llll} 1 & 0 & 0 & 0 \end{array}\right] \bullet y | \left[\begin{array}{llll} 0 & \frac{1}{2} & \frac{1}{2} & 0 \end{array}\right] \bullet y = t, y \in \mathcal{S}^{2}_{+} \right\}. $$

(4)

For any $t \in \mathbb {R}$ we have

$$ \left[\begin{array}{ll} |t| +1 & t \\ t & |t| +1 \end{array}\right] \in \text{int} \mathcal{S}^{2}_{+} \quad \text{and} \quad \left[\begin{array}{llll} 0 & \frac{1}{2} & \frac{1}{2} & 0 \end{array}\right] \bullet \left[\begin{array}{llll} |t| +1 & t \\ t & |t| +1 \end{array}\right] = t. $$

Consequently, A1 is fulfilled. Moreover, we have

$$ M_{D} = \left\{ u \in \mathbb{R} | \left[\begin{array}{llll} 1 & 0 & 0 & 0 \end{array}\right] - \left[\begin{array}{llll} 0 & \frac{1}{2} & \frac{1}{2} & 0 \end{array}\right] \cdot u \in \mathcal{S}^{2}_{+} \right\} = \{ 0 \}. $$

(5)

As (4) is strictly feasible for any right-hand side $t \in \mathbb {R}^{s}$, strong duality holds and (5) implies that the infimum of (4) is zero. Furthermore, for any $t \in \mathbb {R} \setminus \{ 0 \}$ we have

$$ \left[\begin{array}{ll} y_{11} & \frac{t}{2} \\ \frac{t}{2} & y_{22} \end{array}\right] \in \mathcal{S}^{2}_{+} \quad \Longleftrightarrow \quad y_{11} > 0,~ y_{22} > 0,~ y_{11}y_{22}-\left( \frac{t}{2} \right)^{2} \geq 0, $$

which yields the lower bound y₁₁ ≥ t²/(4y₂₂) > 0 for any y that is feasible for (4). Consequently, the optimal value in (4) is not attained if t≠ 0.

3 Structure of Risk-Averse Stochastic SDPs

Let us now return to problem (3) and consider various choices of $\mathcal {R}$. To ensure finiteness, we shall work with moment conditions on the Borel probability measure $\mathbb {P} \circ Z^{-1}$ induced by the underlying random vector Z(⋅). Let $\mathcal {P}(\mathbb {R}^{s})$ denote the space of all Borel probability measures on $\mathbb {R}^{s}$ and

$$ \mathcal{M}^{p}_{s} := \left\{ \mu \in \mathcal{P}(\mathbb{R}^{s}) | {\int}_{\mathbb{R}^{s}} \|t\|^{p}~\mu(dt) < \infty \right\} $$

be the subspace of measures having finite moments of order p ≥ 1.

Lemma 3

Assume A1, A2 and$\mathbb {P} \circ Z^{-1} \in {}^{p}_{s}$.Then$f(x,Z(\cdot )) \in L^{p}({\Omega }, \mathcal {F}, \mathbb {P})$forall$x \in \mathcal {S}^{n}_{+}$andthe mapping$F: \mathcal {S}^{n}_{+} \to L^{p}({\Omega }, \mathcal {F}, \mathbb {P})$,F(x) := f(x,Z(⋅)) isconvex and Lipschitz continuous with constant∥c∥ + L_φ ⋅∥T∥ w.r.t.theL^p-norm.

Proof

For any $x \in \mathcal {S}^{n}_{+}$ we have

$$ \begin{array}{@{}rcl@{}} \|F(x)\|_{L^{p}}^{p} &=& {\int}_{\mathbb{R}^{s}} |c \bullet x + \varphi(z - T \bullet x)|^{p}~(\mathbb{P} \circ Z^{-1})(dz) \\ &\leq& |c \bullet x|^{p} + |\varphi(0)|^{p} + {\int}_{\mathbb{R}^{s}} |\varphi(z - T \bullet x) - \varphi(0)|^{p}~(\mathbb{P} \circ Z^{-1})(dz) \\ &\leq& |c \bullet x|^{p} + |\varphi(0)|^{p} + L_{\varphi}^{p} \|T \bullet x\|^{p} + L_{\varphi}^{p} {\int}_{\mathbb{R}^{s}} \|z\|^{p}~(\mathbb{P} \circ Z^{-1})(dz) < \infty \end{array} $$

by Lemma 2.

For any $x_{1}, x_{2} \in \mathcal {S}^{n}_{+}$, λ ∈ [0,1] and $z \in \mathbb {R}^{s}$, the convexity of φ yields

$$ f(\lambda x_{1} + (1-\lambda)x_{2}, z) \leq \lambda f(x_{1},z) + (1-\lambda)f(x_{2},z) $$

and thus in particular F(λx₁ + (1 − λ)x₂) ≤ λF(x₁) + (1 − λ)F(x₂) with respect to the $\mathbb {P}$-almost sure partial order, proving the asserted convexity of F.

Finally,

$$ \begin{array}{@{}rcl@{}} \|F(x_{1})-F(x_{2})\|_{L^{p}} &=& \| c \bullet (x_{1} - x_{2}) + \varphi(z - T \bullet x_{1}) - \varphi(z - T \bullet x_{2}) \|_{L^{p}}\\ &\leq& \|c \bullet (x_{1}-x_{2}) \|_{L^{p}} + \| \varphi(z - T \bullet x_{1}) - \varphi(z - T \bullet x_{2}) \|_{L^{p}} \\ &\leq& \left( \|c\| + L_{\varphi} \cdot \|T\|\right) \cdot \|x_{1}-x_{2}\| \end{array} $$

holds for all $x_{1}, x_{2} \in \mathcal {S}^{n}_{+}$. □

Remark 3

Lemma 3 shows that under a suitable moment condition on Z the classical L^p-spaces are a natural choice for the domain $\mathcal {X}$ of $\mathcal {R}$ ($1 \leq p < \infty$). Furthermore, Lemma 2 shows that if Z has bounded support one may choose $\mathcal {X} = L^{\infty }({\Omega }, \mathcal {F}, \mathbb {P})$.

Definition 1

A mapping $\mathcal {R}: \mathcal {X} \to \mathbb {R}$ defined on some linear subspace $\mathcal {X}$ of $L^{0}({\Omega }, \mathcal {F}, \mathbb {P})$ containing the constants is called a convex risk measure if the following conditions are fulfilled:

• 1. (Convexity) For any $Z_{1}, Z_{2} \in \mathcal {X}$ and λ ∈ [0,1] we have

  $$ \mathcal{R}[\lambda Z_{1} + (1-\lambda)Z_{2}] \leq \lambda \mathcal{R}[Z_{1}] + (1 - \lambda) \mathcal{R}[Z_{2}]. $$

• 2. (Monotonicity) $\mathcal {R}[Z_{1}] \leq \mathcal {R}[Z_{2}]$ for all $Z_{1}, Z_{2} \in \mathcal {X}$ satisfying Z₁ ≤ Z₂ with respect to the $\mathbb {P}$-almost sure partial order.

• 3. (Translation equivariance) $\mathcal {R}[Z_{1} + z_{2}] = \mathcal {R}[Z_{1}] + z_{2}$ for all $Z_{1} \in \mathcal {X}$ and $z_{2} \in \mathbb {R}$.

A convex risk measure $\mathcal {R}$ is coherent if the following holds true:

• 4. (Positive homogeneity) $\mathcal {R}[z_{2} Z_{1}] = z_{2} \cdot \mathcal {R}[Z_{1}]$ for all $Z_{1} \in \mathcal {X}$ and $z_{2} \in [0,\infty )$.

Definition 2

A mapping $\mathcal {R}: \mathcal {X} \to \mathbb {R}$ is called law-invariant if for all $Z_{1}, Z_{2} \in \mathcal {X}$ with $\mathbb {P} \circ Z_{1}^{-1} = \mathbb {P} \circ Z_{2}^{-1}$ we have $\mathcal {R}[Z_{1}] = \mathcal {R}[Z_{2}]$.

We shall give some examples of risk-measures frequently used in stochastic programming as listed in [17, pp. 447–448], and [21]. Later we will give extensive formulations of discrete mean-risk SDPs based on these risk-measures:

• (i) The expectation $\mathbb {E}: L^{1}({\Omega }, \mathcal {F}, \mathbb {P}) \to \mathbb {R}$ is a law-invariant coherent risk-measure.

• (ii) The expected excess over threshold $\eta \in \mathbb {R}$ (as used in [19]) is the mapping $\mathbb {EE}_{\eta } : L^{1}({\Omega }, \mathcal {F}, \mathbb {P}) \rightarrow \mathbb {R}$ defined by

  $$ \mathbb{EE}_{\eta}[Y] = {\int}_{\Omega} \max\{Y(\omega) - \eta, 0\} \mathbb{P}(\text{d}\omega). $$

  This is a non-decreasing, convex and law-invariant risk measure, but in general not translation-equivariant.

• (iii) The conditional value-at-risk at level α ∈ (0,1)

  $$ \mathbb{CV}\text{@R}_{\alpha}: L^{1}({\Omega}, \mathcal{F}, \mathbb{P}) \to \mathbb{R}, \quad \mathbb{CV}\text{@R}_{\alpha}[Y] = \min_{\eta \in \mathbb{R}} \left\{ \eta + \frac{1}{1 - \alpha} \mathbb{EE}_{\eta}(Y) \right\} $$

  (6)

  is law-invariant coherent (cf. [16]).

• (iv) The value-at-risk at level α ∈ (0,1)

  $$ \mathbb{V}\text{@R}_{\alpha}: L^{0}({\Omega}, \mathcal{F}, \mathbb{P}) \to \mathbb{R}, \quad \mathbb{V}\text{@R}_{\alpha}[Y] = \inf\{t ~|~ \mathbb{P}(Z(\omega) \leq t) \geq \alpha\} $$

  is nondecreasing, law-invariant, translation-equivariant and positively homogenous, but in general non-convex.

• (v) The upper semi-deviation of order p is the mapping $\mathbb {M}\text {ad}^{+}_{p} : L^{p}({\Omega }, \mathcal {F}, \mathbb {P}) \rightarrow \mathbb {R}$ defined by

  $$ \mathbb{M}\text{ad}^{+}_{p}[Y] = \left( \int \max\{ 0 , Y(\omega) - \mathbb{E}_{\mathbb{P}}[Z] \}^{p} \mathbb{P}(\text{d}\omega) \right)^{\frac{1}{p}}. $$

  For ρ ∈ [0,1] this gives rise to the law-invariant and coherent risk measure $\mathbb {E} + \rho \mathbb {M}\text {ad}_{p}$ (cf. [21, p. 276]).

Proposition 1

Assume A1 and A2, let $\mathcal {X}$ be a convex subset of $L^{0}({\Omega }, \mathcal {F}, \mathbb {P})$ that contains $F(\mathcal {S}^{n}_{+})$ and fix a convex and nondecreasing mapping $\mathcal {R}: \mathcal {X} \to \mathbb {R}$. Then $Q_{\mathcal {R}}$ is finite and convex on $\mathcal {S}^{n}_{+}$. In particular, problem (3) is convex.

Proof

Finiteness of $Q_{\mathcal {R}}$ follows directly from the finiteness of $\mathcal {R}$. Furthermore, for any $x_{1}, x_{2} \in \mathcal {S}^{n}_{+}$ and λ ∈ [0,1] we have

$$ \begin{array}{@{}rcl@{}} Q_{\mathcal{R}}(\lambda x_{1} + (1-\lambda)x_{2}) &=& \mathcal{R}[F(\lambda x_{1} + (1-\lambda)x_{2})] \\ &\leq& \mathcal{R}[\lambda F(x_{1}) + (1-\lambda)F(x_{2})] \\ &\leq& \lambda \mathcal{R}[F(x_{1})] + (1-\lambda)\mathcal{R}[F(x_{2})]. \end{array} $$

The first inequality above holds due to the monotonicity of $\mathcal {R}$ and the convexity of F (by Lemma 3), while the second one is justified by the convexity of $\mathcal {R}$. □

Similar to the previous proposition, continuity properties of $\mathcal {R}$ carry over to Lipschitzian properties of $Q_{\mathcal {R}}$:

Proposition 2

Assume A1, A2 and $\mathbb {P} \circ Z^{-1} \in {}^{p}_{s}$. If $\mathcal {R} : \mathcal {X} \rightarrow \mathbb {R}$ is convex and continuous, then $Q_{\mathcal {R}}$ is locally Lipschitz continuous on $\mathcal {S}^{n}_{+}$.

Proof

It is well-known (cf. [7]) that a real-valued continuous and convex mapping on a normed space is locally Lipschitz continuous. Hence the result directly follows from Lemma 3. □

Proposition 3

Assume A1, A2 and $\mathbb {P} \circ Z^{-1} \in {}^{p}_{s}$. If $\mathcal {R} : \mathcal {X} \rightarrow \mathbb {R}$ is Lipschitz, then $Q_{\mathcal {R}}$ is Lipschitz on $\mathcal {S}^{n}_{+}$.

Proof

Straightforward. □

Remark 4

The required continuity in Proposition 2 is always satisfied if $\mathcal {R}$ is convex and nondecreasing (w.r.t. to the $\mathbb {P}$-a.s. partial order). Lipschitz continuity holds for all coherent risk measures (cf. [12]). Concrete Lipschitz constants for coherent law-invariant risk measures may be obtained from representation results, e.g. from [3].

Proposition 4

Assume A1, A2 and that the support of $\mathbb {P} \circ Z^{-1}$ is bounded. Furthermore, let $\mathcal {R}: L^{\infty }({\Omega }, \mathcal {F}, \mathbb {P}) \to \mathbb {R}$ be a coherent risk measure. Then $Q_{\mathcal {R}}$ is Lipschitz continuous with constant ∥c∥ + L_φ ⋅∥T∥ on $\mathcal {S}^{n}_{+}$.

Proof

$\mathcal {R}$ is Lipschitz continuous with constant 1 with respect to the $L^{\infty }$-norm on by $L^{\infty }({\Omega }, \mathcal {F}, \mathbb {P})$ by [8, Lemma 4.3] and F takes essentially bounded values by Remark 3. Thus, for any $x_{1}, x_{2} \in \mathcal {S}^{n}_{+}$ we have

$$ \begin{array}{@{}rcl@{}} |Q_{\mathcal{R}}(x_{1}) - Q_{\mathcal{R}}(x_{2})| &=& |\mathcal{R}[F(x_{1})] - \mathcal{R}[F(x_{2})]| \\ &\leq& \|F(x_{1}) - F(x_{2})\|_{L^{\infty}} \\ &\leq& \|F(x_{1}) - F(x_{2})\|_{L^{1}} \\ &\leq& (\|c\| + L_{\varphi} \cdot \|T\|) \cdot \|x_{1} - x_{2}\| \end{array} $$

by Lemma 3. □

We shall now turn our attention to questions of differentiability, but confine the analysis to the risk neutral model.

Lemma 4

Assume A1, A2 and$\mathbb {P} \circ Z^{-1} \in {}^{1}_{s}$, then thefunctional$Q_{\mathbb {E}}: \mathcal {S}^{n}_{+} \to \mathbb {R}$,$Q_{\mathbb {E}}(x) := \mathbb {E}[F(x)]$isdirectionally differentiableand

$$ Q_{\mathbb{E}}^{\prime}(x; v) := {\int}_{\mathbb{R}^{s}} \varphi^{\prime}(z-T \bullet x;v)~(\mathbb{P} \circ Z^{-1})(dz) $$

holds for all $x, v \in \mathcal {S}^{n}_{+}$.

Proof

$Q_{\mathbb {E}}$ is finite valued by Lemma 3, convex by Proposition 1 and thus directionally differentiable (cf. [18, Theorem 25.4]). Furthermore, $\varphi ^{\prime }(\cdot -Tx;v)$ is a pointwise limit of measurable functions and thus measurable for any $x, v \in \mathcal {S}^{n}_{+}$. The asserted representation of the directional derivative is justified by Lemma 2 and [4, Proposition 2.1]. □

Sufficient conditions for differentiability $Q_{\mathbb {E}}$ can be obtained using the same arguments as for linear recourse (cf. [21]).

Lemma 5

Assume A1, A2 and$\mathbb {P} \circ Z^{-1} \in {}^{1}_{s}$andlet$x_{0} \in \mathcal {S}^{n}_{+}$be suchthat

$$ \text{Argmax} \{u^{\top} (z - T \bullet x_{0}) ~|~ u \in M_{D} \} $$

is a singleton for $(\mathbb {P} \circ Z^{-1})$-almost all $z \in \mathbb {R}^{s}$. Then $Q_{\mathbb {E}}$ is differentiable at x₀.

Proof

For $(\mathbb {P} \circ Z^{-1})$-almost all $z \in \mathbb {R}^{s}$, $h_{z}: \mathcal {S}^{n}_{+} \to \mathbb {R}$, h_z(x) = c ∙ x + φ(z − T ∙ x) is differentiable with measurable derivative

$$ h_{z}^{\prime}(x) = c + - T^{\top} \cdot \text{Argmax} \{ u^{\top} (z - T \bullet x_{0}) | u \in M_{D} \}. $$

Consider the functions $g_{z}: \mathcal {S}^{n}_{+} \to \mathbb {R}$ defined by

$$ g_{z}(x) := \frac{h_{z}(x) - h_{z}(x_{0}) - h_{z}^{\prime}(x_{0})^{\top}(x-x_{0})}{\|x-x_{0}\|}, $$

then $\lim _{x \to x_{0}} g_{z}(x) = 0$ holds for $(\mathbb {P} \circ Z^{-1})$-almost all $z \in \mathbb {R}^{s}$. Furthermore, Lemma 2 implies ∥g_z(x)∥≤ 2(L_φ∥T∥ + ∥c∥) for all $x \in \mathcal {S}^{n}_{+}$ and $z \in \mathbb {R}^{s}$. Hence, by Lebesgue’s dominated convergence theorem, we have

$$ \begin{array}{@{}rcl@{}} &&\lim_{x \to x_{0}} \frac{Q_{\mathbb{E}}(x) - Q_{\mathbb{E}}(x_{0}) - {\int}_{\mathbb{R}^{s}} h^{\prime}_{z}(x_{0})^{\top}(x-x_{0})~(\mathbb{P} \circ Z^{-1})(dz)}{\|x-x_{0}\|} \\ &&\quad= \lim_{x \to x_{0}} {\int}_{\mathbb{R}^{s}} g_{z}(x)~(\mathbb{P} \circ Z^{-1})(dz) = {\int}_{\mathbb{R}^{s}} \lim_{x \to x_{0}} g_{z}(x)~(\mathbb{P} \circ Z^{-1})(dz) = 0. \end{array} $$

Consequently, $Q_{\mathbb {E}}$ is differentiable at x₀ and $Q_{\mathbb {E}}^{\prime }(x_{0}) = {\int \nolimits }_{\mathbb {R}^{s}} h_{z}^{\prime }(x_{0})~(\mathbb {P} \circ Z^{-1})(dz)$. □

Corollary 1

Assume A1, A2 and that $\mathbb {P} \circ Z^{-1} \in {}^{1}_{s}$ is absolutely continuous with respect to the Lebesgue measure. Then $Q_{\mathbb {E}}$ is continuously differentiable on $\mathcal {S}^{n}_{+}$ .

Proof

Let $N_{\varphi } \subset \mathbb {R}^{s}$ denote the set of points of nondifferentiability of φ. By [18, Theorem 25.5],

$$ N_{x} := \{ z \in \mathbb{R}^{s} | z - T \bullet x \in N_{\varphi} \} $$

is a null set with respect to the Lebesgue measure for any $x \in \mathcal {S}^{n}_{+}$, which implies $(\mathbb {P} \circ Z^{-1})[N_{x}] = 0$. Consequently, $Q_{\mathbb {E}}$ is differentiable on $\mathcal {S}^{n}_{+}$. Continuity of the derivative follows from [18, Theorem 25.5] and the convexity of $Q_{\mathbb {E}}$. □

Remark 5

Assuming A1, A2 and $\mathbb {P} \circ Z^{-1} \in {}^{1}_{s}$, the subdifferential of $Q_{\mathbb {E}}$ admits the representation

$$ \begin{array}{@{}rcl@{}} &&\partial Q_{\mathbb{E}}(x) = c + {\int}_{\mathbb{R}}^{s} \partial_{x} \varphi(z-T \bullet x)~(\mathbb{P} \circ Z^{-1})(dz) \\ &&= \left\{ c + {\int}_{\mathbb{R}^{s}} \rho(z)(\mathbb{P} \circ Z^{-1})(dz) | \rho: \mathbb{R}^{s} \!\to\! \mathcal{S}^{n}_{+} \text{ measurable},~\rho(z) \in \partial_{x} \varphi(z - T \!\bullet\! x) \text{ a.s.}\right\}. \end{array} $$

Further details are given in [4].

Corollary 2

Assume A2 and that the underlying random variable Z follows a finite discrete distribution withrealizations$z_{1}, \ldots , z_{S} \in \mathbb {R}^{s}$and respectiveprobabilitiesπ₁,…,π_S > 0. Furthermore,assume that$\{y \in \mathcal {S}^{m}_{+} | W \bullet y = z_{i} - T \bullet x \}$is nonempty for anyi ∈{1,…,S} and$x \in \mathcal {S}^{n}_{+}$.Then

$$ \begin{array}{@{}rcl@{}} \partial Q_{\mathbb{E}}(x) &=& c + \sum\limits_{i=1}^{s} \pi_{i} \cdot \partial_{x} \varphi(z_{i} - T \bullet x) \\ &=& c + \sum\limits_{i=1}^{s} -\pi_{i} \cdot T^{\top} \cdot \text{Argmax} \{u^{\top} (z_{i} - T \bullet x) | u \in M_{D} \} \end{array} $$

holds for any$x \in \mathcal {S}^{n}_{+}$.

Proof

The result follows directly from [18, Theorem 23.8]. □

4 Stability

We shall now study the dependence of $Q_{\mathcal {R}}$ on the underlying probability measure $\mathbb {P} \circ Z^{1}$. This is motivated by the fact that in applications the true probability distribution of the random parameter may be unknown. In such situations, one may work with an approximation if the optimal value function and the optimal solution set mapping of (3) are at least semicontinuous with respect to changes of the underlying distribution. Throughout this section we will assume

• A1′ (Complete recourse) $W \bullet \mathcal {S}^{m}_{+} = \mathbb {R}^{s}$.

instead of condition A1.

Let $({\Omega }_{0}, \mathcal {F}_{0}, \mathbb {P}_{0})$ be an atomless probability space, i.e., assume that for any $A \in \mathcal {F}_{0}$ with $\mathbb {P}_{0}(A) > 0$ there exists some $B \subsetneq A$ with $B \in \mathcal {F}_{0}$ and $\mathbb {P}_{0}(B) > 0$, and fix any p ≥ 1. Then for any $\nu \in {}^{1}_{p}$ there exists some $Z_{\nu } \in L^{p}({\Omega }_{0}, \mathcal {F}_{0}, \mathbb {P}_{0})$ such that $\mathbb {P}_{0} \circ Z_{\nu }^{-1}$. Thus, given any law-invariant mapping $\mathcal {R}_{0}: L^{p}({\Omega }_{0}, \mathcal {F}_{0}, \mathbb {P}_{0}) \to \mathbb {R}$, the function

$$ {\Theta}_{\mathcal{R}_{0}}: \mathcal{M}^{1}_{p} \to \mathbb{R}, \quad {\Theta}_{\mathcal{R}_{0}}[\nu] := \mathcal{R}_{0}[Z_{\nu}] $$

is well-defined. Furthermore, we can construct a mapping $\mathcal {R}_{\mathcal {R}_{0}}: L^{p}({\Omega }, \mathcal {F}, \mathbb {P}) \to \mathbb {R}$ by setting $\mathcal {R}_{\mathcal {R}_{0}}[Z_{1}] := {\Theta }_{\mathcal {R}_{0}}[\mathbb {P} \circ Z_{1}^{-1}]$. To ease the notation, we shall assume that $({\Omega }, \mathcal {F}, \mathbb {P})$ itself is atomless. Given any law-invariant mapping $\mathcal {R}: L^{p}({\Omega }, \mathcal {F}, \mathbb {P}) \to \mathbb {R}$, we shall consider the function

$$ \mathcal{Q}_{\mathcal{R}}: \mathcal{S}^{n}_{+} \times \mathcal{M}^{p}_{s} \to \mathbb{R}, \quad \mathcal{Q}_{\mathcal{R}}(x,\mu) := {\Theta}_{\mathcal{R}}\left[\mu \circ f(x,\cdot)^{-1}\right]. $$

For the following analysis, we equip the space $\mathcal {P}(\mathbb {R}^{s})$ with the topology of weak convergence, where a sequence $\{ \mu _{k} \}_{k \in \mathbb {N}} \subseteq \mathcal {P}(\mathbb {R}^{s})$ converges to some $\mu \in \mathcal {P}(\mathbb {R}^{s})$, written $\mu _{k} \stackrel {w}{\rightarrow } \mu$ if and only if

$$ {\int}_{\mathbb{R}^{s}} h(t)~\mu_{k}(dt) \rightarrow {\int}_{\mathbb{R}^{s}} h(t)~\mu(dt) $$

holds for any bounded and continuous function $h: \mathbb {R}^{s} \to \mathbb {R}$. It is well known that even for linear recourse one cannot expect weak continuity of $\mathcal {Q}_{\mathcal {R}}$ on the entire space $\mathcal {S}^{n}_{+} \times {}^{p}_{s}$. Along the lines of [6], we shall thus restrict the analysis to appropriate subspaces.

Definition 3

A set ${} \subseteq {}^{p}_{s}$ is called locally uniformly ∥⋅∥^p-integrating if for any $\mu \in {}$ and any 𝜖 > 0 there exists some open neighborhood $\mathcal {N}$ of μ with respect to the topology of weak convergence such that

Example 2

• (a) For any K,𝜖 > 0 and p ≥ 1, the set

  $$ U(\epsilon, K) := \left\{ \nu \in \mathcal{M}^{p}_{s} : {\int}_{\mathbb{R}^{s}} \|t\|^{1+\epsilon}~\nu(dt) \leq K \right\} $$

  of measures having uniformly bounded moments of order 1 + 𝜖 is locally uniformly ∥⋅∥^p-integrating (cf. [5, Lemma 2.69]).

• (b) For any p ≥ 1 and compact set ${\Xi } \subset \mathbb {R}^{s}$, the set

  $$ \left\{ \nu \in \mathcal{M}^{p}_{s} : {\int}_{\Xi} 1~\nu(dt) = 1 \right\} $$

  of measures with support in Ξ is locally uniformly ∥⋅∥^p-integrating by [14, Lemma 5.1].

• (c) Any singleton $\{\mu \} \subseteq {}^{p}_{s}$ is locally uniformly ∥⋅∥^p-integrating for any p ≥ 1 by [14, Lemma 5.2].

Theorem 1

Let$\mathcal {R}: L^{p}({\Omega }, \mathcal {F}, \mathbb {P}) \to \mathbb {R}$withp ≥ 1 belaw-invariant, convex and nondecreasing. AssumeA1$^{\prime }$and A2 andlet${} \subseteq {}^{p}_{s}$be locally uniformly∥⋅∥^p-integrating.Then the following statements hold true:

• 1. The restriction of$\mathcal {Q}_{\mathcal {R}}$tothe set$\mathcal {S}^{n}_{+} \times {}$iscontinuous with respect to the product topology of the the standard topologyon$\mathcal {S}^{n}_{+}$andthe relative topology of weak convergenceon${}$.

• 2. The optimal valuefunction

  $$ \phi: \mathcal{M} \to \mathbb{R}, \quad \phi(\mu) := \min_{x} \{\mathcal{Q}_{\mathcal{R}}(x,\mu) | x \in X \} $$

  is weakly upper semicontinuous.

Additionally assume that X is compact. Then

• 3. ϕ is weakly continuous.

• 4. The optimal solution set mapping

  $$ {\Phi}: \mathcal{M} \rightrightarrows \mathcal{S}^{n}_{+}, \quad {\Phi}(\mu) := \text{Argmin}_{x} \lbrace \mathcal{Q}_{\mathcal{R}}(x,\mu) | x \in X \rbrace $$

  is weakly upper semicontinuous in the sense of Berge, i.e., for any $\mu _{0} \in {}$ and any open set $\mathcal {O} \subseteq \mathcal {S}^{n}_{+}$ with ${\Phi }(\mu _{0}) \subseteq \mathcal {O}$ there exists a weakly open neighborhood $\mathcal {N}$ of μ₀ such that ${\Phi }(\mu ) \subseteq \mathcal {O}$ for all $\mu \in \mathcal {N} \cap {}$. Furthermore, Φ(μ) is nonempty and compact for any $\mu \in {}$.

Proof

Invoking Lemma 2, the result follows from [6, Corollary 2]. □

5 Extensive Formulations for Finite Discrete Distributions

Throughout this section, we shall assume A1, A2 and that the underlying random variable Z follows a finite discrete distribution with realizations $z_{1}, \ldots , z_{S} \in \mathbb {R}^{s}$ and respective probabilities π₁,…,π_S > 0. Furthermore, we denote the index set {1,…,S} by $\mathcal {I}_{S}$.

It is well known that in the risk neutral setting, the stochastic SDP admits a reformulation as a block-structured SDP (cf. [1, 15]):

Proposition 5

The risk neutral stochastic SDP

$$ \min \left\{ Q_{\mathbb{E}}(x) | x \in X \right\} $$

(7)

is equivalent to the SDP

$$ \min_{x, y_{1}, \ldots, y_{S}} \left\{c \!\bullet\! x + \sum\limits_{i = 1}^{S} \pi_{i} q \bullet y_{i} | T \bullet x + W \bullet y_{i} = z_{i}~\forall i \in \mathcal{I}_{S},~ x \in X,~ y_{i} \in \mathcal{S}^{m}_{+} ~\forall i \in \mathcal{I}_{S}\right\}, $$

(8)

in the sense that the infimal values of the problems coincide. Furthermore, x is an optimal solution for (7) if and only if there exist y₁,…,y_S such that (x,y₁,…,y_S) is an optimal solution for (8).

Proof

By definition of φ,

$$ Q_{\mathbb{E}}(x) = c \bullet x + \sum\limits_{i = 1}^{S} \pi_{i} \varphi(z_{i} - T \bullet x) \leq c \bullet x + \sum\limits_{i = 1}^{S} \pi_{i} q \bullet y_{i} $$

(9)

holds for any x ∈ X, $y_{1}, \ldots , y_{S} \in \mathcal {S}^{m}_{+}$ satisfying T ∙ x + W ∙ y_i = z_i for all $i \in \mathcal {I}_{S}$. Thus, the infimal value of (7) is less or equal to the infimal value of (8). Furthermore, (9) is satisfied as equality if and only if

$$ y_{i} \in \text{Argmin} \{q \bullet y | T \bullet x + W \bullet y = z_{i},~ y \in \mathcal{S}^{m}_{+} \} $$

holds for all $i \in \mathcal {I}_{S}$. The optimal solution set above is nonempty by strong duality, which holds due to A1 and A2. □

We continue with extensive formulations of the SDP (3) for mean-risk models based on the risk measures immediately following Definition 2. In this context, ρ shall always be a nonnegative, predefined parameter indicating risk-aversion in the optimization.

Proposition 6

$$ \min \left\{Q_{\mathbb{E} + \rho \mathbb{EE}_{\eta}}(x) | x \in X \right\}, $$

(10)

with $\eta \in \mathbb {R}$ as a given parameter, can be equivalently restated as

$$ \begin{array}{@{}rcl@{}} &&\underset{y_{1}, \ldots, y_{S}}{\min_{x, v_{1}, \ldots, v_{S},}} \left\{ c \bullet x + \sum\limits_{i = 1}^{S} \pi_{i} q \bullet y_{i} + \rho \sum\limits_{i = 1}^{S} \pi_{i} v_{i} | T \bullet x + W \bullet y_{i} = z_{i} \forall i \in \mathcal{I}_{S},\right.\\ &&\qquad\qquad\quad\left. v \geq 0, v_{i} \geq c \bullet x + q \bullet y_{i} - \eta \forall i \in \mathcal{I}_{S},\right.\\ &&\qquad\qquad\quad\left. x \in X, y_{i} \in \mathcal{S}^{m}_{+} \forall i \in \mathcal{I}_{S}\vphantom{c \bullet x + \sum\limits_{i = 1}^{S} \pi_{i}}\right\}. \end{array} $$

(11)

Proof

As the objective function of (11) is increasing with respect to v, any optimal solution (x,v₁,…,v_S,y₁,…,y_S) satisfies $v_{i} = {\max \nolimits } \{c \bullet x + q \bullet y_{i} - \eta , 0 \}$ for all $i \in \mathcal {I}_{S}$. The asserted equivalence of (10) and (11) then follows as in the proof of Proposition 5. □

Proposition 7

$$ \min \left\{Q_{\mathbb{E} + \rho \mathbb{CV}@R_{\alpha}}(x) | x \in X \right\} $$

can be equivalently restated as

$$ \begin{array}{@{}rcl@{}} &&\underset{y_{1}, \ldots, y_{S}, \eta}{\min_{x, v_{1}, \ldots, v_{S},}} \left\{ c \bullet x + \sum\limits_{i = 1}^{S} \pi_{i} q \bullet y_{i} + \rho \eta + \frac{\rho}{1-\alpha} \sum\limits_{i = 1}^{S} \pi_{i} v_{i} | T \bullet x + W \bullet y_{i} = z_{i} ~\forall i \in \mathcal{I}_{S},\right.\\ &&\qquad\qquad\quad\left. v \geq 0, v_{i} \geq c \bullet x + q \bullet y_{i} - \eta ~ \forall i \in \mathcal{I}_{S},\right.\\ &&\qquad\qquad\quad\left. \eta \in \mathbb{R}, x \in X, y_{i} \in \mathcal{S}^{m}_{+} ~ \forall i \in \mathcal{I}_{S} \vphantom{c \bullet x + \sum\limits_{i = 1}^{S} \pi_{i} q}\right\}. \end{array} $$

(12)

Proof

This follows directly from the variational representation of $\mathbb {CV}@R$ in (6). The expected-excess can be pushed into the restrictions by the same trick as in Proposition 6. □

As in in the risk-neutral case, problems (11) and (12) exhibit a block structure, i.e., there is no coupling constraint involving variables associated with different scenarios. This allows for a direct adaptation of the decomposition algorithms established for the expectation based model.

Proposition 8

$$ \min \left\{Q_{\mathbb{E} + \rho \mathbb{M}\text{ad}^{+}_{p}}(x) | x \in X \right\} $$

can be equivalently restated as

$$ \begin{array}{@{}rcl@{}} \underset{y_{1}, \ldots, y_{S}}{\min_{x, v_{1}, \ldots, v_{S},}} \left\{ c \bullet x + \sum\limits_{i = 1}^{S} \pi_{i} q \bullet y_{i} + \rho \left( \sum\limits_{i = 1}^{S} \pi_{i} {v_{i}^{p}} \right)^{\frac{1}{p}} | T \bullet x + W \bullet y_{i} = z_{i} ~\forall i \in \mathcal{I}_{S},\right.\\ \left. v \geq 0, v_{i} \geq c \bullet x + q \bullet y_{i} - {\sum}_{j = 1}^{S} \pi_{j} q \bullet y_{j} ~ \forall i \in \mathcal{I}_{S},\right.\\ \left. x \in X, y_{i} \in \mathcal{S}^{m}_{+} ~\forall i \in \mathcal{I}_{S}\vphantom{c \bullet x + {\sum}_{i = 1}^{S} \pi_{i} q}\right\}. \end{array} $$

Proof

Analogous to Proposition 6. □

Unlike the previous models, the equivalent SDP in Proposition 8 contains an individual coupling constraint for each scenario. While Lagrangian relaxation still is possible, it remains to be examined whether this approach is sensible from a computational point of view.

Proposition 9

Consider the problem

$$ \min \left\{Q_{\mathbb{E} + \rho \mathbb{V}@R_{\alpha}}(x) | x \in X \right\} $$

with compact set X. This problem can be equivalently restated as the following SDP with binary variables

$$ \begin{array}{@{}rcl@{}} \underset{\delta_{1} , \ldots, \delta_{S}, \eta}{\underset{y_{1}, \ldots, y_{S},}{\min_{x, v_{1}, \ldots, v_{S},}}} \left\{ (1+\rho) c \bullet x + {\sum}_{i = 1}^{S} \pi_{i} q \bullet y_{i} + \rho \eta |\right.\\ \left. T \bullet x + W \bullet y_{i} = z_{i} \forall i \in \mathcal{I}_{S},\right.\\ \left. \sum\limits_{i = 1}^{S} \delta_{i} \pi_{i} \geq \alpha,\right.\\ \left. \eta - q \bullet y_{i} \geq (1- \delta_{i}) M \forall i \in \mathcal{I}_{S},\right. \\ \left. \eta \in \mathbb{R}, x \in X, \delta_{i} \in \{0,1\}, y_{i} \in \mathcal{S}^{m}_{+} \forall i \in \mathcal{I}_{S}\vphantom{(1+\rho) c \bullet x + {\sum}_{i = 1}^{S}}\right\} \end{array} $$

(13)

if $M \in \mathbb {R}$ is chosen sufficiently big.

Proof

As in the preceding propositions introduce a dummy variable η to push $\mathbb {V}@R[\varphi (z - T \bullet x)]$ into the restrictions as $\eta \geq \mathbb {V}@R[\varphi (z - T \bullet x)]$ and minimize over η. Note that $\eta \geq \mathbb {V}@R[ \varphi (z - T \bullet x) ]$ is equivalent to

$$ \mu(\varphi(z-T\bullet x) \leq \eta ) \geq \alpha. $$

(14)

As for given x ∈ X feasible points to the second stage problem corresponding to realization z_i are denoted as y_i, (14) can be rewritten as

$$ \sum\limits_{i \in \mathcal{I}_{S} : q \bullet y_{i} \leq \eta } \pi_{i} \geq \alpha. $$

This conditional summation can in turn be cast into inequalities with binary variables δ_i, $i \in \mathcal {I}_{S}$,

$$ \begin{array}{@{}rcl@{}} \eta - q \bullet y_{i} &\geq& (1-\delta_{i}) M, \quad i \in \mathcal{I}_{S}, \\ \sum\limits_{i \in \mathcal{I}_{S}} \delta_{i} \pi_{i} &\geq& \alpha \end{array} $$

if M is chosen such that η − q ∙ y_i < M for all feasible y_i and all η close to $\mathbb {V}@R[ \varphi (z_{i} - T \bullet x)]$. Since − q ∙ y_i ≤−φ(z_i − T ∙ x) the existence of M follows from compactness of X, as $\max \nolimits _{x \in X} \varphi (z_{i} - T \bullet x) < \infty$ for all $i \in \mathcal {I}_{S}$. □

Equation (13) does not decompose scenariowise due to the coupling constraint ${\sum }_{i = 1}^{S} \delta _{i} \pi _{i} \geq \alpha$, which involves variables from all scenarios. Furthermore, it has an additional binary variable for each scenario. Problems of a similar structure have been considered in the context of minimizing a weighted sum of the expectation and the probability of exceeding a fixed threshold in [20], where Lagrangian relaxation of the coupling constraint enables an approach based on Bender’s decomposition. This direction seems also very promising for the algorithmic treatment of (13).

6 Future Research

Some interesting directions to be considered in a future research project are models involving stochastic costs and stochastic dominance SDP-models. In the presence of stochastic costs the recourse function φ is piecewise quadratic and nonconvex which makes the analysis in Lemma 3 more delicate. For first- and second-order dominance constraints, some of the structural results in [10] and [11] immediately carry over to case of stochastic SDPs. Their numerical treatment shall also be considered in future work.