Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Corollary 17.3 — existence and uniqueness of the primal–dual central path point for each μ>0\mu > 0μ>0

Proved
VanderbeiLP.CentralPath.central_path_exists_unique

by mikedeng1 · Oct 1, 2026 · Mathlib 0df444a (Lean v4.33.1)

central-pathinterior-pointlinear-programmingp2o-batch-b23ap2o-gran-per-chapterp2o-plan-bookp2o-v1

Let AAA be a real m×nm \times nm×n matrix, b∈Rmb \in \mathbb{R}^mb∈Rm and c∈Rnc \in \mathbb{R}^nc∈Rn. Suppose that the primal feasible set has nonempty interior and is bounded, that is,

  1. there is (xˉ,wˉ)(\bar x, \bar w)(xˉ,wˉ) with Axˉ+wˉ=bA\bar x + \bar w = bAxˉ+wˉ=b, xˉ>0\bar x > 0xˉ>0, wˉ>0\bar w > 0wˉ>0, and {x:Ax≤b, x≥0}\{x : Ax \le b,\ x \ge 0\}{x:Ax≤b, x≥0} is bounded;

or, for that matter, that the dual feasible set has nonempty interior and is bounded, that is,

  1. there is (yˉ,zˉ)(\bar y, \bar z)(yˉ​,zˉ) with ATyˉ−zˉ=cA^T \bar y - \bar z = cATyˉ​−zˉ=c, yˉ>0\bar y > 0yˉ​>0, zˉ>0\bar z > 0zˉ>0, and {y:ATy≥c, y≥0}\{y : A^T y \ge c,\ y \ge 0\}{y:ATy≥c, y≥0} is bounded.

Then for each μ>0\mu > 0μ>0 there exists a unique solution (xμ,wμ,yμ,zμ)(x_\mu, w_\mu, y_\mu, z_\mu)(xμ​,wμ​,yμ​,zμ​) with xμ,wμ,yμ,zμ>0x_\mu, w_\mu, y_\mu, z_\mu > 0xμ​,wμ​,yμ​,zμ​>0 to the system (17.6)

Ax+w=b,ATy−z=c,XZe=μe,YWe=μe.Ax + w = b, \qquad A^T y - z = c, \qquad XZe = \mu e, \qquad YWe = \mu e.Ax+w=b,ATy−z=c,XZe=μe,YWe=μe.

The curve {(xμ,wμ,yμ,zμ):μ>0}\{(x_\mu, w_\mu, y_\mu, z_\mu) : \mu > 0\}{(xμ​,wμ​,yμ​,zμ​):μ>0} is the primal–dual central path, which path-following interior-point methods track toward an optimal solution.

Formalization Note The hypothesis is the disjunction of the primal and the dual versions; the book states the primal one and adds the dual one in a parenthesis. Solutions of (17.6) are required to be strictly positive: (17.6) is derived on p. 263 from the barrier problem, whose domain is x>0x > 0x>0, w>0w > 0w>0 (and then y=μW−1e>0y = \mu W^{-1}e > 0y=μW−1e>0, z=μX−1e>0z = \mu X^{-1} e > 0z=μX−1e>0), and Exercise 17.3 (p. 267) states the same system with x,y,z,w>0x, y, z, w > 0x,y,z,w>0 explicitly. Without the positivity, sign-flipped solutions of xjzj=μx_j z_j = \muxj​zj​=μ, yiwi=μy_i w_i = \muyi​wi​=μ are not excluded and uniqueness is not the book's claim.

Preamble
import Mathlib
import Definitions.Def_VanderbeiLP_CentralPath_BarrierProblem

open Matrix Filter Topology
Formal statement
namespace VanderbeiLP.CentralPath

/-- Corollary 17.3 (p. 266). If the primal feasible set has nonempty interior and is bounded (or
the dual feasible set has nonempty interior and is bounded), then for each `μ > 0` the system
(17.6) has a unique solution `(x_μ, w_μ, y_μ, z_μ)` with `x_μ, w_μ, y_μ, z_μ > 0`. -/
theorem central_path_exists_unique {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
    (c : Fin n → ℝ)
    (h : (PrimalStrictlyFeasible A b ∧ Bornology.IsBounded (primalFeasibleSet A b)) ∨
      (DualStrictlyFeasible A c ∧ Bornology.IsBounded (dualFeasibleSet A c))) :
    ∀ μ : ℝ, 0 < μ →
      ∃! p : (Fin n → ℝ) × (Fin m → ℝ) × (Fin m → ℝ) × (Fin n → ℝ),
        IsCentralPathPoint A b c μ p.1 p.2.1 p.2.2.1 p.2.2.2 := by sorry

end VanderbeiLP.CentralPath
Source
Vanderbei, Linear Programming: Foundations and Extensions, 4th ed., Springer 2014, p. 266, Corollary 17.3 (PDF p. 276); system (17.6), p. 263 (PDF p. 273); positivity as in Exercise 17.3, p. 267 (PDF p. 277)
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me