Ambiguous chance constrained problems and robust optimization

Primary tabs

Let x denote a vector of n decision variables and Y denote a random vector. A constraint of the form P(f(x,Y) > 0) < eps
is called a chance constraint on the decision variable x. Optimization problems with chance constraints are notoriously hard to solve.

A simple strategy for solving chance constrained problems is to generate N samples according to the distribution P and then impose the constraints f(x,Y_i) < 0, for all i = 1, ..., N (*)
Since Y_i are random samples, there is no hope that decision
variables x that are feasible for (*) are all feasible for the chance
constraint with probability 1. Therefore, one has to allow a probability of error delta. Question: How large should N be as a function of eps and
delta ?

Recently, Calafiore and Campi showed that when f(x,Y) is a convex function of x for every fixed Y we only need N =O(n/delta log(1/eps)). Nemirovski and Shapiro have shown that if the function f(x,Y) is bi-affine and the distribution P has a "concentration-of-measure" property the number of samples required drops to N = O(n log(1/(eps*delta))).

In many applications of chance constrained problems the distribution P is not completely known, i.e. the distribution is ambiguous. The natural
constraint to impose in this setting is the ambiguous chance constraint:
max_{P in M} {P(f(x,Y) > 0)} < eps, where M is an uncertainty set of distributions. In this talk we discuss how to extend many results known for chance constrained problems to this more general setting. Robust deterministic optimization naturally arises
in these extensions by way of the Strassen-Dudley representation theorem.

(Joint work with Emre Erdogan)

Brief Bio: Garud Iyengar received his PhD in Electrical Engineering from Stanford University in 1998. Since then he has been with the Industrial Engineering and Operations Research (IEOR) department at Columbia
University where he is currently an Associate Professor.


  • Workflow Status: Published
  • Created By: Barbara Christopher
  • Created: 10/08/2010
  • Modified By: Fletcher Moore
  • Modified: 10/07/2016


No keywords were submitted.

Target Audience

No target audience selected.