(25), proof of Lemma 4.1, p. 13 — the shifted direction ηz⁽⁰⁾ + d solves the homogeneous equations, η = 1 − γ
ProvedConicQuadIPM.NewtonStep.eq_25conic-optimizationinterior-pointnewton-directionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a product of cones of the kinds , , with the usual dimension conventions, let , , , let be any point, , and let solve the Newton system (22). Put . Then
In words: the point satisfies the linear equations of the homogeneous model. This is the first step of the proof of Lemma 4.1, and it is what makes the skew-symmetry argument (26) applicable.
Formalization Note The page prints in the third line; the formal statement uses . The second identity is stated block by block. is written out as . The hypothesis is the range of (21) and is not needed for the identity.
Preamble
import Mathlib import Definitions.Def_ConicQuadIPM_NewtonStep_Setting
Formal statement
namespace ConicQuadIPM.NewtonStep
open Matrix
theorem eq_25
{m k : ℕ} (kind : Fin k → ConicQuadIPM.Complementarity.ConeKind) (n : Fin k → ℕ) (hwf : ConicQuadIPM.Complementarity.WellFormed kind n)
(A : (i : Fin k) → Matrix (Fin m) (Fin (n i)) ℝ) (b : Fin m → ℝ)
(c : (i : Fin k) → Fin (n i) → ℝ)
(x0 : (i : Fin k) → Fin (n i) → ℝ) (τ0 : ℝ) (y0 : Fin m → ℝ)
(s0 : (i : Fin k) → Fin (n i) → ℝ) (κ0 : ℝ) (γ : ℝ) (hγ : γ ∈ Set.Icc (0 : ℝ) 1)
(dx : (i : Fin k) → Fin (n i) → ℝ) (dτ : ℝ) (dy : Fin m → ℝ)
(ds : (i : Fin k) → Fin (n i) → ℝ) (dκ : ℝ)
(h22 : NewtonSystem kind n A b c x0 τ0 y0 s0 κ0 γ dx dτ dy ds dκ) :
(∑ i, A i *ᵥ ((1 - γ) • x0 i + dx i)) - ((1 - γ) * τ0 + dτ) • b = 0 ∧
(∀ i, (A i)ᵀ *ᵥ ((1 - γ) • y0 + dy) + ((1 - γ) • s0 i + ds i)
- ((1 - γ) * τ0 + dτ) • c i = 0) ∧
-(∑ i, c i ⬝ᵥ ((1 - γ) • x0 i + dx i)) + b ⬝ᵥ ((1 - γ) • y0 + dy)
- ((1 - γ) * κ0 + dκ) = 0 := 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. 13, proof of Lemma 4.1, (25)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.