PhD graduated
Team : PolSys
    Sorbonne Université - LIP6
    Boîte courrier 169
    Couloir 26-00, Étage 3, Bureau 325
    4 place Jussieu
    75252 PARIS CEDEX 05

Tel: +33 1 44 27 88 43, Andrew.Ferguson (at) nulllip6.fr

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 - 14h - Campus Pierre et Marie Curie, Salle Jacques Pitrat (25-26/105)

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é

2021-2022 Publications