Basics

Stochastic refers to a random variable in our objective function, that's why we can only optimize regarding the expectation.

\begin{array}{cl} min_{x} & E [F (x, ξ)] \\ x \in X . \end{array}

Scenario Optimization with Piecewise Linear Utility

In the following example, a two-stage model, where we start from initial capital $W_{0}$ , and would like to maximize the utility in the next stage, meanwhile meet some liability $L$ .

\begin{array}{ll} max_{x} & E (U (W)) \\ W = W_{0} \cdot (1 + r^{⊤} x) - L \\ 1^{⊤} x = 1 \\ x \geq 0 \end{array}

Denote the utility function as $U (w) = min {a w, b w}$ , where $0 \leq a < b$ . Let's discretize the randomness here to $S$ possible scenario each with probability $p_{k}$ .

r^{k} = {[\begin{array}{lll} r_{1}^{k} & \dots & r_{n}^{k} \end{array}]}^{⊤}, k = 1, \dots, S

Then the optimization problem can be written as the following. Notice that the expectation is taken out writing as a summation. And we introduced a redundant variable $u$ that turns the problem into linear constraints.

\begin{array}{ll} max_{x, u} & \sum_{k = 1}^{S} p_{k} u_{k} \\ s.t. & u_{k} \leq a (W_{0} \cdot (1 + {(r^{k})}^{⊤} x) - L), k = 1, \dots, S \\ u_{k} \leq b (W_{0} \cdot (1 + {(r^{k})}^{⊤} x) - L), k = 1, \dots, S \\ 1^{⊤} x = 1 \\ x \geq 0 . \end{array}