A Survey of the Implications of the Behavior of the Central Path for the Duality Theory of Linear Programming

O. Güler, C. Roos, T. Terlaky and J.-Ph. Vial
Additional contact information
O. Güler: Department of Mathematics and Statistics, University of Maryland Baltimore County, Baltimore, Maryland 21228
T. Terlaky: Faculty of Technical Mathematics and computer Science, Delft University of Technology, P.O. Box 5031, 2600 GA Delft, The Netherlands
J.-Ph. Vial: Départment COMIN, Universitéde Genève, 102 Bd Carl-Vogt, CH-1211 Genève 4, Switzerland

Management Science, 1995, vol. 41, issue 12, 1922-1934

Abstract: The literature in the field of interior point methods for Linear Programming has been almost exclusively algorithmic oriented. Very few contributions have been made towards the theory of Linear Programming itself. In particular none of them offer a simple, self-contained introduction to the theory of Linear Programming and linear inequalities. The purpose of this paper is to show that the interior point methodology can be used to introduce the field of Linear Programming. Starting from scratch, and using only elementary results from calculus and linear algebra, we prove that for every value of the barrier parameter, the logarithmic barrier function for the primal-dual problem has a unique minimizer, and that the path of these minimizers (the central path) converges to a strictly complementary pair of optimal solutions. These results were proved more than a decade ago with advanced mathematical arguments. Our proofs are new: they are also simpler and often more natural than the ones currently known. They provide a new approach to the fundamental results of Linear Programming, including the existence of a strictly complementary solution, and the strong duality theorem.

Keywords: linear inequalities; Linear Programming; interior points; duality; complementarity; Farkas lemma; boundedness; unboundedness (search for similar items in EconPapers)
Date: 1995
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.41.12.1922 (application/pdf)

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:inm:ormnsc:v:41:y:1995:i:12:p:1922-1934

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().