Past exam of the mathematics course of the University of Oxford / 2015 / Prelims / Mathematics IV / 5 / a

If $A$ has $m$ rows and $n$ columns, attach a nonnegative dual variable $y_i$ to each of the $m$ upper-bound constraints. The dual linear program isHere $A^T$ is the transpose of $A$, and all vector inequalities hold componentwise. Nonnegative dual variables preserve the direction of the original inequalities when taking weighted sums.

For feasible solutions $\mathbf{x},\mathbf{y}$, nonnegativity givesThe first inequality uses $A^T\mathbf{y}\ge \mathbf{c}$ and $\mathbf{x}\ge 0$; the second uses $A\mathbf{x}\le \mathbf{b}$ and $\mathbf{y}\ge 0$. This is weak duality.

For every primal feasible solution $\mathbf{x}$, weak duality givesThus no primal feasible solution improves on ${\mathbf{x}}^{\ast }$. Similarly, for every dual feasible solution $\mathbf{y}$,Therefore both candidates are optimal, with the same objective function value. Equality is a linear programming optimality certificate and does not require a separate existence argument.

The complementary slackness conditions areTo see their role, decompose the duality gap asEvery summand is nonnegative for feasible solutions, so the gap is zero exactly when every displayed product vanishes. Zero gap implies optimality by weak duality. Conversely, strong duality states that primal and dual optima, when both are attained, have equal values, and hence satisfy these conditions.