Lemma 7.2.2 — the Goldman–Tucker system solves or refutes the LP
ProvedMatousekLP.InteriorPoint.goldman_tuckerdualityinterior-point-methodslinear-programmingp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be a real matrix, , , and consider the linear program (7.7), maximize subject to , , with dual minimize subject to , . The Goldman–Tucker system (GTS) is
and . Then:
- no solution of (GTS) has both and ;
- exactly one of the following holds: (GTS) has a solution with , or (GTS) has a solution with ;
- for every solution of (GTS) with , is an optimal solution of (7.7) and is an optimal solution of its dual;
- if is a solution of (GTS) with , then (7.7) is infeasible or unbounded.
The homogeneous system (GTS) thus encodes, in a single feasibility problem, both the optimal solutions of (7.7) and a certificate that no optimum exists.
Formalization Note Indices are Fin n and Fin m. Optimality of (resp. ) is stated as feasibility together with for all feasible (resp. for all dual feasible ); unboundedness means that for every real some feasible has . "Exactly one" is Xor.
Preamble
import Mathlib import Definitions.Def_MatousekLP_InteriorPoint_SelfDual
Formal statement
namespace MatousekLP.InteriorPoint
open Matrix
/-- Lemma 7.2.2 (Matoušek & Gärtner, p. 126). For the linear program (7.7)
`maximize cᵀx subject to Ax ≤ b, x ≥ 0` and its Goldman–Tucker system (GTS), with
`ρ = cᵀx − bᵀy`:
1. no solution of (GTS) has both `τ` and `ρ` nonzero;
2. exactly one of the following occurs: (GTS) has a solution with `τ > 0`, or (GTS) has a
solution with `ρ > 0`;
3. for every solution with `τ > 0`, `(1/τ)x` is an optimal solution of (7.7) and `(1/τ)y` is an
optimal solution of its dual `minimize bᵀy subject to Aᵀy ≥ c, y ≥ 0`;
4. if (GTS) has a solution with `ρ > 0`, then (7.7) is infeasible or unbounded. -/
theorem goldman_tucker {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
(c : Fin n → ℝ) :
(∀ (x : Fin n → ℝ) (y : Fin m → ℝ) (τ : ℝ), IsGTSSolution A b c x y τ →
τ = 0 ∨ gtsSlack b c x y = 0) ∧
Xor (∃ (x : Fin n → ℝ) (y : Fin m → ℝ) (τ : ℝ), IsGTSSolution A b c x y τ ∧ 0 < τ)
(∃ (x : Fin n → ℝ) (y : Fin m → ℝ) (τ : ℝ),
IsGTSSolution A b c x y τ ∧ 0 < gtsSlack b c x y) ∧
(∀ (x : Fin n → ℝ) (y : Fin m → ℝ) (τ : ℝ), IsGTSSolution A b c x y τ → 0 < τ →
IsIneqOptimal A b c (τ⁻¹ • x) ∧ IsIneqDualOptimal A b c (τ⁻¹ • y)) ∧
(∀ (x : Fin n → ℝ) (y : Fin m → ℝ) (τ : ℝ), IsGTSSolution A b c x y τ →
0 < gtsSlack b c x y →
(¬ ∃ x' : Fin n → ℝ, IsIneqFeasible A b x') ∨ IsIneqUnbounded A b c) := by sorry
end MatousekLP.InteriorPoint
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, §7.2, p. 126, Lemma 7.2.2 (with (7.7) and (GTS) p. 126)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.