§3.2 — a positive semidefinite Gram matrix gives a sum of squares
ProvedSemialgebraicSDP.Psatz.gram_psd_isSumSqgram-matrixp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programmingsum-of-squares
Let , let be the vector of monomials of total degree at most in variables, and let be a real symmetric positive semidefinite matrix indexed by these monomials. Then the polynomial
is a sum of squares in : there are polynomials with .
This is the sufficiency half of the Gram matrix method: any positive semidefinite point of the affine space of Gram matrices of certifies that is a sum of squares and hence nonnegative.
Formalization Note "Sum of squares" is Mathlib's IsSumSq in the polynomial ring (finite sums of squares; the empty sum included).
Preamble
import Mathlib import Definitions.Def_SemialgebraicSDP_Psatz_Gram
Formal statement
namespace SemialgebraicSDP.Psatz
open MvPolynomial
theorem gram_psd_isSumSq {n d : ℕ} (Q : Matrix (Mon n d) (Mon n d) ℝ)
(hQ : Q.PosSemidef) : IsSumSq (gramPoly Q) := by sorry
end SemialgebraicSDP.Psatz
Source
Parrilo, Semidefinite programming relaxations for semialgebraic problems, Math. Program. Ser. B 96 (2003) 293–320, p. 298, §3.2, last paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.