Optimal inequalities in probability theory: a convex optimization approach (RV of 2002/01/TM)

The authors propose a semi-definite optimization approach to the problem of deriving tight moment inequalities for P(X ? S), for a set S defined by polynomial inequalities and a random vector X defined on ? C Rn that has a given collection of up to kth order moments. In the univariate case, the authors provide optimal bounds on P(X ? S), when the first k moments of X are given, as the solution of a semi-definite 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 semi-definite optimization problems of polynomial size in n, for fixed k. The authors characterize the complexity of the problem of deriving tight moment inequalities. They show that it is NP-hard to find tight bounds for k = 4 and ? = Rn and for k = 2 and ? = R+n, when the data in the problem is rational. For k = 1 and ? = R+n they show that they can find tight upper bounds by solving n convex optimization problems when the set S is convex, and they provide a polynomial time algorithm when S and ? are unions of convex sets, over which linear functions can be optimized efficiently. For the case k = 2 and ? = Rn, they 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.

en

application/pdf

http://flora.insead.edu/fichiersti_wp/inseadwp2004/2004-62.pdf

Copyright INSEAD. All rights reserved