Weak Duality for Finite Standard-Form Linear Programs
ProvedPrimalDual.pd_weak_dualitylinear-programmingoptimizationprimal-dualweak-duality
Weak duality for the finite standard-form pair.
Let , , and be a finite standard-form primal–dual pair with primal variables indexed by and constraints by . Let be primal feasible, i.e. and for every , and let be dual feasible, i.e. and for every . Then
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 into a certificate that no feasible primal of value below exists, which is the engine of the load-balancing failure argument.
Formalization Note No sign conditions on , , or 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 PrimalDualSource
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).