# Robustness Analysis of Stochastic Programs with Joint Probabilistic Constraints

Jitka Dupačová

► To cite this version:

Jitka Dupačová. Robustness Analysis of Stochastic Programs with Joint Probabilistic Constraints. 25th System Modeling and Optimization (CSMO), Sep 2011, Berlin, Germany. pp.155-164, 10.1007/978-3-642-36062-6_16 . hal-01347533

HAL Id: hal-01347533

https://inria.hal.science/hal-01347533

Submitted on 21 Jul 2016

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Robustness Analysis of Stochastic Programs with Joint Probabilistic Constraints

Jitka Dupačová

Charles University in Prague, Faculty of Mathematics and Physics
Department of Probability and Mathematical Statistics
Sokolovská 83, 18675 Prague, Czech Republic

**Abstract.** Due to their frequently observed lack of convexity and/or smoothness, stochastic programs with joint probabilistic constraints have been considered as a hard type of constrained optimization problems, which are rather demanding both from the computational and robustness point of view. Dependence of the set of solutions on the probability distribution rules out the straightforward construction of the convexity-based global contamination bounds for the optimal value; at least local results for probabilistic programs of a special structure will be derived. Several alternative approaches to output analysis will be mentioned.

**Keywords:** Joint probabilistic constraints, contamination technique, output analysis

## 1 Introduction

Consider the following abstract formulation of a stochastic program

$$ \min_{x \in \mathcal{X}(P)} G_0(x, P) \qquad (1) $$

where $P$ is the probability distribution of a random vector $\omega$ with range $\Omega \subset \mathbb{R}^M$ and both the criterion $G_0$ and the set of feasible solutions $\mathcal{X}(P) \subset \mathbb{R}^N$ may depend on $P$. We assume that in (1)

$$ \mathcal{X}(P) := \{x \in \mathcal{X} : G_j(x, P) \le 0, j = 1, \dots, J\} \qquad (2) $$

where $G_j(x, P) \le 0$ are joint probabilistic constraints such as

$$ P(\omega : g(x, \omega) \le 0) \ge 1 - \varepsilon \qquad (3) $$

with $g: \mathbb{R}^N \times \Omega \to \mathbb{R}^K, K > 1$; Individual probabilistic constraints correspond to $K = 1$. Probability level $\varepsilon \in (0, 1)$ in (3) is fixed, prescribed by regulations or chosen by the decision maker.

Probabilistic constraints are sufficiently flexible and model well the intuitive requirements of system reliability or hedging against risk. Depending on the problem, multiple probabilistic constraints can be used. However, the set $\mathcal{X}(P)$
is typically nonconvex, sometimes even disconnected, and functions $G_j(\bullet, P)$ need not be smooth. This is the reason why probabilistic programs have been recognized as hard optimization problems that are very demanding from the computational point of view. For a given probability distribution $P$, (1) with joint probabilistic constraints (3) is a nonlinear program and in principle, known algorithms can be adapted provided that checking feasibility is manageable and the set of feasible solutions is convex. In so doing, one has to cope with the fact that derivatives are expressed as surface or volume integrals, cf. Chapter 5 of [31] for an introductory survey and references.

The seminal results on convexity of problems with joint probabilistic constraints were proved by Prékopa, cf. [20], under assumptions concerning both the function $g$ and the probability distribution $P$.

**Definition 1 (α-concave functions).** A nonnegative function $f(x)$ defined on a convex set $C \subset \mathbb{R}^N$ is α-concave with $\alpha \in [-\infty, \infty]$ if for all $x, y \in C$ and $\lambda \in [0, 1]$ the inequality

$$f(\lambda x + (1 - \lambda)y) \geq m_{\alpha}(f(x), f(y), \lambda)$$

holds true. The function $m_{\alpha}: \mathbb{R}_{+} \times \mathbb{R}_{+} \times [0, 1] \to \mathbb{R}$ is defined as follows:

$$m_{\alpha}(a, b, \lambda) = 0 \text{ if } ab = 0$$

and for $a > 0, b > 0, 0 \le \lambda \le 1$

$$m_{\alpha}(a, b, \lambda) = \begin{cases} a^{\lambda}b^{1-\lambda} & \text{if } \alpha = 0, \quad \text{i.e. } f \text{ log-concave} \\ \max[a, b] & \text{if } \alpha = \infty, \quad \text{i.e. } f \text{ quasi-convex} \\ \min[a, b] & \text{if } \alpha = -\infty, \quad \text{i.e. } f \text{ quasi-concave} \\ (\lambda a^{\alpha} + (1 - \lambda)b^{\alpha})^{1/\alpha} & \text{otherwise.} \end{cases}$$

If $f(x)$ is an α-concave function then it is locally Lipschitz continuous, directionally differentiable and Clarke regular, i.e. directional derivatives $f'(x, d)$ exist and

$$f'(x, d) = \lim_{y \to x, t \to 0} \frac{f(y + td) - f(y)}{t} \quad \forall d \in \mathbb{R}.$$

One of the most general results about convexity of $\mathcal{X}(P)$ is the following extension of Prékopa's original theorem.

**Theorem 1 (Theorem 4.39 in [31]).** Let the functions $g_k: \mathbb{R}^N \times \mathbb{R}^M \to \mathbb{R} \forall k$ be quasi-convex. Let $\omega \in \mathbb{R}^M$ be a random vector that has an α-concave probability distribution, then the function $P(\omega: g_k(x, \omega) \le 0 \forall k)$ is α-concave on the set

$$\mathcal{D} := \{x \in \mathbb{R}^N : \exists y \in \mathbb{R}^M \text{ s.t. } g_k(x, y) \le 0 \forall k\}.$$

The required joint quasi-convexity of $g_k(x, \omega)$ is the main limitation for exploitation of this result. Theorem 1 is applicable e.g. for $g_k(x, \omega) = -g_k(x) + \omega_k \forall k$, i.e. for separable joint probabilistic constraints. We refer to [21], [22] and to Chapter 5 of [31] for details. Another favorable class are linear probabilistic constraints with Gaussian coefficients, see e.g. [22], [32].
To solve complex probabilistic programs one tries to simplify or reformulate the model, to approximate the probability distribution, etc. These approximations and simplifications ask for development of suitable validation techniques and for stability and robustness tests. See e.g. [15] for qualitative stability results under perturbations of all input data, including the probability distribution P, the set X and the probability level α.

Moreover, the probability distribution P itself need not be known completely. Nevertheless, the wish is to find a solution of (1) which is efficient and reliable enough to support sensible decisions. This gives a motivation for stability or robustness analysis of (1) with respect to perturbations of P. Dependence of the set of feasible solutions on P complicates the stability considerations substantially. We denote $\mathcal{X}^*(P)$ the set of optimal solutions, $\varphi(P)$ the optimal value of the objective function in (1) and we shall assume that $\varphi(P)$ is finite.

General stability results for (2) were proved by Römisch without any convexity assumptions; cf. Theorems 5 and 9 in [25]. Then the main stumbling block for their application is the requirement of the *metric regularity property* which is related with continuity of the set $\mathcal{X}(P)$ when some perturbations of P are considered; see e.g. [1] for the general theory and [16] for specific results for probabilistic constraints. When, in addition, the set of optimal solutions is nonempty and bounded, the perturbed probability distribution, say Q, is close to the true one and the objective function is locally Lipschitz continuous one gets a local Lipschitz property of the optimal value

$$|\varphi(P) - \varphi(Q)| \leq Ld(P, Q)$$

and upper semicontinuity of the set of optimal solutions. A proper selection of the probability distance d is crucial. These results were detailed mainly for separable linear probabilistic programs and α-concave probability distributions, see e.g. [16], [25], [26].

Similarly as in [11] we shall focus on quantitative stability properties of the optimal value with respect to perturbations of P. In Section 2 we shall apply relatively simple ideas of output analysis based on the contamination technique initiated in [4], [29] whose applications for stochastic programs with a fixed set of feasible decisions were elaborated e.g. in [8], [12]. The considered special type of perturbations reduces the stability analysis of (2) to that for parametric programs with one-dimensional real parameter. At the same time, it gets on with needs for what-if-analysis or stress testing.

For stochastic programs whose set of feasible decisions does not depend on P and the objective function $G_0(x, P)$ is linear or concave in P one obtains then global bounds for the optimal value function. Local contamination bounds for the optimal value function in (2) were derived in [11] under convexity of the set X and of functions $G_j(\bullet, P) \forall j$. We shall discuss possible extensions of these results to problems with probabilistic constraints for which one cannot rely on convexity properties. In Section 3 some alternative recent approaches will be indicated.
## 2 Robustness Analysis via Contamination

Contamination means to model the perturbations of P by its contamination by another fixed probability distribution Q, i.e. to use $P_t := (1-t)P + tQ$, $t \in [0, 1]$ in stochastic program (1) – (2) at the place of P. Then the set of feasible solutions of (2) for the contaminated probability distribution $P_t$ equals

$$ \mathcal{X}(P_t) = \mathcal{X} \cap \{x : G_j(x, P_t) \le 0, j = 1, \dots, J\}. \quad (4) $$

For probabilistic programs $G_j(x, P) = 1 - \varepsilon - H_j(x, P)$ with $H_j(x, P) = P\{\omega : \omega \in \mathcal{H}_j(x)\}$ where $\mathcal{H}_j(x) = \{y \in \mathbb{R}^s : g_k(x, y) \le 0 \text{ for } k \in K_j\}$ describes the j-th group of constraints depending on $\omega$ and on the decision vector $x$. Evidently, $G_j(x, P_t) = (1-t)G_j(x, P) + tG_j(x, Q) := G_j(x, t) \forall j$ are linear in $t$. We assume that the perturbed objective function $G_0(x, t)$ is also linear in $t$. The perturbed problem (2) is then the linearly perturbed parametric program

$$ \min_{x \in \mathcal{X}} (1-t)G_0(x, 0) + tG_0(x, 1) \quad (5) $$

subject to

$$ (1-t)G_j(x, 0) + tG_j(x, 1) \le 0, j = 1, \dots, J. \quad (6) $$

We denote $\mathcal{X}(t)$, $\varphi(t)$, $\mathcal{X}^*(t)$ the set of feasible solutions, the optimal value and the set of optimal solutions of (5)–(6). For $t = 0$, $\mathcal{X}(0)$, $\varphi(0)$, $\mathcal{X}^*(0)$ denote the set of feasible solutions, the optimal value and the set of optimal solutions of the initial unperturbed problem (1) with probabilistic constraints. We shall assume that $\mathcal{X}^*(0) \neq \emptyset$, i.e., that $\varphi(0)$ is finite.

Contamination technique was developed and applied for $\mathcal{X}(P)$ independent of P and for expectation type objective $G_0(x, P)$, cf. [8], [12]. Assume that such stochastic program

$$ \min_{x \in \mathcal{X}} G_0(x, P) \quad (7) $$

was solved for P and that its optimal value $\varphi(P)$ is finite. Consider a contaminated distribution

$$ P_t := (1-t)P + tQ, t \in [0, 1] $$

with Q another fixed probability distribution such that $\varphi(Q)$ is finite. Via contamination, robustness analysis with respect to changes in P gets reduced to much simpler analysis of parametric program with scalar parameter t.

The objective function in (7) is linear in P so that the perturbed objective $G_0(x, t) := G_0(x, P_t) = (1-t)G_0(x, P) + tG_0(x, Q)$ is linear in t. For a fixed set of feasible solutions $\mathcal{X}(t) \equiv \mathcal{X}$ we get easily (see e.g. Theorem 4.16 of [1])

**Theorem 2.** Assume that $\mathcal{X} \neq \emptyset$ and $\varphi(t)$ is finite for all $t \in [0, 1]$. Then $\varphi(t)$ is a lower semicontinuous concave function on $[0, 1]$.

This result allows us to construct bounds for $\varphi(t)$

$$ (1-t)\varphi(0) + t\varphi(1) \le \varphi(t) \le \varphi(0) + t\varphi'(0^+) \quad \forall t \in [0, 1], \quad (8) $$
i.e. the sought global contamination bounds for the perturbed optimal value $\varphi(P_t)$. They quantify change in optimal value due to considered perturbations of (7).

For parameter dependent sets of feasible solutions the optimal value function $\varphi(t)$ is concave only under rather strict assumptions such as $G_j(x, t)$, $j = 1, \dots, J$ jointly concave on $\mathcal{X} \times [0, 1]$ (cf. Corollary 3.2 of [17].) We shall examine how to construct computable local upper and lower contamination bounds (8) for the perturbed optimal value $\varphi(t)$ for stochastic programs (1) with probabilistic constraints (3). These local bounds can be then exploited in robustness analysis of probabilistic programs with respect to small contamination of data, inclusion of additional scenarios, etc. The form of (8) suggests that we should concentrate on the existence and form of the directional derivatives and on assumptions under which for small $t$, the sets of feasible solutions $\mathcal{X}(t)$ remain fixed or the optimal value function $\varphi(t)$ is concave.

There exist formulas for directional derivative $\varphi(0^+)$ based on the Lagrange function $L(x, u, t) = G_0(x, P_t) + \sum_j u_j G_j(x, P_t)$ for the contaminated problem. The generic formula

$$ \varphi'(0^+) = \min_{x \in \mathcal{X}^*(0)} \max_{u \in \mathcal{U}^*(x, 0)} \frac{\partial}{\partial t} L(x, u, 0) $$

simplifies thanks to linearity of the Lagrange function with respect to the parameter $t$. The derivations proceed in accordance with the assumed properties of problem (5)–(6); consult section 4.3.2 of [1]. The directional derivative $\varphi'(0^+)$ provides information about the influence of contamination on the optimal value $\varphi(t)$ for small $t$. It can be obtained without the second order sufficient condition, e.g. [14], [28], under assumptions which guarantee existence of a continuous trajectory $x^*(t)$ for a small contamination $t$. Besides of uniform compactness of $\mathcal{X}(t)$ for $t > 0$ and small enough, the approach assumes that the unperturbed problem has unique optimal solution $x^*(0)$ for which the Mangasarian-Fromowitz constraint qualification holds. Multiple Lagrange multipliers, whose sets are bounded convex polyhedra, are not excluded and multiple optimal solutions may occur for $t > 0$.

Classical stability results for nonlinear parametric programs with a parameter dependent set of feasible solutions such as (6), including directional differentiability of the optimal value function, were first obtained by applying the Implicit Function Theorem to the first-order optimality conditions under assumptions that imply existence and uniqueness of the optimal solution and of the corresponding Lagrange multipliers for the unperturbed problem, see e.g. [13]. For the Lagrange function

$$ L(x, u, t) = G_0(x, t) + \sum_j u_j G_j(x, t), $$

with differentiable functions $G_j(\bullet, t)$ and for $\mathcal{X} = \mathbb{R}^N$ the optimal solution and the vector of the corresponding Lagrange multipliers for (6) have to satisfy the first-order optimality condition

$$ \nabla_x L(x, u, t) = \nabla_x G_0(x, t) + \sum_j u_j \nabla_x G_j(x, t) = 0. $$
Besides of the linear independence and the strict complementarity conditions valid at the optimal solution $x^*(0)$ of the unperturbed problem and at the corresponding vector of Lagrange multipliers $u^*(0)$, the derivation exploits also existence and nonsingularity of the Hessian matrix of the Lagrange function on the tangent space to the active constraints at $x^*(0)$, $u^*(0)$; see e.g. [1], [13]. Then there exists $t_0 > 0$ and a smooth trajectory $[x^*(t), u^*(t)]$ emanating from $[x^*(0), u^*(0)]$ which satisfies the first-order optimality conditions for $0 \le t \le t_0$:

$$G_j(x^*(t), t) \le 0, u_j^*(t) \ge 0, G_j(x^*(t), t)u_j^*(t) = 0, \quad j = 1, 2, \dots, J,$$

$$\nabla_x G_0(x^*(t), t) + \sum_j u_j^*(t) \nabla_x G_j(x^*(t), P) = 0$$

and the directional derivative

$$\varphi'(0^+) = L(x^*(0), u^*(0), 1) - L(x^*(0), u^*(0), 0).$$

This approach was applied in [5] for probabilistic programs under the second order sufficient condition. Having in mind the nonsmooth character of probabilistic constraints we wish to get bounds for the optimal value function $\varphi(t)$ under relaxed differentiability requirements. We shall see that thanks to the assumed structure of perturbations

• lower bound for $\varphi(t)$ can be derived for $G(x, P)$ linear (or concave) with respect to $P$ without any smoothness or convexity assumptions with respect to $x$,

• further assumptions are needed for derivation of an upper bound.

The lower bound for the optimal value function was derived in [11] for the assumed structure of perturbations without any smoothness or convexity assumptions with respect to $x$. Let us consider first only one probability constraint and an objective $G_0$ independent of $P$, i.e. the unperturbed problem is

$$\min_{x \in \mathcal{X}} G_0(x) \text{ subject to } G(x, P) := 1 - \varepsilon - P(\omega : g(x, \omega) \le 0) \le 0. \quad (9)$$

**Theorem 3 ([11]).** Let $\mathcal{X} \subset \mathbb{R}^N$ be a nonempty convex set, $G(x, t)$ be a linear function of $t \in [0, 1]$ and $\varphi(t)$ be finite for all $t \in [0, 1]$. Then the optimal value function

$$\varphi(t) := \min_{x \in \mathcal{X}} G_0(x) \text{ subject to } G(x, t) \le 0$$

is quasi-concave on $[0, 1]$ with the lower bound

$$\varphi(t) \ge \min\{\varphi(1), \varphi(0)\}. \quad (10)$$

When also the objective function depends on the probability distribution, i.e. on the contamination parameter $t$, the problem is

$$\min_{x \in \mathcal{X}} G_0(x, t) \text{ subject to } G(x, t) \le 0. \quad (11)$$
For $G_0(x, P)$ linear in $P$, a lower bound can be obtained by application of the
bound (10) separately to $G_0(x, P)$ and $G_0(x, Q)$:

$$
\begin{equation}
\begin{split}
\varphi(t) = \min_{x \in \mathcal{X}(t)} & G_0(x,t) = \min_{x \in \mathcal{X}(t)} \left[ (1-t)G_0(x,P) + tG_0(x,Q) \right] \ge \\
& (1-t) \min\{\varphi(0), \min_{\mathcal{X}(Q)} G_0(x,P)\} + t \min\{\varphi(1), \min_{\mathcal{X}(P)} G_0(x,Q)\}.
\end{split}
\tag{12}
\end{equation}
$$

The bound is more complicated but still computable. It requires solution of 4 problems two of which are the non-contaminated programs for probability distributions P, Q and the other ones use both P and Q alternating in the objective function and constraints. For multiple constraints and contaminated probability distributions it would be necessary to prove first the inclusion $\mathcal{X}(t) \subset \mathcal{X}(0) \cup \mathcal{X}(1)$. Then the lower bound (12) for the optimal value $\varphi(t) = \min_{x \in \mathcal{X}(t)} G_0(x, t)$ follows as in the case of one constraint.

Similarly as in [11], trivial *upper bounds* for $\varphi(t)$ can be obtained without any differentiability assumption if no constraint is active at $x^*(0)$ or if for all constraints active at $x^*(0)$, i.e. $G_j(x^*(0), 0) = 0$, $j \in J_0$, inequalities $G_j(x^*(0), 1) \le 0$, $j \in J_0$ hold true. Then for $t$ small enough, $x^*(0)$ is a feasible solution of (6), hence $G_0(x^*(0), t) \ge \varphi(t)$ for $t$ small enough. Using linearity of $G_0$ with respect to $t$ we obtain the upper bound

$$
\varphi(t) \le \varphi(0) + t(G_0(x^*(0), 1) - \varphi(0));
$$

compare with (8). An upper bound for $\varphi(t)$ can be also constructed whenever
there is at disposal a feasible solution $\hat{x} \in \mathcal{X}(P_t)$ which may occur due to the
structure of the solved problem. A direct search for $\hat{x} \in \mathcal{X}$ which satisfies con-
straints

$$
G_j(x, 0) \le 0 \quad \forall j \text{ and } G_j(x, 1) \le 0 \quad \forall j
$$

may be manageable, namely, when $Q = \delta_{\omega^*}$ is a degenerated probability distri-
bution. Using it means to augment $\mathcal{X}$ by deterministic constraints $g_k(x, \omega^*) \le$
$0, k \in K_j, j = 1, \dots, J$. For problems with one joint probability constraint one
may solve

$$
\min_{x \in \mathcal{X}} G(x, 1) \text{ subject to } G(x, 0) \le 0.
$$

These ideas, however, do not exploit the parametric form of constraints in the
definition of $\mathcal{X}(P_t)$. For problems with one joint probabilistic constraint solution
of parametric program

$$
\min_{x \in \mathcal{X}} [(1-t)G(x,0) + tG(x,1)] \quad (13)
$$

for increasing values of $t$ may lead to the sought solution $\hat{x} \in \mathcal{X}(P_t)$ and to the
upper bound $\varphi(t) \le G_0(\hat{x}, t)$.

ILLUSTRATIVE EXAMPLE. In the jointly constrained probabilistic program

$$
\begin{equation}
\begin{array}{ll}
\min & x_1 + x_2 \\
\text{subject to} & \\
\qquad P(\omega_1 x_1 + x_2 \ge 7, \omega_2 x_1 + x_2 \ge 4) \ge 1 - \varepsilon, \\
\qquad & x_1 \ge 0, x_2 \ge 0
\end{array}
\tag{14}
\end{equation}
$$
the random components $(\omega_1, \omega_2)$ are independent and have uniform distributions on the intervals $[1, 4]$ and $[1/3, 1]$. It is a convex program and, thanks to the independence assumption, the explicit form of the optimal solution can be obtained directly: $x_1^*(P) \doteq 3.6735$, $x_2^*(P) \doteq 2.7755$ and $\varphi(P) \doteq 6.4480$ for $\varepsilon = .05$; cf. [18].

To stress the sample distribution we choose the extremal scenario $(\omega_1^*, \omega_2^*) = (1.02, 0.34)$. The optimal solution $x_1^*(P)$, $x_2^*(P)$ is infeasible for $t = 1$, $x_1^*(Q) \doteq 4.4118$, $x_2^*(Q) \doteq 2.5000$ and $\varphi(Q) \doteq 6.9118$. Hence, for all $0 \le t \le 1$ the lower bound (10) for $\varphi(t)$ is $\varphi(P) \doteq 6.4480$.

Solution $\hat{x}_1 = 4.4725$, $\hat{x}_2 = 2.4994$ of the “upper bound problem” (13) obtained for $t = 0$ is feasible for all contaminated problems $(7.0614 \ge 7, 4.02 > 4)$. Then, the value $6.9719 = \hat{x}_1 + \hat{x}_2$ is upper bound for $\varphi(t) \forall t$.

For differentiable functions $G_j$ properties of the set $\mathcal{X}(t) = \mathcal{X}(P_t)$ for small $t$ follow from results of [2], [23], [24]. Linear independence condition at $x^*(0)$ implies that $x^*(0)$ is a nondegenerate point, the vector $u^*(0)$ of Lagrange multipliers is unique and the problem (5)–(6) can be locally reduced to one with a fixed set of feasible solutions:

$$ \min_{z} G_0(T(z, t), t) \text{ on a set } \mathcal{C} \qquad (15) $$

where $T(z, t)$ is continuously differentiable and $T(0, 0) = x^*(0)$. However, the cost for obtaining a fixed set of feasible solutions is that linearity of the objective function with respect to $t$ gets lost. This can be compared to the situation described in detail in Example 1 of [3] for stochastic linear program with individual probabilistic constraints and random right-hand sides $\omega_k$. Using quantiles of marginal probability distributions, the problem can be cast into the form of a linear program for which the dual feasible set is fixed, independent of $P$. However, the quantiles of the contaminated marginal probability distributions that appear as parameter dependent coefficients in the dual objective function are not linear in $t$.

## 3 Conclusions and alternative approaches

Whereas there exists a general lower bound, our discussion indicates that there are limited possibilities to construct local upper contamination bounds for non-convex probabilistic programs when differentiability cannot be guaranteed.

In paper [3], an indirect approach was suggested: To apply contamination technique to a penalty reformulation of the probabilistic program. Then the set of feasible solutions does not depend on $P$ and for the approximate problem, global bounds (8) follow. We refer to Example 4 of [3] for numerical results related with the illustrative example (14).

Another way how to get an upper bound for the optimal value of the probabilistic program is to apply the worst-case analysis with respect to a whole set $\mathcal{P}$ of considered probability distributions, cf. [19], [33]. This means to hedge against
all probability distributions belonging to the chosen ambiguity set and to solve
the following problem:

$$
\min_{x \in \mathcal{X}} \max_{P \in \mathcal{P}} G_0(x, P) \qquad (16)
$$

subject to

$$
P(\omega : g(x, \omega) \le 0) \ge 1 - \epsilon \quad \forall P \in \mathcal{P}. \qquad (17)
$$

The problem (16)–(17) need not be more complicated than the underlying prob-
abilistic program. Its tractability depends on function g(x, ω) and on the choice
of the ambiguity set P. In [19], P is the Prokhorov neighborhood of the true
probability distribution P, whereas in [33], P contains probability distributions
with a given mean, covariance matrix and support. In the last case, (16)–(17)
can be solved via semidefinite optimization techniques. The results depend on
the input information and similarly as in [10], their stability should be studied.

**Acknowledgments.** This research is supported by the grant 402/11/0150 of
the Czech Science Foundation.

References

1. Bonnans, J. F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer, New York (2000)

2. Bonnans, J. F., Shapiro, A.: Nondegeneracy and quantitative stability of parametrized optimization problems with multiple solutions. SIAM J. Optim. 8, 940–946 (1998)

3. Branda, M., Dupačová, J.: Approximation and contamination bounds for probabilistic programs. Ann. Oper. Res. 193, 3–19 (2012)

4. Dupačová, J.: Stability in stochastic programming with recourse – contaminated distributions. Math. Program. Study 27, 133–144 (1986)

5. Dupačová, J.: Stability in stochastic programming – probabilistic constraints. In: Arkin, V. I., Shiraev, A., Wets, R. (eds.), Stochastic Optimization. LNCIS vol. 81, pp. 314–325. Springer, Berlin (1986)

6. Dupačová, J.: Stochastic programming with incomplete information: A survey of results on postoptimization and sensitivity analysis. Optimization 18, 507–532(1987)

7. Dupačová, J.: Stability and sensitivity analysis in stochastic programming. Ann. Oper. Res. 27, 115–142 (1990)

8. Dupačová, J.: Scenario based stochastic programs: Resistance with respect to sample. Ann. Oper. Res. 64, 21–38 (1996)

9. Dupačová, J.: Reflections on robust optimization. In: Marti, K., Kall, P. (eds.), Stochastic Programming Methods and Technical Applications. LNEMS vol. 437, pp. 111–127. Springer, Berlin (1998)

10. Dupačová, J.: Uncertainties in minimax stochastic programs. Optimization 60, 1235–1250 (2011)

11. Dupačová, J., Kopa, M.: Robustness in stochastic programs with risk constraints. Ann. Oper. Res. published online 5. 1. 2011, DOI 10.1007/s10479-010-0824-9

12. Dupačová, J., Polívka, J.: Stress testing for VaR and CVaR. Quantitative Finance 7, 411–421 (2007)
13. Fiacco, A. V.: Introduction to Sensitivity and Stability Analysis in Nonlinear Programming. Academic Press, New York (1983)

14. Gauvin, J., Dubeau, F.: Differential properties of the marginal function in mathematical programming. Math. Program. Study 19, 101–119 (1982)

15. Henrion, R.: Perturbation analysis of chance-constrained programs under variation of all constraint data. In: Marti, K. et al. (eds.), Dynamic Stochastic Optimization. LNEMS vol. 532, pp. 257–274. Springer, Berlin (2004)

16. Henrion, R., Römisch, W.: Hölder and Lipschitz stability of solution sets in programs with probabilistic constraints. Math. Program. 100, 589–611 (2004)

17. Kyparisis, J., Fiacco A.: Generalized convexity and concavity of the optimal value function in nonlinear programming. Math. Program. 39, 285–304 (1987)

18. Pagoncelli, B. K., Ahmed, S., Shapiro, A.: Sample average approximation method for chance constrained programming: Theory and applications. J. Optim. Theory Appl. 142, 399–416 (2009)

19. Pflug, G., Wozabal, D.: Ambiguity in portfolio selection. Quant. Fin. 7, 435–442 (2007)

20. Prékopa, A.: Logarithmic concave measures with application to stochastic programming. Acta Sci. Math. (Szeged) 32, 301–316 (1971)

21. Prékopa, A.: Stochastic Programming. Kluwer Acad. Publ., Dordrecht (1995)

22. Prékopa, A.: Probabilistic Programming. Ch. 5 in [27] (pp. 267–351)

23. Robinson, S. M.: Local structure of feasible sets in nonlinear programming, part II: Nondegeneracy. Math. Program. Study 22, 217–230 (1984)

24. Robinson, S. M.: Local structure of feasible sets in nonlinear programming, Part III: Stability and sensitivity. Math. Program. Study 30, 45–66 (1987)

25. Römisch, W.: Stability of stochastic programming problems. Ch. 8 in [27] (pp. 483–554)

26. Römisch, W., Schultz, R.: Stability analysis for stochastic programs. Ann. Oper. Res. 30, 241–266 (1991)

27. Ruszczyński, A., Shapiro, A. (eds.): Stochastic Programming. Handbooks in OR & MS, vol. 10. Elsevier, Amsterdam (2003)

28. Shapiro, A.: Sensitivity analysis of nonlinear programs and differentiability properties of metric projections. SIAM J. Control and Optimization 26, 628-645 (1988)

29. Shapiro, A.: On differential stability in stochastic programming. Math. Program. 47, 107–116 (1990)

30. Shapiro, A.: Monte Carlo sampling methods, Ch. 6 in [27] (pp. 353–425)

31. Shapiro, A., Dentcheva, D., Ruszczyński, A.: Lectures on Stochastic Programming. SIAM and MPS, Philadelphia (2009)

32. van Ackooij, W., Henrion, R., Möller, A. Zorgati, R.: On joint probabilistic constraints with Gaussian coefficient matrix. Operations Research Letters 39, 99–102 (2011)

33. Zymler, S., Kuhn, D., Rustem, B.: Distributionally robust joint chance constraints with second-order moment information. Math. Program., Ser. A, published online 10. November 2011