Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Finite Standard-Form Primal and Dual Linear Programs

Definition
pd_finite_lp

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

dualitylinear-programmingonline-algorithmsoptimizationprimal-dual

This module fixes the finite standard-form primal–dual pair underlying the online primal–dual method.

A finite standard-form pair consists of a coefficient matrix A=(aij)A=(a_{ij})A=(aij​) indexed by primal variables i∈ιi\in\iotai∈ι and constraints j∈κj\in\kappaj∈κ, a right-hand side b=(bj)b=(b_j)b=(bj​), and a cost vector c=(ci)c=(c_i)c=(ci​). The primal program minimizes ∑icixi\sum_i c_i x_i∑i​ci​xi​ subject to

∑i∈ιaijxi≥bj(j∈κ),x≥0,\sum_{i\in\iota} a_{ij}x_i \ge b_j \quad (j\in\kappa), \qquad x\ge 0,i∈ι∑​aij​xi​≥bj​(j∈κ),x≥0,

and its dual maximizes ∑jbjyj\sum_j b_j y_j∑j​bj​yj​ subject to

∑j∈κaijyj≤ci(i∈ι),y≥0.\sum_{j\in\kappa} a_{ij}y_j \le c_i \quad (i\in\iota), \qquad y\ge 0.j∈κ∑​aij​yj​≤ci​(i∈ι),y≥0.

The module defines both constraint values, both objectives, and the two feasibility predicates, together with the two-sided approximate complementary-slackness conditions with slack factor α\alphaα on primal variables and β\betaβ on dual variables. The extra nonnegativity of AAA, bbb, and ccc that makes the pair a covering primal with packing dual is recorded as a separate predicate.

This is the shared interface through which the mission states weak duality, prefix feasibility, and the failure certificate; the covering–packing subclass is the one instantiated by the unrelated-machines linear program.

Formalization Note The index types ι\iotaι and κ\kappaκ are arbitrary, with a Fintype instance assumed exactly where a finite sum is formed; no nonemptiness is assumed, and no sign conditions are built into the base structure.

Definition code
import Mathlib.Data.Fintype.BigOperators
import Mathlib.Data.Real.Basic

namespace PrimalDual

open scoped BigOperators

/--
A finite standard-form primal/dual pair.  The primal variables are indexed by `ι`,
the primal constraints (and dual variables) by `κ`.
-/
structure FinitePrimalDual (ι κ : Type*) where
  coeff : ι → κ → ℝ
  rhs : κ → ℝ
  cost : ι → ℝ

namespace FinitePrimalDual

variable {ι κ : Type*} [Fintype ι] [Fintype κ]

/-- The value of primal constraint `j` at a primal vector `x`. -/
def primalConstraintValue (P : FinitePrimalDual ι κ) (x : ι → ℝ) (j : κ) : ℝ :=
  ∑ i, P.coeff i j * x i

/-- The value of dual constraint `i` at a dual vector `y`. -/
def dualConstraintValue (P : FinitePrimalDual ι κ) (y : κ → ℝ) (i : ι) : ℝ :=
  ∑ j, P.coeff i j * y j

/-- The minimization objective of the primal program. -/
def primalObjective (P : FinitePrimalDual ι κ) (x : ι → ℝ) : ℝ :=
  ∑ i, P.cost i * x i

/-- The maximization objective of the dual program. -/
def dualObjective (P : FinitePrimalDual ι κ) (y : κ → ℝ) : ℝ :=
  ∑ j, P.rhs j * y j

/-- Feasibility for the standard-form primal: `x >= 0` and `A x >= b`. -/
def PrimalFeasible (P : FinitePrimalDual ι κ) (x : ι → ℝ) : Prop :=
  (∀ i, 0 ≤ x i) ∧ ∀ j, P.rhs j ≤ P.primalConstraintValue x j

/-- Feasibility for the standard-form dual: `y >= 0` and `A^T y <= c`. -/
def DualFeasible (P : FinitePrimalDual ι κ) (y : κ → ℝ) : Prop :=
  (∀ j, 0 ≤ y j) ∧ ∀ i, P.dualConstraintValue y i ≤ P.cost i

/--
The two-sided primal-variable condition from approximate complementary slackness:
every positive primal variable has a dual constraint within a factor `α` of tight.
-/
def SatisfiesPrimalApproxCS (P : FinitePrimalDual ι κ) (α : ℝ)
    (x : ι → ℝ) (y : κ → ℝ) : Prop :=
  ∀ i, 0 < x i →
    P.cost i / α ≤ P.dualConstraintValue y i ∧
      P.dualConstraintValue y i ≤ P.cost i

/--
The two-sided dual-variable condition from approximate complementary slackness:
every positive dual variable has a primal constraint within a factor `β` of tight.
-/
def SatisfiesDualApproxCS (P : FinitePrimalDual ι κ) (β : ℝ)
    (x : ι → ℝ) (y : κ → ℝ) : Prop :=
  ∀ j, 0 < y j →
    P.rhs j ≤ P.primalConstraintValue x j ∧
      P.primalConstraintValue x j ≤ β * P.rhs j

/--
The additional nonnegativity assumptions that make a standard-form pair a
covering-primal/packing-dual pair.  Weak duality and approximate complementary
slackness do not require these assumptions.
-/
structure IsCoveringPacking (P : FinitePrimalDual ι κ) : Prop where
  coeff_nonneg : ∀ i j, 0 ≤ P.coeff i j
  rhs_nonneg : ∀ j, 0 ≤ P.rhs j
  cost_nonneg : ∀ i, 0 ≤ P.cost i

end FinitePrimalDual

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, Section 2.1, pp. 97--101, including the primal/dual displays and the covering--packing paragraph after Theorem 2.3.
Human review
  • Endorsed by Shuze Chen · Nov 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 8, 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