VU Trung Hieu
Supervision : Mohab SAFEY EL DIN
Certificats exacts de positivité pour l'optimisation polynomiale
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.
Defence : 12/09/2022
Jury members :
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é
2020-2023 Publications
-
2023
- V. Magron, M. Safey El Din, T.‑H. VU : “Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients”, SIAM Journal on Optimization, vol. 33 (1), (Society for Industrial and Applied Mathematics) (2023)
-
2022
- T. Vu : “Certificats exacts de positivité pour l’optimisation polynomiale ”, thesis, phd defence 12/09/2022, supervision Safey el din, Mohab (2022)
- V. Magron, M. Safey El Din, M. Schweighofer, T. Vu : “Exact SOHS Decompositions of Trigonometric Univariate Polynomials with Gaussian Coefficients”, International Symposium on Symbolic and Algebraic Computation (ISSAC), Lille, France (2022)
- T.‑H. VU : “On the Nonemptiness and Boundedness of Solution Sets of Weakly Homogeneous Optimization Problems”, Set-Valued and Variational Analysis, vol. 30 (3), pp. 1105-1116, (Springer) (2022)
-
2021
- T.‑H. VU : “On the solution existence and stability of polynomial optimization problems”, Optimization Letters, (Springer Verlag) (2021)
-
2020
- T.‑H. VU : “Solution maps of polynomial variational inequalities”, Journal of Global Optimization, vol. 77 (4), pp. 807-824, (Springer Verlag) (2020)