Theorems of the Alternative and Duality

Abstract

This paper investigates the relations between theorems of the alternative and the minimum norm duality theorem. A typical theorem of the alternative is associated with two systems of linear inequalities and/or equalities, a primal system and a dual one, asserting that either the primal system has a solution, or the dual system has a solution, but never both. On the other hand, the minimum norm duality theorem says that the minimum distance from a given point z to a convex set $\mathbb{K}$ is equal to the maximum of the distances from z to the hyperplanes separating z and $\mathbb{K}$. We consider the theorems of Farkas, Gale, Gordan, and Motzkin, as well as new theorems that characterize the optimality conditions of discrete l ₁-approximation problems and multifacility location problems. It is shown that, with proper choices of $\mathbb{K}$, each of these theorems can be recast as a pair of dual problems: a primal steepest descent problem that resembles the original primal system, and a dual least–norm problem that resembles the original dual system. The norm that defines the least-norm problem is the dual norm with respect to that which defines the steepest descent problem. Moreover, let y solve the least norm problem and let r denote the corresponding residual vector. If r=0, which means that z ∈ $\mathbb{K}$, then y solves the dual system. Otherwise, when r≠0 and z ∉ $\mathbb{K}$, any dual vector of r solves both the steepest descent problem and the primal system. In other words, let x solve the steepest descent problem; then, r and x are aligned. These results hold for any norm on $\mathbb{R}^n$. If the norm is smooth and strictly convex, then there are explicit rules for retrieving x from r and vice versa.