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

By Margaret H. Wright. 2004

345 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Control and Systems Engineering, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/f85fd173ad83632b258ce0397c43fb9cc7bc1bd2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Control and Systems Engineering

In Numerical Analysis

Citations in the corpus

An interior penalty method for optimal control problems with state and input constraints of nonlinear systems (2016, methodology): “In particular, the IPMs that are nowadays implemented in successful software packages such as KNITRO [2], OOQP [3] have their foundations in these approaches.”
Interior Point Methods for Nonlinear Optimization (2010, background): “The “interiorpoint revolution” [92] has completely changed the field of optimization.”
Convex Optimization & Euclidean Distance Geometry (2004, methodology): “1 nascence of interior-point methods of solution [250] [264], © 2001 Jon Dattorro.”
Hinge-Loss Markov Random Fields and Probabilistic Soft Logic (2015, background): “Although in practice they perform better than their worst-case bounds (Wright, 2005), they do not scale well to large structured prediction problems (Yanover et al., 2006).”
Shakedown analysis of engineering structures with limited kinematical hardening (2012, methodology): “From the different techniques to solve such problems we chose the interior-point method (see e.g., Potra and Wright, 2000; Forsgren et al., 2002; Wright, 2004).”
Hinge-Loss Markov Random Fields and Probabilistic Soft Logic (2015, background): “Although in practice they perform better than their worst-case bounds (Wright, 2005), they do not scale well to big structured prediction problems (Yanover et al.”
Numerical Maximisation of Likelihood: A Neglected Alternative to EM? (2014, background): “By the 1980s, the received wisdom was that they suffered from ill-conditioning that rendered them unreliable, but they have turned out to be the main weapon in the hands of the revolutionaries in the ‘interior-point revolution’ of constrained optimisation (Forsgren et al., 2002; Wright, 2004).”
An interior‐point algorithm for elastoplasticity (2007, neutral): “Thus, the paper of Karmarkar [41] in 1984 sparked a revolution which led to the development of the algorithms now known as interior-point methods [42–45].”