Moments, Positive Polynomials and Their Applications

The following sections are included:

• Preface

• Acknowledgments

• Contents

We describe the abstract basic Generalized Moment Problem (GMP) and its dual with a few examples. We also provide some general results concerning the GMP with polynomial data and its dual and show why the theory of moments and its dual theory of positive polynomials can be useful to solve the GMP.

We review basic results of real algebraic geometry on the representation of positive polynomials, among which are the fundamental Positivstellensatz of Krivine, Stengle, Schmüdgen, Putinar and Jacobi and Prestel. We also provide some additional representation results that take into account several specific cases like finite varieties, convex semi-algebraic sets, representations that preserve sparsity, etc.

Most results of this chapter are the dual analogues of those described in Chapter 2. Indeed the problem of representing polynomials that are positive on a set 𝕂 has a dual facet which is the problem of characterizing sequences of reals that are moment sequences of some finite Borel measure supported on 𝕂. Moreover, as we shall see, this beautiful duality is nicely captured by standard duality in convex analysis, applied to some appropriate convex cones of ℝ[x]. We review basic results in the moment problem and also particularize to some specific important cases like in Chapter 2.

We describe a general methodology to solve the abstract generalized moment problem (GMP). That is, we provide a hierarchy of semidefinite relaxations whose associated sequence of optimal values converges to the optimal value of the basic GMP. Variants of this methodology are also provided to handle additional features such as countably many moment constraints, several measures, or GMP wih sparsity properties. This chapter should allow the reader to understand the basic idea underlying the methodology that permits to solve (or approximate) a problem formulated as a particular instance of the GMP.

This chapter is on global optimization, probably the simplest instance of the generalized moment problem. We detail the semidefinite relaxations of Chapter 4 for minimizing a polynomial on ℝⁿ and on a compact basic semi-algebraic set. We also discuss the linear relaxations and several particular cases, e.g. when 𝕂 is a polytope or a finite variety. In particular, this latter case encompasses all 0 – 1 discrete optimization problems.

This chapter is about solving systems of polynomial equations. Of course if the goal is to search for just one solution, one may minimize any polynomial criterion and see the problem as the global optimization of Chapter 5. But we also consider the case where one searches for all complex and/or real solutions and show that the moment approach is well-suited to solve this problem as it provides the first algorithm to compute all real solutions without computing all the complex solutions, in contrast with the usual algebraic approaches based on Gröbner bases or homotopy.

This chapter covers some applications in probability. We first consider the problem of computing an upper bound on μ(S) over all measures μ that satisfy certain moment conditions. We then consider the problem of computing (or at least approximating) the volume of a compact basic semi-algebraic set. We end up with the mass-tranfer (or Monge-Kantorovich) problem.

This chapter is about Markov chains and invariant probabilities. We first address the problem of computing an upper bound on μ(S) over all invariant probability measures μ of a given Markov chain on ℝⁿ. We then consider the problem of approximating the value of an ergodic criterion, as an alternative to simulation which only provides a random estimate.

This chapter considers an application in mathematical finance, namely the pricing of some exotic options. First under a no-arbitrage assumption and knowledge of some moments of the distribution of the underlying asset price. Then when one assumes that the asset price obeys some Ito's stochastic differential equation.

This chapter considers an application in control. We apply the moment approach to the so-called weak formulation of optimal control problems in which the initial problem is viewed as an infinite linear-programming model over suitable occupation measures, an instance of the generalized moment problem.

This chapter considers the following problem: Given a rational function f on a basic semi-algebraic set 𝕂, evaluate at a particular point x in the domain of the convex envelope of f. We then consider the semi-definite representation of the convex hull co(𝕂) of 𝕂. That is, finding a set defined by linear matrix inequalities in a lifted space, such that co(𝕂) is a projection of that set.

This chapter considers the problem of approximating multivariate integrals of rational functions or exponentials of a polynomial, on a compact basic semi-algebraic set. We also describe the moment approach as a tool for evaluating gradients or Hesssians in the maximum entropy approach for estimating an unknown density based on the knowledge of its moments.

This chapter considers some min-max problems, as well as the minimization of the supremum of finitely many rational functions on a compact basic semi-algebraic set. Then this is used to compute (or approximate) the value of Nash equilibria for N-player finite games. We end up with applying the moment approach to polynomial games.

This chapter applies the moment approach to provide bounds on functionals of solutions of linear partial differential equations with boundary conditions and polynomial coefficients.

The following sections are included:

• Final Remarks

• Appendix A Background from Algebraic Geometry
  • Fields and Cones
  • Ideals
  • Varieties
  • Preordering
  • Algebraic and Semi-algebraic Sets over a Real Closed Field
  • Notes and Sources

• Appendix B Measures, Weak Convergence and Marginals
  • Weak Convergence of Measures
  • Measures with Given Marginals
  • Notes and Sources

• Appendix C Some Basic Results in Optimization
  • Non Linear Programming
  • Semidefinite Programming
  • Infinite-dimensional Linear Programming
  • Proof of Theorem 1.3
  • Notes and Sources

• Appendix D The GloptiPoly Software
  • Presentation
  • Installation
  • Getting started
  • Description
    • Multivariate polynomials (mpol)
    • Measures (meas)
    • Moments (mom)
    • Support constraints (supcon)
    • Moment constraints (momcon)
    • Floating point numbers (double)
  • Solving Moment Problems (msdp)
    • Unconstrained minimization
    • Constrained minimization
    • Several measures
  • Notes and Sources

• Glossary

• Bibliography

• Index