A Distributed Interior-Point KKT Solver for Multistage Stochastic Optimization
针对多阶段随机优化中场景树规模过大的问题，提出一种基于数据并行的分布式内点KKT求解器，理论分析表明内存和通信开销极低，实验验证了算法性能，可求解变量数达4亿的二次规划问题。
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. Data are available at https://doi.org/10.1287/ijoc.2017.0748 .