Abstract

Multistage stochastic optimization problems are, by essence, complex as their solutions are functions of both stages and uncertainties. Their large scale nature makes decomposition methods appealing, like dynamic programming which is a sequential decomposition using a state variable defined at all stages. By contrast, in this paper we introduce the notion of state reduction by time blocks, that is, at stages that are not necessarily all the original stages. Then, we prove a dynamic programming equation with value functions that are functions of a state only at some stages. This equation crosses over time blocks, but involves a dynamic optimization inside each block. We illustrate our contribution by showing its potential in three applications in multistage stochastic optimization: mixing dynamic programming and stochastic programming, two-time-scale optimization problems, decision-hazard-decision optimization problems.

Author information

Contact details are reproduced from the original publication and may be historical.

Jean-Philippe Chancelier

CERMICS, Ecole des Ponts ParisTech, Marne-la-Vallée, France

Michel De Lara

CERMICS, Ecole des Ponts ParisTech, Marne-la-Vallée, France

Thomas Martin

CERMICS, Ecole des Ponts ParisTech, Marne-la-Vallée, France

Tristan Rigaut

Efficacity, Marne-la-Vallée, France

Keywords

  • Multistage stochastic optimization
  • dynamic programming
  • time scales
  • time block decomposition
  • decision-hazard-decision

Mathematics Subject Classification

60J05 90C15 90C39 90C06 49M27

References

  1. K. Barty, P. Carpentier, P. Girardeau: Decomposition of large-scale stochastic optimal control problems, RAIRO Oper. Res. 44/3 (2010) 167–183.https://doi.org/10.1051/ro/2010013Google Scholar
  2. R. E. Bellman: Dynamic Programming, Princeton University Press, Princeton (1957).Google Scholar
  3. D. P. Bertsekas, S. E. Shreve: Stochastic Optimal Control: The Discrete-Time Case, Athena Scientific, Belmont (1996).Google Scholar
  4. J. R. Birge: Aggregation bounds in stochastic linear programming, Math. Programming 31 (1985) 25–41.https://doi.org/10.1007/BF02591859Google Scholar
  5. P. Carpentier, J.-P. Chancelier, G. Cohen, M. De Lara: Stochastic Multi-Stage Optimization. At the Crossroads between Discrete Time Stochastic Control and Stochastic Programming, Springer, Berlin (2015).https://doi.org/10.1007/978-3-319-18138-7Google Scholar
  6. P. Carpentier, J.-P. Chancelier, M. De Lara, T. Martin, T. Rigaut: Time Block Decomposition of Multistage Stochastic Optimization Problems, preprint hal-01757113 (2023).https://doi.org/10.68381/jca30034Google Scholar
  7. P. Carpentier, J.-P. Chancelier, M. De Lara, F. Pacaud: Mixed spatial and temporal decompositions for large-scale multistage stochastic optimization problems, J. Optim. Theory Appl. 186/3 (2020) 985–1005.https://doi.org/10.1007/s10957-020-01733-7Google Scholar
  8. B. Cheng, W. B. Powell: Co-optimizing battery storage for the frequency regulation and energy arbitrage using multi-scale dynamic programming, IEEE Trans. Smart Grid 9/3 (2016) 1997–2005.https://doi.org/10.1109/TSG.2016.2605141Google Scholar
  9. I. V. Evstigneev: Measurable selection and dynamic programming, Math. Oper. Res. 1/3 (1976) 267–272.https://doi.org/10.1287/moor.1.3.267Google Scholar
  10. M. Glanzer, G. Ch. Pflug: Multiscale stochastic optimization: modeling aspects and scenario generation, Comp. Optimization Appl. 75/1 (2020) 1–34.https://doi.org/10.1007/s10589-019-00135-4Google Scholar
  11. O. Hernández-Lerma, J.-B. Lasserre: Discrete-Time Markov Control Processes: Basic Optimality Criteria, Stochastic Modelling and Applied Probability Vol. 30, Springer, New York (1996).https://doi.org/10.1007/978-1-4612-0729-0Google Scholar
  12. M. Kaut, K. T. Midthun, A. S. Werner, A. Tomasgard, L. Hellemo, M. Fodstad: Multi-horizon stochastic programming, Comp. Management Sci. 11/1 (2014) 179–193.https://doi.org/10.1007/s10287-013-0182-6Google Scholar
  13. D. Kuhn: Aggregation and discretization in multistage stochastic programming, Math. Programming 113 (2008) 61–94.https://doi.org/10.1007/s10107-006-0048-6Google Scholar
  14. T. Martin: Stochastic Optimization for the Procurement of Crude Oil in Refineries, PhD Thesis, École des Ponts ParisTech, Paris (2021).Google Scholar
  15. R. Porteiro, A. Ferragut, F. Paganini: Towards multi-timescale energy provisioning using stochastic dual dynamic programming, in: IEEE 9th Power, Instrumentation and Measurement Meeting (EPIM) (2018) 1–6.https://doi.org/10.1109/EPIM.2018.8756380Google Scholar
  16. M. L. Puterman: Markov Decision Processes, Wiley, New York (1994).https://doi.org/10.1002/9780470316887Google Scholar
  17. R. T. Rockafellar, R. J-B Wets: Scenarios and policy aggregation in optimization under uncertainty, Math. Oper. Res. 16/1 (1991) 119–147.https://doi.org/10.1287/moor.16.1.119Google Scholar
  18. A. Ruszczyński: Decomposition methods, in: Stochastic Programming, Handbooks in Operations Research and Management Science Vol 10, Elsevier, Amsterdam (2003) 141–211.https://doi.org/10.1016/S0927-0507(03)10003-5Google Scholar
  19. A. Shapiro, D. Dentcheva, A. Ruszczynski: Lectures on Stochastic Programming: Modeling and Theory, MPS/SIAM Series on Optimization Vol. 9, Philadelphia (2009).https://doi.org/10.1137/1.9780898718751Google Scholar
  20. A. Shapiro, L. Ding: Periodical multistage stochastic programs, SIAM J. Optimization 30/3 (2020) 2083–2102.https://doi.org/10.1137/19M129406XGoogle Scholar
  21. A. Street, D. Valladao, A. Lawson, A. Velloso: Assessing the cost of the hazard-decision simplification in multistage stochastic hydrothermal scheduling, Applied Energy 280 (2020), art. no. 115939.https://doi.org/10.1016/j.apenergy.2020.115939Google Scholar
  22. J. Subramanian, A. Mahajan: Approximate information state for partially observed systems, in: IEEE 58th Conference on Decision and Control (CDC) (2019) 1629–1636.https://doi.org/10.1109/CDC40024.2019.9029898Google Scholar
  23. P. Whittle: Optimization over Time. Vol. 1: Dynamic Programming and Stochastic Control, Wiley, New York (1982).Google Scholar
  24. H. S. Witsenhausen: A standard form for sequential stochastic control, Math. Systems Theory 7/1 (1973) 5–11.https://doi.org/10.1007/BF01824800Google Scholar
  25. S. E. Wright: Primal-dual aggregation and disaggregation for stochastic linear programs, Math. Oper. Res. 19/4 (1994) 893–908.https://doi.org/10.1287/moor.19.4.893Google Scholar
  26. S. Yüksel: A universal dynamic program and refined existence results for decentralized stochastic control, SIAM J. Control Optim. 58/5 (2020) 2711–2739.https://doi.org/10.1137/18M1221382Google Scholar

Suggested citation

P. Carpentier, J.-P. Chancelier, M. De Lara, T. Martin, T. Rigaut. “Time Block Decomposition of Multistage Stochastic Optimization Problems.” Journal of Convex Analysis 30 (2023), No. 2, 627–658. https://doi.org/10.68381/jca30034

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2023. Rights now held by Banach Press LLC.