Theorem 4.6, 2 ⇒ 1 — a certificate shows that (4.4) is empty
ProvedSemialgebraicSDP.Psatz.theorem_4_6_sufficiencyinfeasibility-certificatep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1positivstellensatzreal-algebraic-geometry
Let , , be finite families of polynomials in , each possibly empty. Let be the cone generated by the , the multiplicative monoid generated by the , and the ideal generated by the . If there exist , , with
then the set
is empty.
This is the direction of the Positivstellensatz proved in the paper: an algebraic identity of this form is a certificate of infeasibility of the real polynomial system.
Formalization Note This item formalizes only the implication 2 ⇒ 1 of Theorem 4.6; the converse is a separate item.
Preamble
import Mathlib import Definitions.Def_SemialgebraicSDP_Psatz_Cone
Formal statement
namespace SemialgebraicSDP.Psatz
open MvPolynomial
theorem theorem_4_6_sufficiency {n s t u : ℕ} (f : Fin s → MvPolynomial (Fin n) ℝ)
(g : Fin t → MvPolynomial (Fin n) ℝ) (h : Fin u → MvPolynomial (Fin n) ℝ)
(hcert : ∃ F ∈ cone (Set.range f), ∃ G ∈ Submonoid.closure (Set.range g),
∃ H ∈ Ideal.span (Set.range h), F + G ^ 2 + H = 0) :
psatzSet f g h = ∅ := by sorry
end SemialgebraicSDP.Psatz
Source
Parrilo, Semidefinite programming relaxations for semialgebraic problems, Math. Program. Ser. B 96 (2003) 293–320, p. 305, Theorem 4.6 (2 ⇒ 1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.