Claim in the proof of Lemma 7.2.1 — superlevel sets of the barrier are bounded
ProvedMatousekLP.InteriorPoint.barrier_superlevel_boundedbarrier-functioninterior-point-methodslinear-programmingp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be a real matrix of rank , , . Suppose the linear program (7.2) (maximize subject to , ) has a feasible solution , and its dual (7.5) (minimize subject to ) has a feasible solution whose slack vector satisfies . Fix and let . Then the set
is bounded.
This is the compactness step behind the existence of a maximizer of the barrier problem, and hence of the point of the central path.
Formalization Note means every coordinate is strictly positive; indices are Fin n. Boundedness is Bornology.IsBounded in the sup-norm topology of Fin n → ℝ, which is equivalent to boundedness in any norm.
Preamble
import Mathlib import Definitions.Def_MatousekLP_InteriorPoint_CentralPath
Formal statement
namespace MatousekLP.InteriorPoint
open Matrix
/-- Claim in the proof of Lemma 7.2.1 (Matoušek & Gärtner, p. 121). Let `A` be an `m × n`
matrix of rank `m`, let `x̃ > 0` satisfy `Ax̃ = b`, let `ỹ` satisfy `Aᵀỹ − c > 0`, and let
`μ > 0`. Then the set `Q = {x ∈ ℝⁿ : Ax = b, x > 0, f_μ(x) ≥ f_μ(x̃)}` is bounded. -/
theorem barrier_superlevel_bounded {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) (μ : ℝ) (hμ : 0 < μ) :
Bornology.IsBounded
{x : Fin n → ℝ | IsPrimalInterior A b x ∧ barrier c μ xt ≤ barrier c μ x} := by sorry
end MatousekLP.InteriorPoint
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, §7.2, p. 121, Claim in the proof of Lemma 7.2.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.