Abstract
In this paper, we consider multi-stage stochastic optimization problems with convex objectives and conic constraints at each stage. We present a new stochastic first-order method, namely the dynamic stochastic approximation (DSA) algorithm, for solving these types of stochastic optimization problems. We show that DSA can achieve an optimal \({{\mathcal {O}}}(1/\epsilon ^4)\) rate of convergence in terms of the total number of required scenarios when applied to a three-stage stochastic optimization problem. We further show that this rate of convergence can be improved to \({{\mathcal {O}}}(1/\epsilon ^2)\) when the objective function is strongly convex. We also discuss variants of DSA for solving more general multi-stage stochastic optimization problems with the number of stages \(T > 3\). The developed DSA algorithms only need to go through the scenario tree once in order to compute an \(\epsilon \)-solution of the multi-stage stochastic optimization problem. As a result, the memory required by DSA only grows linearly with respect to the number of stages. To the best of our knowledge, this is the first time that stochastic approximation type methods are generalized for multi-stage stochastic optimization with \(T \ge 3\).
Similar content being viewed by others
References
Arrow, K., Hurwicz, L., Uzawa, H.: Studies in Linear and Non-linear Programming. Stanford Mathematical Studies in the Social Sciences. Stanford University Press, Palo Alto (1958)
Birge, J.R., Louveaux, F.V.: Introduction to Stochastic Programming. Springer, New York (1997)
Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vision 40, 120–145 (2011)
Chen, Y., Lan, G., Ouyang, Y.: Optimal primal-dual methods for a class of saddle point problems. SIAM J. Optim. 24(4), 1779–1814 (2014)
Dai, B., He, N., Pan, Y., Boots, B., Song, L.: Learning from conditional distributions via dual embeddings. In: Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pp. 1458–1467. (2017)
Dantzig, George B., Infanger, Gerd: Multi-stage stochastic linear programs for portfolio optimization. Ann. Oper. Res. 45(1), 59–76 (1993)
Donohue, Christopher J., Birge, John R.: The abridged nested decomposition method for multistage stochastic linear programs with relatively complete recourse. Algorithm. Oper. Res. 1(1), 20–30 (2006)
Ghadimi, S., Lan, G.: Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, I: a generic algorithmic framework. SIAM J. Optim. 22, 1469–1492 (2012)
Ghadimi, S., Lan, G.: Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, II: shrinking procedures and optimal algorithms. SIAM J. Optim. 23, 2061–2089 (2013)
Ghadimi, S., Lan, G.: Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM J. Optim. 23(4), 2341–2368 (2013)
Ghadimi, S., Lan, G.: Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Math. Program. 156, 59–99 (2015)
Ghadimi, S., Lan, G., Zhang, H.: Mini-batch stochastic approximation methods for constrained nonconvex stochastic programming. Math. Program. 155, 267–305 (2014)
He, Bingsheng, Yuan, **aoming: On the o(1/n) convergence rate of the douglas-rachford alternating direction method. SIAM J. Numer. Anal. 50(2), 700–709 (2012)
Higle, J.L., Sen, S.: Stochastic decomposition: an algorithm for two-stage linear programs with recourse. Math. Oper. Res. 16, 650–669 (1991)
Hindsberger, Magnus, Philpott, A.B.: Resa: a method for solving multistage stochastic linear programs. J. Appl. Oper. Res. 6(1), 2–15 (2014)
Kozmík, Václav, Morton, David P.: Evaluating policies in risk-averse multi-stage stochastic programming. Math. Program. 152(1–2), 275–300 (2015)
Lan, G.: An optimal method for stochastic composite optimization. Math. Program. 133(1), 365–397 (2012)
Lan, G.: Bundle-level type methods uniformly optimal for smooth and non-smooth convex optimization. Math. Program. 149(1), 1–45 (2015)
Lan, G., Lu, Z., Monteiro, R.D.C.: Primal-dual first-order methods with \({\cal{O}}(1/\epsilon )\) iteration-complexity for cone programming. Math. Program. 126, 1–29 (2011)
Lan, G., Nemirovski, A.S., Shapiro, A.: Validation analysis of mirror descent stochastic approximation method. Math. Program. 134, 425–458 (2012)
Lan, Guanghui, Yi, Zhou: An optimal randomized incremental gradient method. Math. Program. 171, 161–215 (2018)
Monteiro, R.D.C., Svaiter, B.F.: On the complexity of the hybrid proximal projection method for the iterates and the ergodic mean. SIAM J. Optim. 20, 2755–2787 (2010)
Nedić, A.: On stochastic subgradient mirror-descent algorithm with weighted averaging. Optim. Lett. 12, 1179–1197 (2012)
Nemirovski, A.S.: Prox-method with rate of convergence \(o(1/t)\) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim. 15, 229–251 (2005)
Nemirovski, A.S., Juditsky, A., Lan, G., Shapiro, A.: Robust stochastic approximation approach to stochastic programming. SIAM J. Optim. 19, 1574–1609 (2009)
Nemirovski, A.S., Yudin, D.: Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience Series in Discrete Mathematics. Wiley, Hoboken (1993)
Nesterov, Y.E.: A method for unconstrained convex minimization problem with the rate of convergence \(O(1/k^2)\). Doklady AN SSSR 269, 543–547 (1983)
Nesterov, Y.E.: Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, Massachusetts (2004)
Nesterov, Y.E.: Smooth minimization of nonsmooth functions. Math. Program. 103, 127–152 (2005)
Ouyang, Y., Chen, Y., Lan, G., Pasiliao, E.: An accelerated linearized alternating direction method of multipliers. SIAM J. Imaging Sci. 8(1), 644–681 (2014)
Pedersen, Christian S., Satchell, Stephen E.: Utility functions whose parameters depend on initial wealth. Bull. Econ. Res. 55(4), 357–371 (2003)
Pereira, Mario V.F., Pinto, Leontina M.V.G.: Multi-stage stochastic optimization applied to energy planning. Math. Program. 52(1–3), 359–375 (1991)
Philpott, A., Matos, Vd, Finardi, E.: On solving multistage stochastic programs with coherent risk measures. Oper. Res. 61, 957–970 (2013)
Polyak, B.T.: New stochastic approximation type procedures. Automat. i Telemekh. 7, 98–107 (1990)
Polyak, B.T., Juditsky, A.B.: Acceleration of stochastic approximation by averaging. SIAM J. Control Optim. 30, 838–855 (1992)
Robbins, H., Monro, S.: A stochastic approximation method. Ann. Math. Stat. 22, 400–407 (1951)
Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)
Tyrrell Rockafellar, R., Wets, Roger J.-B.: Scenarios and policy aggregation in optimization under uncertainty. Math. Oper. Res. 16(1), 119–147 (1991)
Shapiro, A., Dentcheva, D., Ruszczyński, A.: Lectures on Stochastic Programming: Modeling and Theory. SIAM, Philadelphia (2009)
Shapiro, A., Nemirovski, A.: On complexity of stochastic programming problems. http://www.optimization-online.org, (2004). Accessed Oct 2004
Shaprio, A.: On complexity of multistage stochastic programs. Oper. Res. Lett. 34, 1–8 (2006)
Shaprio, A.: Analysis of stochastic dual dynamic programming method. Eur. J. Oper. Res. 209, 63–72 (2011)
Vershynin, R.: Introduction to the non-asymptotic analysis of random matrices. In: Eldar, Y., Kutyniok, G. (eds.) Compressed Sensing: Theory and Applications, pp. 210–268. Cambridge University Press, Cambridge (2012). https://doi.org/10.1017/CBO9780511794308.00
Wang, M., Fang, E.X., Liu, H.: Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions. Math. Program. 161(1–2), 419–449 (2016)
Wang, **ao, Ma, S., GOLDFARB, D., Liu, W.: Stochastic quasi-newton methods for nonconvex stochastic optimization. SIAM J. Optim. 27, 235–247 (2017)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This work was partially supported by National Science Foundation (CMMI-1637473,1637474) and Army Research Office (W911NF-18-1-0223) and Office of Naval Research (N00014-16-1-2802).
Rights and permissions
About this article
Cite this article
Lan, G., Zhou, Z. Dynamic stochastic approximation for multi-stage stochastic optimization. Math. Program. 187, 487–532 (2021). https://doi.org/10.1007/s10107-020-01489-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-020-01489-y