The interior-point revolution in optimization: History, recent developments, and lasting consequences

Research output: Contribution to journalArticle

Abstract

Interior methods are a pervasive feature of the optimization landscape today, but it was not always so. Although interior-point techniques, primarily in the form of barrier methods, were widely used during the 1960s for problems with nonlinear constraints, their use for the fundamental problem of linear programming was unthinkable because of the total dominance of the simplex method. During the 1970s, barrier methods were superseded, nearly to the point of oblivion, by newly emerging and seemingly more efficient alternatives such as augmented Lagrangian and sequential quadratic programming methods. By the early 1980s, barrier methods were almost universally regarded as a closed chapter in the history of optimization. This picture changed dramatically in 1984, when Narendra Karmarkar announced a fast polynomial-time interior method for linear programming; in 1985, a formal connection was established between his method and classical barrier methods. Since then, interior methods have continued to transform both the theory and practice of constrained optimization. We present a condensed, unavoidably incomplete look at classical material and recent research about interior methods.

Original languageEnglish (US)
Pages (from-to)39-56
Number of pages18
JournalBulletin of the American Mathematical Society
Volume42
Issue number1
DOIs
StatePublished - Jan 2005

ASJC Scopus subject areas

  • Mathematics(all)
  • Applied Mathematics

Fingerprint Dive into the research topics of 'The interior-point revolution in optimization: History, recent developments, and lasting consequences'. Together they form a unique fingerprint.

  • Cite this