Vineet Goyal is an Assistant Professor in the Industrial Engineering and Operations Research department at Columbia University. He received his PhD in Algorithms, Combinatorics and Optimization (ACO) in 2008 from Tepper School of Business, CMU where his advisor was R. Ravi. He also spent a couple of years as a postdoctoral associate at the Operations Research Center, MIT working with Dimitris Bertsimas.

AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI   Info

AG Audience

English

60 Minutes

Saarbrücken

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 that is usually computationally intractable. Moreover, the probability distributions are either not available or hard to estimate from data. An alternate approach for dynamic optimization is robust optimization where uncertain problem parameters are assumed to belong to a set (referred to as the uncertainty set), and the optimization problem is formulated with a worst-case objective (i.e.the objective is optimized for the worst case setting of the parameters). While
computing an optimal dynamic robust solution is also intractable in
general, for a large class of optimization problems, we can efficiently compute a static (single) solution that is feasible for all possible realizations of the parameters. But such a static solution is believed to be highly conservative to be useful in practice.

We study the performance of static robust solutions for two-stage dynamic linear optimization problems with uncertain constraint and objective coefficients and give a tight characterization of the adaptivity gap. We show that for a fairly general class of uncertainty sets, a static solution is optimal for the two-stage adjustable robust linear optimization problem. Furthermore, when a static solution is not optimal, we give a tight approximation bound on the performance of the static solution that is related to geometric properties of the uncertainty set such as the measure of symmetry, or a measure of non-convexity of a transformation of the set.

Time permitting, I will discuss the performance of another class of tractable solutions, referred to as affine policies or linear decision rules for dynamic optimization problems.

Anand Sankaran

--email hidden

passcode not visible

logged in users only