Vu Trung Hieu at Sorbonne University will have his PhD defense entitled "Certified polynomial optimization based on exact sum of squares decompositions".
The defense will take place on Friday 9th December 2022 at 9:00 in room 25-26/105 at the Jussieu campus of Sorbonne Université and will be conducted in English. It will be followed by a pot de thèse in room 26-00/326.
The defense is accessible over Zoom via the following link:
https://cnrs.zoom.us/j/91614637167?pwd=RDdQL1NKTml5OXNWaEJ0bEJPanlwUT09
Meeting ID: 916 1463 7167
Passcode: BQ7QPZ
The jury is composed of:
- Bernard MOURRAIN (reviewer), Inria Sophia Antipolis Méditerranée
- Tien Son PHAM (reviewer), Dalat University
- Stef GRAILLAT (examinator), Sorbonne Université
- Simone NALDI (examinator), Université de Limoges
- Lihong ZHI (examinator), Chinese Academy of Sciences
- Victor MAGRON (advisor), Laboratoire d’Analyse et d’Architecture des Systemes
- Mohab SAFEY EL DIN (advisor), Sorbonne Université
Abstract:
The aim of this thesis is to compute exact certificates of non-negativity for polynomials based on SOS decompositions with rational coefficients. We provide symbolic algorithms to compute SOS decompositions modulo the gradient ideal of non-negative real multivariate polynomials under a genericity condition. These algorithms can tackle a large range of problems that are out of reach for state-of-the-art algorithms. We also compute sums of Hermitian squares decompositions for complex trigonometric univariate polynomials that are positive on the unit circle with Gaussian coefficients. Moreover, we analyze the bit complexity of these algorithms and deduce bitsize bounds of such certificates. Finally, we implement these algorithms in the computer algebra system Maple and the programming environment Julia and evaluate their performance on some standard benchmarks.
Résumé :
L'objectif de cette thèse est de calculer des certificats exacts de non-négativité pour des polynômes basés sur des décompositions SOS à coefficients rationnels. Nous fournissons des algorithmes symboliques pour calculer les décompositions SOS modulo l'idéal gradient de polynômes multivariés réels non-négatifs sous une condition de généricité. Ces algorithmes peuvent s'attaquer à un large éventail de problèmes qui sont hors de portée des algorithmes de pointe. Nous calculons également les sommes des décompositions des carrés hermitiens pour les polynômes trigonométriques complexes univariés qui sont positifs sur le cercle unitaire avec des coefficients gaussiens. De plus, nous analysons la complexité binaire de ces algorithmes et déduisons les limites de taille binaire de ces certificats. Enfin, nous implémentons ces algorithmes dans le système de calcul formel Maple et l'environnement de programmation Julia et nous évaluons leurs performances sur quelques benchmarks standards.
