Theorems of the Alternative and Duality

A. Dax and V. P. Sreedharan

Journal of Optimization Theory and Applications, 1997, vol. 94, issue 3, No 2, 590 pages

Abstract: 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.

Keywords: Theorems of the alternative; duality; minimum norm duality theorem; steepest descent directions; least norm problems; alignment; constructive optimality conditions; degeneracy (search for similar items in EconPapers)
Date: 1997
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1023/A:1022644832111 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:94:y:1997:i:3:d:10.1023_a:1022644832111

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1023/A:1022644832111

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().