Convergence and boundary behavior of the projective scaling trajectories for linear programming

The paper analyzes 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. It shows that a projective scaling trajectory tends to an optimal solution which in general depends on the starting point. When the optimal solution is unique, the paper shows that all projective scaling trajectories approach the optimal solution through the same asymptotic direction. The present 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.