Convergence analysis of the projective scaling algorithm based on a long-step homogeneous affine scaling algorithm

In this paper the authors give a new convergence analysis of a projective scaling algorithm. They consider a long-step affine scaling algorithm applied to a homogeneous linear programming problem obtained from the original linear programming problem. This algorithm takes a fixed fraction of the way towards the boundary of the nonnegative orthant at each iteration. The iteration sequence for the original problem is obtained by pulling back the homogeneous iterates onto the original feasible region with a conical projection, which generates the same search direction as the original projective scaling algorithm at each iterate. The recent convergence results for the long-step affine scaling algorithm by the authors are applied to this algorithm to obtain some convergence results on the projective scaling algorithm. Specifically, the authors will show: (i) polynomiality of the algorithm with complexities of and iterations for and , respectively; (ii) global convergence of the algorithm when the optimal face is unbounded; (iii) convergence of the primal iterates to a relative interior point of the optimal face; (iv) convergence of the dual estimates to the analytic center of the dual optimal face; and (v) convergence of the reduction rate of the objective function value to .