Representation of chance-constraints with strong asymptotic guarantees

Abstract: Given

e p s i l o n i n (0, 1)

, a probability measure

m u

on

O m e g a s u b s e t m a t h b b R^{p}

and a semi-algebraic set

K s u b s e t X i m e s O m e g a

, we consider the feasible set

X_{e}^{*} p s i l o n = x i n X : m P r o b [(x, o m e g a) i n K] g e q 1 - e p s i l o n

associated with a chance-constraint. We provide a sequence of outer approximations

X_{e}^{d} p s i l o n = x i n X : h_{d} (x) g e q 0

,

d i n m a t h b b N

, where

h_{d}

is a polynomial of degree

d

whose vector of coefficients is an optimal solution of a semidefinite program. The size of the latter increases with the degree

d

. We also obtain the strong and highly desirable asymptotic guarantee that

l a m b d a (X_{e}^{d} p s i l o n s e t m i n u s X_{e}^{*} p s i l o n) o 0

as

d

increases, where

l a m b d a

is the Lebesgue measure on

X

. Inner approximations with same guarantees are also obtained.

This page was built for publication: Representation of chance-constraints with strong asymptotic guarantees