Moments and sums of squares for solving the generalized problem of moments
Jean B. Lasserre
LAAS (Laboratoire d'Architecture et d'Analyse des Systèmes)-CNRS, Toulouse, France
Roughly
speaking, the Generalized Problem of Moments (GPM) is an
infinite-dimensional linear optimization problem (i.e. an infinite
dimensional linear program) on a convex set of measures with
support on a given subset K of Rn. From a theoretical viewpoint, the
GPM has produced developments and impact in various areas of Mathematics like
algebra, Fourier analysis, functional analysis, operator theory,
probability and statistics, to cite a few. In addition, and
despite its rather simple and short formulation, the GPM has a large
number of important applications in various fields like optimization,
probability, mathematical finance, optimal control, control and signal
processing, chemistry, crystallography, tomography, quantum computing,
etc.
In its full generality, the GPM is numerically intractable.
However when the set K is compact and semi-algebraic, and
the functions involved are polynomials (and in some cases
piecewise polynomials or rational functions), then the situation is much
nicer. Indeed, one can define a systematic numerical scheme based
on a hierarchy of semidefinite programs, which provides a monotone
sequence that converges to the optimal value of the GPM. Sometimes
finite convergence may even occur.
In the talk, we will
present the semidefinite programming methodology to solve
the GPM and describe in detail several applications of the GPM (notably
in probability and mathematical finance).
Jean B. Lasserre
graduated from "Ecole Nationale Superieure d'Informatique et
Mathematiques Appliquees" (ENSIMAG) in Grenoble (France), then got
his PhD (1978) and "Doctorat d'Etat" (1984) degrees both from the
University of Toulouse (France). Since 1980 he has been at LAAS-CNRS in
Toulouse where he is currently "Directeur de Recherche" and is also an
associate member of the Institute of Mathematics of Toulouse. He was a
one year visitor (1978-79 and 1985-86) at the Electrical Engineering
Dept. of the University of California at Berkeley with a fellowship
from INRIA and NSF. He has published over 130 journal articles and is
author of the forthcoming book "Linear and Integer Programming vs
Linear Integration and Counting" (Springer), and co-author with O.
Hernandez-Lerma of the books "Markov Chains and Invariant
Probabilities" (Birkhauser, 2003), "Discrete-Time Markov Control
Processes: Basic Optimality Criteria" (Springer, 1996), and "Further
Topics on Discrete-Time Markov Control Processes" (Springer, 1999).