Moments and Positive Polynomials

We are interested in the very rich  theory of moments and its dual facet, that of positive polynomials. We have been a pioneer in the development of what is called the Moment-SOS hierarchy (see also the Lasserre hierarchy and Sum-of-Square Optimization), and notably for global optimization. This approach is very natural and the resulting hierarchy of semidefinite relaxations perfectly matches both sides of the same theory, namely the theory of moments and its dual theory of positive polynomials. As a by-product one also obtains Karush-Kuhn-Tucker global optimality conditions, in which the multipliers are nonnegative polynomials instead of scalars as in the usual (local) optimality conditions. In fact the Moment-SOS hierarchy also applies to solving the Generalized Moment Problem (GMP) (with polynomial data) whose list of important applications is endless. In fact, global polynomial optimization is the simplest instance. To appreciate the impact of this methodology in and outside optimization, see for instance:

  • Optimization over polynomials: Selected Topics, M. Laurent, Proceedings of ICM 2014 Congress, Seoul, 2014.

and especially for its impact in Combinatorial Optimization and Theoretical Computer Science, see for instance:

  • Sum-of-Squares proofs and the quest toward optimal algorithms, B. Barak and D. Steurer, Proceedings of ICM 2014 Congress, Seoul, 2014.
  • Candidate Lasserre Integrality Gap For Unique Games, S. Khot and D. Mohskovitz, Electronic Colloquium on Computational Complexity, Report No. 142 (2014).
  • High dimensional estimation via Sum-of-Squares proofs, D. Steurer, Proceedings of ICM 2018 Congress, Rio de janeiro
  • The Moment-SOS Hierarchy, J.B. Lasserre, Proceedings of ICM 2018 Congress, Rio de Janeiro

In particular this methodology has been used:

for Motion Planning in Robotics. See the algorithm NUROA ( Numerical Roadmap Algorithm) and the associated paper:
NUROA: A Numerical Roadmap Algorithm, Reza Iraji, Hamidreza Chitsaz. Proceedings IEEE CDC Conference, Los Angeles, December 20214. arXiv:1403.5384
For solving the Optimal Power Flow Problem, an important problem for the optimal management of energy networks. See e.g. the recent papers:

  • Advanced optimization methods for power systems, P. Panciatici, M.C. Campi, S. Garratti, S.H. Low, D.K. Molzhan, A.X. Sun and L. Wehenkel. Proceedings 18th Power Systems Computation Conference, Wroclaw, Poland, August 2014.
  • Sparsity-Exploiting Moment-Based Relaxations of the Optimal Power Flow Problem, D.K. Molzahn and I.A. Hiskens, IEEE Transactions on Power Systems, 2015. arXiv:1404.5071
  • Global Optimization for power dispatch problems based on theory of moments, J. Tian, H. Wei and J. Tan, Electrical Power and Energy Systems 71, 2015, pp. 184--194.
  • Lasserre hierarchy for large-scale polynomial optimization in real and complex variabales, D. Molzahn, C. Josz, SIAM J. Optim. (2018), pp. 1017--1048
  • Moment-SOS relaxation of the medium term hydrothermal dispatch problem, F. Cicconet, K.C. Almeida, Int. J. Elec. Power & Energy Systems 104, pp. 124--133, 2019

- In computer vision: Convex Relaxations for Consensus and Non-Minimal Problems in 3D Vision, T. Probst, D. Dani Paudel, A. Chhatkuli, L. Van Gool,,  IEEE Int. Conf. Comp. Vision (ICCV), 2019, pp. 10233-10242.

- In IoT Signal Processing for radar applications: Localization performance of 1-Bit passive radars in NB-IoT-applicationsSaeid Sedighi, Kumar Vijay Mishra, Bhavani Shankar Mysore R, Björn Ottersten, IEEE CAMSAP 2019 Conference, December 2019, , Guadeloupe.

This approach also permits to obtain (numerically) bounds on measures that satisfy pre-specified moment conditions. As a consequence we can apply these techniques to provide upper and lower bounds in several problems of performance evaluation. For instance, for option pricing models in financial mathematics based on diffusions (such as Black and Scholes, Ornstein-Ulhenbeck, Cox-Ingersoll interest models) we may obtain good  upper and lower bound on e.g. Asian and Barrier options. The method is generic to diffusion type models. It can be also applied (and provides a new methodology) :

  • For solving weak formulations of Optimal Control problems and of a class of non-linear hyperbolic PDEs (e.g. the Burgers equation).
  • For solving some problems in computational geometry and probability (e.g. Lebesgue and/or Gaussian volume of semi-algebraic sets, Lebesgue decomposition of a measure).
  • For modelling chance-constraints (or probabilistic constraints) and distributionally robust chance-constraints in control or optimization under uncertainty.
  • For Super-Resolution in Signal Processing, i.e.,  to recover a sparse signal (an atomic signed measure) from a few moments. 
  • For Optimal Design in Statistics, 

to cite a few of its applications, some described in the forthcomming book :

The Moment-SOS Hierarchy:

Lectures in Lectures in Probability, Statistics, Computational Geometry, Control and Nonlinear PDEs

by M. Korda, D. Henrion and J.B. Lasserre, World Scientific Publishing, Singapore, to appear in 2020.

More generally, we are also interested in all aspects of positivity of polynomials (and even semi-algebraic functions) on basic semi-algebraic sets, including certificates of positivity with tractable characterization (to be amenable to practical computation).