Direction de recherche : Mohab SAFEY EL DIN

Co-encadrement : BERTHOMIEU Jérémy

Algorithmes exacts pour l'optimisation polynomiale

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.

Publications 2021-2024

• 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”, soutenance de thèse, soutenance 24/10/2022, direction de recherche Safey el din, Mohab, co-encadrement : 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)