Ibrahim E. Bardakci

Probability Maximization via Minkowski Functionals: Convex Representations and Tractable Resolution

In this paper, we consider the maximization of a probability $\mathbb{P}\{ ζ\mid ζ\in \mathbf{K}(\mathbf x)\}$ over a closed and convex set $\mathcal X$, a special case of the chance-constrained optimization problem. We define $\mathbf{K}(\mathbf x)$ as $\mathbf{K}(\mathbf x) \triangleq \{ ζ\in \mathcal{K} \mid c(\mathbf{x},ζ) \geq 0 \}$ where $ζ$ is uniformly distributed on a convex and compact set $\mathcal{K}$ and $c(\mathbf{x},ζ)$ is defined as either {$c(\mathbf{x},ζ) \triangleq 1-|ζ^T\mathbf{x}|^m$, $m\geq 0$} (Setting A) or $c(\mathbf{x},ζ) \triangleq T\mathbf{x} -ζ$ (Setting B). We show that in either setting, $\mathbb{P}\{ ζ\mid ζ\in \mathbf{K(x)}\}$ can be expressed as the expectation of a suitably defined function $F(\mathbf{x},ξ)$ with respect to an appropriately defined Gaussian density (or its variant), i.e. $\mathbb{E}_{\tilde p} [F(\mathbf x,ξ)]$. We then develop a convex representation of the original problem requiring the minimization of ${g(\mathbb{E}[F(\mathbf{x},ξ)])}$ over $\mathcal X$ where $g$ is an appropriately defined smooth convex function. Traditional stochastic approximation schemes cannot contend with the minimization of ${g(\mathbb{E}[F(\cdot,ξ)])}$ over $\mathcal 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 $\mathcal{O}(1/k^{1/2-a})$ in expected sub-optimality where $a > 0$, and a sample complexity of $\mathcal{O}(1/ε^{6+δ})$ where $δ> 0$.