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
is equal to the maximum of the distances from z to the hyperplanes separating z and
. We consider the theorems of Farkas, Gale, Gordan, and Motzkin, as well as new theorems that characterize the optimality conditions of discrete l
1-approximation problems and multifacility location problems. It is shown that, with proper choices of
, 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
, then y solves the dual system. Otherwise, when r 0 and z
, 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
. If the norm is smooth and strictly convex, then there are explicit rules for retrieving x from r and vice versa. |