Exact converging bounds for Stochastic Dual Dynamic Programming via Fenchel duality
| Autor: | Pierre Carpentier, Jean-Philippe Chancelier, François Pacaud, Arnaud Lenoir, Vincent Leclère |
|---|---|
| Přispěvatelé: | Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique (CERMICS), École des Ponts ParisTech (ENPC), Optimisation et commande (OC), Unité de Mathématiques Appliquées (UMA), École Nationale Supérieure de Techniques Avancées (ENSTA Paris)-École Nationale Supérieure de Techniques Avancées (ENSTA Paris), EDF R&D (EDF R&D), EDF (EDF), ITE EFFICACITY, parent |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Stochastic control
Mathematical optimization 021103 operations research Optimization problem Monte Carlo method 0211 other engineering and technologies Regular polygon 010103 numerical & computational mathematics 02 engineering and technology 01 natural sciences Upper and lower bounds Regularization (mathematics) Stochastic programming Theoretical Computer Science Dynamic programming [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC] 0101 mathematics Software Mathematics |
| Zdroj: | SIAM Journal on Optimization SIAM Journal on Optimization, Society for Industrial and Applied Mathematics, 2020, 30 (2), pp.1223-1250. ⟨10.1137/19M1258876⟩ |
| ISSN: | 1052-6234 |
| Popis: | International audience; The Stochastic Dual Dynamic Programming (SDDP) algorithm has become one of the main tools to address convex multistage stochastic optimal control problem. Recently a large amount of work has been devoted to improve the convergence speed of the algorithm through cut-selection and regularization, or to extend the field of applications to non-linear, integer or risk-averse problems. However one of the main downside of the algorithm remains the difficulty to give an upper bound of the optimal value, usually estimated through Monte Carlo methods and therefore difficult to use in the algorithm stopping criterion. In this paper we present a dual SDDP algorithm that yields a converging exact upper bound for the optimal value of the optimization problem. Incidently we show how to compute an alternative control policy based on an inner approximation of Bellman value functions instead of the outer approximation given by the standard SDDP algorithm. We illustrate the approach on an energy production problem involving zones of production and transportation links between the zones. The numerical experiments we carry out on this example show the effectiveness of the method. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|