Linear Programming Duality

This section gives an overview of Linear Programming and specifically states the Linear Programming Duality Theorem which is necessary to prove the The minimax theorem.

An excellent review of this is given in [vonStengel2023].

Definition of a Linear Program

A linear program defined by \(M\in\mathbb{R}^{(m\times n}\), \(b\in\mathbb{R}^{m}\) and \(c\in\mathbb{R}^n\) corresponds to:

\[\max_{x\in\mathbb{R}^{n}} c^Tx\]

Subject to:

\[\begin{split}\begin{align} Mx &\leq b \\ x_i &\geq 0&&\text{ for }i\leq m \end{align}\end{split}\]

Such a linear program is feasible if there exists some vector \(x\) that satisfies the constraints.

Definition of the Dual of a Linear Program

The dual of the linear program of Definition of a Linear Program is defined by:

\[\min_{y\in\mathbb{R}^{m}} y^Tb\]

Subject to:

\[\begin{split}\begin{align} M^T y &\geq c \\ y_i &\geq 0&&\text{ for }i\leq n \end{align}\end{split}\]

Linear Program Duality Theorem

If a linear program and its dual are both feasible then there exists \(x\) and \(y\) that are both optimal solutions such that \(c^Tx=y^Tb\).

A variety of proofs of this theorem exist that take different approaches. One such proof can be found in [Vanderbei1998].