The 1st defence of POEMA ESR is Andrew Ferguson at Sorbonne University on the topic of "Exact Algorithms for Polynomial Optimisation".
The defence will take place on Monday 24th October at 14:00 in room 55-65, 211 at the Jussieu campus of Sorbonne Université and will be conducted in English. It will be followed by a small pot at LIP6 in room 24-25, 405.
Additionally, the defence will be broadcast over zoom via the following link:
https://cnrs.zoom.us/j/96450173418?pwd=dWgvbi9oTS9pTlhCYUt2aXFTWEEvQT09
Meeting ID: 964 5017 3418
Passcode: bpe4hr
The jury is composed of:
- Victor Magron (reviewer), CNRS
- Cordian Riener (reviewer), University of Tromsø
- Alin Bostan (examinator), INRIA
- Bruno Escoffier (examinator), Sorbonne Université
- Hamza Fawzi (examinator), University of Cambridge
- Fatemeh Mohammadi (examinator), KU Leuven
- Jérémy Berthomieu (advisor), Sorbonne Université
- Mohab Safey El Din (advisor), Sorbonne Université
Abstract:
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.
Résumé :
Dans cette thèse, nous nous appuyons sur la méthode dite des points critiques pour calculer une représentation exacte de l'infimum d'un polynôme restreint à un ensemble algébrique. Dans un premier temps, nous démontrons une amélioration de la complexité du calcul des valeurs critiques par une étude approfondie du calcul de bases de Gröbner. À l'aide de ces techniques, nous établissons une méthodologie pour étudier de nombreux problèmes connexes, y compris certains qui se posent dans l'approche des sommes de carrés (SOS) de l'optimisation polynomiale. Ensuite, le cadre permettant de traiter les domaines non compacts repose sur des valeurs critiques généralisées qui donnent une généralisation du théorème de fibration d'Ehresmann aux situations non propres. En suivant les travaux de Kurdyka, Orro et Simon, nous concevons des algorithmes efficaces pour calculer ces valeurs en un temps simplement exponentiel en la dimension de l'espace ambiant. Enfin, nous établissons de premiers résultats en vue de la compréhension de la structure algébrique des décompositions SOS de polynômes.
