Optimal Inequalities in Probability Theory: A Convex Optimization Approach

By Dimitris J. Bertsimas, Ioana Popescu. SIAM Journal on Optimization, 2005

493 citations recorded by the source corpus.

We propose a semidefinite optimization approach to the problem of deriving tight moment inequalities for $P(X\in S)$, for a set S defined by polynomial inequalities and a random vector X defined on $\Omega\subseteq {\cal R}^n$ that has a given collection of up to kth-order moments. In the univariate case, we provide optimal bounds on $P(X\in S)$, when the first k moments of X are given, as the solution of a semidefinite optimization problem in k + 1 dimensions. In the multivariate case, if the sets S and $\Omega$ are given by polynomial inequalities, we obtain an improving sequence of bounds by solving semidefinite optimization problems of polynomial size in n, for fixed k. We characterize the complexity of the problem of deriving tight moment inequalities. We show that it is NP-hard to find tight bounds for $k\geq 4$ and $\Omega={\cal R}^n$ and for $k\geq 2$ and $\Omega={\cal R}^n_+,$ when the data in the problem is rational. For k = 1 and $\Omega={\cal R}^n_+$ we show that we can find tight upper bounds by solving n convex optimization problems when the set S is convex, and we provide a polynomial time algorithm when S and $\Omega$ are unions of convex sets, over which linear functions can be optimized efficiently. For the case k = 2 and $\Omega={\cal R}^n$, we present an efficient algorithm for finding tight bounds when S is a union of convex sets, over which convex quadratic functions can be optimized efficiently.

Subfields: Artificial Intelligence, Numerical Analysis, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/1c73db6d9270b73f117acf417459191a8c822dd8

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Numerical Analysis

In Statistics and Probability

Citations in the corpus

Robust SAA (2014, background): “DRO has since received much attention in the literature, with many authors focusing on DUSs F defined by fixing the first few moments of the distribution [6, 10, 28, 29], although some also consider other structural information such as unimodality [16].”
Distributionally Robust Optimization: A Review (2019, background): “Early DRO models considered ambiguity sets based on the support and moment information, for which techniques in global optimization for polynomial optimization problems and problem of moments are applied to obtain reformulations, see, e.g., Lasserre [182], Bertsimas et al. [38], Bertsimas and Popesc”
Distributionally Robust Chance-Constrained Optimal Power Flow With Uncertain Renewables and Uncertain Reserves Provided by Loads (2017, background): “According to [34], there exists a distribution inD′ to make the inequality tight.”
Practical Ensemble Classification Error Bounds for Different Operating Points (2013, background): “without reject option; further guidelines specific to the reject option may be revealed by higher order analysis [32].”
Robust Optimization (2021, background): “2 can be traced to [23, 24] and are based upon specific implementation of Lagrange relaxation, the so called semidefinite relaxation scheme which goes back to Naum Shor and Laslo Lovacz(4).”
Robust sample average approximation (2014, background): “DRO has since received much attention, with many authors focusing on DUSsF defined by fixing the first few moments of the distribution [8,11, 37,38], although some also consider other structural information such as unimodality [19].”
On Distributionally Robust Chance-Constrained Linear Programs (2006, unknown): “inf d∼(d̂, )S Prob{dT x̃ ≤ 0} ≥ 1 − (16)”
Theory and Applications of Robust Optimization (2010, background): “Along this vein, Popescu [120] has considered the problem of maximizing expected utility in a distributional-robust way when only the mean and covariance of the distribution are known.”
Robust Regression and Lasso (2008, result): “We postpone the proof to the Appendix, and refer the reader to [15] for similar results using semi-definite optimization.”
Adaptive Distributionally Robust Optimization (2019, result): “Note that although similar results have been derived in Isii (1962), Bertsimas and Popescu (2005), Shapiro and Kleywegt (2002), among others, our proof is based on conic duality and avoids analysis of functional spaces.”
Distributionally Robust Convex Optimization (2014, unknown): “Robust optimization, ambiguous probability distributions, conic optimization.”
Distributionally Robust Co-Optimization of Energy and Reserve Dispatch (2016, background): “Proposition 1 [34], [37]: If the covariance matrix Σ is strict positive, strong duality holds, i.”
Regret in the Newsvendor Model with Partial Information (2008, background): “Ben-Tal and Nemirovski (1999) and Bertsimas and Sim (2003) limited the “budget of uncertainty” within which the worst-case scenario is selected to avoid conservative decisions. However, their approach is essentially designed for problems with multiple random variables and applies only trivially to t”