Maestría en Ingeniería Industrial
Escuela Colombiana de Ingeniería Julio Garavito (ECIJG),
Bogotá, Colombia
5-13 de Agosto de 2016
Optimización estocástica dinámica.
Asignación óptima de energía.
Michel DE LARA, CERMICS-École des Ponts ParisTech
Elegibilidad / Requisitos previos.
- Habilidades en matemáticas. Habilidades en programación informática.
- Optimización continua: programación lineal, convexidad, dualidad,
condiciones de optimalidad de primer orden. [Ber96]
- Cálculo de probabilidades: espacio de probabilidad, probabilidad,
variables aleatorias, independencia, esperanza condicional.
[Fel68,Bre93,Pit93]
Aprendizajes al final del curso.
Después del curso el estudiante debería ser capaz a
- diseñar modelos matemáticos para el almacenaje de energía
y la entrega de energías renovables, y formular un problema de minimización de costos,
- usar el software científico Scicoslab y numéricamente solucionar
problemas de pequeña escala.
Contenido principal del curso.
El curso mezcla sesiones teóricas, ejercicios de modelamiento y
sesiones de programación informática.
En la introducción, presentamos casos de manejo de micro-redes
y de central eléctrica virtual
-- donde la cuestión de almacenaje eléctrico es planteada,
debido a las necesidades de cumplir con una demanda que varía
y de incorporar energías renovables intermitentes y sumamente variables.
Mostramos como tales problemas pueden ser formulados como
problemas de optimización dinámicos estocásticos.
En un problema de optimización determinista, los valores de todos los
parámetros se suponen conocidos. ¿Qué pasa cuando este no es el caso?
¿Y cuándo algunos valores son revelados durante las etapas de decisión?
Presentamos la optimización estocástica, al mismo tiempo como un marco para
formular problemas bajo la incertidumbre, y como métodos de solucionarlos
según la formulación. Precisamente, presentamos la
programación estocástica
en dos etapas (y la resolución sobre un árbol de decisión) y el
control estocástico en tiempo discreto
(y la resolución por programación estocástica dinámica).
Dependiendo de los participantes, puedo enfocar más en la teoría
o puedo hacer más ejercicios y trabajos prácticos en la computadora.
Si tenemos tiempo, lo dedicamos al algoritmo SDDP,
extensamente usado en el mundo de la energía,
que mezcla programación dinámico y método de planos de corte.
El acercamiento de SDDP parece sobre todo adaptado a cuestiones
de manejo de micro-redes.
Ejercicios de modelamiento y sesiones de programación informática abordan
cuestiones como
el despacho óptimo económico de unidades de producción de energía,
el problema de optimización de almacenaje/entrega para regular
una fuente intermitente y variable de energía,
el manejo óptimo de una presa con entradas estocásticas de agua,
manejo óptimo de baterías con entradas de energía renovable.
Exámen y requisitos para el grado final.
Al final de cada sesión de programación informática,
el estudiante produce un informe,
que recibe una nota después de la evaluación.
El exámen final, la presencia y la participación
también contribuyen al grado final.
Profesor.
Michel De Lara (Cermics-École des Ponts ParisTech)
Página web profesional
Página web del curso
Página web de la Maestría en Ingeniería Industrial de la
Escuela Colombiana de Ingeniería Julio Garavito, Bogotá, Colombia
Recogidas y ejercicios en optimización continua:
convexidad, dualidad, condiciones de optimalidad de primer orden.
[Ber96]
- 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.
Recogidas y ejercicios en cálculo de probabilidades:
espacio de probabilidad, probabilidad, variables aleatorias,
distribución de probabilidad de una variable aleatoria, función indicador de
un conjunto, esperanza matemática de una variable aleatoria,
independencia de variables aleatorias, ley de los grandes números.
[Fel68,Bre93,Pit93]
Para introducir el curso, presentamos ejemplos de manejo de micro-redes,
y de central eléctrica virtual,
que pueden formularse por la optimización dinámica estocástica:
- trabajo hecho por Tristan Rigaut (Cermics-ENPC y Efficacity)
Optimización de energía y control de clima en una micro-red
de estación de metro.
diapositivas
- trabajo hecho por François Pacaud (Cermics-ENPC y Efficacity)
Dimensionamiento optimo e integración de
cogeneración de electricidad y calor con almacenaje termal y eléctrico
en un alojamiento individual residencial.
diapositivas
- trabajo hecho por Francis Sourd (Sun'R) y Ariel Waserhole (Sun'R)
``SunHydro: la optimización estocástica, el núcleo de un proyecto colaborativo''
diapositivas
Introducción al software científico Scicoslab.
sesión en computador
Programación estocástica en dos etapas
(caso lineal y cuadrático sobre un árbol).
[SDR09,KW12]
diapositivas
Dimensionamiento de reservas para el equilibrio en un mercado eléctrico.
sesión en computador
Programación estocástica en dos etapas
(caso cuadrático y lineal sobre un peine, descomposición por escenarios).
[RW91]
diapositivas
Dimensionamiento de reservas para el equilibrio en un mercado eléctrico.
sesión en computador
Modelos dinámicos de almacenaje (modelos de batería, modelos de presa).
Control óptimo de sistemas estocásticos dinámicos secuenciales.
Programación estocástica dinámica. Maldición de la dimensionalidad.
[Bel57,Put94,Ber00,Whi82,CCCD15]
diapositivas
La ecuación de Bellman como un modo de calcular controles en línea.
[Ber05,PM15a,PM15b,Pow14].
Interacción entre optimización y modelos de evaluación.
Ejercicio sobre modelamiento de una presa.
Problemas de inventario.
Control estocástico óptimo con gastos convexos y dinámica lineal.
Presentación del Stochastic Dual Dynamic Programming (SDDP)
algoritmo.
diapositivas
Exámen sobre programación estocástica dinámica.
- 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.
- 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.
- 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.