Proof of Lemma 2.4, p. 11 — D + diag(c) is positive semidefinite for every instance
ProvedSkutellaCQP.NoRel.cqp_psdconvex-quadratic-relaxationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1positive-semidefinitescheduling
For every instance of (processing times , weights ), the symmetric matrix
is positive semidefinite, where and is the matrix of (4).
This is the case of Lemma 2.4 that its proof establishes, and the reason the objective of (CQP), , is convex.
Formalization Note Positive semidefiniteness is Mathlib's Matrix.PosSemidef (Hermitian, i.e. symmetric over , with for all ).
Preamble
import Mathlib import Definitions.Def_SkutellaCQP_NoRel_Setting
Formal statement
namespace SkutellaCQP.NoRel
/-- Proof of Lemma 2.4 (p. 11): for every instance, `D + diag(c)` is positive semidefinite. -/
theorem cqp_psd {m n : ℕ} (p : Fin m → Fin n → ℝ) (w : Fin n → ℝ)
(hp : ∀ i j, 0 < p i j) (hw : ∀ j, 0 ≤ w j) :
(Dmat p w + Matrix.diagonal (cvec p w)).PosSemidef := by sorry
end SkutellaCQP.NoRel
Source
Skutella, Convex quadratic and semidefinite programming relaxations in scheduling, J. ACM 48 (2001), p. 11, §2.2, proof of Lemma 2.4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.