Optimization Online


A predictor-corrector algorithm for linear optimization based on a specific self-regular proximity function

jiming Peng (pengj***at***mcmaster.ca)
Tamas Terlaky (terlaky***at***mcmaster.ca)
Yunbin Zhao (ybzhao***at***mail.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/2003
Entry Accepted: 05/22/2003
Entry Last Modified: 05/22/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society