LANS Informal Seminar: Cosmin Petra

Seminar Title: Scalable Multi-stage Stochastic Programming via Interior-point Methods
Speaker: Cosmin Petra,

Date/Time: 2010-03-25 15:00
Location: Building 240, Room 1404-1405

Description:
Stochastic programming (SP) is concerned with optimization problems incorporating uncertain parameters in the objective and/or constraints. The sample average approximation (SAA) method is used to solve SP problems as very large deterministic optimization problems.

Interior-point methods (IPM) proved in the last twenty years an unequaled efficiency in solving very large scale optimization problems. In a primal-dual IPM framework, the most time expensive task is solving for Newton linearization steps from a linear system involving the Hessian matrix. The constraints of the deterministic SAA SP problems have a block half-arrow shaped Jacobian that allows the Hessian to be permuted in a nested block arrow shape form. We employ the Direct Schur Complement method to make use of the particular structure of the Hessian. This method is also suitable for a scenario-based tree-like parallelization. The only bottleneck in the parallel execution flow is the factorization of the dense Schur complement. The Preconditioned Schur Complement method removes this bottleneck by using preconditioned Krylov subspace iterative methods. The preconditioner we propose approximates the inverse of the Schur complement ‘exponentially’ better as a larger number of scenarios are considered.

We also present PIPS, a parallel solver for multi-stage programming based on interior-point methods. In this talk we report on the performance of PIPS in the context of two real-life stochastic optimization problems: a building energy system control problem and a unit commitment problem.