V. M. Zavala, "Clustering-Based Interior-Point Strategies for Stochastic Programs," Preprint ANL/MCS-P3050-1112, November 2012. [pdf]
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.