Linear-programming duality

Mathematical statement

Qualify the exact rational m-by-n matrix A and matching b,c. The dual variable has m components and A^T*y≥c has n constraints. For a feasible primal point x and dual point y verify c^T*x≤y^T*A*x≤b^T*y. If both are feasible and the objective values agree, weak duality certifies both points optimal. Equality without both feasibility checks is insufficient. A finite grid does not prove general strong duality or settle infeasible/unbounded cases. General finite-dimensional LP strong duality remains a separately stated theorem, not the result of these finite candidate checks.

Representative formula (exact TeX)

g(x,y)=b^\top*y-c^\top*x

Assumptions

• Use only the fixed maximize/less-equal/nonnegative primal convention.
• Matrices, vectors and candidate points are bounded exact rationals.

Symbol scope

• g — pointwise duality gap function
• A — constraint matrix
• b — primal rhs
• c — primal objective
• x — primal candidate point
• y — dual candidate point

Intuition, definition, and misconceptions

Construct the complete dual from the fixed primal.

Check each step of the weak-duality chain exactly.

Separate a zero-gap certificate from the general strong-duality theorem.

Notation candidate: for fixed problem data(A,b,c),g(x,y)=b^T y−c^T x is a scalar gap depending on both candidate points; A remains in the surrounding feasibility statement. Under the maximize/≤/nonnegative convention,x≥0,Ax≤b,y≥0 and A^T y≥c are required for the weak-duality nonnegative-gap certificate. Equal objectives or a finite grid do not prove general strong duality.

Do not mix dual sign conventions or claim optimality merely because two objective numbers happen to agree.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Standard form of a linear program — Fix one primal convention.
• Optimization problem — Separate feasibility from optimality.
• Usual order on the real numbers — Use componentwise inequalities.

Verification boundary

Finite candidate points or grids do not prove general strong duality or classify infeasible/unbounded cases. The shared D(A,b,c)=g display leaves the gap interpretation unresolved: a candidate-point gap b^T*y−c^T*x also depends on x,y, whereas an optimal-value gap needs its own definition and existence premises. The original formula and roles are retained for alignment review.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Add complementary slackness and LP optimality conditions.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.