§3.2 — a sum of squares of degree has a positive semidefinite Gram matrix
ProvedSemialgebraicSDP.Psatz.isSumSq_exists_gramgram-matrixp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programmingsum-of-squares
Let and let be a sum of squares of polynomials with total degree at most . Then there is a real positive semidefinite matrix , indexed by the monomials of total degree at most , such that
where is the vector of these monomials.
This is the necessity half of the Gram matrix method. Its content includes the fact that in a representation every already has degree at most , because the leading forms of real squares cannot cancel; it is not assumed.
Preamble
import Mathlib import Definitions.Def_SemialgebraicSDP_Psatz_Gram
Formal statement
namespace SemialgebraicSDP.Psatz
open MvPolynomial
theorem isSumSq_exists_gram {n d : ℕ} (F : MvPolynomial (Fin n) ℝ)
(hF : IsSumSq F) (hdeg : F.totalDegree ≤ 2 * d) :
∃ Q : Matrix (Mon n d) (Mon n d) ℝ, Q.PosSemidef ∧ F = gramPoly Q := by sorry
end SemialgebraicSDP.Psatz
Source
Parrilo, Semidefinite programming relaxations for semialgebraic problems, Math. Program. Ser. B 96 (2003) 293–320, pp. 298–299, §3.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.