《《1993 On the realationship of interior-point methods》.pdf

Intenrat. J. Math. Math. Sci. 565 VOL. 16 NO. 3 (1993) 565-572 ON THE RELATIONSHIP OF INTERIOR-POINT METHODS RUEY-LIN SHEU ATT Bell Laboratories, Holmdel and SHU-CHERNG FANG Operations Research Industrial Engineering North Carolina State University Box 7913, Raleigh, NC 27695-7913, USA (Received February 20, 1992 and in revised form October 13, 1992) 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. KEY WORDS AND PHRASES. Linear programming, interior-point method, Newton method, duality theory. AMS SUBJECT CLASSIFICATION CODE. 90c05. 1. INTRODUCTION. Since Karmarkar [7] proposed his polynomial-time projective scaling algorithm for solving linear programming problems in 1984, the interest of studying interior-point methods has been arising to a peak in recent years. In particular, Vanderbei, Meketon, and Freeman [15], and independently, Barnes [2] extended Karmarkar’s algor