IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v152y2007i1p319-33910.1007-s10479-006-0139-z.html
   My bibliography  Save this article

Parallel interior-point solver for structured quadratic programs: Application to financial planning problems

Author

Listed:
  • Jacek Gondzio
  • Andreas Grothey

Abstract

Many practical large-scale optimization problems are not only sparse, but also display some form of block-structure such as primal or dual block angular structure. Often these structures are nested: each block of the coarse top level structure is block-structured itself. Problems with these characteristics appear frequently in stochastic programming but also in other areas such as telecommunication network modelling. We present a linear algebra library tailored for problems with such structure that is used inside an interior point solver for convex quadratic programming problems. Due to its object-oriented design it can be used to exploit virtually any nested block structure arising in practical problems, eliminating the need for highly specialised linear algebra modules needing to be written for every type of problem separately. Through a careful implementation we achieve almost automatic parallelisation of the linear algebra. The efficiency of the approach is illustrated on several problems arising in the financial planning, namely in the asset and liability management. The problems are modelled as multistage decision processes and by nature lead to nested block-structured problems. By taking the variance of the random variables into account the problems become non-separable quadratic programs. A reformulation of the problem is proposed which reduces density of matrices involved and by these means significantly simplifies its solution by an interior point method. The object-oriented parallel solver achieves high efficiency by careful exploitation of the block sparsity of these problems. As a result a problem with over 50 million decision variables is solved in just over 2 hours on a parallel computer with 16 processors. The approach is by nature scalable and the parallel implementation achieves nearly perfect speed-ups on a range of problems. Copyright Springer Science+Business Media, LLC 2007

Suggested Citation

  • 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.
    • Handle: RePEc:spr:annopr:v:152:y:2007:i:1:p:319-339:10.1007/s10479-006-0139-z
    DOI: 10.1007/s10479-006-0139-z
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-006-0139-z
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-006-0139-z?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. David R. Cariño & Terry Kent & David H. Myers & Celine Stacy & Mike Sylvanus & Andrew L. Turner & Kouji Watanabe & William T. Ziemba, 1994. "The Russell-Yasuda Kasai Model: An Asset/Liability Model for a Japanese Insurance Company Using Multistage Stochastic Programming," Interfaces, INFORMS, vol. 24(1), pages 29-49, February.
    2. G. Consigli & M. Dempster, 1998. "Dynamic stochastic programmingfor asset-liability management," Annals of Operations Research, Springer, vol. 81(0), pages 131-162, June.
    3. H. Vladimirou & S.A. Zenios, 1999. "Scalable parallel computations forlarge-scale stochastic programming," Annals of Operations Research, Springer, vol. 90(0), pages 87-129, January.
    4. John M. Mulvey & Hercules Vladimirou, 1992. "Stochastic Network Programming for Financial Planning Problems," Management Science, INFORMS, vol. 38(11), pages 1642-1664, November.
    5. 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.
    6. Blomvall, Jorgen & Lindberg, Per Olov, 2002. "A Riccati-based primal interior point solver for multistage stochastic programming," European Journal of Operational Research, Elsevier, vol. 143(2), pages 452-461, December.
    7. John R. Birge, 1985. "Decomposition and Partitioning Methods for Multistage Stochastic Linear Programs," Operations Research, INFORMS, vol. 33(5), pages 989-1007, October.
    8. Stephen P. Bradley & Dwight B. Crane, 1972. "A Dynamic Model for Bond Portfolio Management," Management Science, INFORMS, vol. 19(2), pages 139-151, 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. Zdeněk Dostál & Lukáš Pospíšil, 2016. "Optimal iterative QP and QPQC algorithms," Annals of Operations Research, Springer, vol. 243(1), pages 5-18, August.
    2. Fábián, Csaba I., 2008. "Handling CVaR objectives and constraints in two-stage stochastic models," European Journal of Operational Research, Elsevier, vol. 191(3), pages 888-911, December.
    3. Jens Hübner & Martin Schmidt & Marc C. Steinbach, 2020. "Optimization techniques for tree-structured nonlinear problems," Computational Management Science, Springer, vol. 17(3), pages 409-436, October.
    4. 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.
    5. Frank E. Curtis & Arvind U. Raghunathan, 2017. "Solving nearly-separable quadratic optimization problems as nonsmooth equations," Computational Optimization and Applications, Springer, vol. 67(2), pages 317-360, June.
    6. Xi Yang & Jacek Gondzio & Andreas Grothey, 2010. "Asset liability management modelling with risk control by stochastic dominance," Journal of Asset Management, Palgrave Macmillan, vol. 11(2), pages 73-93, June.

    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. Jacek Gondzio & Roy Kouwenberg, 2001. "High-Performance Computing for Asset-Liability Management," Operations Research, INFORMS, vol. 49(6), pages 879-891, December.
    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. ManMohan S. Sodhi, 2005. "LP Modeling for Asset-Liability Management: A Survey of Choices and Simplifications," Operations Research, INFORMS, vol. 53(2), pages 181-196, April.
    4. Pieter Klaassen, 1998. "Financial Asset-Pricing Theory and Stochastic Programming Models for Asset/Liability Management: A Synthesis," Management Science, INFORMS, vol. 44(1), pages 31-48, January.
    5. Arjan Berkelaar & Roy Kouwenberg, 2011. "A Liability-Relative Drawdown Approach to Pension Asset Liability Management," Palgrave Macmillan Books, in: Gautam Mitra & Katharina Schwaiger (ed.), Asset and Liability Management Handbook, chapter 14, pages 352-382, Palgrave Macmillan.
    6. Unai Aldasoro & Laureano Escudero & María Merino & Juan Monge & Gloria Pérez, 2015. "On parallelization of a stochastic dynamic programming algorithm for solving large-scale mixed 0–1 problems under uncertainty," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 23(3), pages 703-742, October.
    7. Amy V. Puelz, 2002. "A Stochastic Convergence Model for Portfolio Selection," Operations Research, INFORMS, vol. 50(3), pages 462-476, June.
    8. Barro, Diana & Canestrelli, Elio, 2005. "Dynamic portfolio optimization: Time decomposition using the Maximum Principle with a scenario approach," European Journal of Operational Research, Elsevier, vol. 163(1), pages 217-229, May.
    9. Sebastiano Vitali & Vittorio Moriggia, 2021. "Pension fund management with investment certificates and stochastic dominance," Annals of Operations Research, Springer, vol. 299(1), pages 273-292, April.
    10. Klaassen, Pieter, 1997. "Solving stochastic programming models for asset/liability management using iterative disaggregation," Serie Research Memoranda 0010, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    11. Mulvey, John M. & Rosenbaum, Daniel P. & Shetty, Bala, 1997. "Strategic financial risk management and operations research," European Journal of Operational Research, Elsevier, vol. 97(1), pages 1-16, February.
    12. Moriggia, Vittorio & Kopa, Miloš & Vitali, Sebastiano, 2019. "Pension fund management with hedging derivatives, stochastic dominance and nodal contamination," Omega, Elsevier, vol. 87(C), pages 127-141.
    13. Klaassen, Pieter, 1997. "Discretized reality and spurious profits in stochastic programming models for asset/liability management," European Journal of Operational Research, Elsevier, vol. 101(2), pages 374-392, September.
    14. Oguzsoy, Cemal Berk & Guven, Sibel, 1997. "Bank asset and liability management under uncertainty," European Journal of Operational Research, Elsevier, vol. 102(3), pages 575-600, November.
    15. 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.
    16. 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.
    17. Marco Colombo & Andreas Grothey, 2013. "A decomposition-based crash-start for stochastic programming," Computational Optimization and Applications, Springer, vol. 55(2), pages 311-340, June.
    18. 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.
    19. Zenios, Stavros A. & Holmer, Martin R. & McKendall, Raymond & Vassiadou-Zeniou, Christiana, 1998. "Dynamic models for fixed-income portfolio management under uncertainty," Journal of Economic Dynamics and Control, Elsevier, vol. 22(10), pages 1517-1541, August.
    20. Marco Di Francesco & Roberta Simonella, 2023. "A stochastic Asset Liability Management model for life insurance companies," Financial Markets and Portfolio Management, Springer;Swiss Society for Financial Market Research, vol. 37(1), pages 61-94, March.

    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:spr:annopr:v:152:y:2007:i:1:p:319-339:10.1007/s10479-006-0139-z. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.