Proof of Theorem 2.6, p. 12 — Z_QP(a) = Z_CQP(a) + ½(cᵀa − aᵀdiag(c)a)
ProvedSkutellaCQP.NoRel.zqp_eq_zcqp_addconvex-quadratic-relaxationidentityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling
For every vector ,
where is the objective of (QP) and that of (CQP).
The identity measures the gap between the expected value of the rounded schedule (which is by Theorem 2.1) and the value of the convex relaxation; it is the common step of Theorem 2.6 and Lemma 2.8.
Preamble
import Mathlib import Definitions.Def_SkutellaCQP_NoRel_Setting
Formal statement
namespace SkutellaCQP.NoRel
open Matrix
/-- The identity in the proof of Theorem 2.6 (p. 12):
`Z_QP(a) = Z_CQP(a) + ½ (c^T a - a^T diag(c) a)` for every `a ∈ ℝ^{mn}`. -/
theorem zqp_eq_zcqp_add {m n : ℕ} (p : Fin m → Fin n → ℝ) (w : Fin n → ℝ)
(a : Fin m → Fin n → ℝ) :
ZQP p w a = ZCQP p w a +
(1 / 2) * (cvec p w ⬝ᵥ vec a - vec a ⬝ᵥ (Matrix.diagonal (cvec p w) *ᵥ vec a)) := by sorry
end SkutellaCQP.NoRel
Source
Skutella, Convex quadratic and semidefinite programming relaxations in scheduling, J. ACM 48 (2001), p. 12, §2.3, proof of Theorem 2.6 (displayed equality)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.