On a wide region of centers and primal-dual interior point algorithms for linear programming

Jos F. Sturm, Shuzhong Zhang

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

In the adaptive step primal-dual interior point method for linear programming, polynomial algorithms are obtained by computing Newton directions towards targets on the central path, and restricting the iterates to a neighborhood of this central path. In this paper, the adaptive step methodology is extended, by considering targets in a certain central region, which contains the usual central path, and subsequently generating iterates in a neighborhood of this region. The size of the central region can vary from the central path to the whole feasible region by choosing a certain parameter. An θ(√n L) iteration bound is obtained under mild conditions on the choice of the target points. In particular, we leave plenty of room for experimentation with search directions. The practical performance of the new primal-dual interior point method is measured on part of the Netlib test set for various sizes of the central region.

Original languageEnglish (US)
Pages (from-to)408-431
Number of pages24
JournalMathematics of Operations Research
Volume22
Issue number2
DOIs
StatePublished - May 1997

Keywords

  • Central path
  • Linear programming
  • Primal-dual interior point method
  • Wide neighborhood

Fingerprint Dive into the research topics of 'On a wide region of centers and primal-dual interior point algorithms for linear programming'. Together they form a unique fingerprint.

Cite this