Notes of Jean Lasserre’s lecture nr 1

Moments, positive polynomials and optimization

Hierarchies will come only at the very end, as a tool that helps solving basic problems with many applications. The main theorems will have two facets: real algebraic geometry (positive polynomials), and functional analysis (moments). Implementability is an important feature, to keep in mind.

Let me advertise my recent book [L].

1. Semi-definite programming

${A_i}$, ${b}$ given real symmetric matrices. Unknown is a real vector ${x=(x_1 ,\ldots,x_n)}$. Problem: minimize a linear functional ${c\cdot x}$ subject to the constraint that ${\sum_{i=1}^n x_i A_i -b}$ is positive semidefinite.

The dual problem is to maximize Trace${(bY)}$ over matrices ${Y}$ subject to the constraints that ${Y}$ is positive semidefinite and Trace${(YA_i)\geq 0}$ for all ${i}$.

Softwares SeduMi, SDPT3 can handle thousands of variables. These are hand-made, since industry does not seem to need SDP software now. Pioneers: Nemirovsky, Nesterov, Shor, Yudin.

Guy Kindler: what about special sets of data ? Answer: Symmetries and sparsity allow larger sizes.

From now on, take SDP as a black box.

2. Global optimization

Want to minimize a function on a subset ${K}$ of ${{\mathbb R}^n}$,

• real semialgebraic set.
• discrete cube.

Usually, people are happy with local minima.

2.1. Primal point of view

Proposition 1 Let ${\mathcal{P}(K)}$ denote the set of probability measures on ${{\mathbb R}^n}$ supported on ${K}$.

$\displaystyle \begin{array}{rcl} f^* :=\min f =\inf_{\mu\in\mathcal{P}(K)}\int_{{\mathbb R}^n}f\,d\mu. \end{array}$

This is an LP in infinite dimensions.

2.2. Dual point of view

The dual problem of the above LP is simply

Proposition 2 Let ${\mathcal{P}(K)}$ denote the set of probability measures on ${{\mathbb R}^n}$ supported on ${K}$.

$\displaystyle \begin{array}{rcl} f^* :=\max\{\lambda\,;\, f(x)-\lambda\geq 0\,\forall x\in K\}. \end{array}$

We need practical criteria to express constraints, either the fact that a measure is supported by ${K}$, or that a function is nonnegative on ${K}$. These do not exist in full generality, but exist when ${K}$ is a compact basic semialgebraic set, and ${f}$ a polynomial (or more generally semialgebraic).

2.3. Basic semialgebraic sets

Definition 3 A subset ${K\subset{\mathbb R}^n}$ is basic semialgebraic if it can be defined by real algebraic equations and closed real algebraic inequations.

A powerful theorem from real algebraic geometry will provide us with a sequence of approximations to a semialgebraic global optimization problem, which are computationnally feasible.

The central tool is a set of necessary and sufficient condition for

• a finite Borel measure to be supported on ${K}$,
• a polynomial to be positive on ${K}$.

In both cases, these conditions translate into Linear Matrix Inequalities, or Linear Inequalities satisfied by the Moments

$\displaystyle \begin{array}{rcl} y_{\alpha}:=\int_{{\mathbb R}^n}X^{\alpha}\,d\mu. \end{array}$

of ${\mu}$ (and not ${\mu}$ itself), and on the coefficients of certain polynomials.

No convexity nor discreteness assumptions.

This sounds suspicious: the same tools used to solve convex continuous problems and boolean problems ? These are known to behave very differently. This must be kept in mind too.

3. The generalized problem of moments

Data: a subset ${K\subset{\mathbb R}^n}$, functions ${f_j}$. Unknown: a finite measure on ${K}$. Goal: minimize ${\int f_0 \,d\mu}$ subject to constraints ${\int f_j \,d\mu \geq b_j}$.

This problem was popular in the early XXth century, and solved in the ${1}$-dimensional case. It encompasses many problems in applied mathematics, see [M]. I give examples.

3.1. Convex envelope

Data: a set ${K\subset{\mathbb R}^n}$, a function ${f:K\rightarrow{\mathbb R}}$ (${f=+\infty}$ ouside ${K}$). Output: the largest convex function ${\hat{f}}$ on ${{\mathbb R}^n}$ such that ${\hat{f}\leq f}$.

3.2. Probability

Data: a set ${K\subset{\mathbb R}^n}$, a Borel subset ${S\subset K}$. Output: an estimate on ${\mathop{\mathbb P}(X\in S)}$, assuming certain moments of the random variable ${X}$ take prescribed values.

3.3. Volume of a basic semialgebraic set

There is a polytime approximation scheme (Kannan, Lovácz, Simonovitz, [KLS].

Here is an alternative method. Sample points uniformly in a box ${K}$. The corresponding moments ${\gamma_{\alpha}}$ are known. Write Lebesgue measure as ${\phi+\nu}$ where ${\phi}$ is supported on ${S}$ and ${\nu}$ on ${K\setminus S}$. Then

$\displaystyle \begin{array}{rcl} Volume(S)=\sup\{\int_{S}d\phi \,;\,\phi\textrm{ supported on }S,\,\int X^{\alpha}\,d\phi +\int X^{\alpha}\,d\nu=\gamma_{\alpha}\,\forall\alpha\in{\mathbb N}^{n}\}. \end{array}$

3.4. Measures given by marginals

Generalization of the Monge-Kantorovitch mass transportation problem. Express equality of marginals along certain coordinates by equality of all moments not involving these coordinates.

3.5. Pricing European call options

Want to set price for the following service: buy a given quantity at a fixed future date. There are two unknown measures, the occupation measure (how much time the asset visits an interval) and the exit measure (value of the asset at given horizon). The solution involves a moment problem.

The Black-Scholes model is a special case. See Lasserre, Prieto, Zervos 2006, [LPZ].

3.6. Optimal control

3.7. Multivariate integration of exponentials

Data: a function ${h}$ on ${[0,1]}$. Goal: compute ${\int_{0}^{1}\exp(h(x))\,dx}$.

Use infinitely many integrations by parts. This gives a collection of linear relations between moments of the measure ${\mu=\exp(h(x))\,dx}$. Minmaxing over unknown measure ${\mu}$ subject to these relations is a moment problem. This provides both upper and lower bounds on the integral, which converge as the number of contraints taken into account tends to infinity.

4. Positive polynomials

Hilbert’s 17th problem has a simple solution in one variable: a polynomial is ${\geq 0}$ on ${{\mathbb R}}$ iff it is a sum of squares of polynomials. However,

Theorem 4 (Artin) In several variables, a polynomial is ${\geq 0}$ on ${{\mathbb R}}$ iff it is a sum of squares of rational functions.

The differenced between nonnegative polynomials and sums of squares of polynomials, in several variables, can be quantitatively measured (Blekherman). With a fixed degree, the relative volume tends to zero as the number of variables tends to infinity.

4.1. Sums of squares

Checking wether a polynomial is a sum of square amounts to solve a set of linear matrix inequalities. Indeed, let ${v_d (X)}$ be the vector with entries all degree ${\leq d}$ monomials. Expand

$\displaystyle \begin{array}{rcl} v_d (X)v_d (X)^{\top}=\sum_{|\alpha|\leq 2d}B_{\alpha} X^{\alpha}. \end{array}$

Solve the system of linear matrix inequalities

$\displaystyle \begin{array}{rcl} \mathrm{Trace}(B_{\alpha}Q)=f_{\alpha}\,\quad Q\gg 0. \end{array}$

Then reconstruct ${P}$

Theorem 5 (Berg) Use ${\ell_1}$ norm of coefficients. Sums of squares are dense in polynomials nonnegative on ${[-1,1]^n}$.

Theorem 6 (Lasserre, Netzer) Let ${\Theta_r (X)=\sum_{i=1}^{n}X_{i}^{2r}}$. Let ${f}$ be nonnegative on ${[-1,1]^n}$. Then there exists ${r(\epsilon)}$ such that ${f+\epsilon \Theta_r}$ is a sum of squares.

Theorem 7 (Lasserre) Let ${\theta_r (X)=\sum_{k=0}^{r}\sum_{i=1}^{n}X_{i}^{2r}}$. Let ${f}$ be nonnegative on ${{\mathbb R}^n}$. Then there exists ${r(\epsilon)}$ such that ${f+\epsilon \theta_r}$ is a sum of squares.

Theorem 8 (Polyá) Let ${f}$ be nonnegative on ${(0,+\infty)^n}$. Then there exists ${r}$ such that ${f(x_1 +\cdots+x_n)^{2r}}$ has nonnegative coefficients.

This gives a certificate of nonnegativity of a polynomial on the orthant.

4.2. Theory

Theorem 9 (Krivine 1964, Stengle 1974) Let ${K}$ be a semi-algebraic set, defined by ${g_i \geq 0}$, ${h_j \not=0}$, ${f_k =0}$. Let ${P(g_1 ,\cdots, g_m)}$ be the set of polynomials in the ${g_i}$‘s with coefficients sums of squares. Let ${M(f_1 ,\cdots, f_m)}$ be monoid generated by the ${f_k}$‘s and ${I(h_1 ,\ldots,h_m)}$ the ideal generated by the ${h_j}$‘s.

Then ${K=\emptyset}$ iff there exists ${g\in P(g_1 ,\cdots, g_m)}$, ${f\in M(f_1 ,\cdots, f_m)}$ and ${h\in I(h_1 ,\cdots, h_m)}$ such that

$\displaystyle \begin{array}{rcl} g+f^2 +h=0. \end{array}$

Furthermore, there are theoretical bounds.

Note the problem is becomes an SDP. This can be used to provide a certificate that ${K}$ is empty.

4.3. The case of basic semialgebraic sets

Theorem 10 (Schmüdgen 1991) Let ${K}$ be a basic semi-algebraic set, defined by ${g_i \geq 0}$. Then a polynomial ${f}$ is positive on ${K}$ iff ${f\in P(g_1 ,\cdots, g_m)}$.

Definition 11 Let ${Q(g_1 ,\cdots, g_m)}$ be the set of linear combinations of ${g_i}$‘s with coefficient sums of squares.

Theorem 12 (Putinar, Jacobi, Prestel 1993) Let ${K}$ be a basic semi-algebraic set. Assume that there exists a constant ${M}$ such that ${M-|X|^2 \in Q(g_1 ,\cdots, g_m)}$. Then a polynomial ${f}$ is positive on ${K}$ iff ${f\in Q(g_1 ,\cdots, g_m)}$.

If one fixes an upper bound on the degree of the sum of squares, finding them is solving an SDP.

In practice, if one knows the radius of a ball that contains ${K}$ (this may happen), just add ${g_{m+1}=M-|X|^2}$ to the defining inequalities. Then the extra assumption in Theorem 12 is satisfied.

References

[KLS] Kannan, Ravi; Lovász, László; Simonovits, Miklós; Random walks and an O*(n5) volume algorithm for convex bodies. Random Structures Algorithms 11 (1997), no. 1, 1–50.

[L] Lasserre, Jean-Bernard; Moments, positive polynomials and their applications. Imperial College Press Optimization Series, 1. Imperial College Press, London, 2010.

[LPZ] Lasserre, J. B.; Prieto-Rumeau, T.; Zervos, M; Pricing a class of exotic options via moments and SDP relaxations. Math. Finance 16 (2006), no. 3, 469–494.

[M] Landau, Henry; Moments in mathematics. Papers from the American Mathematical Society annual meeting held in San Antonio, Tex., January 20?22, 1987. Edited by Henry J. Landau. Proceedings of Symposia in Applied Mathematics, 37. AMS Short Course Lecture Notes. American Mathematical Society, Providence, RI, 1987.