Probability maximization via Minkowski functionals: convex representations and tractable resolution

DOI10.1007/S10107-022-01859-8MaRDI QIDQ6038654zbMATH OpenOpenAlexWikidataFDO

Authors I. E. Bardakci, Afrooz Jalilzadeh, Constantino M. Lagoa, Uday V. Shanbhag

Publication date 2 May 2023

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.09682

zbMATH Keywords

chance constraintsstochastic optimization

Mathematics Subject Classification ID

Stochastic approximation (62L20) Stochastic programming (90C15)

Abstract: In this paper, we consider the maximization of a probability $mathbbPzetamidzetainmathbfK(mathbfx)$ over a closed and convex set $mathcalX$, a special case of the chance-constrained optimization problem. We define $mathbfK(mathbfx)$ as $mathbfK(mathbfx)riangleqzetainmathcalKmidc(mathbfx,zeta)geq0$ where $zeta$ is uniformly distributed on a convex and compact set $mathcalK$ and $c(mathbfx,zeta)$ is defined as either {$c(mathbfx,zeta)riangleq1-|zet{a}^{T}mathbfx{|}^m$, $mgeq0$} (Setting A) or $c(mathbfx,zeta)riangleqTmathbfx-zeta$ (Setting B). We show that in either setting, $mathbbPzetamidzetainmathbfK(x)$ can be expressed as the expectation of a suitably defined function $F(mathbfx,xi)$ with respect to an appropriately defined Gaussian density (or its variant), i.e. $mathbb{E}_{ildep}[F(mathbfx,xi)]$. We then develop a convex representation of the original problem requiring the minimization of $g(mathbbE[F(mathbfx,xi)])$ over $mathcalX$ where $g$ is an appropriately defined smooth convex function. Traditional stochastic approximation schemes cannot contend with the minimization of $g(mathbbE[F(cdot,xi)])$ over $mathcalX$, 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 $mathcalO(1/k^{1/2-a})$ in expected sub-optimality where $a>0$, and a sample complexity of $mathcalO(1/epsilo{n}^{6+delta})$ where $delta>0$.

Recommendations

• Maximization of the probability function: an algorithm based on the star-shaped approximation
• Convexity of Gaussian chance constraints and of related probability maximization problems
• Scenario approximations of chance constraints
• scientific article; zbMATH DE number 1328978
• A Sample Approximation Approach for Optimization with Probabilistic Constraints

Cites work

• (Sub-)differentiability of probability functions with elliptical distributions
• (Sub-)gradient formulae for probability functions of random inequality systems under Gaussian distribution
• A bundle method for nonsmooth DC programming with application to chance-constrained problems
• A class of stochastic programming decision problems
• A discussion of probability functions and constraints from a variational perspective
• A joint chance-constrained programming approach for the single-item capacitated lot-sizing problem with stochastic demand
• A Sample Approximation Approach for Optimization with Probabilistic Constraints
• A sampling-and-discarding approach to chance-constrained optimization: feasibility and Optimality
• A sequential algorithm for solving nonlinear optimization problems with chance constraints
• A Single Timescale Stochastic Approximation Method for Nested Stochastic Optimization
• A Stochastic Approximation Method
• Accelerated gradient methods for nonconvex nonlinear and stochastic programming
• Accelerating Stochastic Composition Optimization
• Acceleration of Stochastic Approximation by Averaging
• An approximation-based approach for chance-constrained vehicle routing and air traffic control problems
• Chance Constrained Programming with Joint Constraints
• Chance constrained unit commitment approximation under stochastic wind energy
• Chance-constrained economic dispatch with renewable energy and storage
• Chance-constrained optimal inflow control in hyperbolic supply systems with uncertain demand
• Chance-constrained optimal power flow: risk-aware network control under uncertainty
• Chance-constrained optimization for pension fund portfolios in the presence of default risk
• Chance-constrained programming
• Constrained bundle methods for upper inexact oracles with application to joint chance constrained energy problems
• Convergence analysis for mathematical programs with distributionally robust chance constraint
• Convex Approximations of Chance Constrained Programs
• Convex bodies and norms associated to convex measures
• Derivatives of probability functions and integrals over sets given by inequalities
• Derivatives of probability functions and some applications
• Eventual convexity of chance constrained feasible sets
• Extensions of stochastic optimization results to problems with system failure probability functions
• From CVaR to uncertainty set: implications in joint chance-constrained optimization
• Gradient Formulae for Nonlinear Probabilistic Constraints with Gaussian and Gaussian-Like Distributions
• Gradient formulae for nonlinear probabilistic constraints with non-convex quadratic forms
• scientific article; zbMATH DE number 995813 (Why is no real title available?)
• scientific article; zbMATH DE number 46303 (Why is no real title available?)
• scientific article; zbMATH DE number 3599817 (Why is no real title available?)
• scientific article; zbMATH DE number 2121076 (Why is no real title available?)
• scientific article; zbMATH DE number 3307153 (Why is no real title available?)
• scientific article; zbMATH DE number 3417266 (Why is no real title available?)
• Introduction to Piecewise Differentiable Equations
• Joint chance constrained programming for hydro reservoir management
• Lectures on Stochastic Programming
• Level Sets and NonGaussian Integrals of Positively Homogeneous Functions
• Multilevel stochastic gradient methods for nested composition optimization
• Nonanticipative duality, relaxations, and formulations for chance-constrained stochastic programs
• Nonconvex and nonsmooth approaches for affine chance-constrained stochastic programs
• On extensions of the Brunn-Minkowski and Prekopa-Leindler theorems, including inequalities for log concave functions, and with an application to the diffusion equation
• Probabilistic optimization via approximate \(p\)-efficient points and bundle methods
• Probabilistically Constrained Linear Programs and Risk-Adjusted Controller Design
• Probability Gradient Estimation by Set-Valued Calculus and Applications in Network Design
• Robust Stochastic Approximation Approach to Stochastic Programming
• Sample average approximation method for chance constrained programming: Theory and applications
• Sample size selection in optimization methods for machine learning
• Sequential convex approximations to joint chance constrained programs: A Monte Carlo approach
• SI-ADMM: A Stochastic Inexact ADMM Framework for Stochastic Convex Programs
• Smoothed Variable Sample-Size Accelerated Proximal Methods for Nonsmooth Stochastic Convex Programs
• Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization
• Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions
• The Sequential Unconstrained Minimization Technique (SUMT) Without Parameters
• The subdifferential of measurable composite max integrands and smoothing approximation

Cited in

(3)

• A method to find the minimax of functionals dependent on probability measures
• Maximization of the probability function: an algorithm based on the star-shaped approximation
• Stochastic nested primal-dual method for nonconvex constrained composition optimization

This page was built for publication: Probability maximization via Minkowski functionals: convex representations and tractable resolution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6038654)