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.

2021-2024 Publications

• 2024
  • A. Ferguson, G. Ottaviani, M. Safey El Din, E. Turatti : “On the degree of varieties of sum of squares”, Journal of Pure and Applied Algebra, (Elsevier) (2024)
• 2022
  • A. Ferguson : “Exact Algorithms for Polynomial Optimisation”, thesis, phd defence 10/24/2022, supervision Safey el din, Mohab, co-supervision : Berthomieu, Jérémy (2022)
  • J. Berthomieu, A. Bostan, A. Ferguson, M. Safey El Din : “Gröbner bases and critical values: The asymptotic combinatorics of determinantal systems”, Journal of Algebra, vol. 602, pp. 154-180, (Elsevier) (2022)
  • A. Ferguson, H. Le : “Finer Complexity Estimates for the Change of Ordering of Gröbner Bases for Generic Symmetric Determinantal Ideals”, Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation (ISSAC '22), Villeneuve-d'Ascq, France, pp. 9 (2022)
  • J. Berthomieu, A. Ferguson, M. Safey El Din : “Computing the set of asymptotic critical values of polynomial mappings from smooth algebraic sets”, (2022)
• 2021
  • J. Berthomieu, A. Ferguson, M. Safey El Din : “On the computation of asymptotic critical values of polynomial maps and applications”, (2021)
  • J. Berthomieu, A. Ferguson, M. Safey El Din : “Towards fast one-block quantifier elimination through generalised critical values”, ACM Communications in Computer Algebra, vol. 54 (3), Kalamata, Greece, pp. 109-113, (Association for Computing Machinery (ACM)) (2021)