Chance-Constrained Convex Mixed-Integer Optimization and Beyond: Two Sampling Algorithms within S-optimization

This paper makes two contributions to optimization theory derived from new methods of discrete convex analysis. Our first contribution is to stochastic optimization: The scenario approach developed by Calafiore and Campi to attack chance-constrained convex programs (i.e., optimization problems with convex constraints that are parametrized by an uncertainty parameter) utilizes random sampling on the uncertainty parameter to substitute the original problem with a deterministic continuous convex optimization with

convex constraints which is a relaxation of the original. Calafiore and Campi provided an explicit estimate on the size

N N

of the sampling relaxation to yield high-likelihood feasible solutions of the chance-constrained problem. They measured the probability of the original constraints to be violated by the random optimal solution from the relaxation of size

N N

. We present a generalization of the Calafiore-Campi results to both integer and mixed-integer variables. We demonstrate that their sampling estimates work naturally even for variables that take on more sophisticated values restricted to some subset

S S

of

\mathbb{R}^d R d

. In this way, a sampling or scenario algorithm for chance-constrained convex mixed integer optimization algorithm is just a very special case of a stronger sampling result in convex analysis. Second, motivated by the first half of the paper, for a subset

S \subset \mathbb{R}^d S ⊂ R d

, we formally introduce the notion of an

S S

-optimization problem, where the variables take on values over

S S

.

S S

-optimization generalizes continuous (

S=\mathbb{R}^d S = R d

), integer (

S=\mathbb{Z}^d S = Z d

), and mixed-integer optimization (

S=\mathbb{R}^k \times \mathbb{Z}^{d-k} S = R k × Z d − k

). We illustrate with examples the expressive power of

S S

-optimization to capture combinatorial and integer optimization problems with difficult modular constraints. We reinforce the evidence that

S S

-optimization is “the right concept” by showing that a second well-known randomized sampling algorithm of K. Clarkson for low-dimensional convex optimization problems can be extended to work with variables taking values over

S S

. The key element in all the proofs, are generalizations of Helly's theorem where the convex sets are required to intersect

S \subset \mathbb{R}^d S ⊂ R d

. The size of samples in both algorithms will be directly determined by the

S S

-Helly numbers.