Probability Maximization via Minkowski Functionals: Convex Representations and Tractable Resolution
In this paper, we consider the maximization of a probability P{ζ∣ζ∈K(x)} over a closed and convex set X, a special case of the chance-constrained optimization problem. We define K(x) as K(x)≜{ζ∈K∣c(x,ζ)≥0} where ζ is uniformly distributed on a convex and compact set K and c(x,ζ) is defined as either {c(x,ζ)≜1−∣ζTx∣m, m≥0} (Setting A) or c(x,ζ)≜Tx−ζ (Setting B). We show that in either setting, P{ζ∣ζ∈K(x)} can be expressed as the expectation of a suitably defined function F(x,ξ) with respect to an appropriately defined Gaussian density (or its variant), i.e. Ep~[F(x,ξ)]. We then develop a convex representation of the original problem requiring the minimization of g(E[F(x,ξ)]) over X where g is an appropriately defined smooth convex function. Traditional stochastic approximation schemes cannot contend with the minimization of g(E[F(⋅,ξ)]) over X, 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 both almost-sure convergence guarantees, a convergence rate of O(1/k1/2−a) in expected sub-optimality where a>0, and a sample complexity of O(1/ε6+δ) where δ>0.
