A COLLINEAR SCALING INTERPRETATION OF KARMARKAR'S LINEAR PROGRAMMING ALGORITHM

In 1980 W. C. Davidon proposed a class of unconstrained minimization methods, called collinear scaling algorithms, that are invariant under projective transformations. In these methods the nonlinear function f to be minimized is approximated near a point x(0) by a suitable conic function q (x(0) + p) = f(0) + < g, p > / (1 + < d, p >) + 1/2 < p, Ap > / (1 + < d, p >)(2) and the conic search direction is the global minimizer of q(x(0) + p). The full-dimensional version of Karmarkar's 1984 linear programming algorithm is shown to be a collinear scaling method for minimizing Karmarkar's potential function g(K), where the denominator 1 + < d, p > of the conic function is chosen as the normalized linear program objective function and the Taylor series expansions of g(K) (x(0) + P) and q (x(0) + p) agree to second order.