Abstract

We introduce a class of algorithms, called Trajectory Following Dynamic Programming (TFDP) algorithms, that iteratively refines approximations of cost-to-go functions of multistage stochastic problems with independent random variables. This framework encompasses most variants of the Stochastic Dual Dynamic Programming algorithm. Leveraging a Lipschitz assumption on the expected cost-to-go functions, we provide a new convergence and complexity proof that allows random variables with non-finitely supported distributions. In particular, this leads to new complexity results for numerous known algorithms. Further, we detail how TFDP algorithms can be implemented without the finite support assumption, either through approximations or exact computations.

Author information

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

Maël Forcier

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

Keywords

  • Multistage stochastic programming
  • SDDP
  • duality

Mathematics Subject Classification

90C15, 90C25, 90C39, 90C06, 49M37, 93A15

References

  1. S. Ahmed, F. G. Cabral, B. F. P. da Costa: Stochastic Lipschitz dynamic programming, Math. Programming (2020) 1–39.https://doi.org/10.1007/s10107-020-01569-zGoogle Scholar
  2. M. Akian, J.-P. Chancelier, B. Tran: Tropical dynamic programming for Lipschitz multistage stochastic programming, arXiv: 2010.10619 (2020)Google Scholar
  3. P. Artzner, F. Delbaen, J.-M. Eber, D. Heath: Coherent measures of risk, Math. Finance 9/3 (1999) 203–228.https://doi.org/10.1111/1467-9965.00068Google Scholar
  4. P. Artzner, F. Delbaen, J.-M. Eber, D. Heath, H. Ku: Coherent multiperiod risk adjusted values and Bellman’s principle, Ann. Oper. Research 152/1 (2007) 5–22.https://doi.org/10.1007/s10479-006-0132-6Google Scholar
  5. T. Asamov, W. B. Powell: Regularized decomposition of high-dimensional multistage stochastic programs with markov uncertainty, SIAM J. Optimization 28/1 (2018) 575–595.https://doi.org/10.1137/16M1072231Google Scholar
  6. M. Bandarra, V. Guigues: Single cut and multicut stochastic dual dynamic programming with cut selection for multistage stochastic linear programs: convergence proof and numerical experiments, Comp. Manage. Sci. 18/2 (2021) 125–148.https://doi.org/10.1007/s10287-021-00387-8Google Scholar
  7. R. Baucke, A. Downward, G. Zakeri: A deterministic algorithm for solving multistage stochastic programming problems, Optimization Online (2017) 1–25.Google Scholar
  8. R. Baucke, A. Downward, G. Zakeri: A deterministic algorithm for solving multistage stochastic minimax dynamic programmes, Optimization Online (2018).Google Scholar
  9. F. Beltrán, E. C. Finardi, G. M. Fredo, W. de Oliveira: Improving the performance of the stochastic dual dynamic programming algorithm using Chebyshev centers, Optim. Eng. (2020) 1–22.https://doi.org/10.1007/s11081-020-09558-zGoogle Scholar
  10. J. R. Birge: Decomposition and partitioning methods for multistage stochastic linear programs, Oper. Research 33/5 (1985) 989–1007.https://doi.org/10.1287/opre.33.5.989Google Scholar
  11. J. R. Birge, R. J-B Wets: Designing approximation schemes for stochastic optimization problems, in particular for stochastic programs with recourse, Math. Program. Study 27 (1986) 54–102.https://doi.org/10.1007/BFb0121114Google Scholar
  12. M. Casey, S. Sen: The scenario generation algorithm for multistage stochastic linear programming, Math. Oper. Research 30/3 (2005) 615–631.https://doi.org/10.1287/moor.1050.0146Google Scholar
  13. S. Cerisola, J. M. Latorre, A. Ramos: Stochastic dual dynamic programming applied to nonconvex hydrothermal models, Eur. J. Oper. Research 218/3 (2012) 687–697.https://doi.org/10.1016/j.ejor.2011.11.040Google Scholar
  14. B. F. P. da Costa, V. Leclère: Dual SDDP for risk-averse multistage stochastic programs, Oper. Res. Letters 51/3 (2023) 332–337.https://doi.org/10.1016/j.orl.2023.04.001Google Scholar
  15. J. A. De Loera, J. Rambau, F. Santos: Triangulations Structures for Algorithms and Applications, Springer, Berlin (2010).https://doi.org/10.1007/978-3-642-12971-1Google Scholar
  16. A. Downward, O. Dowson, R. Baucke: Stochastic dual dynamic programming with stagewise-dependent objective uncertainty, Oper. Research Letters 48/1 (2020) 33–39.https://doi.org/10.1016/j.orl.2019.11.002Google Scholar
  17. O. Dowson: Applying Stochastic Optimisation to the New Zealand Dairy Industry, PhD thesis, University of Auckland (2018).Google Scholar
  18. O. Dowson, D. P. Morton, B. K. Pagnoncelli: Partially observable multistage stochastic programming, Oper. Research Letters 48/4 (2020) 505–512.https://doi.org/10.1016/j.orl.2020.06.005Google Scholar
  19. J. Dupačová: Applications of stochastic programming: Achievements and questions, Eur. J. Oper. Research 140/2 (2002) 281–290.https://doi.org/10.1016/S0377-2217(02)00070-XGoogle Scholar
  20. D. Duque, D. P. Morton: Distributionally robust stochastic dual dynamic programming, SIAM J. Optimization 30/4 (2020) 2841–2865.https://doi.org/10.1137/19M1309602Google Scholar
  21. N. C. P. Edirisinghe, W. T. Ziemba: Bounding the expectation of a saddle function with application to stochastic programming, Math. Oper. Research 19/2 (1994) 314–340.https://doi.org/10.1287/moor.19.2.314Google Scholar
  22. M. Forcier: Multistage Stochastic Optimization and Polyhedral Geometry, PhD thesis, École des Ponts, Marne-la-Vallée (2022).Google Scholar
  23. M. Forcier, S. Gaubert, V. Leclère: Exact quantization of multistage stochastic linear problems, arXiv: 2107.09566 (2021).Google Scholar
  24. M. Forcier, V. Leclère: Generalized adaptive partition-based method for two-stage stochastic linear programs: geometric oracle and analysis, Oper. Research Letters 50/5 (2022) 552–557.https://doi.org/10.1016/j.orl.2022.06.004Google Scholar
  25. K. Frauendorfer: Barycentric scenario trees in convex multistage stochastic programming, Math. Programming 75/2 (1996) 277–293.https://doi.org/10.1007/BF02592156Google Scholar
  26. H. Gassmann, W. T. Ziemba: Stochastic Programming: Applications in Finance, Energy, Planning and Logistics, World Scientific Series in Finance Vol. 4, World Scientific, Hackensack (2013).https://doi.org/10.1142/8497Google Scholar
  27. A. Georghiou, A. Tsoukalas, W. Wiesemann: Robust dual dynamic programming, Oper. Research 67/3 (2019) 813–830.https://doi.org/10.1287/opre.2018.1835Google Scholar
  28. P. Girardeau, V. Leclère, A. B. Philpott: On the convergence of decomposition methods for multistage stochastic convex programs, Math. Oper. Research 40/1 (2015) 130–145.https://doi.org/10.1287/moor.2014.0664Google Scholar
  29. A. Gjelsvik, B. Mo, A. Haugstad: Long-and medium-term operations planning and stochastic modelling in hydro-dominated power systems based on stochastic dual dynamic programming, in: Handbook of Power Systems I, S. Rebennack et al. (eds.), Springer, Berlin (2010) 33–55.https://doi.org/10.1007/978-3-642-02493-1_2Google Scholar
  30. V. Guigues: Convergence analysis of sampling-based decomposition methods for risk-averse multistage stochastic convex programs, SIAM J. Optimization 26/4 (2016) 2468–2494.https://doi.org/10.1137/140983136Google Scholar
  31. V. Guigues: Inexact cuts in stochastic dual dynamic programming, SIAM J. Optimization 30/1 (2020) 407–438.https://doi.org/10.1137/18M1211799Google Scholar
  32. V. Guigues, M. A. Lejeune, W. Tekaya: Regularized stochastic dual dynamic programming for convex nonlinear optimization problems, Optim. Eng. 21/3 (2020) 1133–1165.https://doi.org/10.1007/s11081-020-09511-0Google Scholar
  33. G. A. Hanasusanto, D. Kuhn, W. Wiesemann: A comment on “Computational complexity of stochastic programming problems”, Math. Programming 159/1-2 (2016) 557–569.https://doi.org/10.1007/s10107-015-0958-2Google Scholar
  34. T. Homem-de-Mello, V. L. De Matos, E. C. Finardi: Sampling strategies and stopping criteria for stochastic dual dynamic programming: a case study in long-term hydrothermal scheduling, Energy Systems 2/1 (2011) 1–31.https://doi.org/10.1007/s12667-011-0024-yGoogle Scholar
  35. P. Kall, J. Mayer: Stochastic Linear Programming, Springer, Berlin (1976).https://doi.org/10.1007/978-3-642-66252-2Google Scholar
  36. D. Kuhn: Generalized Bounds for Convex Multistage Stochastic Programs, Lecture Notes in Economics and Mathematical Systems 548, Springer, Berlin (2005).Google Scholar
  37. G. Lan: Complexity of stochastic dual dynamic programming, Math. Programming A 191/2 (2020) 717–754; A 194/1-2 (2022) 1187–1189.https://doi.org/10.1007/s10107-022-01798-4Google Scholar
  38. G. Laporte, F. V. Louveaux: The integer L-shaped method for stochastic integer programs with complete recourse, Oper. Research Letters 13/3 (1993) 133–142.https://doi.org/10.1016/0167-6377(93)90002-XGoogle Scholar
  39. V. Leclere, P. Carpentier, J.-P. Chancelier, A. Lenoir, F. Pacaud: Exact converging bounds for stochastic dual dynamic programming via fenchel duality, SIAM J. Optimization 30/2 (2020) 1223–1250.https://doi.org/10.1137/19M1258876Google Scholar
  40. N. Loehndorf: An empirical analysis of scenario generation methods for stochastic optimization, Eur. J. Oper. Research 255/1 (2016) 121–132.https://doi.org/10.1016/j.ejor.2016.05.021Google Scholar
  41. F. V. Louveaux: A solution method for multistage stochastic programs with recourse with application to an energy investment problem, Oper. Research 28/4 (1980) 889–902.https://doi.org/10.1287/opre.28.4.889Google Scholar
  42. M. E. P. Maceiral, D. D. J. Penna, A. L. Diniz, R. J. Pinto, A. C. G. Melo, C. V. Vasconcellos, C. B. Cruz: Twenty years of application of stochastic dual dynamic programming in official and agent studies in Brazil – main features and improvements on the NEWAVE model, in: 2018 Power Systems Computation Conference, IEEE (2018) 1–7.https://doi.org/10.23919/PSCC.2018.8442754Google Scholar
  43. F. Maggioni, E. Allevi, M. Bertocchi: Bounds in multistage linear stochastic programming, J. Optimization Theory Appl. 163/1 (2014) 200–229.https://doi.org/10.1007/s10957-013-0450-1Google Scholar
  44. F. Maggioni, G. Pflug: Guaranteed bounds for general non-discrete multistage risk-averse stochastic optimization programs, SIAM J. Optimization 29/1 (2019) 454–483.https://doi.org/10.1137/17M1140601Google Scholar
  45. J. Matousek, B. Gärtner: Understanding and Using Linear Programming, Springer, Berlin (2007).Google Scholar
  46. M. V. F. Pereira, L. M. V. G. Pinto: Multi-stage stochastic optimization applied to energy planning, Math. Programming 52/1-3 (1991) 359–375.https://doi.org/10.1007/BF01582895Google Scholar
  47. G. C. Pflug, A. Pichler: A distance for multistage stochastic optimization models, SIAM J. Optimization 22/1 (2012) 1–23.https://doi.org/10.1137/110825054Google Scholar
  48. A. Philpott, V. de Matos, E. Finardi: On solving multistage stochastic programs with coherent risk measures, Oper. Research 61/4 (2013) 957–970.https://doi.org/10.1287/opre.2013.1175Google Scholar
  49. A. B. Philpott, Z. Guan: On the convergence of stochastic dual dynamic programming and related methods, Oper. Research Letters 36/4 (2008) 450–455.https://doi.org/10.1016/j.orl.2008.01.013Google Scholar
  50. A. B. Philpott, F. Wahid, J. F. Bonnans: Midas: A mixed integer dynamic approximation scheme, Math. Programming 181/1 (2020) 19–50.https://doi.org/10.1007/s10107-019-01368-1Google Scholar
  51. C. Ramirez-Pico, E. Moreno: Generalized adaptive partition-based method for two-stage stochastic linear programs with fixed recourse, Math. Programming B 196/1-2 (2022) 755–774.https://doi.org/10.1007/s10107-020-01609-8Google Scholar
  52. R. T. Rockafellar, S. Uryasev: Optimization of conditional value-at-risk, J. Risk 2/3 (2000) 21–41.https://doi.org/10.21314/JOR.2000.038Google Scholar
  53. R. T. Rockafellar, R. J-B Wets: Scenarios and policy aggregation in optimization under uncertainty, Math. Oper. Research 16/1 (1991) 119–147.https://doi.org/10.1287/moor.16.1.119Google Scholar
  54. R. T. Rockafellar, R. J-B Wets: Variational Analysis, Grundlehren der Mathematischen Wissenschaften Vol. 317, Springer, Berlin (1998).https://doi.org/10.1007/978-3-642-02431-3Google Scholar
  55. J. O. Royset, R. J-B Wets: An Optimization Primer, Springer, Cham (2021).https://doi.org/10.1007/978-3-030-76275-9Google Scholar
  56. A. Shapiro: On complexity of multistage stochastic programs, Oper. Research Letters 34/1 (2006) 1–8.https://doi.org/10.1016/j.orl.2005.02.003Google Scholar
  57. A. Shapiro: Analysis of stochastic dual dynamic programming method, Eur. J. Oper. Research 209/1 (2011) 63–72.https://doi.org/10.1016/j.ejor.2010.08.007Google Scholar
  58. A. Shapiro, D. Dentcheva, A. Ruszczyński: Lectures on Stochastic Programming: Modeling and Theory, 2nd ed., MOS/SIAM Series on Optimization Vol. 16, Society for Industrial and Applied Mathematics, Philadelphia (2014).https://doi.org/10.1137/1.9781611973433Google Scholar
  59. A. Shapiro, L. Ding: Periodical multistage stochastic programs, SIAM J. Optimization 30/3 (2020) 2083–2102.https://doi.org/10.1137/19M129406XGoogle Scholar
  60. A. Shapiro, A. Nemirovski: On complexity of stochastic programming problems, in: Continuous Optimization. Current Trends and Modern Applications, V. Jeyakumar et al. (eds.), Springer, New York (2005) 111–146.https://doi.org/10.1007/0-387-26771-9_4Google Scholar
  61. A. Shapiro, W. Tekaya, J. P. da Costa, M. P. Soares: Risk neutral and risk averse stochastic dual dynamic programming method, European J. Oper. Research 224/2 (2013) 375–391.https://doi.org/10.1016/j.ejor.2012.08.022Google Scholar
  62. M. Siddig, Y. Song: Adaptive partition-based SDDP algorithms for multistage stochastic linear programming with fixed recourse, Comp. Optim. Appl. 81/1 (2022) 201–250.https://doi.org/10.1007/s10589-021-00323-1Google Scholar
  63. Y. Song, J. Luedtke: An adaptive partition-based approach for solving two-stage stochastic programs with fixed recourse, SIAM J. Optimization 25/3 (2015) 1344–1367.https://doi.org/10.1137/140967337Google Scholar
  64. B. Sturmfels, R. R. Thomas: Variation of cost functions in integer programming, Math. Programming 77/2 (1997) 357–387.https://doi.org/10.1007/BF02614622Google Scholar
  65. W. Van Ackooij, W. de Oliveira, Y. Song: On level regularization with normal solutions in decomposition methods for multistage stochastic programming problems, Comp. Optim. Appl. 74/1 (2019) 1–42.https://doi.org/10.1007/s10589-019-00104-xGoogle Scholar
  66. R. M. Van Slyke, R. Wets: L-shaped linear programs with applications to optimal control and stochastic programming, SIAM J. Appl. Math. 17/4 (1969) 638–663.https://doi.org/10.1137/0117061Google Scholar
  67. D. Walkup, R. J-B Wets: Lifting projections of convex polyhedra, Pacific J. Math. 28/2 (1969) 465–475.https://doi.org/10.2140/pjm.1969.28.465Google Scholar
  68. S. W. Wallace, W. T. Ziemba (eds.): Applications of Stochastic Programming, MPS-SIAM Series on Optimization 5, Society for Industrial and Applied Mathematics, Philadelphia (2005).https://doi.org/10.1137/1.9780898718799Google Scholar
  69. S. Zhang, X. A. Sun: Stochastic dual dynamic programming for multistage stochastic mixed-integer nonlinear optimization, Math. Programming 196/1 (2022) 935–985.https://doi.org/10.1007/s10107-022-01875-8Google Scholar
  70. S. Zhang, X. A. Sun: On distributionally robust multistage convex optimization: new algorithms and complexity analysis, arXiv: 2010.06759 (2020).Google Scholar
  71. J. Zou, S. Ahmed, X. A. Sun: Stochastic dual dynamic integer programming, Math. Programming 175/1 (2019) 461–502.https://doi.org/10.1007/s10107-018-1249-5Google Scholar

Suggested citation

M. Forcier, V. Leclère. “Trajectory Following Dynamic Programming Algorithms without Finite Support Assumptions.” Journal of Convex Analysis 30 (2023), No. 3, 951–999. https://doi.org/10.68381/jca30045

Download BibTeXPublished by Heldermann Verlag.

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