- Adaptive Large Neighborhood Self-Regular Predictor-Corrector IPMs for LO Maziar Salahi (salahimmath.mcmaster.ca) Tama's Terlaky (terlakymcmaster.ca) Abstract: It is known that predictor-corrector methods in a large neighborhood of the central path are among the most efficient interior point methods (IPMs) for linear optimization (LO) problems. The best iteration bound based on the classical logarithmic barrier function is $O\left(n\log{\frac{n}{\epsilon}}\right)$. In this paper we propose a family of self-regular proximity based predictor-corrector (SR-PC) IPM for LO in a large neighborhood of the central path. Like all predictor-corrector IPMs, our new SR-PC algorithms have a predictor step and a corrector step. In the predictor step we use either the affine scaling or a self-regular direction, while in the corrector step we always use a self-regular direction. Our new algorithms use a special proximity function with different search directions and thus allows us to improve the so far best theoretical iteration complexity for a family of SR-PC IPMs. An $O\left(\sqrt{n} \exp(\frac{1-q+\log n}{2})\log n\log{\frac{n}{\epsilon}}\right)$ worst-case iteration bound with quadratic convergence is established, where $q$ is the barrier degree of the SR proximity function. If $q=1+\log n,$ then we have the so far best iteration complexity for the first order predictor-corrector method in a large neighborhood, and if $q=1+2\log(\log n)$ our algorithm has an $O\left(n\log\frac{n}{\epsilon}\right)$ iteration complexity. For the case $q=1,$ the result is a factor $\log n$ worse than the exist recent results. Keywords: Linear Optimization, Predictor-Corrector Method, Quadratic Convergence, Self-regular Proximity Function, Large Neighborhood, Polynomial Complexity. Category 1: Linear, Cone and Semidefinite Programming Citation: Advanced Optimization Lab. McMaster University, Report 2004/7, Submitted. Download: [PDF]Entry Submitted: 08/06/2004Entry Accepted: 08/06/2004Entry Last Modified: 08/06/2004Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.