Seminars & Events

MCS Seminar
"Scalable stochastic programming"

DATE: December 6, 2011
TIME: 3:00 PM - 4:00 PM
SPEAKER: Cosmin Petra, Postdoctoral Appointee, MCS
LOCATION: Building 240, 1404-1405, Argonne National Laboratory

Description:
We present a scalable approach and implementation for solving stochastic programming (SP) problems, with application to the optimization of complex energy systems under uncertainty. Our methodology relies on approximating the underlying uncertainty of the SP problems via sampling, and solving the corresponding sample average approximation (SAA) problem using an interior-point method and parallel distributed-memory linear algebra. The scenario-based decomposition of the linear algebra is obtained by using a direct Schur complement technique (DSC) and allows most of the computations to be performed in parallel with the exception of the linear solves with the dense Schur complement matrix. In many applications the Schur systems are large and cause a computational bottleneck that adversely affects the large-scale computational performance and strong scaling of the DSC method.

We present two approaches that circumvent this bottleneck. The first approach uses a novel stochastic preconditioner and Krylov iterative methods to mitigate the expensive dense factorization of medium-sized Schur complements. The spectral analysis of the preconditioner shows that the eigenvalues of the preconditioner Schur complement clusters around unit exponentially with the size of the samples incorporated in the preconditioner. The second approach distributes and directly solves the large-sized Schur complement systems in parallel. We show numerical experiments and discuss the advantages and drawbacks of this approach in the case of a stochastic economic dispatch problem with wind power integration and transmission constraints which we solve on up to 131,072 cores of the ``Intrepid'' BG/P system.

In addition, we present a novel technique for the estimation of the uncertainty in the solution of SP problems. Traditional methods for the statistical inference of stochastic optimization problems require a large number of samples in order to obtain accurate uncertainty estimates. This requirement usually can not be satisfied in the case of energy models incorporating weather-related uncertainty since numerical weather prediction is extremely expensive and one cannot realistically afford a large number of samples. We propose and analyze an estimator that works with higher-order resampling methods such as bootstrapping, which provides reliable confidence regions despite of the availability of a small number of samples. Numerical evidence supporting this claim will be also presented.

Save the event to your calendar [schedule.ics]