Lemma 7.2.1 — existence and uniqueness of the primal–dual central path
ProvedMatousekLP.InteriorPoint.central_path_exists_uniqueLet be a real matrix of rank , , , and consider the linear program (7.2), maximize subject to , , and its dual (7.5), minimize subject to . Suppose (7.2) has a feasible solution and (7.5) has a feasible solution whose slack vector satisfies ; that is, both programs have an interior feasible point.
Then for every the system
in the unknowns , has exactly one solution , and is the unique maximizer of the barrier function subject to and .
The set is the primal–dual central path of (7.2), the curve that path-following interior point methods track.
Formalization Note Indices are Fin n and Fin m. Uniqueness of the triple is stated as: one solution exists, and every solution of (7.4) equals it. "Unique maximizer" means , , and for every other with , ; the barrier is never evaluated at a point with a nonpositive coordinate in this comparison. The rank hypothesis is the standing assumption of (7.2).
import Mathlib import Definitions.Def_MatousekLP_InteriorPoint_CentralPath
namespace MatousekLP.InteriorPoint
open Matrix
/-- Lemma 7.2.1 (Matoušek & Gärtner, p. 121). Let `A` be an `m × n` matrix of rank `m`.
Suppose the linear program (7.2) `maximize cᵀx subject to Ax = b, x ≥ 0` has a feasible
solution `x̃ > 0` and the dual (7.5) `minimize bᵀy subject to Aᵀy ≥ c` has a feasible solution
`ỹ` whose slack vector `s̃ = Aᵀỹ − c` satisfies `s̃ > 0`. Then for every `μ > 0` the system
(7.4) has a unique solution `x*(μ), y*(μ), s*(μ)`, and `x*(μ)` is the unique maximizer of
`f_μ` subject to `Ax = b` and `x > 0`. -/
theorem central_path_exists_unique {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
(c : Fin n → ℝ) (hrank : A.rank = m) (xt : Fin n → ℝ) (hxt : IsPrimalInterior A b xt)
(yt : Fin m → ℝ) (hyt : IsDualInterior A c yt) :
∀ μ : ℝ, 0 < μ →
∃ (x : Fin n → ℝ) (y : Fin m → ℝ) (s : Fin n → ℝ),
CentralPathSystem A b c μ x y s ∧
(∀ (x' : Fin n → ℝ) (y' : Fin m → ℝ) (s' : Fin n → ℝ),
CentralPathSystem A b c μ x' y' s' → x' = x ∧ y' = y ∧ s' = s) ∧
IsUniqueBarrierMaximizer A b c μ x := by sorry
end MatousekLP.InteriorPoint
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.
Confirmed by the moderator at approval.