Lemma 7.2.3 — the self-dual program (SD) and its strictly complementary optima
ProvedMatousekLP.InteriorPoint.self_dual_embeddinginterior-point-methodslinear-programmingp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1self-dual-embedding
Let be a real matrix, , , , and let
Consider the linear program
in with , and write for its slacks. Then:
- (SD) has a feasible solution, and its objective is bounded from above on the feasible set;
- every optimal solution of (SD) has , and its -part is a solution of the Goldman–Tucker system (GTS) , , , , ;
- if moreover is strictly complementary (for each coordinate , or ), then the resulting solution of (GTS) has or .
Together with Lemma 7.2.2, this reduces solving (7.7) to finding a strictly complementary optimal solution of (SD), a program with an explicit interior starting point.
Formalization Note is indexed by Fin m ⊕ Fin n ⊕ Unit and by (Fin m ⊕ Fin n ⊕ Unit) ⊕ Unit; uY, uX, uTau, vU, vTheta extract , , , , . Optimality and boundedness are stated against every feasible point.
Preamble
import Mathlib import Definitions.Def_MatousekLP_InteriorPoint_SelfDual
Formal statement
namespace MatousekLP.InteriorPoint
open Matrix
/-- Lemma 7.2.3 (Matoušek & Gärtner, p. 128). The linear program
(SD) `maximize −qᵀv subject to Mv ≤ q, v ≥ 0` built from `A, b, c` is feasible and bounded,
every optimal solution `v = (u, ϑ)` has `ϑ = 0`, and hence its `u`-part `u = (y, x, τ)` is a
solution of the Goldman–Tucker system (GTS). Moreover, every strictly complementary optimal
solution yields a solution of (GTS) with `τ > 0` or `ρ > 0`. -/
theorem self_dual_embedding {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
(c : Fin n → ℝ) :
(∃ v : VIdx m n → ℝ, IsSDFeasible A b c v) ∧
IsSDBoundedAbove A b c ∧
(∀ v : VIdx m n → ℝ, IsSDOptimal A b c v →
vTheta v = 0 ∧ IsGTSSolution A b c (uX (vU v)) (uY (vU v)) (uTau (vU v))) ∧
(∀ v : VIdx m n → ℝ, IsSDOptimal A b c v → IsStrictlyComplementary A b c v →
0 < uTau (vU v) ∨ 0 < gtsSlack b c (uX (vU v)) (uY (vU v))) := by sorry
end MatousekLP.InteriorPoint
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, §7.2, p. 128, Lemma 7.2.3 (with M_0, r, M p. 127 and q, (SD) p. 128)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.