Introduction to One and Two-Stage Stochastic and Robust Optimization Michel De Lara Cermics, École des Ponts ParisTech France Êco k des Ponts PansTech December 3, 2018
<ロ> <タ> <ニ> <ニ>
うすると

In decision-making, risk and time are bedfellows, but for the fact that an uncertain outcome is revealed after the decision. The talk moves along the number of decision stages: 1,2, more Working out static examples Two-stage stochastic programming problems
<ロ> <タ> <ミ> <ミ>
うす
Working out static examples Two-stage stochastic programming problems ・ロ> <タ> ・ミ> ・ミ> ・ミ> ・クタや
We will work out classical examples in Stochastic Optimization ▶ the blood-testing problem static, only risk ▶  the newsvendor problem static, only risk
<ロ> <タ> <ミ> <ミ>
うすると
Working out static examples The blood-testing problem The newsvendor problem Two-stage stochastic programming problems Moving from deterministic convex piecewise linear programs Moving from linear programs with constraints Scenario decomposition resolution methods Recalls on duality and Lagrangian decomposition Progressive Hedging
<ロ> <ロ> <ミ> <コ>

▶ Data:
▶ A large number N of individuals are subjected to a blood test ▶ The probability that the test is positive is p. the same for all ind ivid uals (a positive test means that the target individual has a specific disease; the prevalence of the disease in the population is p) Individuals are stochastically independent ▶ Blood-testing method: the blood samples of k individuals are pooled and analyzed together ▷ If the test is negative, this one test suffices for the k individuals ▷ If the test is positive, each of the k > 1 individuals must be tested separately, and k + 1 tests are required, in all
▶ Optimization problem:
▶ Find the value of k which minimizesthe expected number of tests ▶ Find the minimal expected number of tests
<ロ> <タ> <ミ> <ミ>
What is the optimal number of individuals in a group that minimizes the expected number of tests? ▶ For the first pool {1, . . , k}, the test is ▶ negative with probability (1 — p)* (by independence) → 1 test ▶ positive with probability 1 — (1 — p)*  →  k +  1 tests ▶ When the pool size k is small, compared to the number N of individuals, the blood samples {1, . . , N} are split in approximately N/k groups, so that the expected number of tests is

<ロ> <タ> <ミ> <ミ>

Expected number of tests as a function of the number of people by group for N=1000 and p=0.01
▶ The expected number of tests is
▶ For small p,
▶ so that the optimal number of individuals per group is k* ≈ 1/ / pp ▶ and the minimal expected number of tests is about
▶ William Feller reports that, in army practice, R. Dorfman achieved savings up to 80%. compared to making N tests (the worst case solution) (take ρ = 1/100, giving k* = 11 ≈ 1/√1/100 = 10 and J* ≈ N/5)
▶ The optimal number of individuals per group is 11 if one minimizes the mathematical expectation E of the number of tests (see also the top right histogram above) ▶ But if one minimizes the Tail Value at Risk at level λ = 5% of the number of tests (more on TVaR), later), numerical calculation show that, in the range from 2 to 33, the optimal number of individuals per group is 5 (see also the bottom left histogram above) ▶ The bottom left histogram is more tight (less spread) than the top right histogram
Working out static examples The blood-testing problem The newsvendor problem Two-stage stochastic programming problems Moving from deterministic convex piecewise linear programs Moving from linear programs with constraints Scenario decomposition resolution methods Recalls on duality and Lagrangian decomposition Progressive Hedging
<ロ> <タ> <ミ> <ミ>
The “newsboy problem” is now coined the "newsvendor problem" ;-)
<ロ> <タ> <ミ> <ミ>
The (single-period) newsvendor problem stands as a classic in stochastic optimization ▶ Each morning, the newsvendor must decide how many copies u ∈ U = {0, 1, 2 . . .} of the day's paper to order: u is the decision variable ▶ The newsvendor will meet a demand w ∈ W = {0,1,2 . . .}: the variable w is the uncertainty ▶ The newsvendor faces an economic tradeoff ▶ she pays the unitary purchasing cost c per copy ▶ she sells a copy at price p ▶ if she remains with an unsold copy, it is worthless (perishable good) ▶ The newsvendor's costs j(u, w) depend both on the decision u and on the uncertainty w:
If you solve n i ( u . w ) the optimal solution is u* = w... which depends on the unknown quantity w! So, what do you suggest an “optimal” solution?

A
<ロ> <ロ> <ミ> <ミ>
The newsvendor reveals her attitude towards risk in how she aggregates outcomes with respect to uncertainty ▶ In the robust or pessimistic approach, the (paranoid?) newsvendor minimizes the worst costs as if Nature were malevolent ▶ In the stochastic or expected approach, the newsvendor solves as if Nature played stochastically (casino)
▶ We suppose that ▶ the demand w belongs to a set W = [w',w'] ▶ the newsvendor knows the set [w',w']] ▶ The worst costs are
max  [cu-pmin{u,w}] = cu-pmin{u,w}} ▶ Show that the order u* = w* minimizes the above expression J(u) ▶ Once the newsvendor makes the optimal order u* = w*, the optimal costs are
which, here, are no longer uncertain
Not if demands are drawn independently from a probability distribution Regan dis densed The completed profix as function of the number of days.
▶ We suppose that ▶ the demand is a random variable, denoted W ▶ the newsvendor knows the probability distribution Pw of the demand  W ▶ The expected costs are J(u) = Ew[j(u,W)] = Ew[cu − p min{u,W}] ▶ Find an order υ * which minimizes the above expression J( u ) ▶ by calculating J(u + 1) — J(u) ▶ then using the decumulative distribution function u → P(W > u)
<ロ> <タ> <ミ> <ミ>
う。
Here is an example of probability distribution and of decumulative distribution for the demand In destribe debuter situations of Mogand he danael Here stand some steps of the computation J(u) = cu — pE[min{u,W}] min{ u, W}    =    u1 { u<w} + W1 { u>w} min{ u + 1, W}    =    ( u + 1)1{ v +1≤w} + W1{ v +1>w} =   (u + 1)1 { u <w} + W1 { u ≥w} min{ u + 1, W} — min{ u, W}    =    1{ u<w} J(u + 1) − J(u) = c − pE[1{u<w}] = c − pP(W > u) ↑ with u ►  If P(W > 0) = 1, then J(1) − J(0) = c − p < 0 ▶ J( u + 1) — J( u ) → u → +∞ c > 0 Characterization of the optimal decision u* ▶ Define the cut-off decisions u** and u** by
▶ An optimal decision u* satisfies
▶ The optimal decision u* is unique if and only if u* ' + 1 = u* ', that is, if and only if
▶ Once the newsvendor makes the optimal order u*, the optimal costs are the random variable
The distribution of the optimal costs displays lower costs than with the naive deterministic solution u = E[W]
that it pays to do stochastic optimization When deterministic optimization is (wrongly) optimistic ▶ If you plug the mean value W = Ew[W] in the criterion
instead of the random variable W ▶ you obtain a deterministic optimization problem
whose minimal value min , ευ j( u, W) is overly and wrongly optimistic ▶ because, on the proper stochastic benchmark Ew[j( · , W)], the deterministic optimal solution π = W = 50 produces poorer results than the stochastic optimal solution u* = 82
When deterministic optimization is (wrongly) optimistic Proposition Let W be a random variable with mean W = Ew[W]. Suppose that w → j(u, w) is convex, for all decision u. Then,
Supposing that the infima are minima
we have
▶ When you move from deterministic optimization to optimization under uncertainty, you come accross the issue of risk attitudes ▶ Risk is in the eyes of the beholder ;-) and materializes in the a priori knowledge on the uncertainties ▶ either probabilistic/stochastic ▶ independence and Bernoulli distributions in the blood test example ▶ uncertain demand faced by the newsvendor modeled as a random variable ▶ or set-membership ▶ uncertain demand faced by the newsvendor modeled by a set
▶ We have seen two examples of optimization problems with a single deterministic decision variable, and with a criterion including a random variable ▶ Now, we will turn to optimization problems with two decision variables, the first one deterministic and the second one random
Working out static examples Two-stage stochastic programming problems ・ロ・・タ・・ミ・・を・ を▶ We lay out two ways to move from one-stage deterministic optimization problems to two-stage stochastic linear programs ▶ in one, we start from a deterministic convex piecewise linear program (without constraints) ▶ in the other, we start from a deterministic linear program with constraints ▶ We show how we can also obtain two-stage risk-averse programs, when we handle risk by means of the Tail Value at Risk ▶ We show a scenario decomposition resolution method adapted to two-stage stochastic programs that are strongly convex ▶ We outline the Progressive Hedging resolution method, adapted to two-stage stochastic linear programs
<ロ> <タ> <ミ> <ミ>

Working out static examples The blood-testing problem The newsvendor problem Two-stage stochastic programming problems Moving from deterministic convex piecewise linear programs Moving from linear programs with constraints Scenario decomposition resolution methods Recalls on duality and Lagrangian decomposition Progressive Hedging
<ロ> <の> <ミ> <ミ>
We revisit the newsvendor problem ・ロ・・ウ・・ミ・・をWriting the newsvendor problem as a linear program, in three steps We consider the stochastic optimization problem
where
and we show in three steps how to rewrite this problem as a linear program
Step 1: exploiting convex piecewise linearity of the criterion First, we write: j(u, w) =cu — p min{u, w}
<ロ> <写> <写> <写>う。 Step 2: exploiting convexity of the mathematical expectation ▶ We suppose that the demand W can take a finite number S of possible values ws, s ∈ S ▶ where s denotes a scenario in the finite set S (S=card(S)) ▶ and we denote π s the probability of scenario s, with

<ロ> <タ> <ニ> <ニ>
Step 2: exploiting convexity of the mathematical expectation Second, we deduce
Step 3: exploiting min min = min Third, we minimize with respect to the original decision u ∈ U
This is a linear program, especially when we consider that the decision can take continuous values: u ∈ U = [0, u x] The newsvendor problem example is a special case of a general mechanism
・ロ・・タ・・を> ・を> ・を> ・のるや
From convex piecewise linear to linear programming ▶ The convex piecewise linear program
▶ can be written as the linear program
From stochastic convex piecewise linear programming to stochastic linear programming ▶ The stochastic convex piecewise linear program ▶ can be written as the stochastic linear program
What happens if we want to minimize risk, not mathematical expectation? ▶ Instead of minimizing the mathematical expectation we want to minimize the Tail Value at Risk (at level λ ∈ [0, 1[), given by the Rockafellar-Uryasev formula ▶ whose limit cases are mean and worst case
Minimizing the Tail Value at Risk of costs: convex piecewise linear programming formulation ▶ The risk-averse stochastic convex piecewise linear program can be written as the convex piecewise linear program
Minimizing the Tail Value at Risk of costs: linear programming formulation The risk-averse stochastic convex piecewise linear program can be written as the linear program
▶ Denote by x* the (supposed unique) solution ▶ As 1 — λ measures the upper probability of risky events, start with λ = 0 and display, to the decision-maker, the risk-neutral solution x * and the probability distribution (histogram) of the random costs ▶ Then move to the confidence level λ = 0.99 (only events with probability less than 1% are considered), and do the same ▷ For a range of possible values for λ, display, to the decision-maker, the solution x * and the histogram of the random costs ▶ The decision-maker should choose his confidence level λ We can also minimize the mean costs, while controlling for large costs ▶ Instead of only minimizing the mathematical expectation ▶ we add the constraint that the Tail Value at Risk (at level λ ∈ [0,1[) is not too large
▶ We can also choose to minimize a mixture
Minimizing a mixture: convex piecewise linear programming formulation The risk-averse stochastic convex piecewise linear program ▶ can be written as the convex piecewise linear program
Minimizing a mixture: linear programming formulation ▶ The risk-averse stochastic convex piecewise linear program
can be written as the linear program
► Denote by x o the (supposed unique) solution ▶ As 1 — λ measures the upper probability of risky events, let the decision-maker choose a confidence level λ — λ = 0.99 (only events with probability less than 1% are considered), λ = 0.95, λ = 0.90, for instance ▶ Start with θ = 0 and display, to the decision-maker, the risk-neutral solution x๋o (which does not depend on λ ) and the probability distribution (histogram) of the random costs
▶ Increase θ from 0 to 1, and display, to the decision-maker, the solution x e and the histogram of the random costs
▶ The decision-maker reveals his confidence level λ and his mixture (θ, 1 – θ) as he selects his prefered histogram <ロ> <愛> <ミ> <ミ>
Working out static examples The blood-testing problem The newsvendor problem Two-stage stochastic programming problems Moving from deterministic convex piecewise linear programs Moving from linear programs with constraints Scenario decomposition resolution methods Recalls on duality and Lagrangian decomposition Progressive Hedging
<ロ> <の> <ミ> <ミ>
Suppose you had to manage a day-ahead energy market You would have to fix reserves by night and adjust in the morning with recourse energies
<ロ> <の> <を> <を> <を> <の> <
From linear to stochastic programming ▶ The linear program
▶ becomes a stochastic program
▶ We observe that there as many (vector) inequalities as there are possible scenarios s ∈ S
and these inequality constraints can delineate an empty domain for optimization Recourse variables need be introduced for feasability issues ▶ We denote by s ∈ S any possible value of the random variable ξ, with corresponding probability π , ▶ and we introduce a recourse variable y = ( ys )s∈ s and the program
▶ so that the inequality A s x + b s + y s ≥ 0 is now possible, at (unitary recourse) price vector ρ = (ρ s, s ∈ S) ▶ Observe that such stochastic programs are huge problems, with solution (x, (ys)ses), but remain linear Minimizing the Tail Value at Risk of costs: linear programming formulation ▶ The risk-averse stochastic linear program with recourse ▶ can be written as the linear program
Minimizing a mixture: linear programming formulation ▶ The risk-averse stochastic linear program with recourse
▶ can be written as the linear program
Roger Wets example http://cermics.enpc.fr/~delara/TEACHING/ CEA-EDF-INRIA_2012/Roger_Wets1.pdf ・ロ・・タ・・を> ・を> ・を> ・のるやTwo-step stochastic programs with recourse can become deterministic non-smooth convex problems ▶ Define
which is a convex function of x, non-smooth ▷ so that the original two-step stochastic program with recourse
▷ now becomes the deterministic non-smooth convex problem ▶ An optimal solution is now more likely to be an inner solution (more robust) A quadratic toy problem Let c > 0 ,  d1 ≥ 0 ,  d2 ≥ 0 ▶ Show that the (worst case) optimization problem
has (worst case) solution
▶ What happens if we allow room for recourse?
うすC
A quadratic toy problem with recourse
▶ Show that the (stochastic) optimization problem
has a solution x* given by
▶ Therefore, x* belongs to the convex generated by {0, d1, d2}, that is,
▶ Compare with the (worst case) solution × = max{ d 1 , d 2 }
▶ We have arrived at optimization problems with two decision variables ▶ a first one deterministic ▶ a second one random (as it is indexed by the scenarios) ▶ We have handled the risk neutral case, but also the risk averse case, with risk measures displaying good mathematical properties (like the Tail Value at Risk) ▶ We will now present resolution methods that, somehow surprisingly, relax the assumption that the first decision variable is deterministic
Working out static examples The blood-testing problem The newsvendor problem Two-stage stochastic programming problems Moving from deterministic convex piecewise linear programs Moving from linear programs with constraints Scenario decomposition resolution methods Recalls on duality and Lagrangian decomposition Progressive Hedging
<ロ> <タ> <ミ> <ミ>
We start with a two-stage stochastic optimization problem formulated on a tree
▶ Stochastic optimization problem
► Solutions (x, (ys)ses) are naturally indexed by a tree ▶ with one root ► and S = card S leaves We transform the two-stage stochastic optimization problem by extending the solution space ▶ We consider initial decisions ( xs )ses and the problem
▶ This problem has the same solutions (x, (ys)ses) as the original one
t = O  t = 1  t = 2  t = 3 [= T N scenarios We transform the two-stage stochastic optimization problem from a tree to a fan ▶ We consider initial decisions ( xs )ses and the problem
► Solutions ( xs, ys )s∈s are naturally indexed by a fan
<ロ> <タ> <ミ> <ミ>
Primal and dual problems ▶ The primal problem is
▶ The dual problem is

<ロ> <タ> <ミ> <ミ>
*) o' ( *
We can translate the multipliers λς in the dual problem ► Denote by X : S → X the random variable X(s) = xs, s E S ▶ Denote by Λ : § → R the random variable Λ(s) = λ s, s ∈ S
Restricting the multiplier Then the dual problem is

<ロ> <タ> <ミ> <ミ>
気of C The dual problem can be decomposed scenario by scenario ▶ The dual problem
▶ is equivalent to
Under proper assumptions — to be seen later, as they require recalls in duality theory — the dual problem can be solved by an algorithm "à la Uzawa" yielding the following scenario decomposition algorithm
<ロ> <タ> <ミ> <ミ>
う。
Scheme of the scenario decomposition algorithm Data: step ρ > 0, initial multipliers { λ { 0 } s s and mean first decisionジ(0) Result: optimal first decision x; repeat forall scenarios s ∈ S do Solve the deterministic minimization problem for scenario s, with a penalization +λ ′′ and obtain optimal first decision χζ k+1, Update the mean first decisions Update the multiplier by res π s x (k+1) = 0 ,  ∀ s ∈ S :
Working out static examples The blood-testing problem The newsvendor problem Two-stage stochastic programming problems Moving from deterministic convex piecewise linear programs Moving from linear programs with constraints Scenario decomposition resolution methods Recalls on duality and Lagrangian decomposition Progressive Hedging
<ロ> <の> <ミ> <ミ>
Recalls and exercises on continuous optimization http://cermics.enpc.fr/~delara/TEACHING/slides_optimization.pdf +ロ> <タ> <ミ> <ミ>う。あA Thanks to Pierre Carpentier (ENSTA ParisTech), we provide a geometric interpretation of Uzawa’s algorithm
・ロ・・の> ・を> ・を> ・を・のるや

Introducing the perturbation function G given by Uzawa's geometric interpretation Recall that the initial problem consists in obtaining G(0). . .
From a (conceptual) geometric point of view, it amounts to:
== <ロ> <タ> <ミ> <ミ>
== <ロ> <日> <ミ> <ミ>
== <ロ> <日> <ミ> <ミ>
== <ロ> <タ> <ミ> <ミ>うなど
== < 0 >うすぐA
IV Uzawa's geometric interpretation IV
V +ロ> <ウ> <ミ> <ミ>
V In the non convex case, use an augmented Lagrangian. . .
うすぐ
Working out static examples The blood-testing problem The newsvendor problem Two-stage stochastic programming problems Moving from deterministic convex piecewise linear programs Moving from linear programs with constraints Scenario decomposition resolution methods Recalls on duality and Lagrangian decomposition Progressive Hedging
<ロ> <タ> <ミ> <ミ>
Progressive Hedging Rockafellar, R.T., Wets R. J-B. Scenario and policy aggregation in optimization under uncertainty, Mathematics of Operations Research, 16, pp. 119-147, 1991 http://cermics.enpc.fr/~delara/TEACHING/ CEA-EDF-INRIA_2012/Roger_Wets4.pdf
<ロ> <の> <を> <を> <を> <の> <

▷ In addition to the variables x s , we introduce a new variable x , so that the non-anticipativity constraint becomes x s = X ▷ We dualize this constraint with an augmented Lagrangian term, yielding to an optimization problem with variables x , x , x , x ▶ When the multiplier λ is fixed, we minimize the primal problem which, unfortunately, is not separable with respect to scenarios s ▶ Luckily, we recover separability by solving sequentially ‘‘à la Gauss-Seidel''
because the first problem is separable with respect to scenarios s
Data: penalty r > 0, initial multipliers { ∑ ( ) } s ∈ and mean first decision ) =(0). Result: optimal first decision x; repeat forall scenarios s ∈ S do Solve the deterministic minimization problem for scenario s, with || x (k+1) _ penalization + λ ′ k ′ ( x ′ k + 1) _ x ( k ) ( k + l ) and obtain optimal first decision χ Update the mean first decisions
Update the multiplier by r(x(k+1) _ x(k+1)) .  Vs E S : Esres π srx(k+1) = 0 ,  ∀ s ∈ S: <ロ> <ウ> <ミ> <ミ>
▶ We have introduced one and two-stage optimization problems under uncertainty ▶ Thanks to a general framework, using risk measures, stochastic and robust optimization appear as (important) special cases ▷ We have presented resolution methods by scenario decomposition for two-stage optimization problems ▶ Dealing with multi-stage optimization problems requires specific tools, as is the notion of state