Optimal inequalities in probability theory: a convex optimization approach
Author: Bertsimas, Dimitris ; Popescu, IoanaINSEAD Area: Technology and Operations ManagementIn: SIAM Journal on Optimization, vol. 15, no. 3, april 2005 Language: EnglishDescription: p. 780-804.Type of document: INSEAD ArticleNote: Please ask us for this itemAbstract: 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 are 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.| Item type | Current location | Call number | Status | Date due | Barcode | Item holds |
|---|---|---|---|---|---|---|
|
Europe Campus | Available | BC007612 |
Ask Qualtrics
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 are 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.
Digitized
There are no comments for this item.