A Collinear Scaling Interpretation of Karmarkar's Linear Programming Algorithm.

In 1980, W. C. Davidson proposed a class of unconstrained minimization methods, called collinear scaling algorithms, which are invariant under projective transformations. In these methods, the nonlinear function f(x) to be minimized is approximated near a point x sub 0 by a conic function q(bx sub 0 + x) = f sub 0 + {} over {1 + ) sup 2}, and a step is taken in the direction of the global minimum x sup * of q (x sub 0 + x) assuming that it has a global minimum. The full dimensional version of Karmarkar's algorithm is shown to be a collinear scaling algorithm to minimize Karmarkar's potential function, in which the denominator 1 + in the conic function is chosen to be the linear program's objective function normalized to be zero at the optimum, and the Taylor series expansion of f(x sub 0 + x) and q (x sub 0 + x) agree to second order.