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:

and also its impact in extremal discrete geometry (e.g. for sphere packing problems and/or energy minimization) as described in the workshop ``Three days of computational methods for extremal discrete geometry" (University of Cologne, Germany, 2022)

 

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. 28 (2018), pp. 1017--1048

  • Deciding robust feasibility and infeasibility using a set containment approach: An application to stationary passive gas network operations, D. Haussmann, F. Liers, M. Stingl,  J.C. Vera, SIAM J. Optim. 28 (2018), pp. 2489--2517

  • 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

  • Structural impact of the start-up sequence on Pelton turbines lifetime: Analytical prediction and polynomial optimization, A.L Alerci, E. Vagnoni, M. Paolone, Renewable Energy 218, 119341, 2023.

- In Computer Vision, Geometric perception and Pattern Recognition : 

  • 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.​​
  • Certifiably optimal and robust camera pose estimation from points and lines, Lei Sun, Zhongliang Deng,  IEEE Access, 2020.
  • In perfect shape: Certifiably optimal 3D shap reconstruction from 2D landmarks, Heng Yang, L. Carlone,  Proceedings of teh IEEE/CVR conference on Computer Vision and Pattern Recognition, (CVPR), pp. 621--630, 2020

  • TEASER: Fast and Certifiable Point Cloud Registration. H. Yang, J. Shi, and L. Carlone. IEEE Trans. Robotics, 2020.

  • Self-supervised geometric perception. H. Yang, W. Dong, L. Carlone, and V. Koltun. In IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), pp. 14350–14361, 2021. 

  • Certifiable Outlier-Robust Geometric Perception: Exact Semidefinite Relaxations and Scalable Global Optimization. H. Yang and L. Carlone. arXiv:2109.0334 (2021)

    ​Optimal and Robust Category-Level Perception: Object Pose and Shape Estimation From 2-D and 3-D Semantic Keypoints. Jingnan Shi, H. Yang and L. Carlone. IEEE Trans. Robotics 39(5), 2023

- In Computer Graphics: Hexahedral 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 Geometry Processing: Sum-of-Squares Geometry Processing. Z. Marschner, D. Palmer, P. Zhang, J Solomon, ACM Transactions on Graphics 40 (6), pp. 1--13, 2021

- In IoT Signal Processing for radar applications: Localization with 1-Bit passive radars in Narrow Band IoT-applications using multivariate polynomial optimization, Saeid 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 Design: Approximate 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 Networks: Lipschitz Constant Estimator of Neural Networks via Sparse Polynomial Optimization, F. Latorre, P. Rolland,  V. Cevher, ICLR, 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, and also in Ising models in Bootstrap, Markov chain Monte Carlo, and LP/SDP hierarchy for the lattice Ising model, Minjae Cho and Xin Sun, J. High Energy Physics, 2023

- In Chemistry for deriving bounds on stochastic chemical kinetic systems: Dynamics bounds on stochastic chemical  kinetic systems using semidefinite programming, G.R. Dowdy, P. I. Barton, J. Chemical Physics 149, 74103, 2018, and Tighter bounds on transient moments of stochastic chemical  systems, F. Holtorf, P. I. Barton, J. Optimization Theory & Applications, 2023

- In Quantum Information for several problems in entanglement theory: Complete hierarchies of efficient approximations to problems in entanglement theory, Jens Eisert, Philipp Hyllus, Otfried Gühne, and Marcos Curty, Physical Review A 70, 062317, 2004, and  Ruling out static latent homophily in citation networks, P. Wittek, S. Darany, l G. Nelhans, Scientometrics 110(2), pp. 765--777, 2016, Semi-device-independent self-testing of unsharp measurments, N. Miklin, J. Borkala, M. Pawlowski, Physical Review Research 2, pp. 033014, 2020. Correlations constrained by composite measurement,   Lukasz Czekaj, Ana Bel´en Sainz, John H. Selby, and Michal Horodecki, PArXiv:2009.04994, 2020. Verifying the output of quantum optimizers ground-state energy lower bounds, F. Bacari, C. Gogolin, P. Wittek and A. Acin, Physical Review Research 2, 043163, 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

- In Engineering for battery fast-charging:  Discretisation-free battery fast-charging optimisation using  the measure-moment approach, N.E. Courtier, R. Drummond, P. Ascensio, L.D. Couto, D.A. Howey, 2022 European Control Conference (ECC), July 2022, London, UK, pp.  628--634, 2022

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, and risk theory. See for instance:

- In management of hydropower plants : Structural impact of the start-up sequence on Pelton turbines lifetime:  Analyticla prediction and polynomial optimization, A.L. Alerci, E. Vagnoni, M. Paolone, Renewable Energy, 2023

- In Optimal Transport : 

 

The method is also 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).