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
, given real symmetric matrices. Unknown is a real vector . Problem: minimize a linear functional subject to the constraint that is positive semidefinite.
The dual problem is to maximize Trace over matrices subject to the constraints that is positive semidefinite and Trace for all .
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 of ,
- real semialgebraic set.
- discrete cube.
Usually, people are happy with local minima.
2.1. Primal point of view
Proposition 1 Let denote the set of probability measures on supported on .
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 denote the set of probability measures on supported on .
We need practical criteria to express constraints, either the fact that a measure is supported by , or that a function is nonnegative on . These do not exist in full generality, but exist when is a compact basic semialgebraic set, and a polynomial (or more generally semialgebraic).
2.3. Basic semialgebraic sets
Definition 3 A subset 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 ,
- a polynomial to be positive on .
In both cases, these conditions translate into Linear Matrix Inequalities, or Linear Inequalities satisfied by the Moments
of (and not 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 , functions . Unknown: a finite measure on . Goal: minimize subject to constraints .
This problem was popular in the early XXth century, and solved in the -dimensional case. It encompasses many problems in applied mathematics, see [M]. I give examples.
3.1. Convex envelope
Data: a set , a function ( ouside ). Output: the largest convex function on such that .
Data: a set , a Borel subset . Output: an estimate on , assuming certain moments of the random variable 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 . The corresponding moments are known. Write Lebesgue measure as where is supported on and on . Then
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 on . Goal: compute .
Use infinitely many integrations by parts. This gives a collection of linear relations between moments of the measure . Minmaxing over unknown measure 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 on iff it is a sum of squares of polynomials. However,
Theorem 4 (Artin) In several variables, a polynomial is on 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 be the vector with entries all degree monomials. Expand
Solve the system of linear matrix inequalities
Theorem 5 (Berg) Use norm of coefficients. Sums of squares are dense in polynomials nonnegative on .
Theorem 6 (Lasserre, Netzer) Let . Let be nonnegative on . Then there exists such that is a sum of squares.
Theorem 7 (Lasserre) Let . Let be nonnegative on . Then there exists such that is a sum of squares.
Theorem 8 (Polyá) Let be nonnegative on . Then there exists such that has nonnegative coefficients.
This gives a certificate of nonnegativity of a polynomial on the orthant.
Theorem 9 (Krivine 1964, Stengle 1974) Let be a semi-algebraic set, defined by , , . Let be the set of polynomials in the ‘s with coefficients sums of squares. Let be monoid generated by the ‘s and the ideal generated by the ‘s.
Then iff there exists , and such that
Furthermore, there are theoretical bounds.
Note the problem is becomes an SDP. This can be used to provide a certificate that is empty.
4.3. The case of basic semialgebraic sets
Theorem 10 (Schmüdgen 1991) Let be a basic semi-algebraic set, defined by . Then a polynomial is positive on iff .
Definition 11 Let be the set of linear combinations of ‘s with coefficient sums of squares.
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 (this may happen), just add to the defining inequalities. Then the extra assumption in Theorem 12 is satisfied.
[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.