TY - JOUR

T1 - Probability maximization via Minkowski functionals

T2 - convex representations and tractable resolution

AU - Bardakci, I. E.

AU - Jalilzadeh, A.

AU - Lagoa, C.

AU - Shanbhag, U. V.

N1 - Publisher Copyright:
© 2022, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.

PY - 2023/5

Y1 - 2023/5

N2 - In this paper, we consider the maximizing of the probability P{ζ∣ζ∈K(x)} over a closed and convex set X, a special case of the chance-constrained optimization problem. Suppose K(x)≜{ζ∈K∣c(x,ζ)≥0}, and ζ is uniformly distributed on a convex and compact set K and c(x, ζ) is defined as either c(x,ζ)≜1-|ζTx|m where m≥ 0 (Setting A) or c(x,ζ)≜Tx-ζ (Setting B). We show that in either setting, by leveraging recent findings in the context of non-Gaussian integrals of positively homogenous functions, P{ζ∣ζ∈K(x)} can be expressed as the expectation of a suitably defined continuous function F(∙ , ξ) with respect to an appropriately defined Gaussian density (or its variant), i.e. Ep~[F(x,ξ)]. 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(∙,ξ)]) 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 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. 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.

AB - In this paper, we consider the maximizing of the probability P{ζ∣ζ∈K(x)} over a closed and convex set X, a special case of the chance-constrained optimization problem. Suppose K(x)≜{ζ∈K∣c(x,ζ)≥0}, and ζ is uniformly distributed on a convex and compact set K and c(x, ζ) is defined as either c(x,ζ)≜1-|ζTx|m where m≥ 0 (Setting A) or c(x,ζ)≜Tx-ζ (Setting B). We show that in either setting, by leveraging recent findings in the context of non-Gaussian integrals of positively homogenous functions, P{ζ∣ζ∈K(x)} can be expressed as the expectation of a suitably defined continuous function F(∙ , ξ) with respect to an appropriately defined Gaussian density (or its variant), i.e. Ep~[F(x,ξ)]. 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(∙,ξ)]) 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 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. 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.

UR - http://www.scopus.com/inward/record.url?scp=85137578324&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85137578324&partnerID=8YFLogxK

U2 - 10.1007/s10107-022-01859-8

DO - 10.1007/s10107-022-01859-8

M3 - Article

AN - SCOPUS:85137578324

SN - 0025-5610

VL - 199

SP - 595

EP - 637

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1-2

ER -