Generalized Chebyshev Bounds via Semidefinite Programming
Abstract¶
A sharp lower bound on the probability of a set defined by quadratic inequalities, given the first two moments of the distribution, can be efficiently computed using convex optimization. This result generalizes Chebyshev’s inequality for scalar random variables. Two semidefinite programming formulations are presented, with a constructive proof based on convex optimization duality and elementary linear algebra.
Summary¶
Formulates generalized Chebyshev probability bounds as semidefinite programs over moments. The paper shows how SDP duality turns partial distributional information into sharp worst-case probability guarantees.
Links¶
Tags¶
Similar Papers¶
1
83%
2
76%
3
69%
4
67%
Distributionally Robust Joint Chance Constraints with Second-Order Moment Information
Worst-Case CVaR Approximation
5
66%
The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs
Scenario Approach Feasibility Bound