Interior point methods solve linear programs by moving through the interior of the feasible set instead of along its edges — the approach that turned Karmarkar's 1984 breakthrough into today's practical large-scale solvers. This mission formalizes the primal path following algorithm of Chapter 9 of Bertsimas–Tsitsiklis. For the logarithmic barrier
replaces the constraint ; the minimizers of over trace the central path, characterized by the KKT conditions (9.17): , , , , (Lemma 9.5). The algorithm follows the path with one Newton step of the barrier problem per shrink , maintaining the proximity invariant
. The goal theorem is Theorem 9.7: with and a -close start, after iterations the algorithm reaches primal and dual feasible solutions with duality gap — the explicit form of the celebrated iteration bound. Alongside it we formalize the generic potential-reduction scheme (Theorem 9.4): any algorithm cutting by per step reaches gap within an explicit .
theorem LinearOptimization.interior_point_path_following_iterations {m n : ℕ}
(A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(hrank : LinearIndependent ℝ (fun i => A i))
(beta eps alpha : ℝ) (hbeta0 : 0 < beta) (hbeta1 : beta < 1)
(heps : 0 < eps)
(halpha : alpha = 1 -
(Real.sqrt beta - beta) / (Real.sqrt beta + Real.sqrt n))
(x : ℕ → Fin n → ℝ) (p : ℕ → Fin m → ℝ) (s : ℕ → Fin n → ℝ)
(mu : ℕ → ℝ) (hmu0 : 0 < mu 0)
(hxfeas0 : A.mulVec (x 0) = b) (hx0 : ∀ j, 0 < x 0 j)
(hsfeas0 : Aᵀ.mulVec (p 0) + s 0 = c) (hs0 : ∀ j, 0 < s 0 j)
(hprox0 : centralPathProximity (mu 0) (x 0) (s 0) ≤ beta)
(hrun : IsPathFollowingRun A c alpha x p s mu)
(K : ℕ)
(hK : K = ⌈(Real.sqrt beta + Real.sqrt n) / (Real.sqrt beta - beta) *
Real.log ((s 0 ⬝ᵥ x 0) * (1 + beta) / (eps * (1 - beta)))⌉₊) :
A.mulVec (x K) = b ∧ 0 ≤ x K ∧
Aᵀ.mulVec (p K) + s K = c ∧ 0 ≤ s K ∧
s K ⬝ᵥ x K ≤ eps := by
sorry
(Theorem 9.7, p. 426, GOAL — iteration bound for primal path following) Assume that the primal path following algorithm uses
where [formally ; see design_note], and starts with an initial primal and dual feasible solution , with , , that satisfies
Then, after
iterations, it finds a primal and dual feasible solution with duality gap
No open leaves. Every sub-goal is proved or awaiting decomposition.