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


Contents

1 Place, Dates, Public

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)

2 Main Courses

Stochastic optimization will be approached under three angles

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.

2.1 Stochastic Programming (Roger Wets)

Course

  1. 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
  2. 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
  3. Stochastic programs with recourse (2) slides
  4. Solving Stochastic Programs with Recourse slides
  5. Approximations and Law of Large Numbers. Duality slides
  6. Integer stochastic programs and Chance Constraints. The unit commitment problem slides

Computer practical works (Luis Fernando Solari, Vincent Leclère)

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

2.2 Large-Scale Approximate Dynamic Programming and Reinforcement Learning (Dimitri Bertsekas)

Course (Dimitri Bertsekas)

  1. Infinite Horizon Dynamic Programming (DP) slides
  2. Computational Methods for DP slides
  3. Large-Scale DP: General Issues slides
  4. Approximate Policy Iteration and Temporal Difference Methods slides
  5. Projection Methods, Aggregation Methods, and Q-Learning slides
  6. DP and Monte-Carlo Linear Algebra slides

Practical lectures (Mengdi Wang)

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)

2.3 Information Constraints in Stochastic Optimal Control
(Pierre Carpentier, Jean-Philippe Chancelier, Michel De Lara)

Course
(Pierre Carpentier, Jean-Philippe Chancelier, Michel De Lara)

  1. Information constraints and discretization puzzles in stochastic optimal control (MDL) slides
  2. Variational approaches in stochastic optimal control (PC) slides
  3. Probability constraints and stochastic viability (MDL) slides and more details on Advanced Course on Sustainable Optimization
  4. Dynamic consistency and probability constraints (JPC) slides
  5. Decomposition-coordination methods in stochastic optimal control (PC) slides
  6. Introduction to multi-agent decentralized optimization (Aditya Mahajan) slides

Computer practical works
(Pierre Carpentier, Jean-Philippe Chancelier, Michel De Lara)

TP1.
Information constraints discretization in a two-step model
TP2.
Dynamic programming for a single dam
TP3.
Decomposition-coordination methods for interconnected dams

3 Schedule

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).

4 Workshop Days

4.1 Research Workshop Day: Thursday 28 June 2012

The workshop consists of 7 talks, of 55 minutes each. All the talks will be given in English.

Schedule

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

Abstracts

Optimization Techniques in Statistical Estimation: Fusion of hard and soft information (Roger Wets, University of California, Davis)

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.

Dual quantization and dynamic programming / Quantification duale et programmation dynamique (Gilles Pages, Université Pierre et Marie Curie)

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.

Optimization of a liquefied natural gas portfolio by SDDP techniques (Frédéric Bonnans, INRIA and CMAP, École Polytechnique)

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.

Monte Carlo linear algebra: A review and recent results (Dimitri Bertsekas, MIT)

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 $ Cx=d$, using estimates $ C_k$ and $ d_k$ to $ C$ and $ d$, with $ C_k\to C$, $ d_k\to d$ as the number of samples $ k\to\infty$. We discuss simulation approaches for obtaining $ C_k$ and $ d_k$ 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 $ C$ is singular or nearly singular.

Optimistic optimization of a function without the knowledge of its smoothness (Rémi Munos, INRIA Lille)

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.

Performance bounds for Approximate Dynamic Programming in Large Scale Infinite-Horizon Optimal Control Problems (Bruno Scherrer, LORIA)

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.

Tropical methods in dynamic programming (Stéphane Gaubert, INRIA and CMAP, École Polytechnique)

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

4.2 Industrial Workshop Day: Thursday 5 July 2012

On Thursday 5 July 2012 (14h00--18h00), we will have two talks by industry professionals, and additional applied work talks

Schedule

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)

Abstracts

Large scale energy management: an overview on time and space decomposition (Anès Dallagi, EDF)

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 in the Airline Industry: an introduction to RM systems and OR techniques (Thierry Vanhaverbeke, Air France - KLM)

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.