Spring 2010 Seminar Series

DATE: April 1st
LOCATION: E51-376
TIME: 4:15pm
Reception immediately following in the ORC Conference Room, E40-106

SPEAKER:
Vineet Goyal

TITLE
On the Power of Robust and Affine Solutions in Dynamic Optimization

ABSTRACT
Multi-stage dynamic optimization is widely applicable as most real-world problems can be formulated as multi-stage decision making problems under uncertainty. However, such formulations are usually computationally intractable even for two-stage models.

 

We show that robust optimization which optimizes for the worst-case scenario and is a tractable approach, provides a good approximation for the dynamic optimization problem under fairly general assumptions, namely that the uncertainty is distributed symmetrically over a bounded set. This is a mild assumption and is often satisfied in practice. The result is highly surprising as the robust approach is usually believed to be highly conservative and thus, not relevant in practice.

 

In the second part of the talk, I will present our results on the performance of affine policies or linear decision rules. Affine policies are widely used in multi-stage problems due to their computational tractability and perform extremely well in practice. We give a surprising tight characterization of the performance of affine policies for dynamic optimization problems.

 

This talk is based on joint work with Dimitris Bertsimas.