  


A predictorcorrector algorithm for linear optimization based on a specific selfregular proximity function
jiming Peng (pengjmcmaster.ca) Abstract: It is well known that the socalled firstorder predictorcorrector methods working in a large neighborhood of the central path are among the most efficient interiorpoint 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 firstorder predictorcorrector type methods can be further improved. In this paper, based on a specific selfregular 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 firstorder predictorcorrector method for LO that uses a selfregularity induced search direction in the corrector steps is proposed. We prove that our predictorcorrector 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, InteriorPoint Methods,SelfRegular 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/2003 Modify/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  