Summer School CEAEDFINRIA 2012
Stochastic Optimization
Cadarache, June 25th  July 6th, 2012
Organizers: Michel De Lara
(CERMICS)
and Stéphane Gaubert
(INRIA)
You can load the pdf version
of this web page and the poster
Website
http://cermics.enpc.fr/~delara/TEACHING/CEAEDFINRIA_2012/CEAEDFINRIA_2012/
Abstract:
This school will cover three approaches in stochastic optimization  stochastic programming, dynamic programming, variational methods  by emphasizing the modelling of dynamical control problems, as well as
algorithmics aspects. Among the applications, we find the management of
energy systems under uncertainty. Courses are given by
Accommodation and courses take place at
Maison d'Hôtes Château de Cadarache,
Route de Vinon sur Verdon,
13115 Saint Paul Lez Durance,
Tél. +33 4 42 57 68 00 (and also at Olivier Hotel)
from Monday, June 25th till Friday, July 6th, 2012.
A shuttle is available according to this bus schedule
These courses can interest a public of industrial engineers as well as academics (in particular researchers from CEA, EDF and INRIA), confirmed or not, including PhD and postdoctorate students.
Acknowledgement. This event is partially supported by the MarieCurie Initial training network SADCO
(``FP7PEOPLE2010ITN'', Grant agreement number 264735SADCO)
Stochastic optimization will be approached under three angles
 Stochastic Programming
 Dynamic Programming
 Variational Methods
corresponding to different ways to handle nonanticipativity constraints, and leading to different resolution methods.
Each course lasts 9 hours and comprises six sessions of 1h30. Computer practical works and ``practical lectures'' alternate with the theoretical courses and are organized in three (or four) sessions of 2 hours each.
 Deterministic versus stochastic models? Different criteria when
having to cope with uncertainty
slides
and a paper by Pravin Varaiya and Roger JB Wets
(University of California, BerkeleyDavis)
Stochastic Dynamic Optimization
Approaches and Computation
 Stochastic programs with recourse (1): from simple to extensive
dynamic models
slides
and a paper by R.T. Rockafellar and R.JB. Wets
Generalized LinearQuadratic Problems of Deterministic and
Stochastic Optimal Control in Discrete Time
 Stochastic programs with recourse (2)
slides
 Solving Stochastic Programs with Recourse
slides
 Approximations and Law of Large Numbers. Duality
slides
 Integer stochastic programs and Chance Constraints.
The unit commitment problem
slides
 TP1.
 Formulation/solution of simple stochastic programs
download rar file
 TP2.
 Introduction to the scientific software Pyomo. Formulation
(solution) of a hydroelectric power generation problem
download rar file
 TP23.
 Formulation
(solution) of a hydroelectric power generation problem
download rar file
 TP4.
 The unit commitment problem (ISO), i.e., dynamic
mixedinteger stochastic program
download rar file
 Infinite Horizon Dynamic Programming (DP)
slides
 Computational Methods for DP
slides
 LargeScale DP: General Issues
slides
 Approximate Policy Iteration and Temporal Difference Methods
slides
 Projection Methods, Aggregation Methods, and QLearning
slides
 DP and MonteCarlo Linear Algebra
slides
 TP1.
 Theory and computational methods of exact DP
slides
(download exercises 1 & 2
and
exercises 3 & 4)
 TP2.
 Theory and computational methods of approximate DP
slides
(download exercises 2 & 3)
 TP3.
 Approximate policy iteration methods, and QLearning
slides
(download exercises 1)
 Information constraints and discretization
puzzles in stochastic optimal control (MDL)
slides
 Variational approaches in stochastic optimal control (PC)
slides
 Probability constraints and stochastic viability (MDL)
slides
and more details on
Advanced Course on Sustainable Optimization
 Dynamic consistency and probability constraints (JPC)
slides
 Decompositioncoordination methods in stochastic optimal control
(PC)
slides
 Introduction to multiagent decentralized optimization (Aditya Mahajan)
slides
 TP1.
 Information constraints discretization
in a twostep model
 TP2.
 Dynamic programming for a single dam
 TP3.
 Decompositioncoordination methods for interconnected dams
Course 1 refers to Stochastic Programming (
ROGER WETS),
Course 2 to LargeScale Approximate Dynamic Programming and Reinforcement Learning (
DIMITRI BERTSEKAS),
Course 3 to Information Constraints in Stochastic Control (
PIERRE CARPENTIER,
JEANPHILIPPE CHANCELIER,
MICHEL DE LARA).
 June, Monday 25
 11h11h10. Introduction
(
STÉPHANE GAUBERT,
MICHEL DE LARA).
 11h1012h40.
ROGER WETS, Lecture 11.
 14h3016h00.
DIMITRI BERTSEKAS, Lecture 21
 16h3018h00.
MICHEL DE LARA, Lecture 31
 19h0020h00.
Round table (breaking the ice).
 June, Tuesday 26
 8h3010h00.
ROGER WETS, Lecture 12
 10h3012h00.
DIMITRI BERTSEKAS, Lecture 22
 14h0015h30.
PIERRE CARPENTIER, Lecture 32
 16h0016h30.
ADITYA MAHAJAN, Introduction to decentralized control
 16h4519h15.
Visit of wineyard
(Château Vignelaure).
 June, Wednesday 27
 8h3010h00.
ROGER WETS, Lecture 13
 10h3012h30.
PIERRE CARPENTIER and
JEANPHILIPPE CHANCELIER, Computer work 31
 14h3016h30.
MENGDI WANG, Pratical Lecture 21
 17h0019h00.
LUIS FERNANDO SOLARIS and
VINCENT LECLÈRE, Practical lecture 11
 June, Thursday 28. Workshop day.
 8h309h25
ROGER WETS. Optimization Techniques in
Statistical Estimation: Fusion of hard and soft information
slides
 9h2510h20
GILLES PAGÈS. Dual quantization and
dynamic programming slides
 10h20 Break
 10h5011h45
FRÉDÉRIC BONNANS. Optimization of a
liquefied natural gas portfolio by SDDP techniques slides
 12h00 Lunch
 13h3014h25
DIMITRI BERTSEKAS. Monte Carlo linear
algebra: A review and recent results slides
 14h2515h20
R´EMI MUNOS. Optimistic optimization
of a function without the knowledge of its smoothness
slides
 15h20 Break
 15h5016h45
BRUNO SCHERRER. Performance bounds for
Approximate Dynamic Programming in Large Scale InfiniteHorizon
Optimal Control Problems
slides
 16h4517h40
STÉPHANE GAUBERT.
Tropical methods in dynamic programming slides
 June, Friday 29
 8h3010h00.
ROGER WETS, Lecture 14
 10h3012h00.
DIMITRI BERTSEKAS, Lecture 23
 13h3015h30.
LUIS FERNANDO SOLARIS and
VINCENT LECLÈRE, Practical lecture 12
 16h00. Shuttle.
 July, Monday 2
 11h0012h30.
MICHEL DE LARA, Lecture 33
 14h3016h00.
DIMITRI BERTSEKAS, Lecture 24
 16h3018h30.
LUIS FERNANDO SOLARIS and
VINCENT LECLÈRE, Practical lecture 13
 July, Tuesday 3
 8h3010h00.
ROGER WETS, Lecture 15
 10h3012h00.
JEANPHILIPPE CHANCELIER, Lecture 34
 14h0016h00.
MENGDI WANG, Practical lecture 22
 16h3018h30.
PIERRE CARPENTIER and
MICHEL DE LARA, Computer work 32
 July, Wednesday 4
 8h3010h00.
PIERRE CARPENTIER, Lecture 35
 10h3012h00.
ROGER WETS, Lecture 16
 14h0015h30.
DIMITRI BERTSEKAS, Lecture 25
 16h0018h00.
JEANPHILIPPE CHANCELIER and
MICHEL DE LARA, Computer work 33
 July, Thursday 5.
 8h3010h30.
LUIS FERNANDO SOLARIS and
VINCENT LECLÈRE, Practical lecture 14
 11h0012h30.
DIMITRI BERTSEKAS, Lecture 26
 14h3015h30
THIERRY VANHAVERBEKE,
AIR FRANCE,
Revenue Management in the Airline Industry: an introduction to RM
systems and OR techniques
slides
 15h3016h30
ANÈS DALLAGI, EDF,
Large scale energy management: an overview on time and space
decomposition
 16h3017h00 Break
 17h0017h30
BERNARDO PAGNONCELLI KULNIG,
UAI CHILE,
The optimal harvesting problem under price uncertainty
slides
 17h3018h00
EDUARDO MORENO,
UAI CHILE,
Openpit mining problem and the BZ algorithm
slides
 18h3019h30 Closing session (panel discussion).
 20h00.
School dinner.
 July, Friday 6
 8h3010h00.
ADITYA MAHAJAN, Lecture 36
 10h3012h30.
MENGDI WANG, Practical Lecture 23
 Shuttle: 14h30.
The workshop consists of 7 talks, of 55 minutes each. All the talks
will be given in English.
 8h30

ROGER WETS. Optimization Techniques in
Statistical Estimation: Fusion of hard and soft information
slides
 9h25

GILLES PAGÈS. Dual quantization and
dynamic programming slides
 10h20
 Break
 10h50

FRÉDÉRIC BONNANS. Optimization of a
liquefied natural gas portfolio by SDDP techniques slides
 12h00
 Lunch
 13h30

DIMITRI BERTSEKAS. Monte Carlo linear
algebra: A review and recent results slides
 14h25

RÉMI MUNOS. Optimistic optimization of a
function without the knowledge of its smoothness slides
 15h20
 Break
 15h50

BRUNO SCHERRER. Performance bounds for
Approximate Dynamic Programming in Large Scale InfiniteHorizon
Optimal Control Problems
slides
 16h45

STÉPHANE GAUBERT. Tropical methods in
dynamic programming slides
 17h40
 End of talks
To describe the stochastic environment in descriptive or prescriptive models, it is implicitly assumed that enough data will be available to guarantee the validity of a decision or the consistency of a statistical estimate. Unfortunately, in a real life environment the data available is rarely enough to reach the asymptotic range, either because it is not available or there is not enough time to collect an adequate database before decisions or estimates must be produced. One serious shortcoming is our ability to systematically blend data and nondata information, in other words, our inability to deal with the fusion of hard and soft information. The lecture deals with these challenges.
Les problèmes de contrôle stochastiques en temps discret se représentent généralement sous forme d'un principe de programmation dynamique rétrograde.
Les méthodes d'arbre, popularisés en Finance, sont un outil naturel de résolution numérique. La construction de tels arbres en dimension supérieure, pour etre efficace, doit à chaque pas de temps discrétiser la loi du processus de structure de façon aussi efficace que possible pour un budget donné.
Les méthodes de quantification optimales, issues du traitement du signal, se sont révélées très adaptées à cette tâche. Nous en présenterons ici deux types: la quantification de Voronoi, classique, liée à l'approximation par des fonctions constantes par morceaux et la quantification de Delaunay (ou duale), liée à un opérateur d'interpolation sur une triangulation.
Nous proposerons une analyse comparée succincte de leurs propriétés et passerons en revue quelques algorithmes d'optimisation stochastiques  de type gradient stochastique ou point fixe randomisé  permettant le calcul, éventuellement parallélisé, des grilles de quantification optimales en dimension supérieure à partir desquelles sont construits les arbres éponymes.
References.
1. S. Graf , H. Luschgy, Foundations of Quantization for Probability Distributions, Lecture Notes in Mathematics, 1730, Berlin (2000)
2. G. Pagès, J. Printems, Optimal quantization for finance: from random vectors to stochastic processes, in Mathematical Modeling and Numerical Methods in Finance (special volume) (A. Bensoussan, Q. Zhang guest éds.), coll. Handbook of Numerical Analysis (P.G. Ciarlet Editor), North Holland, 595649, 2009.
3. G. Pagès, B. Wilbertz, Intrinsic stationarity for vector quantization: Foundation of dual quantization, SIAM J. on Numerical Analysis, 50:747780, 2012.
4. G. Pagès, B. Wilbertz, Optimal Delaunay et Voronoi quantization methods for pricing American options, Numerical methods in Finance (R. Carmona, P. Hu, P. Del Moral, N. Oudjane éds.), Springer, 171217, 2012.
We consider the problem of optimal management of
energy contracts, with bounds on the local (time step) amounts and
global (whole period) amounts to be traded, integer
constraint on the decision variables and uncertainty on prices only.
After building a finite state Markov chain by using
vectorial quantization tree method, we rely on the stochastic dual
dynamic programming (SDDP) method to solve the continuous relaxation
of this stochastic optimization problem.
An heuristic for computing sub optimal solutions to the
integer optimization problem, based on the Bellman values of
the continuous relaxation, is provided.
Combining the previous techniques, we are able to
deal with highdimension state variables
problems and to analyze sensitivity results. Numerical tests applied to
realistic energy markets problems have been performed.
The term ``Monte Carlo linear algebra" indicates an emerging field where the methods of Monte Carlo simulation and algorithmic linear algebra are brought to bear on the solution of large problems, possibly through the use of approximations. This approach, which originated with von Neumann and Ulam more than 60 years ago, has played a central role in approximate Dynamic Programming (DP) for the last 20 years. It also relates to methods of Galerkin approximation and aggregation, which have a very broad range of applications, because of the widespread use of linear models in engineering, the natural sciences, statistical regression, and machine learning.
Our emphasis will be on simulationbased methods for solution of linear systems , using estimates and to and , with , as the number of samples
. We discuss simulation approaches for obtaining and that are motivated by corresponding DP methods, and involve the use of Markov chains. We also discuss matrix inversion and iterative approaches for computing a solution, with a special emphasis on the case where is singular or nearly singular.
We investigate algorithms for global optimization of a function given a finite budget of function evaluations. The function is assumed to satisfy a local smoothness property around one of its global maxima. The first algorithm (DOO) implements an optimistic exploration strategy and requires the knowledge of the function local smoothness property. Its performance is analyzed using a measure of quantity of nearoptimal states. The second algorithm (SOO) does not require this knowledge and performs almost as well as DOO optimally fitted. I will relate this approach to related works including UCT, HOO, Zooming, Optimistic planning, DIRECT algorithms.
Infinite horizon optimal control problems can be solved by dynamic programming by computing the socalled optimal value function on the state space of the problem. When the state space is large, computing and even storing the value function may not be possible. I will describe approximation techniques that can be used in practice, and discuss their theoretical property. I will in particular present a recent unification performance analysis that applies to a family of algorithms that contains the two most celebrated algorithms of the literature, Value and Policy Iteration.
I will survey some recent applications of tropical methods to dynamic programming, with emphasis on algorithmic issues. These include the equivalence between decision problem concerning the tropical analogues of polyhedra and deterministic mean payoff games. Here, tropical (maxplus or minplus) polyhedra arise
as sets of certificates (potentials) allowing one
to check that the game is subfair or superfair. More generally,
stochastic mean payoff games problems can be expressed in terms
of feasibility problems for tropical convex sets.
This leads to some extensions to the two player case of the
classical policy iteration algorithms,
in which tropical spectral theory / nonlinear
potential theory results, are used to avoid cycling
in degenerate iterations. Another instance where tropical methods
have been applied, this time in an infinite dimensional setting,
concerns the so called ``maxplus basis methods'' originally
introduced by Fleming and McEneaney,
to solve deterministic optimal control problems. Here, the tropically
linear character of the LaxOleinik semigroup is exploited
to approximate the value function by a supremum of basis
functions, leading to a reduction of the curse of dimensionality
in some special instances.
References
1. M. Akian, S. Gaubert, and A. Guterman.
Tropical polyhedra are equivalent to mean payoff games.
International of Algebra and Computation, 22(1):125001 (43 pages), 2012.
doi:10.1142/S0218196711006674, arxiv:0912.2462
2. S. Gaubert, W. McEneaney, and Z. Qu.
Curse of dimensionality reduction in maxplus based approximation
methods: theoretical estimates and improved pruning algorithms.
In Proceedings of the 50th IEEE Conference on Decision and
Control and European Control Conference (CDCECC 11), pages 10541061,
Orlando, FL, USA, December 2011, arxiv:1109.5241
On Thursday 5 July 2012 (14h0018h00), we will have two talks by
industry professionals, and additional applied work talks
 14h3015h30
 Thierry Vanhaverbeke, Air France,
Revenue Management in the Airline Industry: an introduction to RM
systems and OR techniques
slides
 15h3016h30
 Anès Dallagi, EDF,
Large scale energy management: an overview on time and space
decomposition
 16h3017h00
 Pause
 17h0017h30
 Bernardo Pagnoncelli Kulnig, UAI Chile,
The optimal harvesting problem under price uncertainty
slides
 17h3018h00
 Eduardo Moreno, UAI Chile,
Openpit mining problem and the BZ algorithm
slides
 18h3019h30
 Closing session (panel discussion)
EDF is one of the European leaders in the energy field and the
major electricity producer in France. One of the main goals of EDF is to
insure at all times that the production of its energy mix meets the demand
of its clients.
To mach supply and demand, EDF has to cope with several technical and
economical constraints that appear on both short and long run. This
induces a large scale management problem. Decomposition techniques appear
then to be the appropriate tool to be used.
This presentation will focus on the decomposition methods present on the
EDF power management process. First, we begin by a large overview on the
time decomposition procedure that split the optimization process on Long,
Mid and short term. Then we will focus on two space decomposition
techniques: price decomposition (for daily and intraday power portfolio
schedule) and splitting algorithms (for pan European long term marginal
costs forecast). Finally we will present a numerical application.
Revenue Management, a major business area for Airlines, is in charge
to optimize product availability and prices in order to maximize
their network revenue, by "selling the right seat to the right
customer at the right price and time". Through this presentation I
will provide a general introduction to Airline Revenue Management and
a quick overview of RM information systems. We will then focus on
Revenue Management algorithms that can be used by the Airlines for
overbooking and optimization and on associated challenges.