Tuesday, May 1 at 4:15pm
Frank H. T. Rhodes Hall, 253
Optimization under uncertainty (or dynamic optimization) is widely applicable as most real-world problems require decision making under uncertainty. Typically, uncertainty in problem parameters is modeled using a probability distribution and the decision problem is formulated as a stochastic optimization problem. However, computing an optimal fully-adjustable is usually computationally intractable even for two-stage models. Moreover, the probability distributions are often not available and hard to estimate from the available data.
Robust optimization is an alternate approach to optimization under uncertainty where we find a single (static) solution that optimizes the objective over the worst case realization of uncertain parameters. This is a tractable approach but is believed to be highly conservative to be useful in practice. We show that robust optimization provides a good approximation for the dynamic convex optimization problems under fairly general assumptions. The performance bound depends on the geometric property (namely “symmetry”) of the uncertainty set. The result is highly surprising due to perceived conservativeness of the robust approach. Also, the relation between performance and geometric properties provides useful insights into constructing uncertainty sets.
Affine policies is another tractable solution approach where instead of fully-adjustable solutions, we consider solutions that are only affinely-adjustable in uncertain parameters. These are widely used and perform well in practice. We give a tight characterization of the performance of affine policies for a class dynamic optimization problem.