Strong duality and complementary slackness for a standard-form linear program

Strong duality and complementary slackness for a linear program in standard form. Let $M \in \mathbb{R}^{m \times n}$, $d \in \mathbb{R}^n$, $g \in \mathbb{R}^m$, and suppose $u_0$ is optimal for

Then there is a dual vector $p \in \mathbb{R}^m$ with

The first condition is feasibility for the dual program $\max\{g^{\mathsf T}p : M^{\mathsf T}p \le d\}$, the second says the duality gap vanishes, and the third is complementary slackness: a variable that is positive in the primal forces its dual constraint to be tight.

This is the statement on which the optimality conditions of linear programming rest, and through which multipliers are extracted for problems, such as two-stage stochastic programs, whose deterministic equivalent is a linear program. The proof applies Gale's theorem of the alternative to the system $M^{\mathsf T}p \le d$, $g^{\mathsf T}p \ge d^{\mathsf T}u_0$: an alternative certificate would produce either a strictly better feasible point or a feasible direction of strictly negative cost, contradicting optimality of $u_0$.

Formalization note. Optimality of $u_0$ is given as a hypothesis in pointwise form (it is a minimizer over the feasible set), so no notion of optimal value is needed; attainment of the primal minimum is therefore assumed rather than derived here.