Theorem 1, p. 13 — for polyhedral Γ with dim 𝒱(ℱ) ≥ aff dim{b(γ) : γ ∈ ℱ} + 1 on every semidefinite face, conv(𝒟) = 𝒟_SDP and Opt = Opt_SDP
ProvedQCQPTightness.ConvHull.theorem_1Consider the QCQP (1) with constraints, its epigraph and the projected epigraph of its standard SDP relaxation. Suppose Assumption 1 (primal feasibility and some , nonnegative on the inequality constraints, with ) and Assumption 3 ( is polyhedral) hold. Suppose furthermore that every semidefinite face of satisfies
Then
This is the main convex hull result of §4: under the stated conditions the Shor relaxation describes the convex hull of the epigraph exactly, and in particular its value equals the QCQP's value.
Formalization Note. Constraints are indexed by (Fin m), constraint being the paper's constraint ; it is an inequality exactly when . Faces are nonempty (the empty face imposes nothing under the page's convention ). and are infima in EReal. The hypotheses are exactly those of the page together with the paper's standing assumption (p. 1); Assumption 2 is not assumed, since it follows from Assumption 3.
import Mathlib import Definitions.Def_QCQPTightness_ConvHull_QCQP import Definitions.Def_QCQPTightness_ConvHull_Faces
namespace QCQPTightness.ConvHull
/-- Theorem 1 (arXiv:1911.09195v3, p. 13). Suppose `m ≥ 1`, Assumptions 1 and 3 hold, and every
semidefinite face `ℱ` of `Γ` has `dim 𝒱(ℱ) ≥ aff dim {b(γ) : γ ∈ ℱ} + 1`. Then
`conv(𝒟) = 𝒟_SDP` and `Opt = Opt_SDP`. -/
theorem theorem_1 {N m : ℕ} (P : QCQP N m) (hm : 1 ≤ m)
(h1 : P.Assumption1) (h3 : P.Assumption3)
(hdim : ∀ F, P.IsSemidefiniteFace F →
affdim (P.bγ '' F) + 1 ≤ Module.finrank ℝ (P.V F)) :
convexHull ℝ P.D = P.DSDP ∧ P.Opt = P.OptSDP := by sorry
end QCQPTightness.ConvHull
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.