Proof of Lemma 4.1, p. 14 — the Newton direction is orthogonal: d_xᵀd_s + d_τd_κ = 0
ProvedConicQuadIPM.NewtonStep.direction_orthogonalconic-optimizationinterior-pointnewton-directionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
In the setting of the Newton system (22) — a product cone with the usual dimension conventions, data , , , any point , and a solution of (22) — the primal and dual parts of the direction are orthogonal:
Orthogonality is what makes the complementarity gap along the step linear in , with no quadratic term; it is the fourth identity of Lemma 4.1.
Formalization Note over the blocks. The hypothesis is the range of (21) and is not needed. No interiority of the current point is assumed, as in Lemma 4.1.
Preamble
import Mathlib import Definitions.Def_ConicQuadIPM_NewtonStep_Setting
Formal statement
namespace ConicQuadIPM.NewtonStep
open Matrix
theorem direction_orthogonal
{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, dx i ⬝ᵥ ds i) + dτ * 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. 14, proof of Lemma 4.1, 'These two facts combined gives d_xᵀd_s + d_τd_κ = 0'
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.