Insights into the interior-point methods

In this paper, the authors study the search directions of three important interior-point algorithms, namely, the primal-affine scaling method (with logarithmic barrier function), the dual-affine scaling method (with logarithmic barrier function), and the primal-dual interior point method. From an algebraic point of view, they show that the search directions of these three algorithms are merely Newton directions along three different ‘paths’ that led to a solution of the Karush-Kuhn-Tucker conditions of a given linear programming problem. From a geometric point of view, the authors show that these directions can be obtained by solving certain well-defined subproblems. Both views provide a general platform for studying the existing interior-point methods and deriving new interior-point algorithms. The authors illustrate the derivation of new interior-point algorithms by replacing the logarithmic barrier function with an entropic barrier function. The results have been generalized and discussed.