Strong Duality Theorem

For the standard symmetric primal-dual pair

$$\textrm{(P): } \max\ \mathbf{c}^T \mathbf{x} \quad \textrm{s.t.}\quad A\mathbf{x} \le \mathbf{b},\ \mathbf{x} \ge \mathbf{0},$$ $$\textrm{(D): } \min\ \mathbf{b}^T \mathbf{y} \quad \textrm{s.t.}\quad A^T \mathbf{y} \ge \mathbf{c},\ \mathbf{y} \ge \mathbf{0},$$

weak duality gives $\mathbf{c}^T \mathbf{x} \le \mathbf{b}^T \mathbf{y}$ for every feasible pair $(\mathbf{x}, \mathbf{y})$.

The Strong Duality Theorem says this inequality closes to equality at the optimum:

If (P) has an optimal solution $\mathbf{x}^*$, then (D) also has an optimal solution $\mathbf{y}^*$, and

$$\mathbf{c}^T \mathbf{x}^* = \mathbf{b}^T \mathbf{y}^*.$$

The statement is symmetric: if (D) has an optimal solution, so does (P), with the same objective value. There is no duality gap at optimality.

This is a much stronger guarantee than weak duality, which only bounds one objective by the other.