Probability maximization via Minkowski functionals: convex representations and tractable resolution

Abstract

In this paper, we consider the maximizing of the probability P { zeta vertical bar zeta is an element of K(x) } over a closed and convex set chi, a special case of the chance-constrained optimization problem. Suppose K(x) (sic) { zeta is an element of K vertical bar c(x, zeta) >= 0}, and zeta is uniformly distributed on a convex and compact set K and c(x, zeta) is defined as either c(x, zeta) (sic) 1 - vertical bar zeta(T)x vertical bar(m) where m >= 0 (Setting A) or c(x, zeta) (sic) Tx - zeta (Setting B). We show that in either setting, by leveraging recent findings in the context of non-Gaussian integrals of positively homogenous functions, P { zeta vertical bar zeta is an element of K(x) } can be expressed as the expectation of a suitably defined continuous function F(., xi) with respect to an appropriately defined Gaussian density (or its variant), i.e. E-(p) over tilde[ F(x, xi) ]. Aided by a recent observation in convex analysis, we then develop a convex representation of the original problem requiring the minimization of g (E [ F(., xi) ] ) over chi, where g is an appropriately defined smooth convex function. Traditional stochastic approximation schemes cannot contend with the minimization of g (E [F(., xi) ]) over chi, since conditionally unbiased sampled gradients are unavailable. We then develop a regularized variance-reduced stochastic approximation (r-VRSA) scheme that obviates the need for such unbiasedness by combining iterative regularization with variance-reduction. Notably, (r-VRSA) is characterized by almost-sure convergence guarantees, a convergence rate of O(1/k(1/2-a)) in expected sub-optimality where a > 0, and a sample complexity of O(1/epsilon(6)(+delta)) where delta > 0. To the best of our knowledge, this may be the first such scheme for probability maximization problems with convergence and rate guarantees. Preliminary numerics on a portfolio selection problem (Setting A) and a set-covering problem (Setting B) suggest that the scheme competes well with naive mini-batch SA schemes as well as integer programming approximation methods.