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

We 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. Our methods comprise the following features: At each step, a projection is used to recenter the variables to the domainx_is_i. The projections are separable into two-dimensional orthogonal projections on a convex set, and thus they are seasy 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 nonnegativity condition. We prove that a short step version of our method converges in polynomial time.Research performed while visiting the Institut für Angewandte Mathematik, University of Würzburg, D-87074 Würzburg, Germany, as a Research Fellow of the Alexander von Humboldt Foundation.