|
Friday, February 5, 2010 |
|
|
|
|
Risk-Averse Stochastic Optimization: Models and Algorithms |
|
|
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. |