IDEAS home Printed from https://ideas.repec.org/p/wop/iasawp/wp94125.html
   My bibliography  Save this paper

On Augmented Lagrangian Decomposition Methods for Multistage Stochastic Programs

Author

Listed:
  • C.H. Rosa
  • A. Ruszczynski

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.

Suggested Citation

  • C.H. Rosa & A. Ruszczynski, 1994. "On Augmented Lagrangian Decomposition Methods for Multistage Stochastic Programs," Working Papers wp94125, International Institute for Applied Systems Analysis.
    • Handle: RePEc:wop:iasawp:wp94125
    as

    Download full text from publisher

    File URL: http://www.iiasa.ac.at/Publications/Documents/WP-94-125.ps
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. R. T. Rockafellar & Roger J.-B. Wets, 1991. "Scenarios and Policy Aggregation in Optimization Under Uncertainty," Mathematics of Operations Research, INFORMS, vol. 16(1), pages 119-147, February.
    2. Irvin J. Lustig & John M. Mulvey & Tamra J. Carpenter, 1991. "Formulating Two-Stage Stochastic Programs for Interior Point Methods," Operations Research, INFORMS, vol. 39(5), pages 757-770, October.
    3. A. Ruszczynski, 1992. "Augmented Lagrangian Decomposition for Sparse Convex Optimization," Working Papers wp92075, International Institute for Applied Systems Analysis.
    4. R. T. Rockafellar, 1976. "Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming," Mathematics of Operations Research, INFORMS, vol. 1(2), pages 97-116, May.
    5. Alan S. Manne & Richard G. Richels, 1991. "Global CO2 Emission Reductions -the Impacts of Rising Energy Costs," The Energy Journal, , vol. 12(1), pages 87-108, January.
    6. George B. Dantzig & Philip Wolfe, 1960. "Decomposition Principle for Linear Programs," Operations Research, INFORMS, vol. 8(1), pages 101-111, February.
    7. Alan Manne & Richard Richels, 1992. "Buying Greenhouse Insurance: The Economic Costs of CO2 Emission Limits," MIT Press Books, The MIT Press, edition 1, volume 1, number 026213280x, December.
    8. John R. Birge, 1985. "Decomposition and Partitioning Methods for Multistage Stochastic Linear Programs," Operations Research, INFORMS, vol. 33(5), pages 989-1007, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Jesús Latorre & Santiago Cerisola & Andrés Ramos & Rafael Palacios, 2009. "Analysis of stochastic problem decomposition algorithms in computational grids," Annals of Operations Research, Springer, vol. 166(1), pages 355-373, February.
    2. Diana Barro & Elio Canestrelli, 2005. "Time and nodal decomposition with implicit non-anticipativity constraints in dynamic portfolio optimization," GE, Growth, Math methods 0510011, University Library of Munich, Germany.
    3. Diana Barro & Elio Canestrelli, 2011. "Combining stochastic programming and optimal control to solve multistage stochastic optimization problems," Working Papers 2011_24, Department of Economics, University of Venice "Ca' Foscari", revised 2011.
    4. K. Kiwiel & C.H. Rosa & A. Ruszczynski, 1995. "Decomposition via Alternating Linearization," Working Papers wp95051, International Institute for Applied Systems Analysis.
    5. M. Makowski & L. Somlyody & D. Watkins, 1995. "Multiple Criteria Analysis for Regional Water Quality Management: the Nitra River Case," Working Papers wp95022, International Institute for Applied Systems Analysis.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Castro, Jordi & Escudero, Laureano F. & Monge, Juan F., 2023. "On solving large-scale multistage stochastic optimization problems with a new specialized interior-point approach," European Journal of Operational Research, Elsevier, vol. 310(1), pages 268-285.
    2. N. Edirisinghe & E. Patterson, 2007. "Multi-period stochastic portfolio optimization: Block-separable decomposition," Annals of Operations Research, Springer, vol. 152(1), pages 367-394, July.
    3. A. Ruszczynski, 1992. "Augmented Lagrangian Decomposition for Sparse Convex Optimization," Working Papers wp92075, International Institute for Applied Systems Analysis.
    4. A. Ruszczynski, 1993. "Regularized Decomposition of Stochastic Programs: Algorithmic Techniques and Numerical Results," Working Papers wp93021, International Institute for Applied Systems Analysis.
    5. Nordhaus, William, 2013. "Integrated Economic and Climate Modeling," Handbook of Computable General Equilibrium Modeling, in: Peter B. Dixon & Dale Jorgenson (ed.), Handbook of Computable General Equilibrium Modeling, edition 1, volume 1, chapter 0, pages 1069-1131, Elsevier.
    6. Barry C. Smith & Ellis L. Johnson, 2006. "Robust Airline Fleet Assignment: Imposing Station Purity Using Station Decomposition," Transportation Science, INFORMS, vol. 40(4), pages 497-516, November.
    7. Ketabchi, Saeed & Behboodi-Kahoo, Malihe, 2015. "Augmented Lagrangian method within L-shaped method for stochastic linear programs," Applied Mathematics and Computation, Elsevier, vol. 266(C), pages 12-20.
    8. V.I. Norkin & G.C. Pflug & A. Ruszczynski, 1996. "A Branch and Bound Method for Stochastic Global Optimization," Working Papers wp96065, International Institute for Applied Systems Analysis.
    9. Guo, Zhaomiao & Fan, Yueyue, 2017. "A Stochastic Multi-Agent Optimization Model for Energy Infrastructure Planning Under Uncertainty and Competition," Institute of Transportation Studies, Working Paper Series qt89s5s8hn, Institute of Transportation Studies, UC Davis.
    10. Zhang, Zhong Xiang, 1998. "Macroeconomic Effects of CO2 Emission Limits: A Computable General Equilibrium Analysis for China," Journal of Policy Modeling, Elsevier, vol. 20(2), pages 213-250, April.
    11. Gyana R. Parija & Shabbir Ahmed & Alan J. King, 2004. "On Bridging the Gap Between Stochastic Integer Programming and MIP Solver Technologies," INFORMS Journal on Computing, INFORMS, vol. 16(1), pages 73-83, February.
    12. J. Gondzio, 1994. "Preconditioned Conjugate Gradients in an Interior Point Method for Two-stage Stochastic Programming," Working Papers wp94130, International Institute for Applied Systems Analysis.
    13. Maqsood, Imran & Huang, Guo H. & Scott Yeomans, Julian, 2005. "An interval-parameter fuzzy two-stage stochastic program for water resources management under uncertainty," European Journal of Operational Research, Elsevier, vol. 167(1), pages 208-225, November.
    14. Julia Higle & Suvrajeet Sen, 2006. "Multistage stochastic convex programs: Duality and its implications," Annals of Operations Research, Springer, vol. 142(1), pages 129-146, February.
    15. Martin Šmíd & Václav Kozmík, 2024. "Approximation of multistage stochastic programming problems by smoothed quantization," Review of Managerial Science, Springer, vol. 18(7), pages 2079-2114, July.
    16. Xie, Fei & Huang, Yongxi, 2018. "A multistage stochastic programming model for a multi-period strategic expansion of biofuel supply chain under evolving uncertainties," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 111(C), pages 130-148.
    17. Lijian Chen & Tito Homem-de-Mello, 2010. "Re-solving stochastic programming models for airline revenue management," Annals of Operations Research, Springer, vol. 177(1), pages 91-114, June.
    18. Ankur Kulkarni & Uday Shanbhag, 2012. "Recourse-based stochastic nonlinear programming: properties and Benders-SQP algorithms," Computational Optimization and Applications, Springer, vol. 51(1), pages 77-123, January.
    19. Tonbari, Mohamed El & Ahmed, Shabbir, 2023. "Consensus-based Dantzig-Wolfe decomposition," European Journal of Operational Research, Elsevier, vol. 307(3), pages 1441-1456.
    20. Sanjay Mehrotra & M. Gokhan Ozevin, 2009. "Decomposition Based Interior Point Methods for Two-Stage Stochastic Convex Quadratic Programs with Recourse," Operations Research, INFORMS, vol. 57(4), pages 964-974, August.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wop:iasawp:wp94125. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Thomas Krichel (email available below). General contact details of provider: https://edirc.repec.org/data/iiasaat.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.