Normal view MARC view

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.
Tags: No tags from this library for this title. Log in to add tags.
Item type Current location Call number Status Date due Barcode Item holds
INSEAD Article Europe Campus
Available BC007612
Total holds: 0

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.

Log in to your account to post a comment.
Koha 18.11 - INSEAD Catalogue
Home | Contact Us | What's Koha?