The interior-point revolution in constrained optimization

Interior methods are a central, striking feature of the constrained optimization landscape today, but it was not always so. Primarily in the form of barrier methods, interior-point techniques were widely used during the 1960s to solve nonlinearly constrained problems. However, their use for linear programming was not even contemplated because of the total dominance of the simplex method. During the 1970s, barrier methods were superseded by newly emerging, apparently 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 the mid-1980s. In 1984, 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, the new incarnations of interior methods have advanced so far, so fast, that their influence has transformed both the theory and practice of constrained optimization. This paper is intended to provide a condensed, selective, unavoidably incomplete look at classical material and recent research about interior methods.