{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T17:13:18Z","timestamp":1775149998333,"version":"3.50.1"},"reference-count":77,"publisher":"Emerald","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,5,22]]},"abstract":"<jats:p>Optimization problems involving sequential decisions in a stochastic environment were studied in Stochastic Programming (SP), Stochastic Optimal Control (SOC) and Markov Decision Processes (MDP). In this monograph, we mainly concentrate on SP and SOC modeling approaches. In these frameworks, there are natural situations when the considered problems are convex. The classical approach to sequential optimization is based on dynamic programming. It has the problem of the so-called \u201ccurse of dimensionality\u201d, in that its computational complexity increases exponentially with respect to the dimension of state variables. Recent progress in solving convex multistage stochastic problems is based on cutting plane approximations of the cost-to-go (value) functions of dynamic programming equations. Cutting plane type algorithms in dynamical settings is one of the main topics of this monograph. We also discuss stochastic approximation type methods applied to multistage stochastic optimization problems. From the computational complexity point of view, these two types of methods seem to be complementary to each other. Cutting plane type methods can handle multistage problems with a large number of stages but a relatively smaller number of state (decision) variables. On the other hand, stochastic approximation type methods can only deal with a small number of stages but a large number of decision variables.<\/jats:p>","DOI":"10.1561\/2400000044","type":"journal-article","created":{"date-parts":[[2024,5,22]],"date-time":"2024-05-22T06:02:53Z","timestamp":1716357773000},"page":"63-144","source":"Crossref","is-referenced-by-count":3,"title":["Numerical Methods for Convex Multistage Stochastic Optimization"],"prefix":"10.1561","volume":"6","author":[{"given":"Guanghui","family":"Lan","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology ,","place":["USA"]}]},{"given":"Alexander","family":"Shapiro","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology ,","place":["USA"]}]}],"member":"140","published-online":{"date-parts":[[2024,5,22]]},"reference":[{"key":"2026033014424387400_ref001","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1111\/1467-9965.00068","article-title":"Coherent measures of risk","volume":"9","author":"Artzner","year":"1999","journal-title":"Mathematical Finance"},{"key":"2026033014424387400_ref002","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1111\/j.2517-6161.1955.tb00191.x","article-title":"On minimizing a convex function subject to linear inequalities","volume":"17","author":"Beale","year":"1955","journal-title":"Journal of the Royal Statistical Society, Series B"},{"key":"2026033014424387400_ref003","volume-title":"Dynamic Programming","author":"Bellman","year":"1957"},{"key":"2026033014424387400_ref004","volume-title":"Stochastic Optimal Control, The Discrete Time Case","author":"Bertsekas","year":"1978"},{"key":"2026033014424387400_ref005","doi-asserted-by":"crossref","first-page":"989","DOI":"10.1287\/opre.33.5.989","article-title":"Decomposition and partitioning methods for multistage stochastic linear programs","volume":"33","author":"Birge","year":"1985","journal-title":"Operations Research"},{"key":"2026033014424387400_ref006","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4614-0237-4","volume-title":"Introduction to Stochastic Programming","author":"Birge","year":"2011","edition":"2nd"},{"key":"2026033014424387400_ref007","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/s10479-011-0973-5","article-title":"Energy contracts management by stochastic programming techniques","volume":"200","author":"Bonnans","year":"2012","journal-title":"Annals of Operations Research"},{"key":"2026033014424387400_ref008","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1394-9","volume-title":"Perturbation Analysis of Optimization Problems","author":"Bonnans","year":"2000"},{"key":"2026033014424387400_ref009","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1016\/j.orl.2023.04.001","article-title":"Dual SDDP for risk-averse multistage stochastic programs","volume":"51","author":"da Costa","year":"2023","journal-title":"Operations Research Letters"},{"key":"2026033014424387400_ref010","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1287\/mnsc.1.3-4.197","article-title":"Linear programming under uncertainty","volume":"1","author":"Dantzig","year":"1955","journal-title":"Management Science"},{"key":"2026033014424387400_ref011","unstructured":"L.\n              Ding\n            , S.Ahmed, and A.Shapiro, \u201cA python package for multistage stochastic programming,\u201d Optimization online, 2019. URL: http:\/\/www.optimization-online.org\/DB_FILE\/2019\/05\/7199.pdf."},{"issue":"1","key":"2026033014424387400_ref012","article-title":"The abridged nested decomposition method for multistage stochastic linear programs with relatively complete recourse","volume":"1","author":"Donohue","year":"2006","journal-title":"Algorithmic Operations Research"},{"key":"2026033014424387400_ref013","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1287\/ijoc.2020.0987","article-title":"SDDP.jl: A Julia Package for Stochastic Dual Dynamic Programming","volume":"33","author":"Dowson","year":"2021","journal-title":"Informs Journal on Computing"},{"key":"2026033014424387400_ref014","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/s10107-005-0597-0","article-title":"Computational complexity of stochastic programming problems","volume":"106","author":"Dyer","year":"2006","journal-title":"Mathematical Programming"},{"key":"2026033014424387400_ref015","doi-asserted-by":"crossref","DOI":"10.1515\/9783110212075","volume-title":"Stochastic Finance: An Introduction in Discrete Time","author":"F\u00f6llmer","year":"2004","edition":"2nd"},{"key":"2026033014424387400_ref016","article-title":"Stochastic dual dynamic programming and its variants","volume-title":"Optimization online","author":"F\u00fcllner","year":"2021"},{"issue":"1","key":"2026033014424387400_ref017","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1137\/18M1230542","article-title":"A single timescale stochastic approximation method for nested stochastic optimization","volume":"30","author":"Ghadimi","year":"2020","journal-title":"SIAM Journal on Optimization"},{"key":"2026033014424387400_ref018","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1287\/moor.2014.0664","article-title":"On the convergence of decomposition methods for multistage stochastic convex programs","volume":"40","author":"Girardeau","year":"2016","journal-title":"Mathematics of Operations Research"},{"key":"2026033014424387400_ref019","doi-asserted-by":"crossref","DOI":"10.2139\/ssrn.3102988","volume-title":"Inexact cuts in deterministic and stochastic dual dynamic programming applied to linear optimization problems","author":"Guigues","year":"2018"},{"key":"2026033014424387400_ref020","volume-title":"Single cut and multicut sddp with cut selection for multistage stochastic linear programs: Convergence proof and numerical experiments","author":"Guigues","year":"2019"},{"key":"2026033014424387400_ref021","doi-asserted-by":"crossref","first-page":"752","DOI":"10.1016\/j.ejor.2022.11.051","article-title":"Duality and sensitivity analysis of multistage linear stochastic programs","volume":"308","author":"Guigues","year":"2023","journal-title":"European Journal of Operational Research"},{"key":"2026033014424387400_ref022","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1016\/j.orl.2023.05.002","article-title":"Risk-averse stochastic optimal control: An efficiently computable statistical upper bound","volume":"51","author":"Guigues","year":"2023","journal-title":"Operations Research Letters"},{"key":"2026033014424387400_ref023","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1007\/s10107-015-0958-2","article-title":"A comment on computational complexity of stochastic programming problems","volume":"159","author":"Hanasusanto","year":"2015","journal-title":"Mathematical Programming"},{"issue":"1","key":"2026033014424387400_ref024","first-page":"2","article-title":"Resa: A method for solving multistage stochastic linear programs","volume":"6","author":"Hindsberger","year":"2014","journal-title":"Journal of Applied Operational Research"},{"key":"2026033014424387400_ref025","volume-title":"Dual dynamic programming for stochastic programs over an infinite horizon","author":"Ju","year":"2023"},{"key":"2026033014424387400_ref026","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1137\/0108053","article-title":"The cutting-plane method for solving convex programs","volume":"8","author":"Kelley","year":"1960","journal-title":"Journal of the Society for Industrial and Applied Mathematics"},{"issue":"1","key":"2026033014424387400_ref027","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/s10107-010-0434-y","article-title":"An optimal method for stochastic composite optimization","volume":"133","author":"Lan","year":"2012","journal-title":"Mathematical Programming"},{"issue":"1","key":"2026033014424387400_ref028","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10107-013-0737-x","article-title":"Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization","volume":"149","author":"Lan","year":"2015","journal-title":"Mathematical Programming"},{"key":"2026033014424387400_ref029","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-030-39568-1","volume-title":"First-order and Stochastic Optimization Methods for Machine Learning","author":"Lan","year":"2020"},{"key":"2026033014424387400_ref030","volume-title":"Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes","author":"Lan","year":"2021"},{"key":"2026033014424387400_ref031","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1007\/s10107-020-01567-1","article-title":"Complexity of stochastic dual dynamic programming","volume":"191","author":"Lan","year":"2022","journal-title":"Mathematical Programming"},{"key":"2026033014424387400_ref032","volume-title":"Policy optimization over general state and action spaces","author":"Lan","year":"2022"},{"key":"2026033014424387400_ref033","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1007\/s10107-011-0442-6","article-title":"Validation analysis of mirror descent stochastic approximation method","volume":"134","author":"Lan","year":"2012","journal-title":"Mathematical Programming"},{"key":"2026033014424387400_ref034","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1007\/s10107-020-01489-y","article-title":"Dynamic stochastic approximation for multi-stage stochastic optimization","volume":"187","author":"Lan","year":"2021","journal-title":"Mathematical Programming"},{"key":"2026033014424387400_ref035","doi-asserted-by":"crossref","first-page":"1223","DOI":"10.1137\/19M1258876","article-title":"Exact converging bounds for Stochastic Dual Dynamic Programming via Fenchel duality.","volume":"30","author":"Lecl\u00e9re","year":"2020","journal-title":"SIAM J. Optimization"},{"key":"2026033014424387400_ref036","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF01585555","article-title":"New variants of bundle methods","volume":"69","author":"Lemar\u00e9chal","year":"1995","journal-title":"Mathematical Programming"},{"issue":"4","key":"2026033014424387400_ref037","doi-asserted-by":"crossref","first-page":"2955","DOI":"10.1137\/20M1327513","article-title":"A proximal bundle variant with optimal iteration-complexity for a large range of prox stepsizes","volume":"31","author":"Liang","year":"2021","journal-title":"SIAM Journal on Optimization"},{"key":"2026033014424387400_ref038","doi-asserted-by":"crossref","first-page":"650","DOI":"10.1016\/j.ejor.2018.08.001","article-title":"Modeling time-dependent randomness in stochastic dual dynamic programming","volume":"273","author":"L\u00f6hndorf","year":"2019","journal-title":"European Journal of Operational Research"},{"key":"2026033014424387400_ref039","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1287\/opre.2013.1182","article-title":"Optimizing trading decisions for hydro storage systems using approximate dual dynamic programming","volume":"61","author":"L\u00f6hndorf","year":"2013","journal-title":"Operational Research"},{"key":"2026033014424387400_ref040","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1016\/j.cam.2015.04.048","article-title":"Improving the performance of stochastic dual dynamic programming","volume":"290","author":"de Matos","year":"2015","journal-title":"Journal of Computational and Applied Mathematics"},{"key":"2026033014424387400_ref041","first-page":"560","volume-title":"Error bounds for approximate policy iteration","author":"Munos","year":"2003"},{"key":"2026033014424387400_ref042","first-page":"1006","volume-title":"Error bounds for approximate value iteration","author":"Munos","year":"2005"},{"key":"2026033014424387400_ref043","first-page":"815","article-title":"Finite-time bounds for fitted value iteration","volume-title":"Journal of Machine Learning Research","author":"Munos","year":"2008"},{"key":"2026033014424387400_ref044","doi-asserted-by":"crossref","first-page":"1574","DOI":"10.1137\/070704277","article-title":"Robust stochastic approximation approach to stochastic programming","volume":"19","author":"Nemirovski","year":"2009","journal-title":"SIAM J. Optimization"},{"key":"2026033014424387400_ref045","volume-title":"Problem complexity and method efficiency in optimization","author":"Nemirovski","year":"1983"},{"key":"2026033014424387400_ref046","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970791","volume-title":"Interior-Point Polynomial Algorithms in Convex Programming","author":"Nesterov","year":"1994"},{"issue":"1","key":"2026033014424387400_ref047","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/BF01582895","article-title":"Multi-stage stochastic optimization applied to energy planning","volume":"52","author":"Pereira","year":"1991","journal-title":"Mathematical programming"},{"key":"2026033014424387400_ref048","volume-title":"Probabilistic Constrained Optimization: Methodology and Applications, S. Uryasev","author":"Pflug","year":"2000"},{"key":"2026033014424387400_ref049","doi-asserted-by":"crossref","first-page":"957","DOI":"10.1287\/opre.2013.1175","article-title":"On solving multistage stochastic programs with coherent risk measures","volume":"61","author":"Philpott","year":"2013","journal-title":"Operations Research"},{"key":"2026033014424387400_ref050","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/s10107-019-01368-1","article-title":"A mixed integer dynamic approximation scheme","volume":"181","author":"Philpott","year":"2020","journal-title":"Mathematical Programming"},{"key":"2026033014424387400_ref051","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1016\/j.ejor.2011.10.056","article-title":"Dynamic sampling algorithms for multi-stage stochastic programs with risk aversion","volume":"218","author":"Philpott","year":"2012","journal-title":"European Journal of Operational Research"},{"issue":"4","key":"2026033014424387400_ref052","doi-asserted-by":"crossref","first-page":"957","DOI":"10.1287\/opre.2013.1175","article-title":"On solving multistage stochastic programs with coherent risk measures","volume":"61","author":"Philpott","year":"2013","journal-title":"Operations Research"},{"key":"2026033014424387400_ref053","doi-asserted-by":"crossref","first-page":"3044","DOI":"10.1137\/21M1390517","article-title":"Mathematical foundations of distributionally robust multistage optimization","volume":"31","author":"Pichler","year":"2021","journal-title":"SIAM J. Optimization"},{"key":"2026033014424387400_ref054","first-page":"98","article-title":"New stochastic approximation type procedures","volume":"7","author":"Polyak","year":"1990","journal-title":"Automat. i Telemekh."},{"key":"2026033014424387400_ref055","doi-asserted-by":"crossref","first-page":"838","DOI":"10.1137\/0330046","article-title":"Acceleration of stochastic approximation by averaging","volume":"30","author":"Polyak","year":"1992","journal-title":"SIAM J. Control and Optimization"},{"key":"2026033014424387400_ref056","doi-asserted-by":"crossref","DOI":"10.1002\/9781118029176","volume-title":"Approximate Dynamic Programming: Solving the Curses of Dimensionality","author":"Powell","year":"2011","edition":"2nd"},{"key":"2026033014424387400_ref057","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1214\/aoms\/1177729586","article-title":"A stochastic approximation method","volume":"22","author":"Robbins","year":"1951","journal-title":"Annals of Mathematical Statistics"},{"issue":"1","key":"2026033014424387400_ref058","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1287\/moor.16.1.119","article-title":"Scenarios and policy aggregation in optimization under uncertainty","volume":"16","author":"Rockafellar","year":"1991","journal-title":"Mathematics of Operations Research"},{"key":"2026033014424387400_ref059","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970524","volume-title":"Conjugate Duality and Optimization","author":"Rockafellar","year":"1974"},{"issue":"7","key":"2026033014424387400_ref060","doi-asserted-by":"crossref","first-page":"1443","DOI":"10.1016\/S0378-4266(02)00271-6","article-title":"Conditional value-at-risk for general loss distributions","volume":"26","author":"Rockafellar","year":"2002","journal-title":"J. of Banking and Finance"},{"key":"2026033014424387400_ref061","doi-asserted-by":"crossref","DOI":"10.1515\/9781400873173","volume-title":"Convex Analysis","author":"Rockafellar","year":"1970"},{"key":"2026033014424387400_ref062","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1287\/moor.1060.0204","article-title":"Conditional risk mappings","volume":"31","author":"Ruszczy\u0144ski","year":"2006","journal-title":"Mathematics of Operations Research"},{"key":"2026033014424387400_ref063","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1287\/moor.1050.0186","article-title":"Optimization of convex risk functions","volume":"31","author":"Ruszczy\u0144ski","year":"2006","journal-title":"Mathematics of Operations Research"},{"key":"2026033014424387400_ref064","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.orl.2005.02.003","article-title":"On complexity of multistage stochastic programs","volume":"34","author":"Shapiro","year":"2006","journal-title":"Operations Research Letters"},{"key":"2026033014424387400_ref065","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/j.ejor.2010.08.007","article-title":"Analysis of stochastic dual dynamic programming method","volume":"209","author":"Shapiro","year":"2011","journal-title":"European Journal of Operational Research"},{"key":"2026033014424387400_ref066","doi-asserted-by":"crossref","first-page":"676","DOI":"10.1016\/j.orl.2021.06.019","article-title":"Central limit theorem and sample complexity of stationary stochastic programs","volume":"49","author":"Shapiro","year":"2021","journal-title":"Operations Research Letters"},{"key":"2026033014424387400_ref067","article-title":"Dual bounds for periodical stochastic programs","volume-title":"Operations Research","author":"Shapiro","year":"2021"},{"key":"2026033014424387400_ref068","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611976595","volume-title":"Lectures on Stochastic Programming: Modeling and Theory","author":"Shapiro","year":"2021"},{"key":"2026033014424387400_ref069","doi-asserted-by":"crossref","first-page":"2083","DOI":"10.1137\/19M129406X","article-title":"Periodical multistage stochastic programs","volume":"30","author":"Shapiro","year":"2020","journal-title":"SIAM J. Optimization"},{"key":"2026033014424387400_ref070","first-page":"111","volume-title":"Continuous Optimization: Current Trends and Applications: Current Trends and Applications","author":"Shapiro","year":"2005"},{"key":"2026033014424387400_ref071","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/j.ejor.2012.08.022","article-title":"Risk neutral and risk averse stochastic dual dynamic programming method","volume":"224","author":"Shapiro","year":"2013","journal-title":"European Journal of Operational Research"},{"key":"2026033014424387400_ref072","doi-asserted-by":"crossref","first-page":"1037","DOI":"10.1109\/TSTE.2022.3144022","article-title":"Multistage stochastic programming for vpp trading in continuous intraday electricity markets","volume":"13","author":"Shinde","year":"2022","journal-title":"IEEE Transactions on Sustainable Energy"},{"issue":"1","key":"2026033014424387400_ref073","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1007\/s10107-016-1017-3","article-title":"Stochastic compositional gradient descent: Algorithms for minimizing compositions of expected-value functions","volume":"161","author":"Wang","year":"2017","journal-title":"Mathematical Programming"},{"key":"2026033014424387400_ref074","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1007\/s10107-022-01875-8","article-title":"Stochastic dual dynamic programming for multistage stochastic mixed-integer nonlinear optimization","volume":"196","author":"Zhang","year":"2022","journal-title":"Mathematical Programming"},{"key":"2026033014424387400_ref075","article-title":"Optimal methods for convex nested stochastic composite optimization","volume-title":"Mathematical Programming","author":"Zhang","year":"2020"},{"key":"2026033014424387400_ref076","volume-title":"Foundation of inventory management","author":"Zipkin","year":"2000"},{"key":"2026033014424387400_ref077","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/s10107-018-1249-5","article-title":"Stochastic dual dynamic integer programming","volume":"175","author":"Zou","year":"2019","journal-title":"Mathematical Programming"}],"container-title":["Foundations and Trends\u00ae in Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.emerald.com\/ftopt\/article-pdf\/6\/2\/63\/10976050\/2400000044en.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/www.emerald.com\/ftopt\/article-pdf\/6\/2\/63\/10976050\/2400000044en.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T18:42:59Z","timestamp":1774896179000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.emerald.com\/ftopt\/article\/6\/2\/63\/1324797\/Numerical-Methods-for-Convex-Multistage-Stochastic"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,22]]},"references-count":77,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,22]]}},"URL":"https:\/\/doi.org\/10.1561\/2400000044","relation":{},"ISSN":["2167-3888","2167-3918"],"issn-type":[{"value":"2167-3888","type":"print"},{"value":"2167-3918","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,22]]}}}