Proof of Lemma 4.1, p. 14, first equality — (x⁽⁰⁾)ᵀd_s + (s⁽⁰⁾)ᵀd_x = eᵀ(X⁽⁰⁾Td_s + S⁽⁰⁾Td_x)
ProvedConicQuadIPM.NewtonStep.p14_first_eqarrow-head-matrixconic-optimizationinterior-pointp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a product of cones of the kinds , , with the usual dimension conventions, the matrix of Definition 3.2 and (22), and the stacked first unit vectors. For arbitrary vectors and reals , with and ,
This is the first link of the chain on p. 14 that evaluates the middle term of (26): it rewrites the linear term of the complementarity gap through the fourth line of the Newton system (22).
Formalization Note is written block by block as . The identity holds for all vectors; it uses no hypothesis from (22).
Preamble
import Mathlib import Definitions.Def_ConicQuadIPM_NewtonStep_Setting
Formal statement
namespace ConicQuadIPM.NewtonStep
open Matrix
theorem p14_first_eq
{k : ℕ} (kind : Fin k → ConicQuadIPM.Complementarity.ConeKind) (n : Fin k → ℕ) (hwf : ConicQuadIPM.Complementarity.WellFormed kind n)
(x0 s0 dx ds : (i : Fin k) → Fin (n i) → ℝ) (τ0 κ0 dτ dκ : ℝ) :
(∑ i, x0 i ⬝ᵥ ds i) + (∑ i, s0 i ⬝ᵥ dx i) + τ0 * dκ + κ0 * dτ
= (∑ i, ConicQuadIPM.Complementarity.e1 ⬝ᵥ (ConicQuadIPM.Complementarity.arrow (ConicQuadIPM.Complementarity.Tmat (kind i) (n i) *ᵥ x0 i) *ᵥ (ConicQuadIPM.Complementarity.Tmat (kind i) (n i) *ᵥ ds i)
+ ConicQuadIPM.Complementarity.arrow (ConicQuadIPM.Complementarity.Tmat (kind i) (n i) *ᵥ s0 i) *ᵥ (ConicQuadIPM.Complementarity.Tmat (kind i) (n i) *ᵥ dx i)))
+ τ0 * dκ + κ0 * dτ := by sorry
end ConicQuadIPM.NewtonStep
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, p. 14, proof of Lemma 4.1, first equality of the display after 'Moreover,'
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.