KMUTT Department of Mathematics
King Mongkut's University of Technoloty Thonburi
Bangkok, Thailand
21-29 December 2015
Stochastic and Dynamic Optimization.
Optimal Energy Allocation in Micro-Grids.
Michel DE LARA, CERMICS-École des Ponts ParisTech
Eligibility/Pre-requisites.
- Mathematical skills. Computer skills.
- Continuous optimization: linear programming, convexity, duality,
first-order optimality conditions. [Ber96]
- Probability calculus: probability space, probability, random variable,
distribution law of a random variable,
indicator function, mathematical expectation, independence,
law of large numbers. [Fel68,Bre93,Pit93]
- Software Scicoslab to be installed
Scicoslab
(else, install software Scilab)
Learning outcomes.
After the course the student should be able to
- design mathematical models for energy storage and delivery of renewable
energies, especially in micro-grids, and formulate cost-minimization problems,
- use the scientific software Scicoslab and numerically solve small
scale problems.
Course main content.
The course mixes theoretical sessions, modeling exercises and computer
sessions.
In introduction, we present examples of micro-grid
and virtual power plant management
-- where the question of electrical storage is put, due to the need
to answer a varying demand and to incorporate intermittent and
highly variable renewable energies.
We show how such problems can be formulated as
dynamic stochastic optimization problems
[LCCL14].
In a deterministic optimization problem, the values of all parameters
are supposed known. What happens when this is no longer the case?
And when some values are revealed during the stages of decision?
We present stochastic optimization, at the same time as a frame
to formulate problems under uncertainty,
and as methods to solve them according to the formulation.
More precisely, we present stochastic programming in two stages
(and the resolution on scenario tree or by scenarios)
and stochastic control in discrete time
(and the resolution by stochastic dynamic programming).
We devote time to the Stochastic Dual Dynamic Programming (SDDP)
algorithm, widely used in the world of the energy,
which mixes dynamic programming and cutting plane algorithm.
The SDDP approach seems especially adapted to micro-grid management issues.
Modeling exercises and computer sessions tackle issues like
optimal economic dispatch of energy production units,
storage/delivery optimization problem to buffer an
intermittent and variable source of energy,
dam optimal management with stochastic water inflows,
battery optimal management with renewable energy inputs.
Contact person.
Michel De Lara (Cermics-École des Ponts ParisTech)
professional webpage
Link course.
http://cermics.enpc.fr/~delara/ENSEIGNEMENT/KMUTT2015/
course webpage
To introduce the course, we present examples of micro-grid
and virtual power plant management
that make use of dynamic stochastic optimization
- ``Cooperating between academy and industry
for the optimization of smart grids''
slides
- Work done by Francis Sourd (Sun'R) and Ariel Waserhole (Sun'R)
``SunHydro: l'optimisation stochastique au c
ur d'un
projet collaboratif''
slides
- Work done by Tristan Rigaut (Efficacity)
``Energy optimization and climate control of a subway station microgrid''
slides
- Work done by Romain Bonabe de Rougé (Efficacity),
Valentin Foucher (student at École Polytechnique) and
François Pacaud (Efficacity)
``Optimal sizing and integration of a micro-combined heat and power
generation with thermal and electrical storage in an individual residential
housing''
slides
slides
We present, under the form of exercises, examples of
optimization problems under uncertainty: ``the blood-testing problem'',
``the newsvendor problem'' (``stock management problems'').
slides
Recalls and exercises on probability calculus.
End of the newsvendor problem.
Introduction to the scientific software Scicoslab.
[CCN10]
computer session
- ``Cooperating between academy and industry
for the optimization of smart grids''
slides
- Work done by Francis Sourd (Sun'R) and Ariel Waserhole (Sun'R)
``SunHydro: l'optimisation stochastique au cur d'un
projet collaboratif''
slides
- Work done by Tristan Rigaut (Efficacity)
``Energy optimization and climate control of a subway station microgrid''
slides
- Work done by Romain Bonabe de Rougé (Efficacity),
Valentin Foucher (student at École Polytechnique) and
François Pacaud (Efficacity)
``Optimal sizing and integration of a micro-combined heat and power
generation with thermal and electrical storage in an individual residential
housing''
slides
slides
Introduction to the scientific software Scicoslab.
[CCN10]
computer session
Computer exercise on the newsvendor problem.
computer session
(only Section 1)
We begin by formulating a problem of optimal choice of a product quantity
(energy, for instance) to satisfy a demand, with costs of purchase,
of backorder and of holding.
We show how to obtain a linear program, first in a determinist setting
(demand known in advance), then in a probabilistic one
with a finite number of scenarios of demand.
We continue by an exercise of modelling.
How can we mathematically formulate a problem of optimal allocation of
power production units, at minimal cost, with guaranteed minimal production
and guaranteed maximal pollution?
We naturally obtain a linear program.
We will see how the introduction of uncertainties
(costs, renewable power production) modifies the problem formulation.
It is the opportunity to touch the notions of risk and of
non anticipativity.
Two-stage stochastic programming on a scenario tree.
Non-anticipativity constraint along scenarios: tree representation.
[SDR09,KW12]
Sizing of reserves for the balancing on an electric market.
Two stage stochastic programming
(linear optimization on a tree).
computer session
(From Question 1 to Question 4)
Sizing of reserves for the balancing on an electric market.
Two stage stochastic programming
(convex quadratic optimization on a tree).
computer session
(From Question 5 to Question 7)
Recalls and exercises on continuous optimization [Ber96].
slides
- Recalls on convexity: convex sets, convex functions,
strict and strong convexity (characterization by the Hessian in the
smooth case), operations preserving convexity.
- Abstract formulation of a minimization problem: criterion, constraints.
Sufficient conditions for the existence of a minimum
(continuity and compacity/coercivity).
Sufficient condition for the uniqueness of a minimum (strict convexity).
Exercises with a quadratic objective function on an interval.
- Definition of a local minimizer; necessary condition in the differentiable
case. Formulation of a minimization problem under explicit equality
constraints. Necessary first-order optimality conditions in the
regular/affine equality constraints case; Lagrangian, duality, multipliers.
Sufficient first-order optimality conditions in the convex-affine case.
Exercises.
- Saddle point. Existence of a saddle point for a continuous, convex-concave
function displaying coercivity along two coordinate lines.
Uzawa algorithm.
Two-stage stochastic programming on a comb.
Non-anticipativity constraint along scenarios.
Scenario decomposition by Lagrangian relaxation. Progressive Hedging
[RW91].
Sizing of reserves for the balancing on an electric market.
Two stage stochastic programming
(linear and convex quadratic optimization on a comb).
computer session
(From Question 8 to Question 12)
Sizing of reserves for the balancing on an electric market.
Two stage stochastic programming
(linear and convex quadratic optimization on a comb).
computer session
(From Question 8 to Question 12)
Dynamical models of storage (battery models, dam models).
Inventory problems.
The secretary problem.
- Bel57
-
R. E. Bellman.
Dynamic Programming.
Princeton University Press, Princeton, N.J., 1957.
- Ber96
-
D. P. Bertsekas.
Constrained Optimization and Lagrange Multiplier Methods.
Athena Scientific, Belmont, Massachusets, 1996.
- Ber00
-
D. P. Bertsekas.
Dynamic Programming and Optimal Control.
Athena Scientific, Belmont, Massachusets, second edition, 2000.
Volumes 1 and 2.
- Ber05
-
D.P. Bertsekas.
Dynamic programming and suboptimal control: A survey from ADP to
MPC.
European J. of Control, 11(4-5), 2005.
- Bre93
-
L. Breiman.
Probability.
Classics in applied mathematics. SIAM, Philadelphia, second
edition, 1993.
- CCCD15
-
P. Carpentier, J.-P. Chancelier, G. Cohen, and M. De Lara.
Stochastic Multi-Stage Optimization. At the Crossroads between
Discrete Time Stochastic Control and Stochastic Programming.
Springer-Verlag, Berlin, 2015.
- CCN10
-
Stephen Campbell, Jean-Philippe Chancelier, and Ramine Nikoukhah.
Modeling and Simulation in Scilab/Scicos with ScicosLab 4.4.
Springer-Verlag, New York, 2 edition, 2010.
- DD08
-
Michel De Lara and Luc Doyen.
Sustainable Management of Natural Resources. Mathematical Models
and Methods.
Springer-Verlag, Berlin, 2008.
- Fel68
-
W. Feller.
An Introduction to Probability Theory and its Applications,
volume 1.
Wiley, New York, third edition, 1968.
- KW12
-
Alan J. King and Stein W. Wallace.
Modeling with Stochastic Programming.
Springer Series in Operations Research and Financial Engineering.
Springer New York, 2012.
- LCCL14
-
M. De Lara, P. Carpentier, J.-P. Chancelier, and V. Leclère.
Optimization methods for the smart grid.
Report commissioned by the Conseil Français de l'Énergie,
École des Ponts ParisTech, October 2014.
- Pit93
-
J. Pitman.
Probability.
Springer-Verlag, New-York, 1993.
- PM15a
-
Warren Powell and Stephan Meisel.
Tutorial on stochastic optimization in energy i: Modeling and
policies.
IEEE Transactions on Power Systems, 2015.
Publication status: In press.
- PM15b
-
Warren Powell and Stephan Meisel.
Tutorial on stochastic optimization in energy ii: An energy storage
illustration.
IEEE Transactions on Power Systems, 2015.
Publication status: In press.
- Pow14
-
Warren B. Powell.
Clearing the Jungle of Stochastic Optimization, chapter 5,
pages 109-137.
Informs, 2014.
- Put94
-
M. L. Puterman.
Markov Decision Processes.
Wiley, New York, 1994.
- RW91
-
R.T. Rockafellar and R. J-B. Wets.
Scenarios and policy aggregation in optimization under uncertainty.
Mathematics of operations research, 16(1):119-147, 1991.
- SDR09
-
A. Shapiro, D. Dentcheva, and A. Ruszczynski.
Lectures on stochastic programming: modeling and theory.
The society for industrial and applied mathematics and the
mathematical programming society, Philadelphia, USA, 2009.
- Whi82
-
P. Whittle.
Optimization over Time: Dynamic Programming and Stochastic
Control, volume 1 and 2.
John Wiley & Sons, New York, 1982.