A Distributed Interior-Point KKT Solver for Multistage Stochastic Optimization

Jens Hübner (), Martin Schmidt () and Marc C. Steinbach ()
Additional contact information
Jens Hübner: HaCon Ingenieurgesellschaft mbH, 30163 Hannover, Germany
Martin Schmidt: Department Mathematik, Friedrich-Alexander-Universität Erlangen-Nürnberg, 91058 Erlangen, Germany; and Energie Campus Nürnberg, 90429 Nürnberg, Germany
Marc C. Steinbach: Leibniz Universität Hannover, Institute of Applied Mathematics, 30167 Hannover, Germany

INFORMS Journal on Computing, 2017, vol. 29, issue 4, 612-630

Abstract: Multistage stochastic optimization leads to NLPs over scenario trees that become extremely large when many time stages or fine discretizations of the probability space are required. Interior-point methods are well suited for these problems if the arising huge, structured KKT systems can be solved efficiently, for instance, with a large scenario tree but a moderate number of variables per node. For this setting we develop a distributed implementation based on data parallelism in a depth-first distribution of the scenario tree over the processes. Our theoretical analysis predicts very low memory and communication overheads. Detailed computational experiments confirm this prediction and demonstrate the overall performance of the algorithm. We solve multistage stochastic quadratic programs with up to 400 × 10 6 variables and 8.59 × 10 9 KKT matrix entries or 136 × 10 6 variables and 12.6 × 10 9 entries on a compute cluster with 384 GB RAM.

Keywords: interior-point methods; KKT systems; multistage stochastic programming; parallel computing; distributed computing; portfolio optimization (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2017.0748 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:29:y:2017:i:4:p:612-630

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().