An Algorithmic and Numerical Comparison of
Several Interior-Point Methods
Vanderbei, R. J., Duarte, A. and Yang, B.
We present a unified framework for studying interior point methods for
linear programming. Within this framework, we compare three
fundamental methods: (1) path-following, (2) barrier, and (3)
primal/dual affine-scaling (our terminology differs slightly from the
commonly accepted terminology). The step directions for each of
these methods are linear combinations of three fundamental directions:
(1) step-toward-optimality, (2) step-toward-center, and (3)
step-toward- feasibilty. By making very simple modifications to LOQO,
we have created efficient implementations of each of these methods,
which we compared one to another. We shall present the results of this
comparison. In addition, associated with each of the three
fundamental algorithms, there are three choices for how to organize
the system of equations that must be solved: (1) general ordering
heuristics applied to the KKT system, (2) primal-scaling, and (3)
dual-scaling. Each of these three choices produce identical step
directions but the choice can have a dramatic effect on the efficiency
of the implementation.
Contact the first author at rvdb@princeton.edu
![[IP PAGE]](../../InteriorPoint/gif/HOME.gif)
![[SEARCH AGAIN]](../../InteriorPoint/gif/SEARCH.gif)