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.
|
|
| FullText | Links: – Type: pdflink Text: Availability: 1 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 163252478 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Probability maximization via Minkowski functionals: convex representations and tractable resolution. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Bardakci%2C+I%2E+E%2E%22">Bardakci, I. E.</searchLink><relatesTo>1</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Jalilzadeh%2C+A%2E%22">Jalilzadeh, A.</searchLink><relatesTo>2</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Lagoa%2C+C%2E%22">Lagoa, C.</searchLink><relatesTo>3</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Shanbhag%2C+U%2E+V%2E%22">Shanbhag, U. V.</searchLink><relatesTo>3</relatesTo> (AUTHOR)<i> udaybag@psu.edu</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Mathematical+Programming%22">Mathematical Programming</searchLink>. May2023, Vol. 199 Issue 1/2, p595-637. 43p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Integer+approximations%22">Integer approximations</searchLink><br /><searchLink fieldCode="DE" term="%22Functionals%22">Functionals</searchLink><br /><searchLink fieldCode="DE" term="%22Stochastic+approximation%22">Stochastic approximation</searchLink><br /><searchLink fieldCode="DE" term="%22Smoothness+of+functions%22">Smoothness of functions</searchLink><br /><searchLink fieldCode="DE" term="%22Probability+theory%22">Probability theory</searchLink><br /><searchLink fieldCode="DE" term="%22Constrained+optimization%22">Constrained optimization</searchLink><br /><searchLink fieldCode="DE" term="%22Convex+sets%22">Convex sets</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=163252478 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s10107-022-01859-8 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 43 StartPage: 595 Subjects: – SubjectFull: Integer approximations Type: general – SubjectFull: Functionals Type: general – SubjectFull: Stochastic approximation Type: general – SubjectFull: Smoothness of functions Type: general – SubjectFull: Probability theory Type: general – SubjectFull: Constrained optimization Type: general – SubjectFull: Convex sets Type: general Titles: – TitleFull: Probability maximization via Minkowski functionals: convex representations and tractable resolution. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Bardakci, I. E. – PersonEntity: Name: NameFull: Jalilzadeh, A. – PersonEntity: Name: NameFull: Lagoa, C. – PersonEntity: Name: NameFull: Shanbhag, U. V. IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 05 Text: May2023 Type: published Y: 2023 Identifiers: – Type: issn-print Value: 00255610 Numbering: – Type: volume Value: 199 – Type: issue Value: 1/2 Titles: – TitleFull: Mathematical Programming Type: main |
| ResultId | 1 |
