We present results on global and polynomial-time convergence of infeasible-interior-point methods for self-scaled conic programming, which includes linear and semidefinite programming. First, we establish global convergence for an algorithm using a wide neighborhood. Next, we prove polynomial complexity for the algorithm with a slightly narrower neighborhood. Both neighborhoods are related to the wide (minus infinity) neighborhood and are much larger than the 2-norm neighborhood. We also provide stopping rules giving an indication of infeasibility.
Citation
Technical Report TR1388, Department of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY 14853. Date: October 10, 2003.