Basic lemmas in polynomial-time infeasible-interior-point methods for linear programs

The primal-dual infeasible-interior-point algorithm is knwon as one of the most efficient computational methods for linear programs. Recently, a polynomial-time computational complexity bound was established for special variants of the algorithm. However, they impose severe restrictions on initial points and requrie a common step length in the primal and dual spaces. This paper presents some basic lemmas that bring great flexibility and improvement into such restrictions on initial points and step lengths, and discusses their extensions to linear and nonlinear monotone complementarity problems.