= Solution
Associate a nonnegative <Lagrange multiplier> $\lambda_i$ with each inequality. The <Lagrangian dual problem> begins with
$$
L(x,\lambda)=c^Tx+\lambda^T(Ax-b)
=(c+A^T\lambda)^Tx-b^T\lambda,
\qquad \lambda\geq0.
$$
Its infimum over $x\in\mathbb R^n$ is finite exactly when $A^T\lambda+c=0$, in which case it equals $-b^T\lambda$. The dual <linear program> is consequently
$$
\boxed{\max_{\lambda\in\mathbb R^m}
\{-b^T\lambda:A^T\lambda+c=0,\ \lambda\geq0\}}.
$$
For any primal-feasible $x$ and dual-feasible $\lambda$,
$$
-b^T\lambda
\leq-x^TA^T\lambda
=c^Tx,
$$
which proves <weak duality>. <Strong duality> means equality of the two optimal values. The stated strict feasibility is the <Slater condition>; together with finiteness of the primal optimum it gives strong duality and an attained dual optimum $\lambda^*$.
Back to article page
