Generalized Gauss inequalities via semidefinite 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 determine...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2016-03, Vol.156 (1-2), p.271-302
Main Authors: Van Parys, Bart P. G., Goulart, Paul J., Kuhn, Daniel
Format: Article
Language:English
Subjects:
Calculus of Variations and Optimal Control
Optimization
Chebyshev approximation
Combinatorics
Computation
Computer programming
Decision theory
Falling
Full Length Paper
Inequalities
Inequality
Mathematical analysis
Mathematical and Computational Physics
Mathematical Methods in Physics
Mathematical programming
Mathematics
Mathematics and Statistics
Mathematics of Computing
Numerical Analysis
Optimization
Probability
Random variables
Representations
Studies
Theoretical
Vectors (mathematics)
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0025-5610
1436-4646
DOI:10.1007/s10107-015-0878-1