Finite Standard-Form Primal and Dual Linear Programs
Definitionpd_finite_lpThis 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 indexed by primal variables and constraints , a right-hand side , and a cost vector . The primal program minimizes subject to
and its dual maximizes subject to
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 on primal variables and on dual variables. The extra nonnegativity of , , and 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 and 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.
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.