Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Weak Duality for Finite Standard-Form Linear Programs

Proved
PrimalDual.pd_weak_duality

by wenxinzhang · Aug 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

linear-programmingoptimizationprimal-dualweak-duality

Weak duality for the finite standard-form pair.

Let A=(aij)A=(a_{ij})A=(aij​), b=(bj)b=(b_j)b=(bj​), and c=(ci)c=(c_i)c=(ci​) be a finite standard-form primal–dual pair with primal variables indexed by i∈ιi\in\iotai∈ι and constraints by j∈κj\in\kappaj∈κ. Let xxx be primal feasible, i.e. x≥0x\ge 0x≥0 and ∑iaijxi≥bj\sum_i a_{ij}x_i\ge b_j∑i​aij​xi​≥bj​ for every jjj, and let yyy be dual feasible, i.e. y≥0y\ge 0y≥0 and ∑jaijyj≤ci\sum_j a_{ij}y_j\le c_i∑j​aij​yj​≤ci​ for every iii. Then

∑j∈κbj yj  ≤  ∑i∈ιci xi.\sum_{j\in\kappa} b_j\,y_j \;\le\; \sum_{i\in\iota} c_i\,x_i.j∈κ∑​bj​yj​≤i∈ι∑​ci​xi​.

Every feasible dual value is therefore a lower bound on every feasible primal value. In this mission the inequality turns a feasible dual of value kkk into a certificate that no feasible primal of value below kkk exists, which is the engine of the load-balancing failure argument.

Formalization Note No sign conditions on AAA, bbb, or ccc are required: the statement covers the general standard form, not only the covering–packing subclass.

Preamble
import Definitions.Def_pd_finite_lp
Formal statement
namespace PrimalDual

theorem pd_weak_duality {ι κ : Type*} [Fintype ι] [Fintype κ]
    (P : FinitePrimalDual ι κ) (x : ι → ℝ) (y : κ → ℝ)
    (hx : P.PrimalFeasible x) (hy : P.DualFeasible y) :
    P.dualObjective y ≤ P.primalObjective x := by
  sorry

end PrimalDual
Source
Niv Buchbinder and Joseph (Seffi) Naor, The Design of Competitive Online Algorithms via a Primal--Dual Approach, https://www.tau.ac.il/~nivb/download/pd-survey.pdf, Theorem 2.1 and proof, pp. 98--99, equations (2.1)--(2.3).

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