Global convergence property of the affine scaling methods for primal degenerate linear programming problems

This paper investigates the global convergence property of the affine scaling method under the assumption of dual nondegeneracy. The behavior of the method near degenerate vertices is analyzed in detail on the basis of the equivalence between the affine scaling methods for homogeneous LP problems and Karmarkar’s method. It is shown that the step-size 1/8, where the displacement vector is normalized with respect to the distance in the scaled space, is sufficient to guarantee the global convergence for dual nondegenerate LP problems. The result can be regarded as a counterpart to Dikin’s global convergence result on the affine scaling method assuming primal nondegeneracy.