An Overview of Decomposition/Coordination Methods for Multistage Stochastic Optimization Problems M. De Lara, with P. Carpentier, J.-Ph. Chancelier École des Ponts ParisTech and ENSTA ParisTech BIRS-CMO, Oaxaca, 22-27 September 2019
1 / 39
Lecture outline Decomposition and coordination The three dimensions of stochastic optimization problems A bird's eye view of decomposition methods:  the cube A brief insight into three decomposition methods Scenario decomposition methods Spatial (price/resource) decomposition methods Time decomposition methods Summary and research agenda
3 / 39

Decomposition and coordination A brief insight into three decomposition methods Summary and research agenda
Decomposition and coordination The three dimensions of stochastic optimization problems A bird’s eye view of decomposition methods: the cube A brief insight into three decomposition methods Scenario decomposition methods Spatial (price/resource) decomposition methods Time decomposition methods Summary and research agenda
5 / 39
Temporal, scenario and spatial structures in multistage stochastic optimization problems In multistage stochastic optimization problems, we consider that the control variable U ′ (ω) is indexed by ▶ Time/stages t ∈ T (= {0,..., T − 1}) ► Scenarios ω ∈ Ω ▶ Space/units i ∈ I (= {1,...,N}) The letter U comes from the Russian word upravlenie for control
6 / 39
Let us fix problem and notations
dynamics constraints measurability constraints (nonanticipativity of the control U i )
spatially coupling constraints
Decomposition and coordination The three dimensions of stochastic optimization problems A bird's eye view of decomposition methods:  the cube A brief insight into three decomposition methods Scenario decomposition methods Spatial (price/resource) decomposition methods Time decomposition methods Summary and research agenda
8 / 39

min E(ΣΣι;(x;, υ;, w t+1)) t .i Couplings for stochastic problems: in time
Couplings for stochastic problems: in uncertainty
Couplings for stochastic problems: in space
Can we decouple stochastic optimization problems?
Sequential decomposition in time
Bellman (56)
9 / 39
Parallel decomposition in uncertainty/scenarios
Progressive Hedging Rockafellar-Wets (91)
9 / 39
Parallel decomposition in space/units
∑ Θ† (×†, ∪†) = 0 Price and Resource Decompositions
9 / 39

▶ Temporal decomposition
▶ A state is an information summary ▷ Time coordination realized through Dynamic Programming, by value functions (of the state) ▶ Hard nonanticipativity constraints ▶ Scenario decomposition ▶ Along each scenario, subproblems are deterministic (powerful algorithms) ▷ Scenario coordination realized through Progressive Hedging, by updating nonanticipativity multipliers ▶ Soft nonanticipativity constraints ▶ Spatial decomposition ▷ By prices (multipliers of the spatial coupling constraint) ▶ By resources (splitting the spatial coupling constraint)
10 / 39

Decomposition and coordination A brief insight into three decomposition methods Summary and research agenda
Decomposition and coordination The three dimensions of stochastic optimization problems A bird’s eye view of decomposition methods: the cube A brief insight into three decomposition methods Scenario decomposition methods Spatial (price/resource) decomposition methods Time decomposition methods Summary and research agenda
12 / 39
Moving from tree to fan (and scenarios) Equivalent formulations of the nonanticipativity constraints ▶ On a (scenario) tree, the nonanticipativity constraints
are “hardwired” ▶ On a fan, the nonanticipativity constraints write as linear equality constraints
Progressive Hedging stands as a scenario decomposition method Rockafellar-Wets (91) dualize the nonanticipativity constraints
▶ When the criterion is strongly convex, one uses a Lagrangian relaxation (algorithm "à la Uzawa") to obtain a scenario decomposition ▶ When the criterion is linear, Rockafellar-Wets (91) propose to use an augmented Lagrangian, and obtain the Progressive Hedging algorithm
14 / 39
Data: step ρ > 0, initial multipliers { λ{ 0 } s ∈ S and mean first decision  (0) . Result: optimal first decision u; repeat forall scenarios s ∈ S do Solve the deterministic minimization problem for scenario s, with a penalization +λξk) ( uξk+1) and obtain optimal first decision us f Update the mean first decisions Update the multiplier by u 15 / 39
Decomposition and coordination The three dimensions of stochastic optimization problems A bird’s eye view of decomposition methods: the cube A brief insight into three decomposition methods Scenario decomposition methods Spatial (price/resource) decomposition methods Time decomposition methods Summary and research agenda
16 / 39
We consider an additive model Consider the following minimization problem
for which exists a decomposition of the space U = U 1 × . . . × U N , so that u ∈ U writes u = ( u 1 , . . , u N ) with u 1 ∈ U 1 , and also

17 / 39
Additive model — Price decomposition
2. Solve this problem by the Uzawa algorithm

18 / 39

ll Additive model — Resource allocation
1. Write the constraint in a equivalent manner by introducing new variables ν = ( ν 1 , . . , ν N ) (the so-called “allocation”)
and minimize the criterion w.r.t. u and v

39 / 39
Additive model — Resource allocation =
2. Solve the last problem using a projected gradient method
21 / 39
== Preparing Pierre Carpentier’s talk 23 / 39 We can also use price/resource decomposition to bound a minimization problem
► u' E U' be a local decision variable ► J' : U' → R, i ∈ [1, N] be a local objective function ▶ U a be a subset of the local decision set U a ► Θ ′ : U ′ → C ′ be a local constraint mapping ▶ S be a subset of C = C 1 × . . . × C N We denote by S° the polar cone of S

24 / 39
Price and resource local value functions For each i ∈ [1, N],
Proposition (upper and lower bounds for optimal value)

25 / 39

Decomposition and coordination The three dimensions of stochastic optimization problems A bird’s eye view of decomposition methods: the cube A brief insight into three decomposition methods Scenario decomposition methods Spatial (price/resource) decomposition methods Time decomposition methods Summary and research agenda
26 / 39

▶ The timeline is
▶ and the history is

28 / 39
History is the largest state The history follows the dynamics

8 / 39
We formulate a sequence of minimization problems over increasing history spaces ▶ Once given ► a criterion j : H r → R a sequence of stochastic kernels ρτ:τ+1 : H t → Δ(W t+1) ▶ we define, for any history ht, a minimization problem
39 / 39
There is a Bellman equation involving value functions over increasing history spaces without white noise assumption V τ = j Vt = Bt+1:t Vt+1 with (Bt+1:tQ)(ht) = ϕ( ht, Ut, Wt+1)Pt:t+1( ht, dWt+1)
31 / 39
Preparing Jean-Philippe Chancelier's talk
► History ht is itself a canonical state variable, which lives in the history space Ht = Wo × Πt=1(Us × Ws+1) ▷ However the size of this canonical state increases with t, which is a nasty feature for dynamic programming ▶ We will now ▷ introduce “state” spaces X, ▷ and then reduce the history with a mapping θ r : H r → X r ▶ to obtain a compressed "state" variable θ t (h t ) = x t ∈ X t ▶ but only at some specified times 0 = to < t 1 < · · · < t N = T ▶ As an application, we will handle stochastic independence between time blocks but possible dependence within time blocks
33 / 39

The triplet (θ r,θ t, fr:t ) is a state reduction across ( r:t ) if
→ H. θ f

34 / 39
Bellman operator across ( r : t )

35 / 39
State reduction and Dynamic Programming Denoting by θ * : L ⇒ (X, X,) → L ⇒ (H,,H,) the operator defined by
that is, the following diagram is commutative
Decomposition and coordination A brief insight into three decomposition methods Summary and research agenda We have sketched three main decomposition methods in multistage stochastic optimization ▶ time: Dynamic Programming ▶ scenario: Progressive Hedging ▶ space: decomposition by prices or by resources Numerical walls are well-known ▶ in dynamic programming, the bottleneck is the dimension of the state ▶ in stochastic programming, the bottleneck is the number of stages
38 / 39

▶ Designing risk criteria compatible with decomposition ▶ Combining different decomposition methods ▶ time: Dynamic Programming ▶ scenario: Progressive Hedging ▶ space: decomposition by prices or by resources ▷ to produce blends and tackle large scale energy applications ▶ time blocks + prices/resources (talk of Jean-Philippe Chancelier) ▶ dynamic programming across time blocks + prices/resources decomposition by time block ▶ application to two time scales battery management ▶ time + space (talk of Pierre Carpentier) ▶ nodal decomposition by prices or by resources. + dynamic programming within node ▶ application to large scale microgrid management
39 / 39