TITLE: Solving Convex Stochastic Problem with Interior Point Method and Sparse Grid Method

SPEAKER: Michael Chen, PhD Candidate, Northwestern University

DATE / TIME: Friday, February 22, 2008 / 2:30 – 3:45 p.m.

LOCATION: Room 453 Mohler Lab, 200 W. Packer Avenue

ABSTRACT: Stochastic programming studies how to model and seek optimal decision variables subject to many decision constraints and under uncertainties across multiple periods. Applications of stochastic programming include financial engineering, supply chain management, revenue management, transportation, water resource allocation and more. We present a state-of-the-art algorithm to efficiently solve stochastic programming models, which (i) constructively approximates the expectation of the underlying random process via sparse grid method and yield a scenario-based problem instance; (ii) efficiently solves the instance with our multistage interior point method. We show that the approximated instances epi-converge to the original problem, and the multistage interior point method can achieve an epsilon-optimal solution with only polynomial number of Newton steps. We especially apply the sparse grid method in CVaR optimal portfolio problem, and compare its performance against Quasi Monte Carlo method.

BIOGRAPHY: Michael Chen is a PhD candidate in Industrial Engineering & Management Sciences department at Northwestern University. He obtained his Master of Science degree in Management Sciences from University of British Columbia. Michael has been working on decision under uncertainty, especially on stochastic programming model for the last few years. His research is unique in combining modern Interior Point Method, advanced numerical integration method, and high dimensional and multistage convex stochastic programming. Michael also applies his algorithmic research into risk management problems, such as portfolio selecting and hedging.