Global Resolution of Chance-Constrained Optimization Problems: Minkowski Functionals and Monotone Inclusions

Abstract

Chance-constrained optimization problems, an important subclass of stochastic optimization problems, are of- ten complicated by nonsmoothness, and nonconvexity. Thus far, non-asymptotic rates and complexity guarantees for computing an ε-global minimizer remain open questions. We consider a subclass of problems in which the probability is defined as P{ζ |ζ ∈K(x)}, where K is a set defined as K(x) = {ζ ∈ K | c(x, ζ ) ≤ 1}, c(x, •) is a positively homogenous function for any x ∈ X , and K is a nonempty and convex set, symmetric about the origin. We make two contributions in this context. (i) First, when ζ admits a log-concave density on K, the probability function is equivalent to an expectation of a nonsmooth Clarke-regular integrand, allowing for the chance- constrained problem to be restated as a convex program. Under a suitable regularity condition, the necessary and sufficient conditions of this problem are given by a monotone inclusion with a compositional expectation-valued operator. (ii) Second, when ζ admits a uniform density, we present a variance- reduced proximal scheme and provide amongst the first rate and complexity guarantees for resolving chance-constrained optimization problems.

Peixuan Zhang

PhD student

My research interests include stochastic optimization, convex optimization, chance constrained optimization.