Theorem 7.7, p. 318 — a feasible solution of the SDPs (7.7) makes and copositive; (7.6) implies (7.7) is feasible
ProvedSemialgebraicSDP.Copositive.theorem_7_7Let be a real symmetric matrix and . Consider the SDPs (7.7) in symmetric matrices :
Then:
- If (7.7) has a feasible solution, then for every , and is copositive ( whenever for all ).
- The test is at least as powerful as condition (7.6): if with and for all , then (7.7) has a feasible solution.
Theorem 7.7 is the first level () of a hierarchy of semidefinite programming tests for copositivity, a property for which deciding that a given matrix is not copositive is NP-complete. It gives an explicit semidefinite program that certifies copositivity of every matrix covered by the classical decomposition test (7.6).
Formalization Note "At least as powerful as condition (7.6)" is formalized as the implication (7.6) (7.7) feasible, i.e. every matrix certified by (7.6) is also certified by (7.7). "" is read as pairwise distinct (see the definition Feasible77). Copositivity is the published MurtyKabadi.Reduction.Copositive.
import Mathlib import Definitions.Def_MurtyKabadi_Reduction_QuadraticProblems import Definitions.Def_SemialgebraicSDP_Copositive_Forms import Definitions.Def_SemialgebraicSDP_Copositive_Certificates
namespace SemialgebraicSDP.Copositive
open MvPolynomial
/-- Theorem 7.7 (Parrilo 2003, p. 318). Let `M` be a real symmetric `n × n` matrix. If the
SDPs (7.7) have a feasible solution, then `P₁(z)` is nonnegative, and therefore `M` is
copositive. Furthermore, the test is at least as powerful as condition (7.6): whenever (7.6)
holds, (7.7) is feasible. -/
theorem theorem_7_7 {n : ℕ} (M : Matrix (Fin n) (Fin n) ℝ) (hM : M.IsSymm) :
(Feasible77 M →
(∀ z : Fin n → ℝ, 0 ≤ eval z (formP1 M)) ∧ MurtyKabadi.Reduction.Copositive M) ∧
(Cond76 M → Feasible77 M) := by sorry
end SemialgebraicSDP.Copositive
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.