Optimization Online


Adaptive Large Neighborhood Self-Regular Predictor-Corrector IPMs for LO

Maziar Salahi (salahim***at***math.mcmaster.ca)
Tama's Terlaky (terlaky***at***mcmaster.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/2004
Entry Accepted: 08/06/2004
Entry Last Modified: 08/06/2004

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