Summer School CEA-EDF-INRIA 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_PAST/CEA-EDF-INRIA_2012/CEA-EDF-INRIA_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 post-doctorate students.
Acknowledgement. This event is partially supported by the Marie-Curie Initial training network SADCO
(``FP7-PEOPLE-2010-ITN'', Grant agreement number 264735-SADCO)
Stochastic optimization will be approached under three angles
- Stochastic Programming
- Dynamic Programming
- Variational Methods
corresponding to different ways to handle non-anticipativity 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 J-B Wets
(University of California, Berkeley-Davis)
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.J-B. Wets
Generalized Linear-Quadratic 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 hydro-electric power generation problem
download rar file
- TP2-3.
- Formulation
(solution) of a hydro-electric power generation problem
download rar file
- TP4.
- The unit commitment problem (ISO), i.e., dynamic
mixed-integer stochastic program
download rar file
- Infinite Horizon Dynamic Programming (DP)
slides
- Computational Methods for DP
slides
- Large-Scale DP: General Issues
slides
- Approximate Policy Iteration and Temporal Difference Methods
slides
- Projection Methods, Aggregation Methods, and Q-Learning
slides
- DP and Monte-Carlo 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 Q-Learning
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
- Decomposition-coordination methods in stochastic optimal control
(PC)
slides
- Introduction to multi-agent decentralized optimization (Aditya Mahajan)
slides
- TP1.
- Information constraints discretization
in a two-step model
- TP2.
- Dynamic programming for a single dam
- TP3.
- Decomposition-coordination methods for interconnected dams
Course 1 refers to Stochastic Programming (
ROGER WETS),
Course 2 to Large-Scale Approximate Dynamic Programming and Reinforcement Learning (
DIMITRI BERTSEKAS),
Course 3 to Information Constraints in Stochastic Control (
PIERRE CARPENTIER,
JEAN-PHILIPPE CHANCELIER,
MICHEL DE LARA).
- June, Monday 25
- 11h-11h10. Introduction
(
STÉPHANE GAUBERT,
MICHEL DE LARA).
- 11h10-12h40.
ROGER WETS, Lecture 1-1.
- 14h30-16h00.
DIMITRI BERTSEKAS, Lecture 2-1
- 16h30-18h00.
MICHEL DE LARA, Lecture 3-1
- 19h00-20h00.
Round table (breaking the ice).
- June, Tuesday 26
- 8h30-10h00.
ROGER WETS, Lecture 1-2
- 10h30-12h00.
DIMITRI BERTSEKAS, Lecture 2-2
- 14h00-15h30.
PIERRE CARPENTIER, Lecture 3-2
- 16h00-16h30.
ADITYA MAHAJAN, Introduction to decentralized control
- 16h45-19h15.
Visit of wineyard
(Château Vignelaure).
- June, Wednesday 27
- 8h30-10h00.
ROGER WETS, Lecture 1-3
- 10h30-12h30.
PIERRE CARPENTIER and
JEAN-PHILIPPE CHANCELIER, Computer work 3-1
- 14h30-16h30.
MENGDI WANG, Pratical Lecture 2-1
- 17h00-19h00.
LUIS FERNANDO SOLARIS and
VINCENT LECLÈRE, Practical lecture 1-1
- June, Thursday 28. Workshop day.
- 8h30-9h25
ROGER WETS. Optimization Techniques in
Statistical Estimation: Fusion of hard and soft information
slides
- 9h25-10h20
GILLES PAGÈS. Dual quantization and
dynamic programming slides
- 10h20 Break
- 10h50-11h45
FRÉDÉRIC BONNANS. Optimization of a
liquefied natural gas portfolio by SDDP techniques slides
- 12h00 Lunch
- 13h30-14h25
DIMITRI BERTSEKAS. Monte Carlo linear
algebra: A review and recent results slides
- 14h25-15h20
R´EMI MUNOS. Optimistic optimization
of a function without the knowledge of its smoothness
slides
- 15h20 Break
- 15h50-16h45
BRUNO SCHERRER. Performance bounds for
Approximate Dynamic Programming in Large Scale Infinite-Horizon
Optimal Control Problems
slides
- 16h45-17h40
STÉPHANE GAUBERT.
Tropical methods in dynamic programming slides
- June, Friday 29
- 8h30-10h00.
ROGER WETS, Lecture 1-4
- 10h30-12h00.
DIMITRI BERTSEKAS, Lecture 2-3
- 13h30-15h30.
LUIS FERNANDO SOLARIS and
VINCENT LECLÈRE, Practical lecture 1-2
- 16h00. Shuttle.
- July, Monday 2
- 11h00-12h30.
MICHEL DE LARA, Lecture 3-3
- 14h30-16h00.
DIMITRI BERTSEKAS, Lecture 2-4
- 16h30-18h30.
LUIS FERNANDO SOLARIS and
VINCENT LECLÈRE, Practical lecture 1-3
- July, Tuesday 3
- 8h30-10h00.
ROGER WETS, Lecture 1-5
- 10h30-12h00.
JEAN-PHILIPPE CHANCELIER, Lecture 3-4
- 14h00-16h00.
MENGDI WANG, Practical lecture 2-2
- 16h30-18h30.
PIERRE CARPENTIER and
MICHEL DE LARA, Computer work 3-2
- July, Wednesday 4
- 8h30-10h00.
PIERRE CARPENTIER, Lecture 3-5
- 10h30-12h00.
ROGER WETS, Lecture 1-6
- 14h00-15h30.
DIMITRI BERTSEKAS, Lecture 2-5
- 16h00-18h00.
JEAN-PHILIPPE CHANCELIER and
MICHEL DE LARA, Computer work 3-3
- July, Thursday 5.
- 8h30-10h30.
LUIS FERNANDO SOLARIS and
VINCENT LECLÈRE, Practical lecture 1-4
- 11h00-12h30.
DIMITRI BERTSEKAS, Lecture 2-6
- 14h30-15h30
THIERRY VANHAVERBEKE,
AIR FRANCE,
Revenue Management in the Airline Industry: an introduction to RM
systems and OR techniques
slides
- 15h30-16h30
ANÈS DALLAGI, EDF,
Large scale energy management: an overview on time and space
decomposition
- 16h30-17h00 Break
- 17h00-17h30
BERNARDO PAGNONCELLI KULNIG,
UAI CHILE,
The optimal harvesting problem under price uncertainty
slides
- 17h30-18h00
EDUARDO MORENO,
UAI CHILE,
Open-pit mining problem and the BZ algorithm
slides
- 18h30-19h30 Closing session (panel discussion).
- 20h00.
School dinner.
- July, Friday 6
- 8h30-10h00.
ADITYA MAHAJAN, Lecture 3-6
- 10h30-12h30.
MENGDI WANG, Practical Lecture 2-3
- 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 Infinite-Horizon
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 non-data 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, 595-649, 2009.
3. G. Pagès, B. Wilbertz, Intrinsic stationarity for vector quantization: Foundation of dual quantization, SIAM J. on Numerical Analysis, 50:747-780, 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, 171-217, 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 high-dimension 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 simulation-based 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 near-optimal 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 so-called 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 (max-plus or min-plus) polyhedra arise
as sets of certificates (potentials) allowing one
to check that the game is sub-fair or super-fair. 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 ``max-plus basis methods'' originally
introduced by Fleming and McEneaney,
to solve deterministic optimal control problems. Here, the tropically
linear character of the Lax-Oleinik 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 max-plus based approximation
methods: theoretical estimates and improved pruning algorithms.
In Proceedings of the 50th IEEE Conference on Decision and
Control and European Control Conference (CDC-ECC 11), pages 1054-1061,
Orlando, FL, USA, December 2011, arxiv:1109.5241
On Thursday 5 July 2012 (14h00--18h00), we will have two talks by
industry professionals, and additional applied work talks
- 14h30-15h30
- Thierry Vanhaverbeke, Air France,
Revenue Management in the Airline Industry: an introduction to RM
systems and OR techniques
slides
- 15h30-16h30
- Anès Dallagi, EDF,
Large scale energy management: an overview on time and space
decomposition
- 16h30-17h00
- Pause
- 17h00-17h30
- Bernardo Pagnoncelli Kulnig, UAI Chile,
The optimal harvesting problem under price uncertainty
slides
- 17h30-18h00
- Eduardo Moreno, UAI Chile,
Open-pit mining problem and the BZ algorithm
slides
- 18h30-19h30
- 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 intra-day 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.