Tutte seminar - Chaitanya Swamy

Risk-Averse Stochastic Optimization: Models and Algorithms

Abstract:

Stochastic optimization problems provide a means to model uncertainty in the input data, where the uncertainty is modeled by a probability distribution over the possible realizations of the data. One well-studied paradigm is the 2-stage recourse model, where one seeks to take actions both before and after the data has been realized so as to minimize the expected cost incurred. We consider various stochastic models that incorporate the notion of risk-averseness into the standard 2-stage recourse model, and develop techniques for solving the algorithmic problems arising in these models. A key notable feature of our work that distinguishes it from work in some other related models, is that we obtain results in the black-box setting, that is, where one is given only sampling access to the underlying distribution. One such model is what we call the risk-averse budget model, where we incorporate the notion of risk-averseness via a probabilistic constraint that restricts the probability (according to the underlying distribution) of the second-stage cost exceeding a given budget B to at most a given input threshold $\rho$, thus, in some sense, guarding against "disaster scenarios". We first devise an approximation scheme for solving the LP-relaxations of a variety of risk-averse budgeted problems. Complementing this, we give a rounding procedure that lets us use existing LP-based approximation algorithms for the 2-stage stochastic and/or deterministic counterpart of the problem to round the fractional solution. Thus, we obtain approximation algorithms for a variety of combinatorial optimization problems in our risk-averse models with black-box distributions. To the best of our knowledge, these are the first approximation results for problems involving probabilistic constraints with black-box distributions. 

The talk will be self-contained.