Probability maximization via Minkowski functionals: convex representations and tractable resolution.
Saved in:
| Title: | Probability maximization via Minkowski functionals: convex representations and tractable resolution. |
|---|---|
| Authors: | Bardakci, I. E.1 (AUTHOR), Jalilzadeh, A.2 (AUTHOR), Lagoa, C.3 (AUTHOR), Shanbhag, U. V.3 (AUTHOR) udaybag@psu.edu |
| Source: | Mathematical Programming. May2023, Vol. 199 Issue 1/2, p595-637. 43p. |
| Subjects: | Integer approximations, Functionals, Stochastic approximation, Smoothness of functions, Probability theory, Constrained optimization, Convex sets |
| Abstract: | 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 - ζ T x m where m ≥ 0 (Setting A) or c (x , ζ) ≜ T x - ζ (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. E p ~ 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 / k 1 / 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. [ABSTRACT FROM AUTHOR] |
| Copyright of Mathematical Programming is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| Abstract: | 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 - ζ T x m where m ≥ 0 (Setting A) or c (x , ζ) ≜ T x - ζ (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. E p ~ 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 / k 1 / 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. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 00255610 |
| DOI: | 10.1007/s10107-022-01859-8 |
