Adaptive Large-Neighborhood Self-Regular Predictor-Corrector Interior-Point Methods for Linear Optimization

M. Salahi () and T. Terlaky
Additional contact information
M. Salahi: McMaster University
T. Terlaky: McMaster University

Journal of Optimization Theory and Applications, 2007, vol. 132, issue 1, No 9, 143-160

Abstract: 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(nlog (n/∊)). In this paper, we propose a family of self-regular proximity-based predictor-corrector (SRPC) IPMs for LO in a large neighborhood of the central path. In the predictor step, we use either an affine scaling or a self-regular direction; in the corrector step, we use always 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 SRPC IPMs. An O $$(\sqrt{n}{\exp} ((1 - q + {\log} n)/2) {\log} n {\log} (n/\epsilon))$$ worst-case iteration bound with quadratic convergence is established, where q is the barrier degree of the SR proximity function.

Keywords: Linear optimization; predictor-corrector methods; quadratic convergence; self-regular proximity functions; polynomial complexity (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-006-9095-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:132:y:2007:i:1:d:10.1007_s10957-006-9095-7

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-006-9095-7

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().