Optimal inequalities in probability theory: A convex optimization approach
Optimal inequalities in probability theory: A convex optimization approach
复制标题
DOI：
10.1137/s1052623401399903
复制
发表时间：
2005-01-01
影响因子：
3.1
通讯作者：
Popescu, I
中科院分区：
文献类型：
--
作者：
Bertsimas, D;Popescu, I
对于由多项式不等式和随机向量X de定义的集合S，我们提出了一种半定优化方法来求解P（X是S的一个元素）的紧矩不等式问题. ned上的Ω子集的R-n，具有给定的收集高达第k阶矩。在单变量的情况下，我们提供了最佳的界限P（X是一个元素的S），当第一个K时刻的X是给定的，作为一个半定优化问题的解决方案，在k + 1维。在多变量的情况下，如果集合S和。由多项式不等式给出，我们通过求解n中多项式大小的半定优化问题，得到了一个改进的界序列，对固定的k，我们刻画了紧矩不等式推导问题的复杂性.我们证明了当问题中的数据是有理数时，对于k >= 4且Ω = R-n和k >= 2且Ω = R-+（n），找到紧界是NP-困难的。对于k = 1和Omega = R-+（n），我们证明了当集合S是凸的时，我们可以通过解n个凸优化问题找到紧上界，并且当S和Omega是凸集的并时，我们提供了一个多项式时间算法，在此算法上线性函数可以有效地优化。对于k = 2和Omega = R-n的情形，当S是凸集并时，我们给出了一个求紧界的有效算法，在此紧界上凸二次函数可以有效地优化.
We propose a semidefinite optimization approach to the problem of deriving tight moment inequalities for P(X is an element of S), for a set S defined by polynomial inequalities and a random vector X de. ned on Omega subset of R-n that has a given collection of up to kth- order moments. In the univariate case, we provide optimal bounds on P(X is an element of 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. 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 >= 4 and Omega = R-n and for k >= 2 and Omega = R-+(n), when the data in the problem is rational. For k = 1 and Omega = 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 = 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.