Clustering-Based Interior-Point Strategies for Stochastic Programs

TitleClustering-Based Interior-Point Strategies for Stochastic Programs
Publication TypeJournal Article
Year of Publication2012
AuthorsZavala, VM
Date Published11/2012
Other NumbersANL/MCS-P3050-1112

We present interior-point strategies for convex stochastic programs in which inexpensive inexact Newton steps are computed from compressed Karush-Kuhn-Tucker (KKT) systems obtained by clustering block scenarios. Using Schur analysis, we show that the compression can be characterized as a parametric perturbation of the full-space KKT matrix. This property enables the possibility of retaining superlinear convergence without requiring matrix convergence. In addition, it enables an explicit characterization of the residual and we use this characterization to derive a clustering strategy. We demonstrate that high compression rates of 50-90% are possible and we also show that effective preconditioners can be obtained.