Convergence and Boundary Behavior of the Projective Scaling Trajectories for Linear Programming

We analyze the convergence and boundary behavior of the continuous trajectories of the vector field induced by the projective scaling algorithm as applied to (possibly degenerate) linear programming problems in Karmarkar's standard form. We show that a projective scaling trajectory tends to an optimal solution which in general depends on the starting point. When the optimal solution is unique, we show that all projective scaling trajectories approach the optimal solution through the same asymptotic direction. Our analysis is based on the affine scaling trajectories for the homogeneous standard form linear program that arises from Karmarkar's standard form linear program by removing the unique nonhomogeneous constraint.