Text
Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients
Assessing nonnegativity of multivariate polynomials over the reals, through the computation of certificates of nonnegativity, is a topical issue in polynomial optimization. This is usually tackled through the computation of sum of squares decompositions which rely on efficient numerical solvers for semidefinite programming. This method faces two difficulties. The first one is that the certificates obtained this way are approximate and then nonexact. The second one is due to the fact that not all nonnegative polynomials are sums of squares. In this paper, we build on previous works by Parrilo and Nie, Demmel, and Sturmfels who introduced certificates of nonnegativity modulo gradient ideals. We prove that, actually, such certificates can be obtained exactly over the rationals if the polynomial under consideration has rational coefficients, and we provide exact algorithms to compute them. We analyze the bit complexity of these algorithms and deduce bitsize bounds of such certificates.
Barcode | Tipe Koleksi | Nomor Panggil | Lokasi | Status | |
---|---|---|---|---|---|
art144745 | null | Artikel | Gdg9-Lt3 | Tersedia namun tidak untuk dipinjamkan - No Loan |
Tidak tersedia versi lain