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:

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:

- In Computer Vision and Pattern Recognition : 

- In Computer GraphicsHexahedral mesh repair via Sum-of-Squares relaxations. Z. Marschner, D. Palmer, P. Zhang, J Solomon, Eurographics Symposium on Geometry Processing 39, No 5, pp. 133--147, 2020

- In IoT Signal Processing for radar applications: Localization with 1-Bit passive radars in Narrow Band IoT-applications using multivariate polynomial optimizationSaeid Sedighi, Kumar Vijay Mishra, Bhavani Shankar M. R., Björn Ottersten (2021), IEEE Transactions on Signal Processing 69, pp. 2525--2540. 

- In Signal Processing for Super-Resolution, extending seminal work of Candès & Fernandez-Granda: Exact solutions to Super Resolution on semi-algebraic domains in higher dimensions, De Castro Y, Gamboa F,  Henrion D., Lasserre J.B. (2017) , IEEE Trans. Info. Theory  63,  pp. 621--630, and also:

  •  Low Complexity Beamspace Super Resolution for DOA Estimation of Linear Array, Pan Jie, Fu Jiang, Sensors 20, No 8, 2020.
  • Sparse signal reconstruction for nonlinear models via piecewise rational optimization, A. Marmin, M. Castella, J-C. Pequet, L. Duval, Signal Processing 179, 2021

In Statistics for Optimal DesignApproximate Optimal Designs for Multivariate Polynomial Regression, De Castro Y, Gamboa F,  Henrion D., Hess R., Lasserre J.B. (2019) , Annals of Statistics 47, pp. 125--157.

In Machine Learning for Certification of Robustness for Neural NetworksLipschitz Constant Estimator of Neural Networks via Sparse Polynomial OptimizationF. Latorre, P. Rolland,  V. CevherICLR, December 2020.

- In Physics for bounding ground-state energy of interacting particule systems: Moment methods in energy minimization: New bounds for Riesz minimal energy problems, D. de Laat, Trans. Amer. Math. Soc. 373, pp. 1407--1453, 2020

- In Quantum Information for several problems in entanglement theory: Complete hierarchies of efficient approximations to problems in entanglement theoryJens Eisert, Philipp Hyllus, Otfried Gühne, and Marcos CurtyPhysical Review A 70, 062317, 2004, and  Ruling out static latent homophily in citation networks, P. Wittek, S. Darany, l G. NelhansScientometrics 110(2), pp. 765--777, 2016, Semi-device-independent self-testing of unsharp measurments, N. Miklin, J. Borkala, M. PawlowskiPhysical Review Research 2, pp. 033014, 2020. Correlations constrained by compsite measurement,   Lukasz Czekaj, Ana Bel´en Sainz, John H. Selby, an Michal HorodeckiPArXiv:2009.04994, 2020. 

- in traffic networks for bounding travel time: Moment-based travel time reliability assessment with Lasserre's relaxation, Xiangfeng Ji, Xuegang (Jeff) Ban, Jian Zhang, Bin Ran, Transportmetrica B: Transport Dynamics 7(1), pp. 401--422, 2019

- In models for control of chemo and immunotherapy: Robust Optimal Control-based Design of Combined Chemo-and-Immunotherapy Delivery Profile, K. Moussa, M. Fiacchini, M. Alamir, IFAC Papers On Line 52-26 (2019), pp.  76–81

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 book :

The Moment-SOS Hierarchy:

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

by D. Henrion, M. Korda and J.B. Lasserre, World Scientific Publishing, Singapore, 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).