ISSN:
1573-2878
Keywords:
Theorems of the alternative
;
duality
;
minimum norm duality theorem
;
steepest descent directions
;
least norm problems
;
alignment
;
constructive optimality conditions
;
degeneracy
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
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 1-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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1022644832111
Permalink
