Semidefinite Programming for the Generalized Problem of Moments : application to a distributionnally robust approach for optimization under uncertainty
Agnès Gorge

11 January 2013, 10h30 - 11 January 2013, 11h30 Salle/Bat : 475/PCRI-N
Contact :

Activités de recherche :

Résumé :

The Generalized Problem of Moments (GPM) is a famous problem of optimization, stemming from the need to derive bounds over the expected value of a random variable, in a setting where support and moments of related random variables are known. The reason for the interest for this problem are threefold : firstly, it is very versatile and includes numerous interesting special cases such as polynomial and combinatorial optimization. Secondly, through duality, it is closely related to the theory of nonnegative polynomials over semi-algebraic sets. Finally, although NP-hard, these problems can be approximated as closely as desired by a hierarchy of polynomially-solvable semidefinite programs.

In this talk, we will start by defining the GPM and the associated duality theory. Then, we will present the Lasserre hierarchy of Semidefinite Programs whose sequence of optimal values converges to the optimal value of the GPM. Then, we will provide some applications of this paradigm, in particular concerning an original approach for handling uncertainty in an optimization problem : the distributionnally robust optimization.