Abstract
A general decomposition framework for large convex optimization problems based on augmented Lagrangians is described. The approach is then applied to multistage stochastic programming problems in two different ways: by decomposing the problem into scenarios and by decomposing it into nodes corresponding to stages. Theoretical convergence properties of the two approaches are derived and a computational illustration is presented.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
A.J. Berger, J.M. Mulvey and A. Ruszczyński, An extension of the DQA algorithm to convex stochastic programs, SIAM Journal on Optimization 4, 1994, 735–753.
D.P. Bertsekas,Constrained Optimization and Lagrange Multiplier Methods, Academic Press, 1982.
D.P. Bertsekas and J.N. Tsitsiklis,Parallel and Distributed Computation, Prentice-Hall, Englewood Cliffs, 1989.
J.R. Birge, Decomposition and partitioning methods for multistage stochastic linear programs, Operations Research 33, 1985, 989–1007.
A. Brooke, D. Kendrick and A. Meeraus,GAMS: A User's Guide, The Scientific Press, San Francisco, 1992.
G.B. Dantzig and P. Wolfe, Decomposition principle for linear programs, Operations Research 8, 1960, 101–111.
M. Fortin and R. Glowinski, On decomposition-coordination methods using an augmented Lagrangian, inAugmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems, M. Fortin and R. Glowinski, eds., North-Holland, Amsterdam, 1983, pp. 97–146.
H.I. Gassmann, MSLiP: A computer code for the multistage stochastic linear programming problem, Mathematical Programming 47, 1990, 407–423.
J. Gondzio and A. Ruszczyński, A sensitivity method for basis inverse representation in multistage stochastic linear programming problems, Journal of Optimization Theory and Applications 74, 1992, 221–242.
I.J. Lustig, J.M. Mulvey and T.J. Carpenter, Formulating stochastic programs for interior point methods, Operations Research 39, 1991, 757–770.
A.S. Manne and R.G. Richels, Global CO2 emission reductions — the impacts of rising energy costs, The Energy Journal 12, 1991, 87–107.
A.S. Manne and R.G. Richels,Buying Greenhouse Insurance: The Economic Costs of CO2 Emission Limits, MIT Press, Cambridge, 1992.
J.M. Mulvey and A. Ruszczyński, A diagonal quadratic approximation method for large-scale linear programs, Operations Research Letters 12, 1992, 205–215.
J.M. Mulvey and A. Ruszczyński, A new scenario decomposition method for large-scale stochastic optimization, Operations Research 43, 1995, 477–490.
B.A. Murtagh and M.A. Saunders,MINOS 5.1 User's Guide, Report SOL-83-20R, Systems Optimization Library, Standford, CA, 1987.
B.N. Pshenichnyi,Convex Analysis and Extremal Problems, Nauka, Moscow, 1980 (in Russian).
R.T. Rockafellar,Convex Analysis, Princeton University Press, Princeton, 1973.
R.T. Rockafellar, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Mathematics of Operations Research 1, 1976, 97–116.
R.T. Rockafellar and R.J-B Wets, Scenarios and policy aggregation in optimization under uncertainty, Mathematics of Operations Research 16, 1991, 1–23.
C.H. Rosa, Pathways of economic development in an uncertain environment: A finite scenario approach to the U.S. region under carbon emission restrictions, WP-94-41, International Institute for Applied Systems Analysis, Laxenburg, Austria, 1992.
A. Ruszczyński, A regularized decomposition method for minimizing a sum of polyhedral functions, Mathematical Programming 35, 1986, 309–333.
A. Ruszczyński, Parallel decomposition of multistage stochastic programs, Mathematical Programming 58, 1993, 201–228.
A. Ruszczyński, An augmented Lagrangian decomposition method for block diagonal linear programming problems, Operations Research Letters 8, 1989, 287–294.
A. Ruszczyński, On convergence of an augmented Lagrangian decomposition method for sparse convex optimization, Mathematics of Operations Research 20, 1995, 634–656.
G. Stephanopoulos and W. Westerberg, The use of Hestenes' method of multipliers to resolve dual gaps in engineering system optimization, Journal of Optimization Theory and Applications 15, 1975, 285–309.
R. Van Slyke and R.J-B Wets, L-shaped linear programs with applications to optimal control and stochastic programming, SIAM Journal on Applied Mathematics 17, 1969, 638–663.
R.J-B Wets, Large scale linear programming techniques, inNumerical Methods in Stochastic Programming, Yu. Ermoliev and R.J-B Wets, eds., Springer, Berlin, 1988, pp. 65–94.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Rosa, C.H., Ruszczyński, A. On augmented Lagrangian decomposition methods for multistage stochastic programs. Ann Oper Res 64, 289–309 (1996). https://doi.org/10.1007/BF02187650
Issue Date:
DOI: https://doi.org/10.1007/BF02187650