(26), proof of Lemma 4.1, p. 13 — 0 = (ηx⁽⁰⁾ + d_x)ᵀ(ηs⁽⁰⁾ + d_s) + (ητ⁽⁰⁾ + d_τ)(ηκ⁽⁰⁾ + d_κ) and its expansion
ProvedConicQuadIPM.NewtonStep.eq_26conic-optimizationinterior-pointnewton-directionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
In the setting of the Newton system (22) of Andersen, Roos and Terlaky — a product cone with the usual dimension conventions, data , , , any point , and a solution of (22) — put . Then
The first equality says that the shifted direction of (25) is complementary; the second expands the product. Together with the value of the middle term computed on p. 14 it yields the orthogonality .
Formalization Note Both equalities of (26) are stated, as a conjunction: the first equality, and the expansion of its right-hand side. is over the blocks; is written out as . The hypothesis is the range of (21) and is not needed.
Preamble
import Mathlib import Definitions.Def_ConicQuadIPM_NewtonStep_Setting
Formal statement
namespace ConicQuadIPM.NewtonStep
open Matrix
theorem eq_26
{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κ) :
0 = (∑ i, ((1 - γ) • x0 i + dx i) ⬝ᵥ ((1 - γ) • s0 i + ds i))
+ ((1 - γ) * τ0 + dτ) * ((1 - γ) * κ0 + dκ) ∧
(∑ i, ((1 - γ) • x0 i + dx i) ⬝ᵥ ((1 - γ) • s0 i + ds i))
+ ((1 - γ) * τ0 + dτ) * ((1 - γ) * κ0 + dκ)
= (1 - γ) ^ 2 * ((∑ i, x0 i ⬝ᵥ s0 i) + τ0 * κ0)
+ (1 - γ) * ((∑ i, x0 i ⬝ᵥ ds i) + (∑ i, s0 i ⬝ᵥ dx i) + τ0 * dκ + κ0 * dτ)
+ ((∑ i, dx i ⬝ᵥ ds i) + dτ * 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. 13, proof of Lemma 4.1, (26)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.