Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 22.8 — a strictly complementary solution of the self-dual embedding solves the LP or certifies infeasibility

Proved
VanderbeiLP.SelfDual.self_dual_embedding_solution

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

dualityinfeasibilitylinear-programmingp2o-batch-b23ap2o-gran-per-chapterp2o-plan-bookp2o-v1self-dual

Let AAA be a real m×nm \times nm×n matrix, b∈Rmb \in \mathbb{R}^mb∈Rm, c∈Rnc \in \mathbb{R}^nc∈Rn, and consider the primal problem (22.1) max⁡cTx\max c^TxmaxcTx s.t. Ax≤bAx \le bAx≤b, x≥0x \ge 0x≥0, its dual (22.2) min⁡bTy\min b^TyminbTy s.t. ATy≥cA^Ty \ge cATy≥c, y≥0y \ge 0y≥0, and the self-dual embedding (22.21)

−ATy+cϕ+z=0,Ax−bϕ+w=0,−cTx+bTy+ψ=0,x,y,ϕ,z,w,ψ≥0.-A^T y + c\phi + z = 0,\qquad Ax - b\phi + w = 0,\qquad -c^T x + b^T y + \psi = 0,\qquad x, y, \phi, z, w, \psi \ge 0.−ATy+cϕ+z=0,Ax−bϕ+w=0,−cTx+bTy+ψ=0,x,y,ϕ,z,w,ψ≥0.

Suppose that (xˉ,yˉ,ϕˉ,zˉ,wˉ,ψˉ)(\bar x, \bar y, \bar\phi, \bar z, \bar w, \bar\psi)(xˉ,yˉ​,ϕˉ​,zˉ,wˉ,ψˉ​) is a strictly complementary feasible solution of (22.21): xˉj+zˉj>0\bar x_j + \bar z_j > 0xˉj​+zˉj​>0 for all jjj, yˉi+wˉi>0\bar y_i + \bar w_i > 0yˉ​i​+wˉi​>0 for all iii, and ϕˉ+ψˉ>0\bar\phi + \bar\psi > 0ϕˉ​+ψˉ​>0.

  1. If ϕˉ>0\bar\phi > 0ϕˉ​>0, then x∗=xˉ/ϕˉx^* = \bar x/\bar\phix∗=xˉ/ϕˉ​ is optimal for the primal problem (22.1) and y∗=yˉ/ϕˉy^* = \bar y/\bar\phiy∗=yˉ​/ϕˉ​ is optimal for its dual (22.2).
  2. If ϕˉ=0\bar\phi = 0ϕˉ​=0, then either cTxˉ>0c^T\bar x > 0cTxˉ>0 or bTyˉ<0b^T\bar y < 0bTyˉ​<0 (possibly both), and
    • (a) if cTxˉ>0c^T\bar x > 0cTxˉ>0, then the dual problem is infeasible;
    • (b) if bTyˉ<0b^T\bar y < 0bTyˉ​<0, then the primal problem is infeasible.

This is what makes the homogeneous self-dual method a complete algorithm for linear programming: a strictly complementary solution of one auxiliary problem, which always has feasible solutions, either yields a primal–dual optimal pair or proves that one of the two problems is infeasible.

Formalization Note The book's parenthetical "(hence, optimal)" in the hypothesis is not formalized: every feasible solution of (22.21) is optimal, its objective being 000. "Either … or" in (2) is the inclusive or, as the book's proof says. Division by ϕˉ\bar\phiϕˉ​ is written as scalar multiplication by ϕˉ−1\bar\phi^{-1}ϕˉ​−1 and only occurs under ϕˉ>0\bar\phi > 0ϕˉ​>0.

Preamble
import Mathlib
import Definitions.Def_VanderbeiLP_SelfDual_SelfDualEmbedding

open Matrix
Formal statement
namespace VanderbeiLP.SelfDual

/-- Theorem 22.8 (Vanderbei, p. 334). Let `(x̄, ȳ, φ̄, z̄, w̄, ψ̄)` be a strictly complementary
feasible solution of the self-dual embedding (22.21) of the primal (22.1)
`max cᵀx, Ax ≤ b, x ≥ 0` and its dual (22.2) `min bᵀy, Aᵀy ≥ c, y ≥ 0`.
(1) If `φ̄ > 0`, then `x̄/φ̄` is optimal for (22.1) and `ȳ/φ̄` is optimal for (22.2).
(2) If `φ̄ = 0`, then `cᵀx̄ > 0` or `bᵀȳ < 0`; (a) if `cᵀx̄ > 0` the dual is infeasible;
(b) if `bᵀȳ < 0` the primal is infeasible. -/
theorem self_dual_embedding_solution {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ)
    (b : Fin m → ℝ) (c : Fin n → ℝ)
    (x : Fin n → ℝ) (y : Fin m → ℝ) (φ : ℝ) (z : Fin n → ℝ) (w : Fin m → ℝ) (ψ : ℝ)
    (hfeas : EmbeddingFeasible A b c x y φ z w ψ)
    (hsc : EmbeddingStrictlyComplementary x y φ z w ψ) :
    (0 < φ → VanderbeiLP.StrictComp.PrimalOptimal A b c (φ⁻¹ • x) ∧ VanderbeiLP.StrictComp.DualOptimal A b c (φ⁻¹ • y)) ∧
    (φ = 0 →
      (0 < c ⬝ᵥ x ∨ b ⬝ᵥ y < 0) ∧
      (0 < c ⬝ᵥ x → ¬ ∃ y' : Fin m → ℝ, DualFeasible A c y') ∧
      (b ⬝ᵥ y < 0 → ¬ ∃ x' : Fin n → ℝ, PrimalFeasible A b x')) := by sorry

end VanderbeiLP.SelfDual
Source
Vanderbei, Linear Programming: Foundations and Extensions, 4th ed., Springer 2014, p. 334, Theorem 22.8 and Eq. (22.21) (PDF p. 340); problems (22.1)–(22.2) on p. 323 (PDF p. 329)
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