A survey of the implications of the behavior of the central path for the duality theory of Linear Programming

A survey of the implications of the behavior of the central path for the duality theory of Linear Programming

0.00 Avg rating0 Votes
Article ID: iaor1997337
Country: United States
Volume: 41
Issue: 12
Start Page Number: 1922
End Page Number: 1934
Publication Date: Dec 1995
Journal: Management Science
Authors: , , ,
Keywords: interior point methods
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 te 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 poitn methodology can be used to introduce the field of Linear Programming. Starting from scratch, and using only elementary results from calculus and linear algebra, the authors 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. The present 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.

Reviews

Required fields are marked *. Your email address will not be published.