11
$\begingroup$

I want to solve an optimization model that contains a constraint like $$ \Pr[F(x,\xi)\leq0]\geq1-\varepsilon $$ where $x$ are my decision variables, $\xi$ is a random vector, and $\varepsilon\in(0,1)$ is some tolerance that measures how certain I want to be to satisfy my constraint. Is there a general way to solve such a problem?

(Disclaimer: I'm asking this because the Nemirovski and Shapiro paper was hard for me to read, and I wanted a brief, accessible summary).

$\endgroup$
10
$\begingroup$

In addition to David M's excellent answer, another approach which sometimes can be useful is to use integer programming. Specifically, if your distribution of $\xi$ is discrete (e.g. taking a sample-average-approximation of uncertainty is a reasonable approach) and you are willing to make a big-M assumption on $F(x, \xi)$ then another way to model a chance constraint is using integer programming.

In particular, if we have $L$ realizations of $\xi_i$ total, and they all occur with equal probability, then we can let $z_i=1$ if $F(x, \xi_i) \leq 0$ and $0$ otherwise, and model the chance constraint exactly using the following big-M constraints: $$ F(x, \xi_i) \leq M(1-z_i), \forall i \in \{1, .., L\},\\ \frac{1}{L}\sum_i z_i \geq 1-\epsilon. $$ This approach cannot be applied to a general continuous distribution, because it relies on the support of $\xi$ being discrete. However, there are some fairly general conditions under which the optimal solutions $x^*_L$ from sample-average-approximations of size $L$ converge almost-surely to the optimal solution $x^*$ for the full continuous distribution of $\xi$ as $L \mapsto \infty$, and therefore discretizing a continuous distribution $\xi$ and applying a big-M approach to the discretized distribution is often a reasonable idea.

I believe that some other approaches have since been shown to be faster (see here for instance), but the integer programming approach seems worth knowing.

Further reading: chapter 5.7 of this book, and this paper.

$\endgroup$
8
$\begingroup$

In general, chance constraints are difficult to handle computationally. Given a fixed $x$, is it often very difficult to event compute the value of $\Pr[F(x,\xi)\leq0]$, making the incorporation of such a constraint into an optimization model quite troublesome.

One possible approach is outlined in the 2006 paper by Nemirovksi and Shapiro entitled Convex Approximations of Chance Constrained Programs. In this paper, the authors propose techniques for creating conservative approximations of chance constraints (i.e., approximations with smaller feasible regions). See this paper by Shabbir Ahmed for convex relaxations.

In what follows, we'll assume that for all $\xi$, the function $F(\cdot,\xi)$ is convex in its first argument (if this is not the case, you'll have to do some hard thinking). We'll also assume $F$ is real-valued (not vector-valued---i.e. not a joint chance constraint). For the remainder, we'll deal with the complement of the given constraint, that is, we'll deal with $\Pr[F(x,\xi)>0]\leq\varepsilon$. It is well known that the probability of an event is equal to the expectation of an indicator function on that event. That is, $$ \Pr[F(x,\xi)>0]=\mathbb{E}[\mathbf{1}_{\{F(x,\xi)>0\}}]. $$ The BIG IDEA behind this approximation scheme is to replace the discontinuous, non-convex indicator function $\mathbf{1}_{\{\cdot\}}$ with some nicer function---let's call it $\psi(\cdot)$. Ideally, we want $\psi$ to be continuous, convex (for easier computing), and be greater than (or equal to) the indicator function (so that our approximation is conservative).

Now, because $\psi(t)\geq\mathbf{1}_{\{t>0\}}$, we have that $$ \Pr[F(x,\xi)>0]=\mathbb{E}[\mathbf{1}_{\{F(x,\xi)>0\}}]\leq\mathbb{E}[\psi(F(x,\xi))]. $$ Hence, if we enforce $\mathbb{E}[\psi(F(x,\xi))]\leq\varepsilon$, this implies $\Pr[F(x,\xi)>0]\leq\varepsilon$ (just like we want).

So how do we pick $\psi$, the approximation to the indicator function? Here are three popular choices:

  1. $\psi(t)=\max\{1+t,0\}$. This choice is actually equivalent to Conditional Value-at-Risk (CVaR).
  2. $\psi(t)=(1+t)^2$. This choice is equivalent to approximating the chance constraint using Chebyshev's inequality (see, e.g., slide 10 of these slides).
  3. $\psi(t)=\exp(t)$. This choice is advantageous because the function $\mathbb{E}[\exp(tX)]$ for a random variable $X$ is known as a moment-generating function, and has some nice, well-studied properties.

In fact, you can do a little bit better than this approximation. Nemirovski and Shapiro show that you can actually enforce $$ t\mathbb{E}[\psi(\tfrac{1}{t}F(x,\xi))]\leq{t}\varepsilon\quad\leftarrow\text{If you only remember one thing...} $$ for any $t>0$, and the approximation is still valid. This function on the left-hand side is actually convex in $t$ (as long as $\psi$ is convex)---this is called a perspective function (see, e.g., Section 3.2.6 of Boyd and Vandenberghe's Convex Optimization). So we can just throw in a new variable $t\geq0$ and enforce the above constraint, and get a tighter approximation.

Toy Example

Suppose we have the constraint $$ \Pr[\xi_1x_1+\xi_2x_2\leq2]\geq0.9. $$ where $x_1$ and $x_2$ are non-negative decision variables, $\xi_1\sim\mathrm{Poisson}(1)$, and $\xi_2\sim\mathrm{Poisson}(1/2)$. In this example, $F(x,\xi)=\xi_1x_1+\xi_2x_2-2$, and $\varepsilon=0.1$. If we use $\psi(t)=\exp(t)$ to approximate the indicator, then we get the approximation below. feasible region approximation The true feasible region is shown in light gray (highly non-convex!). The convex approximation is in dark gray--much nicer. Note that the approximation is conservative (the dark gray is completely within the light gray). Also, the missing strip of dark gray on the left is an off-by-one error in my code to make the plot--sorry!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.