An infeasible-interior-point algorithm using projections onto a convex set

The authors present a new class of primal-dual infeasible-interior-point methods for solving linear programs. Unlike other infeasible-interior-point algorithms, the iterates generated by our methods lie in general position in the positive orthant of ℝ²ⁿ and are not restricted to some linear manifold. The present methods comprise the following features: At each step, a projection is used to ‘recenter’ the variables to the domain xisi≥μ. The projections are separable into two-dimensional orthogonal projections on a convex set, and thus they are easy to implement. The use of orthogonal projections allows that a full Newton step can be taken at each iteration, even if the result violates the non-negativity condition. The authors prove that a short step version of our method converges in polynomial time.