(426c) Clustering-Based Interior-Point Strategies for Stochastic Programs

We present a clustering-based interior-point strategy for two-stage stochastic programs. This problem class arises in stochastic optimal control, robust design, and parameter estimation and has the property that an arrowhead block representation of the KKT system can be obtained. Each block corresponds to a scenario, which is typically obtained by sampling a probability distribution. Our key observation is that scenarios can be clustered on the fly inside the linear solver based on the influence of the associated block on the Schur complement system (first-stage decision). This results in a much smaller compressed KKT system compared to scenario aggregation typically performed prior to the solution of the problem. We show how to use the compressed system as a pre-conditioner for the full space KKT system. We also describe the features of our implementation in C++, demonstrate that high compression rates of 50-90% are possible, and that speedups of an order of magnitude are achievable.