  


Adaptive Large Neighborhood SelfRegular PredictorCorrector IPMs for LO
Maziar Salahi (salahimmath.mcmaster.ca) Abstract: It is known that predictorcorrector 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 selfregular proximity based predictorcorrector (SRPC) IPM for LO in a large neighborhood of the central path. Like all predictorcorrector IPMs, our new SRPC algorithms have a predictor step and a corrector step. In the predictor step we use either the affine scaling or a selfregular direction, while in the corrector step we always use a selfregular 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 SRPC IPMs. An $O\left(\sqrt{n} \exp(\frac{1q+\log n}{2})\log n\log{\frac{n}{\epsilon}}\right)$ worstcase 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 predictorcorrector 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, PredictorCorrector Method, Quadratic Convergence, Selfregular 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/2004 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  