Abstract

Multistage stochastic optimization problems are oftentimes formulated informally in a pathwise way. These formulations are appealing in a discrete setting and suitable when addressing computational challenges, for example. But the pathwise problem statement does not allow an analysis with mathematical rigor and is therefore not appropriate. R. T. Rockafellar and R. J.-B. Wets [Nonanticipativity and L1L^1-martingales in stochastic optimization problems, Math. Programming Study 6 (1976) 170–187] address the fundamental measurability concern of the value functions in the case of convex costs and constraints. This paper resumes these foundations. The contribution is a proof that there exist measurable versions of intermediate value functions, which reveals regularity in addition. Our proof builds on the Kolmogorov continuity theorem. It is demonstrated that verification theorems allow stating traditional problem specifications in the novel setting with mathematical rigor. Further, we provide dynamic equations for the general problem. The problem classes covered include Markov decision processes, reinforcement learning and stochastic dual dynamic programming.

Author information

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

Paul Dommel

Faculty of Mathematics, University of Technology, Chemnitz, Germany

Keywords

  • Multistage stochastic optimization
  • stochastic processes
  • measurability

Mathematics Subject Classification

90C08, 90C15, 60G07

References

  1. R. E. Bellman: Dynamic Programming, Princeton University Press, Princton (1957).Google Scholar
  2. R. E. Bellman: Adaptive Control Processes, Princeton Legacy Library 2045, Princeton University Press (1961).https://doi.org/10.1515/9781400874668Google Scholar
  3. D. Bertsekas: Dynamic Programming and Optimal Control, Athena Scientific, Belmont (2012).Google Scholar
  4. D. Bertsekas, S. E. Shreve: Stochastic Optimal Control: the Discrete Time Case, Academic Press, New York (1978).Google Scholar
  5. P. Carpentier, J.-P. Chancelier, G. Cohen, M. De Lara: Stochastic Multi-Stage Optimization, Springer, Cham (2015).https://doi.org/10.1007/978-3-319-18138-7Google Scholar
  6. P. Carpentier, J.-P. Chancelier, G. Cohen, M. De Lara, P. Girardeau: Dynamic consistency For stochastic optimal control problems, Ann. Oper. Res. 200/1 (2012) 247–263.https://doi.org/10.1007/s10479-011-1027-8Google Scholar
  7. N. Dunford, J. T. Schwartz: Linear Operators. Part I: General Theory, Wiley-Interscience, New York (1957).Google Scholar
  8. 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
  9. E. A. Feinberg: On measurability and representation of strategic measures in Markov decision processes, in: Statistics, Probability and Game Theory, IMS Lecture Notes and Monograph Series Vol. 30 Institute of Mathematical Statistics (1996) 29–43.https://doi.org/10.1214/lnms/1215453563Google Scholar
  10. W. H. Fleming, H. M. Soner: Controlled Markov Processes and Viscosity Solutions, 2nd ed., Springer, New York (2006).Google Scholar
  11. S.-E. Fleten, E. Haugom, A. Pichler, C. J. Ullrich: Structural estimation of switching costs for peaking power plants, Eur. J. Oper. Res. 285/1 (2020) 23–33.https://doi.org/10.1016/j.ejor.2019.03.031Google Scholar
  12. H. Föllmer, A. Schied: Stochastic Finance: An Introduction in Discrete Time, De Gruyter Studies in Mathematics 27, De Gruyter, Berlin (2004.https://doi.org/10.1515/9783110212075Google Scholar
  13. P. Girardeau, V. Leclère, A. B. Philpott: On the convergence of decomposition methods for multistage stochastic convex programs, Math. Oper. Res. 40/1 (2014) 1–16.https://doi.org/10.1287/moor.2014.0664Google Scholar
  14. K. Gowrisankaran: Measurability of functions in product spaces, Proc. Amer. Math. Soc. 31 (1972) 485–488.https://doi.org/10.1090/S0002-9939-1972-0291403-XGoogle Scholar
  15. O. Kallenberg: Foundations of Modern Probability, Springer, New York (2002).https://doi.org/10.1007/978-1-4757-4015-8Google Scholar
  16. I. Karatzas, S. E. Shreve: Methods of Mathematical Finance, Applications of Mathematics Vol. 39, Springer, Berlin (1998).https://doi.org/10.1007/b98840Google Scholar
  17. A. Klenke: Probability Theory, Springer, London (2014).https://doi.org/10.1007/978-1-4471-5361-0Google Scholar
  18. G. Lan, Z. Zhou: Dynamic stochastic approximation for multi-stage stochastic optimization, Math. Programming Ser. A 187/1-2 (2021) 487–532.https://doi.org/10.1007/s10107-020-01489-yGoogle Scholar
  19. N. Löhndorf, D. Wozabal, S. Minner: Optimizing trading decisions for hydro storage systems using approximate dual dynamic programming, Oper. Res. 61/4 (2013) 810–823.https://doi.org/10.1287/opre.2013.1182Google Scholar
  20. 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
  21. P. Olsen: Multistage stochastic programming with recourse as mathematical programming in an lp space, SIAM J. Control Optimization 3 (1976) 528–537.https://doi.org/10.1137/0314035Google Scholar
  22. P. Olsen: Discretizations of multistage stochastic programming problems, Math. Programming Study 6 (1976) 111–124.https://doi.org/10.1007/BFb0120747Google Scholar
  23. P. Olsen: When is a multistage stochastic programming problem well-defined?, SIAM J. Control Optimization 14/3 (1976) 518–527.https://doi.org/10.1137/0314034Google Scholar
  24. T. Pennanen, A.-P. Perkkiö: Dynamic programming in convex stochastic optimization, J. Convex Analysis 30/4 (2023) 1241–1283.https://doi.org/10.68381/jca30056Google Scholar
  25. T. Pennanen, A.-P. Perkkiö: Convex stochastic optimization, preprint (2023).https://doi.org/10.1007/978-3-031-76432-5Google Scholar
  26. 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
  27. G. Pflug, A. Pichler: Multistage Stochastic Optimization, Springer Series in Operations Research and Financial Engineering, Springer, Cham (2014).https://doi.org/10.1007/978-3-319-08843-3Google Scholar
  28. A. B. Philpott, Z. Guan: On the convergence of stochastic dual dynamic programming and related methods, Oper. Res. Letters 36/4 (2008) 450–455.https://doi.org/10.1016/j.orl.2008.01.013Google Scholar
  29. A. B. Philpott, V. L. de Matos, E. Finardi: On solving multistage stochastic programs with coherent risk measures, Oper. Res. 61/4 (2013) 957–970.https://doi.org/10.1287/opre.2013.1175Google Scholar
  30. A. Pichler, R. P. Liu, A. Shapiro: Risk-averse stochastic programming: Time consistency and optimal stopping, Oper. Res. 70/4 (2022) 2439–2455.https://doi.org/10.1287/opre.2021.2120Google Scholar
  31. A. Pichler, A. Shapiro: Mathematical foundations of distributionally robust multistage optimization, SIAM J. Optimization 31/4 (2021) 3044–3067.https://doi.org/10.1137/21M1390517Google Scholar
  32. R. T. Rockafellar: Integral functionals, normal integrands and measurable selections, in: Nonlinear Operators and the Calculus of Variations, Summer School Bruxelles 1975, Lecture Notes in Mathematics 543, Springer, Berlin (1976) 157–207.https://doi.org/10.1007/BFb0079944Google Scholar
  33. R. T. Rockafellar, R. J.-B. Wets: Nonanticipativity and L1 -martingales in stochastic optimization problems, Math. Programming Study 6 (1976) 170–187.https://doi.org/10.1007/BFb0120750Google Scholar
  34. R. T. Rockafellar, R. J.-B. Wets: On the interchange of subdifferentiation and conditional expectations for convex functionals, Stochastics 7/3 (1982) 173–182.https://doi.org/10.1080/17442508208833217Google Scholar
  35. R. T. Rockafellar, R. J.-B. Wets: Variational Analysis, Grundlehren der Mathematischen Wissenschaften 317, Springer, Berlin (1998).https://doi.org/10.1007/978-3-642-02431-3Google Scholar
  36. W. Römisch, V. Guigues: Sampling-based decomposition methods for multistage stochastic programs based on extended polyhedral risk measures, SIAM J. Optimization 22/2 (2012) 286–312.https://doi.org/10.1137/100811696Google Scholar
  37. A. Ruszczyński: Risk-averse dynamic programming for Markov decision processes, Math. Programming Ser. B 125 (2010) 235–261.https://doi.org/10.1007/s10107-010-0393-3Google Scholar
  38. A. Shapiro: Analysis of stochastic dual dynamic programming method, Eur. J. Oper. Res. 209/1 (2010) 63–72.https://doi.org/10.1016/j.ejor.2010.08.007Google Scholar
  39. A. Shapiro: Time consistency of dynamic risk measures, Oper. Res. Letters 40/6 (2012) 436–439.https://doi.org/10.1016/j.orl.2012.08.007Google Scholar
  40. A. Shapiro: Interchangeability principle and dynamic equations in risk averse stochastic programming, Oper. Res. Letters 45/4 (2017) 377–381.https://doi.org/10.1016/j.orl.2017.05.008Google Scholar
  41. A. Shapiro: Tutorial on risk neutral, distributionally robust and risk averse multistage stochastic programming, Eur. J. Oper. Res. 288/1 (2021) 1–13.https://doi.org/10.1016/j.ejor.2020.03.065Google Scholar
  42. A. Shapiro, D. Dentcheva, A. Ruszczyński: Lectures on Stochastic Programming. Modeling and Theory, 3rd ed., MOS-SIAM Series on Optimization Vol. 28, Society for Industrial and Applied Mathematics, Philadelphia (2021).Google Scholar
  43. A. Shapiro, W. Tekaya, J. P. da Costa, M. Pereira Soares: Risk neutral and risk averse stochastic dual dynamic programming method, Eur. J. Oper. Res. 224/2 (2013) 375–391.https://doi.org/10.1016/j.ejor.2012.08.022Google Scholar
  44. A. N. Shiryaev: Probability, Springer, New York (1996).https://doi.org/10.1007/978-1-4757-2539-1Google Scholar
  45. A. W. van der Vaart, J. A. Wellner: Weak Convergence and Empirical Processes. With Applications to Statistics, Springer Series in Statistics, Springer, New York (1996).https://doi.org/10.1007/978-1-4757-2545-2Google Scholar
  46. J. Zhen, D. Kuhn, W. Wiesemann: Mathematical foundations of robust and distributionally robust optimization, arXiv: 2105.00760 (2021).Google Scholar

Suggested citation

P. Dommel, A. Pichler. “Dynamic Programming For Data Independent Decision Sets.” Journal of Convex Analysis 30 (2023), No. 3, 897–916. https://doi.org/10.68381/jca30042

Download BibTeXPublished by Heldermann Verlag.

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