Corollary 17.3 — existence and uniqueness of the primal–dual central path point for each
ProvedVanderbeiLP.CentralPath.central_path_exists_uniqueLet be a real matrix, and . Suppose that the primal feasible set has nonempty interior and is bounded, that is,
- there is with , , , and is bounded;
or, for that matter, that the dual feasible set has nonempty interior and is bounded, that is,
- there is with , , , and is bounded.
Then for each there exists a unique solution with to the system (17.6)
The curve 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 , (and then , ), and Exercise 17.3 (p. 267) states the same system with explicitly. Without the positivity, sign-flipped solutions of , are not excluded and uniqueness is not the book's claim.
import Mathlib import Definitions.Def_VanderbeiLP_CentralPath_BarrierProblem open Matrix Filter Topology
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.