§6, proof of Theorem 7, p. 30 — if k ≥ m + 2, system (18) has a solution y ∈ 𝐒^{k−1}
ProvedQCQPTightness.MultHull.system_18_feasiblelinear-algebrap2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1qcqpquadratic-eigenvalue-multiplicity
Let with , let and , and let be the quadratic and linear data of a QCQP with constraints. Then the system in
is feasible, where is the Euclidean unit sphere of and is the vector whose -th block of entries is .
The first equations are homogeneous and linear in ; with unknowns they have a nonzero solution. The unit vector is the direction along which the proof of Theorem 7 splits a point of into two.
Formalization Note is written . No Kronecker structure of the is assumed: the claim is pure linear algebra in .
Preamble
import Mathlib import Definitions.Def_QCQPTightness_MultHull_QCQP import Definitions.Def_QCQPTightness_MultHull_Mult import Definitions.Def_QCQPTightness_MultHull_Kron
Formal statement
namespace QCQPTightness.MultHull
open Matrix
theorem system_18_feasible {N m k n : ℕ} (P : QCQP N m) (h : k * n = N) (hkm : m + 2 ≤ k)
(x : Fin N → ℝ) (z : Fin n → ℝ) :
∃ y : Fin k → ℝ, y ⬝ᵥ y = 1 ∧
(P.A₀ *ᵥ x + P.b₀) ⬝ᵥ kronVec h y z = 0 ∧
∀ i, (P.A i *ᵥ x + P.b i) ⬝ᵥ kronVec h y z = 0 := by sorry
end QCQPTightness.MultHull
Source
arXiv:1911.09195v3, §6, proof of Theorem 7, p. 30, display (18) and the claim that it is feasible
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.