Basic lemmas in polynomial-time infeasible-interiorpoint methods for linear programs

The primal-dual infeasible-interior-point algorithm is known 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 require 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.Partial support from the Okawa Institute of Information and Telecommunication.