An introduction to the theory of SDDP algorithm

Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
An introduction to the theory of SDDP algorithm
V. Lecl`ere (ENPC)
August 1, 2014
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
1 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
Introduction
Large scale stochastic problem are hard to solve.
Two ways of attacking such problems :
decompose (spatially) the problem and coordinate solutions,
construct easily solvable approximations (Linear
Programming).
Behind the name SDDP there is three different things:
a class of algorithms,
a specific implementation of the algorithm,
a software implementing this method develloped by PSR.
The aim of this talk is to give you an idea of how the class of
algorithm is working and give a convergence result.
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
2 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
Introduction
Large scale stochastic problem are hard to solve.
Two ways of attacking such problems :
decompose (spatially) the problem and coordinate solutions,
construct easily solvable approximations (Linear
Programming).
Behind the name SDDP there is three different things:
a class of algorithms,
a specific implementation of the algorithm,
a software implementing this method develloped by PSR.
The aim of this talk is to give you an idea of how the class of
algorithm is working and give a convergence result.
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
2 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
Introduction
Large scale stochastic problem are hard to solve.
Two ways of attacking such problems :
decompose (spatially) the problem and coordinate solutions,
construct easily solvable approximations (Linear
Programming).
Behind the name SDDP there is three different things:
a class of algorithms,
a specific implementation of the algorithm,
a software implementing this method develloped by PSR.
The aim of this talk is to give you an idea of how the class of
algorithm is working and give a convergence result.
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
2 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
An introductive application
A dam is seen as a stock of
energy
with uncertain inflows,
valorized at an uncertain
price.
The objective is to minimize
the expected cumulated cost.
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
3 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
Contents
1
Technical Preliminaries
Problem Formulation and Dynamic Programming
Duality Approach
2
SDDP Algorithm
The SDDP algorithm
Miscellaneous
3
Convergence and Numerical Results
4
Conclusion
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
3 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
Problem Formulation
(
min
A0 x0 =b0
x0 ≥0
c0T x0
"
+E
min
B1 (ξ1 )x0 +A1 (ξ1 )x1 =b1
x1 ≥0
+E
h
c1T (ξ1 )x1
+ E ···
min
BT (ξT )xT −1 +AT (ξT )xT =bT (ξT )
xT ≥0
cTT (ξT )xT
#)
i
Key “practical” assumption: the noise ξ1 , . . . , ξT is
independent from time to time.
If it is not the case we can often extend the state x to obtain
an independent noise
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
4 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
Problem Formulation
(
min
A0 x0 =b0
x0 ≥0
c0T x0
"
+E
min
B1 (ξ1 )x0 +A1 (ξ1 )x1 =b1
x1 ≥0
+E
h
c1T (ξ1 )x1
+ E ···
min
BT (ξT )xT −1 +AT (ξT )xT =bT (ξT )
xT ≥0
cTT (ξT )xT
#)
i
Key “practical” assumption: the noise ξ1 , . . . , ξT is
independent from time to time.
If it is not the case we can often extend the state x to obtain
an independent noise
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
4 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
Dynamic Programming Approach
This problem can be solved by Dynamic Programming with:
QT −1 (xT −1 , ξT ) =
min
BT (ξT )xT −1 +AT (ξT )xT =bT (ξT )
xT ≥0
cTT (ξT )xT
VT −1 = E QT −1 (xT −1 , ξT )
Qt−1 (xt−1 , ξt ) =
min
Bt (ξt )xt−1 +At (ξt )xt =bt (ξt )
xt ≥0
ctT xt + Vt (xt )
Vt−1 (xt−1 ) = E Qt−1 (xt−1 , ξt )
Note that:
the resolution can be done backward in time but require a
priori discretization;
functions Qt and Vt are convex in x;
functions Qt and Vt are pieciewise linear, hence above
problems are linear programming problems.
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
5 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
Dynamic Programming Approach
This problem can be solved by Dynamic Programming with:
QT −1 (xT −1 , ξT ) =
min
BT (ξT )xT −1 +AT (ξT )xT =bT (ξT )
xT ≥0
cTT (ξT )xT
VT −1 = E QT −1 (xT −1 , ξT )
Qt−1 (xt−1 , ξt ) =
min
Bt (ξt )xt−1 +At (ξt )xt =bt (ξt )
xt ≥0
ctT xt + Vt (xt )
Vt−1 (xt−1 ) = E Qt−1 (xt−1 , ξt )
Note that:
the resolution can be done backward in time but require a
priori discretization;
functions Qt and Vt are convex in x;
functions Qt and Vt are pieciewise linear, hence above
problems are linear programming problems.
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
5 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
Contents
1
Technical Preliminaries
Problem Formulation and Dynamic Programming
Duality Approach
2
SDDP Algorithm
The SDDP algorithm
Miscellaneous
3
Convergence and Numerical Results
4
Conclusion
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
5 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
Subgradient of a Value Function
1/2
Consider the following problem:
Qt (x, ξ) = min
xt ,xt+1
s.t.
ctT (ξ)xt + Vt+1 (xt+1 )
xt = x
λt (ξt )
Bt (ξ)xt−1 + At (ξ)xt = bt (ξ)
Note λt (ξt ) the Lagrangian multiplier associated to the constraint
xt = x. Marginalist interpretation of the multiplier (and convexity
of Qt ) implies that λt (ξt ) ∈ ∂Qt (xt , ξ) is a subgradient of Qt (·, ξ).
In other words
Qt (·, ξ) ≥ Qt (xt , ξ) + λt , · − xt .
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
6 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Subgradient of a Value Function
Conclusion
2/2
We have:
∀x,
Qt (x, ξ) ≥ Qt (xt , ξ) + λt , x − xt .
Recall that
Vt (x) = E Qt (x, ξ) .
By linearity we obtain
Vt (·) ≥ E Qt (xt , ξ) + E λt (ξt ) , · − xt .
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
7 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
Constructing a Cut from a Lower Approximation
1/2
ˇ (k) ≤ Vt+1 . Choose a point xt(k) .
Assume that we have V
t+1
Recall that
Qt (xt , ξ) =
min
Bt+1 (ξ)xt +At+1 (ξ)xt+1 =bt+1 (ξ)
xt+1 ≥0
T
ct+1
xt + Vt+1 (xt+1 )
For any possible ξ, consider
β (k) (ξ) = min
xt ,xt+1
s.t.
ˇ (k) (xt+1 )
ctT (ξ)xt + V
t+1
(k)
xt = xt
(k)
λt (ξ)
Bt (ξ)xt−1 + At (ξ)xt = bt (ξ)
Hence we have,
(k)
(k) βt (ξ) + λt (ξ), · − xt
≤ Qt (·, ξ) .
then,
(k)
(k) E βt (ξt ) + E λt (ξt ) , · − xt
≤ Vt (·) .
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
8 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Constructing a Cut from a Lower Approximation
Conclusion
2/2
Recall that,
Vt (x) = E Qt (x, ξt+1 ) .
Hence
(k)
(k) βt (ξ) + λt (ξ), · − xt
≤ Qt (·, ξ) ,
leads to
(k)
(k) E βt (ξt ) + E λt (ξt ) , · − xt
≤ Vt (·)
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
9 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
Contents
1
Technical Preliminaries
Problem Formulation and Dynamic Programming
Duality Approach
2
SDDP Algorithm
The SDDP algorithm
Miscellaneous
3
Convergence and Numerical Results
4
Conclusion
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
9 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
Probabilistic Assumption
The noise process (ξ1 , · · · , ξT ) is assumed to be independent
in time.
If the actual noise process is autoregressive, i.e.
Wt = a0 + a1 Wt−1 + · · · + aτ Wt−τ + ξt
we can extend the state of the problem by considering
(xt , Wt−1 , · · · , Wt−τ ) as the new state, and ξ as the new
(independent) noise.
The noise is assumed to be discrete.
At time t the noise affecting the system is assumed to be
known before the decision xt is made (Hazard-Decision
information structure).
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
10 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
Global Scheme
(k)
Assume that we have lower approximation Vt
Forward Phase Replacing the actual value functions Vt by their
(k)
approximation Vt , and selecting a scenario of noise
(k)
(k)
(ξ0 , . . . , ξT ) we derive a state trajectory
(k)
(k)
x0 , . . . , xT .
Backward Phase Recursively backward compute a new cut (i.e.
(k)
affine function lower than Vt ) of Vt at xt . The new
approximation is given by
(k+1)
Vt
V. Lecl`
ere
(k) (k)
(k)
(k) = max Vt , βt + hλt , · − xt i .
Introduction to SDDP
August 1, 2014
11 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
Forward Phase
The forward phase of iteration k find a “good state trajectory”,
(k)
given a sequence of lower approximation Vt :
(k)
(k)
1
Select a sequence of noise (ξ0 , . . . , ξT ).
2
Fix x0
3
Solve, recursively forward in time,
(k)
= x0 .
(k)
min
ˇ (xt+1 )
ctT (ξ)xt + V
t+1
s.t.
xt = xt
xt+1
(k)
(k)
(k)
Bt (ξt )xt−1 + At (ξ)xt = bt (ξt )
(k)
(k) to obtain a sequence x0 , · · · , xT
.
This is the optimal trajectory given by the approximation of the
Bellman function along the given scenario.
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
12 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
Backward Phase
For any time step t
1 For any ξ in the support of ξ
t+1 , solve
(k)
βt (ξ) = min
xt ,xt+1
s.t.
ˇ (k) (xt+1 )
ctT (ξ)xt + V
t+1
(k)
(k)
xt = xt
λt (ξ)
Bt (ξ)xt−1 + At (ξ)xt = bt (ξ)
2
Compute the exact expectations
(k)
(k)
(k)
(k)
βt = E βt (ξt+1 ) ,
λt = E λt (ξt+1 ) .
3
Update the approximation at time t:
(k) (k)
(k+1)
(k)
(k) Vt
:= max Vt , βt + hλt , · − xt i .
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
13 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
Contents
1
Technical Preliminaries
Problem Formulation and Dynamic Programming
Duality Approach
2
SDDP Algorithm
The SDDP algorithm
Miscellaneous
3
Convergence and Numerical Results
4
Conclusion
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
13 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
Bounds
Lower Bound At any stage of the algorithm we have an exact
(k)
lower bound of the problem given by V0 (x0 ).
Upper Bound From the collection of value functions
approximations we derive a policy
(k) (k)
X0 , · · · , XT that can be simulated. Hence, an
upper bound of the value of the problem is given by
E
T
hX
(k)
ctT Xt
i
,
t=1
which can be estimated by Monte-Carlo method.
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
14 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
Stopping Rule
A number of stopping rules for the SDDP method has been
proposed. In practice it is often simply a given number of iteration
(or a given computation time).
An interesting stopping rule is the following.
Fix an objective gap ε.
(k)
Compute the lower bound v (k) = Vt (x0 ).
Estimate by Monte-Carlo the upper bound v (k) . It is easy to
obtain an (asymptotic) 90% confiance interval for the upper
bound [v (k) − e (k) , v (k) + e (k) ].
Stop if the difference v (k) + e (k) − v (k) between the upper
estimation of the upper bound and the lower bound is lower
than the objective gap, in which case we can certified, with
95% confidence that the solution of the algorithm is less than
ε from the optimal.
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
15 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
A Number of Approximations
1
We fit on the data available an autoregressive process
representing the noise.
first uncontrollable error.
2
We discretize the stochastic process to obtain a scenario tree
representation.
second error controlable through Sampling
Average Approximation (SAA) theory.
ˇt(k) of the real value functions
We compute approximations V
Vt .
third error controlable by bounds from the SDDP
algorithm.
3
4
The upper bound is obtained through Monte Carlo.
error controlable through central limit theorem.
V. Lecl`
ere
Introduction to SDDP
fourth
August 1, 2014
16 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
Convergence result - linear case
Convergence result
Assume that:
the admissible sets of states are compact,
we are in the relatively complete recourse case,
the random selection in the forward phase satisfy some
independence condition,
every value function is updated an infinite number of time.
Then the upper and lower bounds converges almost surely toward
the value of the problem.
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
17 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
Convergence result - convex case
Convergence result
Assume that:
the admissible sets of states are compact convex,
the cost functions are convex,
we are in the extended relatively complete recourse case,
the random selection in the forward phase satisfy some
independence condition,
every value function is updated an infinite number of time.
Then the upper and lower bounds converges almost surely toward
the value of the problem.
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
18 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
Numerical Results
Widely used in the energy community (management of dam,
sizing of network etc...)
Efficient up to 10-15 dams.
Numerical experiments available on A. Shapiro website:
120 time-step, 4 dams for a state of dimension 8,
each ξt is discretized in 100 points, hence there is 100119
scenarios,
3000 iterations runs in 15 minutes,
20% gap, 4% in dimension 4.
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
19 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
Contents
1
Technical Preliminaries
Problem Formulation and Dynamic Programming
Duality Approach
2
SDDP Algorithm
The SDDP algorithm
Miscellaneous
3
Convergence and Numerical Results
4
Conclusion
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
19 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
Conclusion
SDDP is an algorithm, more precisely a class of algorithms that
exploit convexity of the value functions (from convexity of
costs...);
does not require discretization;
construct outer approximations of Vt , those approximations
being precise only “in the right places”;
gives bounds :
(k)
real lower bound V0 (x0 ),
estimated (by Monte-Carlo) upper bound;
construct linear-convex approximations, thus enabling the use
of linear solver like CPLEX,
have proofs of asymptotic convergence.
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
20 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
Available Extensions
Cut dropping methods are studied.
Hot start by bypassing the forward phase and selecting
artificial trajectories are numerically efficient.
Work is done to apply SDDP in some non-convex cases.
Risk aversion (through CVAR - either as constraint or as an
element of the objective function) can be taken into account
(by extending the state).
Non linear convex cost can be used (convergence result).
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
21 / 21
Technical Preliminaries
SDDP Algorithm
Convergence and Numerical Results
Conclusion
M. Pereira, L.Pinto (1991).
Multi-stage stochastic optimization applied to energy planning.
Mathematical Programming
Z.Chen, W. Powell (1999).
A convergent cutting plane and partial-sampling algorithm for
multistage linear programs with recourse.
Journal of Optimization Theory and Applications
A.Philpott, Z. Guan (2008).
On the convergence of stochastic dual dynamic programming
and related methods.
Operations research letters
`re, A. Philpott (2014).
P.Girardeau, V.Lecle
On the convergence of decomposition methods for multi-stage
stochastic convex programs.
accepted in Mathematics of Operations Research.
V. Lecl`
ere
Introduction to SDDP
August 1, 2014
21 / 21

Download Report