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

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.

• 저널Management Science · 41(12) · 1922–1934
• 토픽Advanced Optimization Algorithms Research · Numerical Analysis
• DOI10.1287/mnsc.41.12.1922
• 저자Osman Güler, C. Roos, Tamás Terlaky, Jean-Philippe Vial