386109 Clustering-Based Interior-Point Strategies for Stochastic Programs

Wednesday, November 19, 2014: 9:12 AM
406 - 407 (Hilton Atlanta)
Yankai Cao1, Carl Laird1 and Victor M. Zavala2, (1)School of Chemical Engineering, Purdue University, West Lafayette, IN, (2)Mathematics and Computer Science, Argonne National Laboratory, Argonne, IL

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.

Extended Abstract: File Not Uploaded
See more of this Session: Advances in Optimization I
See more of this Group/Topical: Computing and Systems Technology Division