ABSTRACT
The general appeal of interior point methods is that they can exhibit both good practical and theoretical properties. For example, although the simplex method performs very well in practice, it can, (as seen in Chapter 3) in the worst case, explore most or all extreme points thereby exhibiting exponential worst-case complexity. For this chapter, we develop a variant of interior point methods called primal-dual path-following methods, which is found to be very effective in solving linear programs and exhibits polynomial worst-case complexity, i.e., the number of basic computational steps needed to find an optimal solution is bounded in the worst case by a polynomial whose value is a function of the size of the problem and desired level of accuracy.
