IDEAS home Printed from https://ideas.repec.org/p/vua/wpaper/1999-26.html
   My bibliography  Save this paper

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

Author

Listed:
  • Berkelaar, Arjan

    (Vrije Universiteit Amsterdam, Faculteit der Economische Wetenschappen en Econometrie (Free University Amsterdam, Faculty of Economics Sciences, Business Administration and Economitrics)

  • Dert, Cees
  • Oldenkamp, Bart

Abstract

Decision making under uncertainty is a challenge faced by many decision makers. Stochas-tic 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 manage-ment. Computationally however, many models in stochastic programming remain unsolvable because of overwhelming dimensionality. For a model to be well solvable, its special struc-ture 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 decomposition 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, 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.
    • Handle: RePEc:vua:wpaper:1999-26
    as

    Download full text from publisher

    File URL: http://degree.ubvu.vu.nl/repec/vua/wpaper/pdf/19990026.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. 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. 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.
    2. 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.
    3. 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.
    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. 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.
    6. Enzo Busseti, 2019. "Derivative of a Conic Problem with a Unique Solution," Papers 1903.05753, arXiv.org, revised Mar 2019.
    7. 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.
    8. G. Y. Zhao, 1999. "Interior-Point Methods with Decomposition for Solving Large-Scale Linear Programs," Journal of Optimization Theory and Applications, Springer, vol. 102(1), pages 169-192, July.
    9. Jacek Gondzio & Andreas Grothey, 2009. "Exploiting structure in parallel implementation of interior point methods for optimization," Computational Management Science, Springer, vol. 6(2), pages 135-160, May.
    10. 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.
    11. Sturm, Jos F. & Zhang, Shuzhong, 2000. "On weighted centers for semidefinite programming," European Journal of Operational Research, Elsevier, vol. 126(2), pages 391-407, October.
    12. Cosmin Petra & Mihai Anitescu, 2012. "A preconditioning technique for Schur complement systems arising in stochastic optimization," Computational Optimization and Applications, Springer, vol. 52(2), pages 315-344, June.
    13. Jacek Gondzio & Roy Kouwenberg, 2001. "High-Performance Computing for Asset-Liability Management," Operations Research, INFORMS, vol. 49(6), pages 879-891, December.
    14. Gondzio, Jacek, 2012. "Interior point methods 25 years later," European Journal of Operational Research, Elsevier, vol. 218(3), pages 587-601.
    15. Mehdi Karimi & Levent Tunçel, 2020. "Primal–Dual Interior-Point Methods for Domain-Driven Formulations," Mathematics of Operations Research, INFORMS, vol. 45(2), pages 591-621, May.
    16. Wong, Man Hong & Zhang, Shuzhong, 2013. "Computing best bounds for nonlinear risk measures with partial information," Insurance: Mathematics and Economics, Elsevier, vol. 52(2), pages 204-212.
    17. Meszaros, Csaba, 1997. "The augmented system variant of IPMs in two-stage stochastic linear programming computation," European Journal of Operational Research, Elsevier, vol. 101(2), pages 317-327, September.
    18. Kuang-Yu Ding & Xin-Yee Lam & Kim-Chuan Toh, 2023. "On proximal augmented Lagrangian based decomposition methods for dual block-angular convex composite programming problems," Computational Optimization and Applications, Springer, vol. 86(1), pages 117-161, September.
    19. 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.
    20. Coralia Cartis & Yiming Yan, 2016. "Active-set prediction for interior point methods using controlled perturbations," Computational Optimization and Applications, Springer, vol. 63(3), pages 639-684, April.

    More about this item

    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:vua:wpaper:1999-26. 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: R. Dam (email available below). General contact details of provider: https://edirc.repec.org/data/fewvunl.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.