Interior Point Methods for Linear Programming: Just Call Newton, Lagrange, and Fiacco and McCormick!

Abstract

Interior point methods are the right way to solve large linear programs. They are also much easier to derive, motivate, and understand than they at first appeared. Lagrange told us how to convert a minimization with equality constraints into an unconstrained minimization. Fiacco and McCormick told us how to convert a minimization with inequality constraints into a sequence of unconstrained minimizations. Newton told us how to solve unconstrained minimizations. Linear programs are minimizations with equations and inequalities. Voila!