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: | Roos C., Terlaky T., Gler O., Vial J.-P.H. |
Keywords: | interior point methods |
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.