Equations (4)–(5) — duality measure and centrality along a step
ProvedAdaptiveStepIPM.PredCorr.equations_4_5interior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , let be strictly positive, and let solve the primal-dual direction system (2) at with parameter . For any real step , write and . Then
Here , while . The identities expose the second-order term that controls both algorithmic steps.
Preamble
import Mathlib import Definitions.Def_AdaptiveStepIPM_PredCorr_Direction open Matrix
Formal statement
namespace AdaptiveStepIPM.PredCorr
/-- Equations (4) and (5), printed p. 4. -/
theorem equations_4_5 {m n : ℕ} (hn : 1 ≤ n)
(A : Matrix (Fin m) (Fin n) ℝ) (x s dx ds : Fin n → ℝ)
(dy : Fin m → ℝ) (γ θ : ℝ)
(hx : ∀ j, 0 < x j) (hs : ∀ j, 0 < s j)
(hd : SearchDirection A x s γ dx dy ds) :
mu (stepX x dx θ) (stepS s ds θ) =
(1 - θ) * mu x s + θ * γ * mu x s ∧
(fun j => stepX x dx θ j * stepS s ds θ j -
mu (stepX x dx θ) (stepS s ds θ)) =
(fun j => (1 - θ) * (x j * s j - mu x s) + θ ^ 2 * (dx j * ds j)) := by sorry
end AdaptiveStepIPM.PredCorr
Source
Mizuno, Todd, Ye, On adaptive-step primal-dual interior-point algorithms for linear programming, Cornell ORIE Technical Report No. 944 (1990, rev. 1991), p. 4, equations (4)–(5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.