Proof of Lemma 4.1, p. 14 — (x⁽⁰⁾)ᵀd_s + (s⁽⁰⁾)ᵀd_x + τ⁽⁰⁾d_κ + κ⁽⁰⁾d_τ = (γ − 1)µ⁽⁰⁾(k + 1) (page prints k)
ProvedConicQuadIPM.NewtonStep.p14_chainconic-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) — with
one has
Equivalently, the left-hand side equals .
This is the value of the linear term in (26). Combined with (26) it gives the orthogonality of the direction and the reduction of the complementarity gap in Lemma 4.1.
Formalization Note The page ends the chain with . That constant is a slip: , so the chain evaluates to , and the printed value is false whenever and (for , one block, , , the left side is and the printed value is ). The corrected constant is the one Lemma 4.1 needs. 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 p14_chain
{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, x0 i ⬝ᵥ ds i) + (∑ i, s0 i ⬝ᵥ dx i) + τ0 * dκ + κ0 * dτ
= (γ - 1) * mu0 x0 τ0 s0 κ0 * ((k : ℝ) + 1) := 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, the display after 'Moreover,' (final constant corrected from k to k + 1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.