IDEAS home Printed from https://ideas.repec.org/p/ems/eureir/1588.html

A primal-dual decomposition based interior point approach to two-stage stochastic linear programming

Author

Listed:
  • Berkelaar, A.B.
  • Dert, C.L.
  • Oldenkamp, K.P.B.
  • Zhang, S.

Abstract

Decision making under uncertainty is a challenge faced by many decision makers. Stochastic programming is a major tool developed to deal with optimization with uncertainties that has found applications in, e.g. finance, such as asset-liability and bond-portfolio management. Computationally however, many models in stochastic programming remain unsolvable because of overwhelming dimensionality. For a model to be well solvable, its special structure must be explored. Most of the solution methods are based on decomposing the data. In this paper we propose a new decomposition approach for two-stage stochastic programming, based on a direct application of the path-following method combined with the homogeneous self-dual technique. Numerical experiments show that our decomposition algorithm is very efficient for solving stochastic programs. In particular, we apply our deompostition method to a two-period portfolio selection problem using options on a stock index. In this model the investor can invest in a money-market account, a stock index, and European options on this index with different maturities. We experiment our model with market prices of options on the S&P500.

Suggested Citation

  • Berkelaar, A.B. & Dert, C.L. & Oldenkamp, K.P.B. & Zhang, S., 1999. "A primal-dual decomposition based interior point approach to two-stage stochastic linear programming," Econometric Institute Research Papers EI 9918-/A, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    • Handle: RePEc:ems:eureir:1588
    as

    Download full text from publisher

    File URL: https://repub.eur.nl/pub/1588/1588_ps.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Yinyu Ye & Michael J. Todd & Shinji Mizuno, 1994. "An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm," Mathematics of Operations Research, INFORMS, vol. 19(1), pages 53-67, February.
    2. John R. Birge & Liqun Qi, 1988. "Computing Block-Angular Karmarkar Projections with Applications to Stochastic Programming," Management Science, INFORMS, vol. 34(12), pages 1472-1479, December.
    3. Stein W. Wallace & Stein-Erik Fleten, 2002. "Stochastic programming in energy," GE, Growth, Math methods 0201001, University Library of Munich, Germany, revised 13 Nov 2003.
    4. Luo, Z-Q. & Sturm, J.F. & Zhang, S., 1996. "Duality and Self-Duality for Conic Convex Programming," Econometric Institute Research Papers EI 9620-/A, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    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. 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.

    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. 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.
    2. Berkelaar, Arjan & Dert, Cees & Oldenkamp, Bart, 1999. "A primal-dual decompsition-based interior point approach to two-stage stochastic linear programming," Serie Research Memoranda 0026, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    3. Arjan Berkelaar & Cees Dert & Bart Oldenkamp & Shuzhong Zhang, 2002. "A Primal-Dual Decomposition-Based Interior Point Approach to Two-Stage Stochastic Linear Programming," Operations Research, INFORMS, vol. 50(5), pages 904-915, October.
    4. Sturm, J.F., 2002. "Implementation of Interior Point Methods for Mixed Semidefinite and Second Order Cone Optimization Problems," Discussion Paper 2002-73, Tilburg University, Center for Economic Research.
    5. Badenbroek, Riley & Dahl, Joachim, 2020. "An Algorithm for Nonsymmetric Conic Optimization Inspired by MOSEK," Other publications TiSEM bcf7ef05-e4e6-4ce8-b2e9-6, Tilburg University, School of Economics and Management.
    6. Jacek Gondzio & Andreas Grothey, 2007. "Parallel interior-point solver for structured quadratic programs: Application to financial planning problems," Annals of Operations Research, Springer, vol. 152(1), pages 319-339, July.
    7. Geoffrey Hewings & Chokri Dridi & Joaquim Guilhoto, 2005. "Impacts of Reallocation of Resource Constraints on the Northeast Economy of Brazil," ERSA conference papers ersa05p14, European Regional Science Association.
    8. E. Nasakkala & J. Keppo, 2008. "Hydropower with Financial Information," Applied Mathematical Finance, Taylor & Francis Journals, vol. 15(5-6), pages 503-529.
    9. Avilés A., Camilo & Oliva H., Sebastian & Watts, David, 2019. "Single-dwelling and community renewable microgrids: Optimal sizing and energy management for new business models," Applied Energy, Elsevier, vol. 254(C).
    10. Constantin Zălinescu, 2008. "On Zero Duality Gap and the Farkas Lemma for Conic Programming," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 991-1001, November.
    11. Parpas, Panos & Webster, Mort, 2014. "A stochastic multiscale model for electricity generation capacity expansion," European Journal of Operational Research, Elsevier, vol. 232(2), pages 359-374.
    12. Elverhøi, Morten & Fleten, Stein-Erik & Fuss, Sabine & Heggedal, Ane Marte & Szolgayova, Jana & Troland, Ole Christian, 2010. "Evaluation of hydropower upgrade projects - a real options approach," MPRA Paper 23005, University Library of Munich, Germany.
    13. Eduardo Faria & Stein-Erik Fleten, 2011. "Day-ahead market bidding for a Nordic hydropower producer: taking the Elbas market into account," Computational Management Science, Springer, vol. 8(1), pages 75-101, April.
    14. Möst, Dominik & Keles, Dogan, 2010. "A survey of stochastic modelling approaches for liberalised electricity markets," European Journal of Operational Research, Elsevier, vol. 207(2), pages 543-556, December.
    15. Enzo Busseti, 2019. "Derivative of a Conic Problem with a Unique Solution," Papers 1903.05753, arXiv.org, revised Mar 2019.
    16. Luo, Z-Q. & Sturm, J.F. & Zhang, S., 1998. "Conic convex programming and self-dual embedding," Econometric Institute Research Papers EI 9815, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    17. Asgeir Tomasgard & Shane Dye & Stein W. Wallace & Leen Stougie, 1997. "Modelling in Distributed Telecommunications Networks," Tinbergen Institute Discussion Papers 97-030/4, Tinbergen Institute.
    18. Sturm, J.F., 2002. "Implementation of Interior Point Methods for Mixed Semidefinite and Second Order Cone Optimization Problems," Other publications TiSEM b25faf5d-0142-4e14-b598-a, Tilburg University, School of Economics and Management.
    19. Oliver Hinder & Yinyu Ye, 2024. "Worst-Case Iteration Bounds for Log Barrier Methods on Problems with Nonconvex Constraints," Mathematics of Operations Research, INFORMS, vol. 49(4), pages 2402-2424, November.
    20. Listes, O.L., 2002. "A decomposition approach to a stochastic model for supply-and-return network design," Econometric Institute Research Papers EI 2002-43, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    JEL classification:

    • C61 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Optimization Techniques; Programming Models; Dynamic Analysis
    • G11 - Financial Economics - - General Financial Markets - - - Portfolio Choice; Investment Decisions

    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:ems:eureir:1588. 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: RePub The email address of this maintainer does not seem to be valid anymore. Please ask RePub to update the entry or send us the correct address (email available below). General contact details of provider: https://edirc.repec.org/data/feeurnl.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.