Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Generalized Gauss Inequalities via Semidefinite Programming
 
research article

Generalized Gauss Inequalities via Semidefinite Programming

Van Parys, Bart P. G.
•
Goulart, Paul J.
•
Kuhn, Daniel  
2016
Mathematical Programming

A sharp upper bound on the probability of a random vector falling outside a polytope, based solely on the first and second moments of its distribution, can be computed efficiently using semidefinite programming. However, this Chebyshev-type bound tends to be overly conservative since it is determined by a discrete worst-case distribution. In this paper we obtain a less pessimistic Gauss-type bound by imposing the additional requirement that the random vector's distribution must be unimodal. We prove that this generalized Gauss bound still admits an exact and tractable semidefinite representation. Moreover, we demonstrate that both the Chebyshev and Gauss bounds can be obtained within a unified framework using a generalized notion of unimodality. We also offer new perspectives on the computational solution of generalized moment problems, since we use concepts from Choquet theory instead of traditional duality arguments to derive semidefinite representations for worst-case probability bounds.

  • Details
  • Metrics
Type
research article
DOI
10.1007/s10107-015-0878-1
Web of Science ID

WOS:000370174400010

Author(s)
Van Parys, Bart P. G.
Goulart, Paul J.
Kuhn, Daniel  
Date Issued

2016

Publisher

Springer Verlag

Published in
Mathematical Programming
Volume

156

Issue

1

Start page

271

End page

302

Subjects

Convex optimization

•

Probability inequalities

•

Unimodality

Note

Available from Optimization Online

URL

URL

http://www.optimization-online.org/DB_HTML/2014/01/4187.html
Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
RAO  
Available on Infoscience
January 22, 2014
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/100097
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés