Polynomial OPtimization

- pop -


The POP team focuses on solving notoriously difficult and non-convex polynomial optimization problems, arising from several adjacent fields.


The team currently investigates the following research topics:

Structure exploitation

How to make the Moment-SOS hierarchy more tractable?

+

Dynamical systems with algebraic data

Extension of the Moment-SOS hierarchy to dynamical systems

+

Noncommutative POP

Polynomial optimization in non-commuting variables

+

Koopman operators, data-driven control

for control of complex nonlinear dynamical systems

+

Tropical geometry

Connections between tropical geometry and positivity certificates

+

Algebraic methods for validated optimization

Going from approximate to exact certificates

+

Application fields

Quantum, learning and energy

+

Christoffel-Darboux (CD) kernels

Borrowed to approximation theory

+

Latest publications

2024

Books

Nathanaël Fijalkow (Dir.). Games on Graphs: From Logic and Automata to Algorithms. pp.1-491, In press, ⟨10.48550/arXiv.2305.10546⟩. ⟨hal-04273394⟩

Preprints, Working Papers, ...

Igor Klep, Victor Magron, Gaël Massé, Jurij Volčič. Upper bound hierarchies for noncommutative polynomial optimization. 2024. ⟨hal-04440949⟩

Yoshio Ebihara, Noboru Sebe, Hayato Waki, Dimitri Peaucelle, Sophie Tarbouriech, et al.. Induced Norm Analysis of Linear Systems for Nonnegative Input Signals. 2024. ⟨hal-04438031⟩

Benoît Bonnet-Weill, Milan Korda. Set-Valued Koopman Theory for Control Systems. 2024. ⟨hal-04408228⟩

Jared Miller, Matteo Tacchi, Didier Henrion, Mario Sznaier. Unsafe Probabilities and Risk Contours for Stochastic Processes using Convex Optimization. 2023. ⟨hal-04382156⟩

Didier Henrion, Alessandro Rudi. Solving moment and polynomial optimization problems on Sobolev spaces. 2024. ⟨hal-04393205⟩

2023

Journal articles

Marianne Souaiby, Aneel Tanwani, Didier Henrion. Ensemble Approximations for Constrained Dynamical Systems using Liouville Equation. Automatica, 2023, 149, pp.110836. ⟨10.1016/j.automatica.2022.110836⟩. ⟨hal-03167458v3⟩

Didier Henrion, Felix Kirschner, Etienne de Klerk, Milan Korda, Jean-Bernard Lasserre, et al.. Revisiting semidefinite programming approaches to options pricing: complexity and computational perspectives. INFORMS Journal on Computing, 2023, 35 (2), pp.265-517. ⟨hal-03429272v2⟩

Victor Magron, Mohab Safey El Din, Trung-Hieu Vu. Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients. SIAM Journal on Optimization, 2023, 33 (1), ⟨10.1137/21M1436245⟩. ⟨hal-03312392⟩

Serban Belinschi, Victor Magron, Victor Vinnikov. Noncommutative Christoffel-Darboux Kernels. Transactions of the American Mathematical Society, 2023, 376, pp.181-230. ⟨10.1090/tran/8648⟩. ⟨hal-03433869⟩

Matteo Tacchi, Jean Bernard Lasserre, Didier Henrion. Stokes, Gibbs and volume computation of semi-algebraic sets. Discrete and Computational Geometry, 2023, 69 (1), pp.260-283. ⟨10.1007/s00454-022-00462-0⟩. ⟨hal-02947268v3⟩

Jean Lasserre. PELL'S EQUATION, SUM-OF-SQUARES AND EQUILIBRIUM MEASURES OF A COMPACT SET. Comptes Rendus. Mathématique, 2023, 361 (G5), pp.935-952. ⟨10.5802/crmath.465⟩. ⟨hal-03813195v2⟩

Milan Korda, Monique Laurent, Victor Magron, Andries Steenkamp. Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks. Mathematical Programming, 2023, ⟨10.1007/s10107-023-01993-x⟩. ⟨hal-03782934⟩

Khazhgali Kozhasov, Jean-Bernard Lasserre. Volumes of sublevel sets of nonnegative forms and complete monotonicity. SIAM Journal on Applied Algebra and Geometry, 2023, 7 (4), pp.10.1137/22M1502458. ⟨10.1137/22M1502458⟩. ⟨hal-03693810⟩

Jean-Bernard Lasserre. A modified Christoffel function and its asymptotic properties. Journal of Approximation Theory, 2023, ⟨10.1016/j.jat.2023/105955⟩. ⟨hal-03949201v2⟩

Adrien Le Franc, Victor Magron, Jean-Bernard Lasserre, Manuel Ruiz, Patrick Panciatici. Minimal Sparsity for Second-Order Moment-SOS Relaxations of the AC-OPF Problem. IEEE Transactions on Power Systems, 2023, pp.1 - 10. ⟨10.1109/TPWRS.2023.3333691⟩. ⟨hal-04110742v2⟩

Books

Victor Magron, Jie Wang. Sparse Polynomial Optimization: Theory and Practice. World Scientific Press. 2023, Series on Optimization and Its Applications, 978-1-80061-294-5. ⟨hal-03760501⟩

Book sections

Jean-Bernard Lasserre. Polynomial Optimization, Certificates of Positivity, and Christoffel Function. Michal Kočvara; Bernard Mourrain; Cordian Riener. Polynomial Optimization, Moments, and Applications, Springer, pp.1-20, 2023. ⟨hal-04076663⟩

Conference papers

Alban Puech, Tristan Rigaut, Adrien Le Franc, William Templier, Jean-Christophe Alais, et al.. Controlling Microgrids Without External Data: A Benchmark of Stochastic Programming Methods. IEEE PES Innovative Smart Grid Technologies Europe (ISGT EUROPE 2023), Oct 2023, Grenoble, France. ⟨10.1109/ISGTEUROPE56780.2023.10407934⟩. ⟨hal-04083666v3⟩

Mateusz Skomra. Signed Tropicalizations of Convex Semialgebraic Sets. Extended Abstracts presented at the 25th International Symposium on Mathematical Theory of Networks and Systems MTNS 2022, Sep 2022, Bayreuth, Germany. pp.697-700, ⟨10.15495/EPub_UBT_00006809⟩. ⟨hal-04273455⟩

Preprints, Working Papers, ...

Nicolas Augier, Didier Henrion, Milan Korda, Victor Magron. Symmetry reduction and recovery of trajectories of optimal control problems via measure relaxations. 2023. ⟨hal-04159304⟩

Jie Wang, Jacopo Surace, Irénée Frérot, Benoît Legat, Marc-Olivier Renou, et al.. Certifying ground-state properties of many-body systems. 2023. ⟨hal-04264341⟩

Victor Magron. Exploiting sparsity in polynomial optimization. École thématique. Luminy, France. 2023. ⟨hal-04193936⟩

Jean-Bernard Lasserre. The Moment-SOS hierarchy: Applications and related topics. 2023. ⟨hal-04201167⟩

Jean-Bernard Lasserre. CHEBYSHEV AND EQUILIBRIUM MEASURE VS BERNSTEIN AND LEBESGUE MEASURE. 2023. ⟨hal-04043186⟩

Igor Klep, Victor Magron, Jurij Volčič, Jie Wang. State polynomials: positivity, optimization and nonlinear Bell inequalities. 2023. ⟨hal-03964830⟩

Jared Miller, Milan Korda, Victor Magron, Mario Sznaier. Peak Estimation of Time Delay Systems using Occupation Measures. 2023. ⟨hal-04047493⟩

John H. Selby, Ana Belén Sainz, Victor Magron, Łukasz Czekaj, Michał Horodecki. Correlations constrained by composite measurements. 2023. ⟨hal-04117038⟩

Victor Magron, Przemysław Koprowski, Tristan Vaccon. Pourchet's theorem in action: decomposing univariate nonnegative polynomials as sums of five squares. 2023. ⟨hal-03976836⟩

Didier Henrion, Simone Naldi, Mohab Safey El Din. Algebraic certificates for the truncated moment problem. 2023. ⟨hal-03987123⟩

Didier Henrion, Milan Korda, Jean-Bernard Lasserre. POLYNOMIAL ARGMIN FOR RECOVERY AND APPROXIMATION OF MULTIVARIATE DISCONTINUOUS FUNCTIONS. 2023. ⟨hal-03986252v2⟩

Jie Wang, Victor Magron. A real moment-HSOS hierarchy for complex polynomial optimization with real coefficients. 2023. ⟨hal-04189927⟩

Didier Henrion, Milan Korda, Martin Kružík, Rodolfo Rios-Zertuche. Occupation measure relaxations in variational problems: the role of convexity. 2023. ⟨hal-04118080⟩

Yukai Tang, Jean-Bernard Lasserre, Heng Yang. Uncertainty Quantification of Set-Membership Estimation in Control and Perception: Revisiting the Minimum Enclosing Ellipsoid. 2023. ⟨hal-04311534⟩

Igor Klep, Victor Magron, Jurij Volčič. Sums of squares certificates for polynomial moment inequalities. 2023. ⟨hal-04125262⟩

Milan Korda, Victor Magron, Rodolfo Rios-Zertuche. Convergence rates for sums-of-squares hierarchies with correlative sparsity. 2023. ⟨hal-04049383⟩

Jean-Bernard Lasserre. A hierarchy of convex relaxations for the total variation distance. 2023. ⟨hal-04367575⟩

Yoshio Ebihara, Xin Dai, Victor Magron, Dimitri Peaucelle, Sophie Tarbouriech. Local Lipschitz Constant Computation of ReLU-FNNs: Upper Bound Computation with Exactness Verification. 2023. ⟨hal-04247204⟩

Didier Henrion, Maria Infusino, Salma Kuhlmann, Victor Vinnikov. Infinite-dimensional moment-SOS hierarchy for nonlinear partial differential equations. 2023. ⟨hal-04117218⟩

Didier Henrion. Geometry of exactness of moment-SOS relaxations for polynomial optimization. 2023. ⟨hal-04258249v2⟩

Jean-Bernard Lasserre, Yuan Xu. A Generalized Pell's equation for a class of multivariate orthogonal polynomials. 2023. ⟨hal-04163153⟩

Ngoc Hoang Anh Mai, Victor Magron. Sums of squares representations on singular loci. 2023. ⟨hal-04023980⟩

2022

Journal articles

Milan Korda. Stability and performance verification of dynamical systems controlled by neural networks: algorithms and complexity. IEEE Control Systems Letters, 2022, 6, pp.3265 - 3270. ⟨10.1109/LCSYS.2022.3181806⟩. ⟨hal-03441657⟩

Ngoc Hoang Anh Mai, Victor Magron. On the complexity of Putinar-Vasilescu's Positivstellensatz. Journal of Complexity, 2022, ⟨10.1016/j.jco.2022.101663⟩. ⟨hal-03820206⟩

Jean-Bernard Lasserre. Optimization on the Euclidean Unit Sphere. SIAM Journal on Optimization, 2022, 32 (2), pp.1430--1445. ⟨10.1137/21M1433150⟩. ⟨hal-03291242v2⟩

Jie Wang, Victor Magron. Exploiting Sparsity in Complex Polynomial Optimization. Journal of Optimization Theory and Applications, 2022, 192, pp.335-359. ⟨10.1007/s10957-021-01975-z⟩. ⟨hal-03178832⟩

Jie Wang, Victor Magron, Jean-Bernard Lasserre. Certifying Global Optimality of AC-OPF Solutions via the CS-TSSOS Hierarchy. Electric Power Systems Research, 2022, 213, pp.108683. ⟨10.1016/j.epsr.2022.108683⟩. ⟨hal-03351160⟩

N. H. A. Mai, Victor Magron, Jean-Bernard Lasserre. A sparse version of Reznick's Positivstellensatz. Mathematics of Operations Research, 2022, ⟨10.1287/moor.2022.1284⟩. ⟨hal-02477339⟩

Felix Huber, Igor Klep, Victor Magron, Jurij Volčič. Dimension-free entanglement detection in multipartite Werner states. Communications in Mathematical Physics, 2022, 396, pp.1051-1070. ⟨10.1007/s00220-022-04485-9⟩. ⟨hal-03322991⟩

Masahiro Ikeda, Isao Ishikawa, Corbinian Schlosser. Koopman and Perron–Frobenius operators on reproducing kernel Banach spaces. Chaos: An Interdisciplinary Journal of Nonlinear Science, 2022, 32 (12), pp.123143. ⟨10.1063/5.0094889⟩. ⟨hal-04174199⟩

Corbinian Schlosser. Converging Approximations of Attractors via Almost Lyapunov Functions and Semidefinite Programming. IEEE Control Systems Letters, 2022, 6, pp.2912-2917. ⟨10.1109/LCSYS.2022.3180110⟩. ⟨hal-03740699⟩

Adrien Le Franc, Jean-Philippe Chancelier, Michel de Lara. The Capra-subdifferential of the l0 pseudonorm. Optimization, 2022, pp.1-23. ⟨10.1080/02331934.2022.2145172⟩. ⟨hal-03505168v3⟩

Ngoc Hoang Anh Mai, Jean-Bernard Lasserre, Victor Magron, Jie Wang. Exploiting constant trace property in large-scale polynomial optimization. ACM Transactions on Mathematical Software, 2022, 48 (4), pp.1-39. ⟨10.1145/3555309⟩. ⟨hal-03079000⟩

Jean-Bernard Lasserre. ON THE CHRISTOFFEL FUNCTION AND CLASSIFICATION IN DATA ANALYSIS. Comptes Rendus. Mathématique, 2022, 360, pp.919--928. ⟨10.5802/crmath.358⟩. ⟨hal-03620965v2⟩

Nils Vreman, Paolo Pazzaglia, Jie Wang, Victor Magron, Martina Maggio. Stability of Linear Systems under Extended Weakly-Hard Constraints. IEEE Control Systems Letters, 2022, 6, pp.2900-2905. ⟨10.1109/LCSYS.2022.3179960⟩. ⟨hal-03127108⟩

Jean-Bernard Lasserre. A DISINTEGRATION OF THE CHRISTOFFEL FUNCTION. Comptes Rendus. Mathématique, 2022, 360, pp.1071--1079. ⟨10.5802/crmath.380⟩. ⟨hal-03624003v2⟩

Conference papers

Yoshio Ebihara, Hayato Waki, Noboru Sebe, Victor Magron, Dimitri Peaucelle, et al.. L 2+ Induced Norm Analysis of Continuous-Time LTI Systems Using Positive Filters and Copositive Programming. European Control Conference (ECC 2022), Jul 2022, Londres, United Kingdom. ⟨10.23919/ECC55457.2022.9838085⟩. ⟨hal-03740522⟩

Jean-Bernard Lasserre. Optimization of Polynomials with Sparsity Encoded in a Few Linear Forms. 25th International Symposium on Mathematical Theory of Networks and Systems (MTNS 2022), Sep 2022, Beyreuth, Germany. pp.383-387. ⟨hal-03628891⟩

Master thesis

Srećko Ðurašinović. The Christoffel function for supervised learning: theory and practice. Machine Learning [stat.ML]. 2022. ⟨hal-03768886⟩

Autres documents

Jean B Lasserre. Moment-SOS Hierarchies. Encyclopedia of Optimization, 2022, pp.1-7. ⟨10.1007/978-3-030-54621-2_740-1⟩. ⟨hal-04054990⟩

Corbinian Schlosser. Converging approximations of attractors via almost Lyapunov functions and semidefinite programming. 2022. ⟨hal-04174217⟩

Preprints, Working Papers, ...

Matthias Preindl, Luiz Fernando Lavado Villa, Liwei Zhou, Matthew Jahnes, Jean Alinei. ITEC+EATS 2022 Short Course Software-Defined Power Electronics: Theory and Study Cases. Doctoral. ITEC + EATS Conference 2022 Anaheim, CA, United States. 2022, pp.139. ⟨hal-04430648⟩

Antonio Bellon, Didier Henrion, Vyacheslav Kungurtsev, Jakub Mareček. Time-Varying Semidefinite Programming: Geometry of the Trajectory of Solutions. 2022. ⟨hal-03196925v2⟩

Victor Magron, Ngoc Hoang Anh Mai, Yoshio Ebihara, Hayato Waki. Tractable semidefinite bounds of positive maximal singular values. 2022. ⟨hal-03580048⟩

Georg Loho, Mateusz Skomra. Signed tropical halfspaces and convexity. 2022. ⟨hal-03765509⟩

Mateusz Skomra. Optimal bounds for bit-sizes of stationary distributions in finite Markov chains. 2022. ⟨hal-03765666⟩

Ngoc Hoang Anh Mai, Victor Magron, Jean-Bernard Lasserre, Kim-Chuan Toh. Tractable hierarchies of convex relaxations for polynomial optimization on the nonnegative orthant. 2022. ⟨hal-03776853⟩

Milan Korda, Jean-Bernard Lasserre, Alexey Lazarev, Victor Magron, Simone Naldi. Urysohn in action: separating semialgebraic sets by polynomials. 2022. ⟨hal-03712510⟩

Kévin Ducharlet, Louise Travé-Massuyès, Jean-Bernard Lasserre, Marie-Véronique Le Lann, Youssef Miloudi. Leveraging the Christoffel-Darboux Kernel for Online Outlier Detection. 2022. ⟨hal-03562614⟩

2021

Autres documents

Corbinian Schlosser, Milan Korda. Sparsity structures for Koopman operators. 2021. ⟨hal-04174190⟩

Preprints, Working Papers, ...

Victor Magron, Jie Wang, Corbinian Schlosser, Milan Korda. Exploiting Term Sparsity in Moment-SOS hierarchy for Dynamical Systems. 2021. ⟨hal-03439458⟩

Abhishek Bhardwaj, Igor Klep, Victor Magron. Noncommutative Polynomial Optimization. 2021. ⟨hal-03333504⟩

Ngoc Hoang Anh Mai, Victor Magron, Jean-Bernard Lasserre. A hierarchy of spectral relaxations for polynomial optimization. 2021. ⟨hal-03149938⟩

2020

Preprints, Working Papers, ...

Jared Miller, Didier Henrion, Mario Sznaier. Peak Estimation and Recovery with Occupation Measures. 2020. ⟨hal-02937464⟩

Corbinian Schlosser, Milan Korda. Sparse moment-sum-of-squares relaxations for nonlinear dynamical systems with guaranteed convergence. 2020. ⟨hal-03059465⟩

Daniel Wagner, Didier Henrion, Martin Hromčík. Measures and Linear Matrix Inequalities for Verification and Validation of a Flexible Aircraft with Adaptive Control. 2020. ⟨hal-02939504⟩

Jie Wang, Victor Magron, Jean B Lasserre, Ngoc Hoang Anh Mai. CS-TSSOS: Correlative and term sparsity for large-scale polynomial optimization. 2020. ⟨hal-02566472⟩

Grigory Devadze, Victor Magron, Stefan Streif. Computer-assisted proofs for Lyapunov stability via Sums of Squares certificates and Constructive Analysis. 2020. ⟨hal-02873040⟩

International

Editorial activities

Series on Optimization and Its Applications, World Scientific (Jean-Bernard Lasserre)

AE SIAM J on Optimization (Didier Henrion)

AE Mathematics of Controls, Signals and Systems (Didier Henrion)

IFAC TC Robust Control (Didier Henrion)

IEEE-CSS TC RoCS (Didier Henrion)

National

Vice-Chair of the Scientific Committee on Foundations of Numerics for the French National Research Agency ANR 2021-2022 (Didier Henrion)

Member of the Scientific Board of the International Center of Mathematics and Computer Science in Toulouse 2019-2022 (Didier Henrion)

ANITI chair Polynomial optimization for machine learning 2019-2023 (Senior chair: Jean-Bernard Lasserre, Junior chair members: Milan Korda and Victor Magron)

SMAI-MODE Committee 2018-2022 (Victor Magron)

Math-Info Toulouse seminar organizer (Mateusz Skomra)

SPOT Toulouse optimization seminar, organization committee (Victor Magron)

BrainPOP Brainstorming days on measure and polynomial optimization, organization committee (Milan Korda)

Awards

CNRS Bronze medal (Didier Henrion 2004 and Victor Magron 2023)

Lagrange Prize in Continuous Optimization (Jean-Bernard Lasserre 2009)

ERC-Advanced Grant TAMING project (Jean-Bernard Lasserre 2014)

L. Khachyan Prize for lifetime achievement, Optimization Society of INFORMS (Jean-Bernard Lasserre 2015)

John von Neumann Theory Prize INFORMS Society (Jean-Bernard Lasserre 2015)

Invited Speaker at International Congress of Mathematicians 2018, Rio de Janeiro, Brasil (Jean-Bernard Lasserre 2018)

Grand Prix INRIA-Académie des Sciences (Jean-Bernard Lasserre 2021)

The team members have been implementing several  software packages  with open-source tools, released under free licenses. Advantages of this policy include the free access to source-code information, collaboration across academic partners without compromising the design of quality software and content for peer-reviewing. We present below a non-exhaustive list of these software libraries.

Numerical software

GloptiPoly3: Moments, optimization and semidefinite programming. Matlab parser for generalized problems of moments. Allows to build and solve convex linear matrix inequality (LMI) relaxations of the (generally non-convex) global optimization problem of minimizing a multi-variable polynomial function subject to polynomial inequality, equality or integer constraints.  Can be freely downloaded and used. Developed by/with the help of: Didier Henrion, Jean-Bernard Lasserre and Johan Löfberg (Linköping University).

TSSOS: This is an open source Julia library developed for large-scale polynomial optimization, based on the sparsity adapted moment-SOS hierarchies. Related modules can perform complex polynomial optimization, eigenvalue/trace optimization of noncommutative polynomials, compute joint spectral radii for stability analysis, approximate attractors and invariants of sparse dynamical systems. Developed by/with the help of: Victor Magron, Jie Wang (Chinese Academy of Sciences, Beijing).

Validated computing software

We propose efficient numerical routines together with sure and reasonably tight error bounds. Applications include  computer aided proofs, certification of numerical results in safety-critical control systems (e.g. cyber-physical systems).

RealCertify:  Maple package to tackle the problem of deciding the non-negativity of rational polynomials over semi-algebraic domains defined by polynomial constraints with rational coefficients.
This is done by computing sum of squares certificates of non-negativity for inputs where such certificates hold over the rational numbers.
It can be applied to numerous problems coming from engineering sciences, program verification and cyber-physical systems.
It is based on hybrid symbolic-numeric algorithms relying on semi-definite programming. Developed by/with the help of: Victor Magron, Mohab Safey El Din (Sorbonne University).

SPECTRA: a Maple library which aims at finding at least one point in a spectrahedron, using exact arithmetic. SPECTRA should be used for small-dimension problems. It should not be considered as a competitor to numerical algorithms such as interior-point methods for semidefinite programming (SDP).
Contrary to numerical algorithms which are based on approximate computations and floating point arithmetic, SPECTRA is exclusively based on computations with exact arithmetic, and hence it should be primarily used either in potentially degenerate situations, for example when it is expected that the spectrahedron has empty interior, or when a rigorous certificate of infeasibility or feasibility is required.
Developed by/with the help of: Didier Henrion, Simone Naldi (XLIM Limoges), Mohab Safey El Din (Sorbonne University).

OTHER TEAMS OF DEPARTMENT

REJOINDRE

Notre équipe de recherche

Pour plus d’informations sur les offres d’emploi, vous pouvez contacter