It is well known that the so-called first-order predictor-corrector methods working in a large neighborhood of the central path are among the most efficient interior-point methods (IPMs) for linear optimization (LO) problems. However, the best known iteration complexity of this type of methods is $O\br{n \log\frac{(x^0)^Ts^0}{\varepsilon}}$. It is of interests to investigate whether the complexity of the first-order predictor-corrector type methods can be further improved. In this paper, based on a specific self-regular proximity function, we define a new neighborhood of the central path. In particular, we show that the new neighborhood matches the standard large neighborhood that is defined by the infinity norm and widely used in the IPM literature. A new first-order predictor-corrector method for LO that uses a self-regularity induced search direction in the corrector steps is proposed. We prove that our predictor-corrector algorithm, working in a large neighborhood, has an $O\left(\sqrt{n}\log n \log\frac{(x^0)^Ts^0}{\varepsilon} \right)$ iteration bound. Local quadratic convergence of the algorithm is also established.
Citation
Technical Report, Advanced Optimization Lab, Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada, May, 2003