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

Decomposition via Alternating Linearization

Author

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

Abstract

A new approximate proximal point method for minimizing the sum of two convex functions is introduced. It replaces the original problem by a sequence of regularized subproblems in which the functions are alternately represented by linear models. The method updates the linear models and the prox center, as well as the prox coefficient. It is monotone in terms of the objective values and converges to a solution of the problem, if any. A dual version of the method is derived and analyzed. Applications of the methods to multistage stochastic programming problems are discussed and preliminary numerical experience presented.

Suggested Citation

  • K. Kiwiel & C.H. Rosa & A. Ruszczynski, 1995. "Decomposition via Alternating Linearization," Working Papers wp95051, International Institute for Applied Systems Analysis.
    • Handle: RePEc:wop:iasawp:wp95051
    as

    Download full text from publisher

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

    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. Andrzej Ruszczyński, 1995. "On Convergence of an Augmented Lagrangian Decomposition Method for Sparse Convex Optimization," Mathematics of Operations Research, INFORMS, vol. 20(3), pages 634-656, August.
    3. A. Ruszczynski, 1994. "On Augmented Lagrangian Decomposition Methods For Multistage Stochastic Programs," Working Papers wp94005, International Institute for Applied Systems Analysis.
    4. A. Ruszczynski, 1992. "Augmented Lagrangian Decomposition for Sparse Convex Optimization," Working Papers wp92075, International Institute for Applied Systems Analysis.
    5. John M. Mulvey & Andrzej Ruszczyński, 1995. "A New Scenario Decomposition Method for Large-Scale Stochastic Optimization," Operations Research, INFORMS, vol. 43(3), pages 477-490, June.
    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. Necdet Aybat & Donald Goldfarb & Shiqian Ma, 2014. "Efficient algorithms for robust and stable principal component pursuit problems," Computational Optimization and Applications, Springer, vol. 58(1), pages 1-29, May.

    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. 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. 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.
    3. Cooper, W. W. & Hemphill, H. & Huang, Z. & Li, S. & Lelas, V. & Sullivan, D. W., 1997. "Survey of mathematical programming models in air pollution management," European Journal of Operational Research, Elsevier, vol. 96(1), pages 1-35, January.
    4. A. Ruszczynski, 1994. "On Augmented Lagrangian Decomposition Methods For Multistage Stochastic Programs," Working Papers wp94005, International Institute for Applied Systems Analysis.
    5. 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.
    6. Sodhi, ManMohan S. & Tang, Christopher S., 2009. "Modeling supply-chain planning under demand uncertainty using stochastic programming: A survey motivated by asset-liability management," International Journal of Production Economics, Elsevier, vol. 121(2), pages 728-738, October.
    7. Panos Parpas & Berç Rustem, 2007. "Computational Assessment of Nested Benders and Augmented Lagrangian Decomposition for Mean-Variance Multistage Stochastic Problems," INFORMS Journal on Computing, INFORMS, vol. 19(2), pages 239-247, May.
    8. Manuel Laguna, 1998. "Applying Robust Optimization to Capacity Expansion of One Location in Telecommunications with Demand Uncertainty," Management Science, INFORMS, vol. 44(11-Part-2), pages 101-110, November.
    9. Jie Sun & Xinwei Liu, 2006. "Scenario Formulation of Stochastic Linear Programs and the Homogeneous Self-Dual Interior-Point Method," INFORMS Journal on Computing, INFORMS, vol. 18(4), pages 444-454, November.
    10. 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.
    11. Dimitris Bertsimas & Omid Nohadani & Kwong Meng Teo, 2010. "Robust Optimization for Unconstrained Simulation-Based Problems," Operations Research, INFORMS, vol. 58(1), pages 161-178, February.
    12. Siva Sankaran & Tung Bui, 2008. "An organizational model for transitional negotiations: concepts, design and applications," Group Decision and Negotiation, Springer, vol. 17(2), pages 157-173, March.
    13. Yan, Yongze & Hong, Liu & He, Xiaozheng & Ouyang, Min & Peeta, Srinivas & Chen, Xueguang, 2017. "Pre-disaster investment decisions for strengthening the Chinese railway system under earthquakes," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 105(C), pages 39-59.
    14. Semih Atakan & Suvrajeet Sen, 2018. "A Progressive Hedging based branch-and-bound algorithm for mixed-integer stochastic programs," Computational Management Science, Springer, vol. 15(3), pages 501-540, October.
    15. Lee, Chungmok, 2022. "A robust optimization approach with probe-able uncertainty," European Journal of Operational Research, Elsevier, vol. 296(1), pages 218-239.
    16. Fudong Xie & Ce Wang & Housheng Duan, 2024. "Optimizing Fleet Size in Point-to-Point Shared Demand Responsive Transportation Service: A Network Decomposition Approach," Mathematics, MDPI, vol. 12(19), pages 1-20, September.
    17. Samer Takriti & John R. Birge, 2000. "Lagrangian Solution Techniques and Bounds for Loosely Coupled Mixed-Integer Stochastic Programs," Operations Research, INFORMS, vol. 48(1), pages 91-98, February.
    18. X. W. Liu & M. Fukushima, 2006. "Parallelizable Preprocessing Method for Multistage Stochastic Programming Problems," Journal of Optimization Theory and Applications, Springer, vol. 131(3), pages 327-346, December.
    19. Chia-Hung Chen & Shangyao Yan & Miawjane Chen, 2010. "Short-term manpower planning for MRT carriage maintenance under mixed deterministic and stochastic demands," Annals of Operations Research, Springer, vol. 181(1), pages 67-88, December.
    20. Zhang, S., 2002. "An interior-point and decomposition approach to multiple stage stochastic programming," Econometric Institute Research Papers EI 2002-35, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.

    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:wp95051. 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.