- A predictor-corrector algorithm for linear optimization based on a specific self-regular proximity function jiming Peng (pengjmcmaster.ca) Tamas Terlaky (terlakymcmaster.ca) Yunbin Zhao (ybzhaomail.amss.ac.cn) Abstract: 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. Keywords: Linear Optimization, Interior-Point Methods,Self-Regular Proximity Function, Large Neighborhood, Polynomial Complexity Category 1: Linear, Cone and Semidefinite Programming Citation: Technical Report, Advanced Optimization Lab, Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada, May, 2003 Download: [Postscript][PDF]Entry Submitted: 05/22/2003Entry Accepted: 05/22/2003Entry Last Modified: 05/22/2003Modify/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.