Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients - LAAS - Laboratoire d'Analyse et d'Architecture des Systèmes Accéder directement au contenu
Article Dans Une Revue SIAM Journal on Optimization Année : 2023

Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients

Résumé

Assessing non-negativity of multivariate polynomials over the reals, through the computation of {\em certificates of non-negativity}, is a topical issue in polynomial optimization. This is usually tackled through the computation of {\em sums-of-squares decompositions} which rely on efficient numerical solvers for semi-definite programming. This method faces two difficulties. The first one is that the certificates obtained this way are {\em approximate} and then non-exact. The second one is due to the fact that not all non-negative polynomials are sums-of-squares. In this paper, we build on previous works by Parrilo, Nie, Demmel and Sturmfels who introduced certificates of non-negativity modulo {\em gradient ideals}. We prove that, actually, such certificates can be obtained {\em exactly}, over the rationals if the polynomial under consideration has rational coefficients and we provide {\em exact} algorithms to compute them. We analyze the bit complexity of these algorithms and deduce bit size bounds of such certificates.

Dates et versions

hal-03312392 , version 1 (02-08-2021)

Identifiants

Citer

Victor Magron, Mohab Safey El Din, Trung-Hieu Vu. Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients. SIAM Journal on Optimization, 2023, 33 (1), ⟨10.1137/21M1436245⟩. ⟨hal-03312392⟩
95 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More