# Linear-programming duality

This English edition is an AI candidate and does not yet have an OCME Atlas (GPT-6) Twin closure receipt.

For primal maximize c^T*x with A*x≤b,x≥0, the dual minimizes b^T*y with A^T*y≥c,y≥0; feasible pairs satisfy weak duality.

mko-linear-program-duality · theorem · v0.10.0



## 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 weak-duality chain and a zero-gap optimality certificate](https://ocme.evemisslab.com/en/derivations/derivation-mko-linear-program-duality-01/)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](https://ocme.evemisslab.com/en/mko/mko-linear-program-standard-form/) — Fix one primal convention.
- [Optimization problem](https://ocme.evemisslab.com/en/mko/mko-optimization-problem/) — Separate feasibility from optimality.
- [Usual order on the real numbers](https://ocme.evemisslab.com/en/mko/mko-order-relation/) — 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.

[Canonical MKO JSON](https://ocme.evemisslab.com/data/mko/source13-20261018-linear-program-duality.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-linear-program-duality/index.md)