On the relationship of interior-point methods

Abstract

In this paper, we show that the moving directions of 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 are merely the Newton directions along three different algebraic “paths” that lead to a solution of the Karush-Kuhn-Tucker conditions of a given linear programming problem. We also derive the missing dual information in the primal-affine scaling method and the missing primal information in the dual-affine scaling method. Basically, the missing information has the same form as the solutions generated by the primal-dual method but with different scaling matrices.

Keywords

• linear programming
• interior-point method
• Newton method
• duality theory.