PhD graduated
Team : PolSys
Departure date : 09/30/2022

Supervision : Mohab SAFEY EL DIN

Co-supervision : BERTHOMIEU Jérémy

Exact Algorithms for Polynomial Optimisation

In this thesis, we shall rely on the so-called critical point method to compute an exact representation of the infimum of a polynomial restricted to an algebraic set. Firstly, we demonstrate an improvement in the complexity of computing the critical values by a close study of Gröbner bases computations. Using these techniques, we lay out a methodology to study many related problems, including some that arise in the popular sums of squares (SOS) approach to polynomial optimisation. Then, the framework allowing one to handle non-compact domains relies on generalised critical values which give a generalisation of Ehresmann’s fibration theorem to non-proper situations. Following the works of Kurdyka, Orro and Simon, we design efficient algorithms for computing said values within time singly exponential in the dimension of the ambient space. Finally, we give the first steps towards an understanding of the algebraic structure of SOS decompositions of polynomials.

Defence : 10/24/2022

Jury members :

Victor Magron, CNRS [Rapporteur]
Cordian Riener, University of Tromsø [Rapporteur]
Alin Bostan, INRIA
Bruno Escoffier, Sorbonne Université
Hamza Fawzi, University of Cambridge
Fatemeh Mohammadi, KU Leuven
Jérémy Berthomieu, Sorbonne Université
Mohab Safey El Din, Sorbonne Université

Departure date : 09/30/2022

2021-2024 Publications