Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 1.4.1 — homogeneous Farkas lemma: aTx<0, aiTx≥0a^Tx<0,\ a_i^Tx\ge0aTx<0, aiT​x≥0 is infeasible iff a=∑λiaia=\sum\lambda_ia_ia=∑λi​ai​ with λ≥0\lambda\ge0λ≥0

Proved
ModernConvex.LPDuality.homogeneous_farkas_lemma

by Shuze Chen · Oct 20, 2026 · Mathlib 0df444a (Lean v4.33.1)

farkas-lemmalinear-programming

Let a,a1,…,am∈Rna, a_1, \dots, a_m \in \mathbb R^na,a1​,…,am​∈Rn and consider the system of homogeneous linear inequalities in x∈Rnx \in \mathbb R^nx∈Rn

(F)aTx<0,aiTx≥0, i=1,…,m.\text{(F)}\qquad a^Tx < 0, \qquad a_i^Tx \ge 0,\ i = 1,\dots,m.(F)aTx<0,aiT​x≥0, i=1,…,m.

Then

{(F) is infeasible}  ⟺  {∃λ≥0:a=∑i=1mλiai}.\{\text{(F) is infeasible}\} \iff \left\{ \exists \lambda \ge 0 : a = \sum_{i=1}^m \lambda_i a_i \right\}.{(F) is infeasible}⟺{∃λ≥0:a=i=1∑m​λi​ai​}.

This is the special case of the general theorem on the alternative from which the book derives the general case (Exercise 1.9), and so the root of the LP duality theorem.

Formalization Note λ\lambdaλ ranges over Rm\mathbb R^mRm with λ≥0\lambda \ge 0λ≥0 componentwise; aTxa^TxaTx is the dot product. Both directions of the equivalence are stated.

Preamble
import Mathlib

open Matrix
Formal statement
namespace ModernConvex.LPDuality

/-- Ben-Tal–Nemirovski, Lemma 1.4.1 (the homogeneous Farkas lemma), p. 34:
the system `(F) : aᵀx < 0, aᵢᵀx ≥ 0 (i = 1, …, m)` is infeasible iff `a = ∑ λᵢaᵢ` with `λ ≥ 0`. -/
theorem homogeneous_farkas_lemma {m n : ℕ} (a : Fin n → ℝ) (as : Fin m → Fin n → ℝ) :
    (¬ ∃ x : Fin n → ℝ, a ⬝ᵥ x < 0 ∧ ∀ i, 0 ≤ as i ⬝ᵥ x) ↔
      ∃ l : Fin m → ℝ, 0 ≤ l ∧ a = ∑ i, l i • as i := by sorry

end ModernConvex.LPDuality
Source
Ben-Tal & Nemirovski, Lectures on Modern Convex Optimization, SIAM 2001, p. 34, Lemma 1.4.1 (the homogeneous Farkas lemma), system (F)
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Fix natural numbers m,nm, nm,n, a vector a∈Rna \in \mathbb{R}^na∈Rn, and vectors a1,…,am∈Rna_1, \dots, a_m \in \mathbb{R}^na1​,…,am​∈Rn. Write u⊤x=∑jujxju^\top x = \sum_j u_j x_ju⊤x=∑j​uj​xj​ for the standard dot product. The statement asserts the equivalence of two conditions.

Condition 1. There is no x∈Rnx \in \mathbb{R}^nx∈Rn satisfying both

a⊤x<0andai⊤x≥0 for all i=1,…,m.a^\top x < 0 \quad\text{and}\quad a_i^\top x \ge 0 \text{ for all } i = 1, \dots, m .a⊤x<0andai⊤​x≥0 for all i=1,…,m.

Condition 2. There exists λ∈Rm\lambda \in \mathbb{R}^mλ∈Rm with λi≥0\lambda_i \ge 0λi​≥0 for every iii (the inequality 0≤λ0 \le \lambda0≤λ is componentwise) such that

a=∑i=1mλiai.a = \sum_{i=1}^m \lambda_i a_i .a=i=1∑m​λi​ai​.

This is a full "if and only if". The inequality on a⊤xa^\top xa⊤x is strict; the inequalities on the ai⊤xa_i^\top xai⊤​x are non-strict.

Degenerate cases:

  • m=0m = 0m=0: the sum is empty and equals 000, so the right side says a=0a = 0a=0. The left side says no xxx has a⊤x<0a^\top x < 0a⊤x<0, which also holds exactly when a=0a = 0a=0.
  • n=0n = 0n=0: every vector is the zero vector and every dot product is 000. Both sides are then true.
Human review
  • Endorsed by Community (Bot) · Oct 20, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 20, 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