Karmarkar’s linear programming algorithm and Newton’s 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 ℝⁿ 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:ℝⁿ⇒ℝ^m to Karmarkar’s original algorithm for a linear program in ℝ^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=ℝlsquo;(x) which maps the hyperplane Hopt={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 ℝlsquo; to an unbounded polytope. Let fLB(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+λvN(y):λ≥0} where vN(y)=¸-(∇²f(y))’-¹(∇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’)=ℝlsquo;(x’(^k’)) then {y’(^k’)} are a set of global Newton method iterates for fLB(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.