Session II.2 - Continuous Optimization
Thursday, June 15, 14:30 ~ 15:00
Complexity Guarantees for Chance-Constrained Optimization by leveraging Minkowski Functionals
Uday Shanbhag
Pennsylvania State University, USA - This email address is being protected from spambots. You need JavaScript enabled to view it.
Chance-constrained optimization represents a challenging class of problems in stochastic programming. First studied by Charnes and Cooper in the 1950s, this class of problems has seen significant interest by researchers in both continuous and discrete optimization. Important recent results include the development of schemes that have combined smoothing, sampling, and variational analysis. Yet much much of these findings provide convergence guarantees to (appropriately defined) stationary points while complexity guarantees for computing approximate global minimizers have remained elusive. We consider the resolution of precisely such a gap for a subclass of such problems. We begin by considering the maximization of the probability $\mathbb{P}\left\{ \, \zeta \, \mid \, \zeta \, \in \, K(x) \, \right\}$ over a closed and convex set $\mathcal X$. When $K$ is defined via positively homogenous functions and $\zeta$ satisfies suitable distributional requirements, by leveraging properties of Minkowski functionals and recent findings in the context of non-Gaussian integrals of positively homogenous functions, the probability of interest $\mathbb{P}\left\{\,\zeta \, \mid \, \zeta \, \in \, K(x) \, \right\}$ can be expressed as the expectation of a Clarke-regular function $F(\bullet,\xi)$ with respect to an appropriately defined Gaussian density (or its variant). In fact, we may show that a suitably defined compositional representation is convex. A regularized variance-reduced stochastic approximation framework is provided for computing approximate global minimizers of the original problem and rate and complexity guarantees are provided. In the second part of the talk, we extend the results to a chance-constrained regimes and provide avenues for weakening the distributional assumptions. We show that the chance-constrained problem is equivalent to an optimization problem with compositional convex constraints. Complexity guarantees are provided for computing an approximate global minimizer of the original problem via an inexact variance-reduced proximal-point framework.
Joint work with Ibrahim Bardakci (Bartin University, Turkey), Afrooz Jalilzadeh (University of Arizona, USA), Constantino Lagoa (Penn. State, USA) and Peixuan Zhang (Penn. State, USA).