KARMARKAR LINEAR-PROGRAMMING ALGORITHM AND NEWTON METHOD

This paper describes a full-dimensional version of Karmarkar's linear programming algorithm, the projective scaling algorithm, which is defined for any linear program in R(n) having a bounded, full-dimensional polytope of feasible solutions. If such a linear program has m inequality constraints, then it is equivalent under an injective affine mapping J:R(n) --> R(m) to Karmarkar's original algorithm for a linear program in R(m) having m - n equality constraints and m inequality constraints. Karmarkar's original algorithm minimizes a potential function g(x), and the projective scaling algorithm is equivalent to that version of Karmarkar's algorithm whose step size minimizes the potential function in the step direction. The projective scaling algorithm is shown to be a global Newton method for minimizing a logarithmic barrier function in a suitable coordinate system. The new coordinate system is obtained from the original coordinate system by a fixed projective transformation y = PHI(x) which maps the hyperplane H(opt) = {x:< c,x > = c0} specified by the optimal value of the objective function to the "hyperplane at infinity". The feasible solution set is mapped under PHI to an unbounded polytope. Let f(LB)(y) denote the logarithmic barrier function associated to the m inequality constraints in the new coordinate system. It coincides up to an additive constant with Karmarkar's potential function in the new coordinate system. The global Newton method iterate y* for a strictly convex function f(y) defined on a suitable convex domain is that point y* that minimizes f(y) on the search ray {y + lambda-upsilon-N(y):lambda greater-than-or-equal-to 0} where upsilon-N(y) = -(DELTA-2f(y))-1(DELTA-f(y)) is the Newton's method vector. If {x(k)} are a set of projective scaling algorithm iterates in the original coordinate system and y(k) = PHI(x(k)) then {y(k)} are a set of global Newton method iterates for f(LB)(y) and conversely. Karmarkar's algorithm with step size chosen to minimize the potential function is known to converge at least at a linear rate. It is shown (by example) that this algorithm does not have a superlinear convergence rate.