An O(√n L) iteration bound primal-dual cone affine scaling algorithm for linear programming

Jos F. Sturm, Shuzhong Zhang

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

In this paper we introduce a primal-dual affine scaling method. The method uses a search-direction obtained by minimizing the duality gap over a linearly transformed conic section. This direction neither coincides with known primal-dual affine scaling directions (Jansen et al., 1993; Monteiro et al., 1990), nor does it fit in the generic primal-dual method (Kojima et al., 1989). The new method requires O(√n L) main iterations. It is shown that the iterates follow the primal-dual central path in a neighbourhood larger than the conventional script N sign2 neighbourhood. The proximity to the primal-dual central path is measured by trigonometric functions.

Original languageEnglish (US)
Pages (from-to)177-194
Number of pages18
JournalMathematical Programming, Series B
Volume72
Issue number2
StatePublished - Feb 1996

Keywords

  • Affine scaling
  • Linear programming
  • Polynomiality
  • Primal-dual interior point algorithm

Fingerprint Dive into the research topics of 'An O(√n L) iteration bound primal-dual cone affine scaling algorithm for linear programming'. Together they form a unique fingerprint.

Cite this