Appendix, (61), p. 36 — eᵀXSe = Σᵢ (Tⁱxⁱ)ᵀTⁱsⁱ = xᵀs
ProvedConicQuadIPM.Complementarity.eq_61complementarityconic-optimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1second-order-cone
Let be as in §3, and for arbitrary (partitioned like ) put and , with the first unit vector of . Then for each
and consequently
This identity shows that any satisfying the arrow-head conditions (20) are complementary.
Formalization Note. No cone membership is needed. The block-diagonal matrices , are represented by their blocks, so is written as the sum over blocks. The printed upper limit of the first sum is a slip for ; the Lean sums over the blocks. Block dimensions (WellFormed) are assumed so that .
Preamble
import Mathlib import Definitions.Def_ConicQuadIPM_Complementarity_Setting open Matrix
Formal statement
namespace ConicQuadIPM.Complementarity
theorem eq_61 {k : ℕ} (kind : Fin k → ConeKind) (n : Fin k → ℕ)
(hwf : WellFormed kind n) (x s : (i : Fin k) → Fin (n i) → ℝ) :
(∀ i,
e1 ⬝ᵥ ((arrow (Tmat (kind i) (n i) *ᵥ x i) * arrow (Tmat (kind i) (n i) *ᵥ s i)) *ᵥ e1)
= (Tmat (kind i) (n i) *ᵥ x i) ⬝ᵥ (Tmat (kind i) (n i) *ᵥ s i) ∧
(Tmat (kind i) (n i) *ᵥ x i) ⬝ᵥ (Tmat (kind i) (n i) *ᵥ s i) = x i ⬝ᵥ s i) ∧
∑ i, e1 ⬝ᵥ ((arrow (Tmat (kind i) (n i) *ᵥ x i) * arrow (Tmat (kind i) (n i) *ᵥ s i)) *ᵥ e1)
= ∑ i, x i ⬝ᵥ s i := by sorry
end ConicQuadIPM.Complementarity
Source
Andersen, Roos & Terlaky, On implementing a primal-dual interior-point method for conic quadratic optimization, Math. Program. (2003); authors' preprint of 18 Dec 2000, Appendix, proof of Lemma 3.1, p. 36, (61)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.