An affine scaling method with an infeasible starting point: Convergence analysis under nondegeneracy assumption

In this paper, the authors propose an infeasible-interior-point algorithm for linear programming based on the affine scaling algorithm by Dikin. The search direction of the algorithm is composed of two directions, one for satisfying feasibility and the other for aiming at optimality. Both directions are affine scaling directions of certain linear programming problems. Global convergence of the algorithm is proved under a reasonable nondegeneracy assumption. A summary of analogous global convergence results without any nondegeneracy assumption is also given.