9 The Interior Revolution

Learning Objectives

Understand Karmarkar’s 1984 polynomial-time LP algorithm and why it was revolutionary
Grasp the complexity-theoretic significance of polynomial vs. exponential algorithms
Understand the AT&T context and the patent controversy
Connect Karmarkar’s algorithm to the modern interior point methods in IPOPT

9.1 The Announcement

On August 13, 1984, Narendra Karmarkar submitted a paper to the journal Combinatorica titled “A new polynomial-time algorithm for linear programming.” He was 28 years old, working at Bell Laboratories in Murray Hill, New Jersey. The paper was seven pages long.

Bell Labs held a press conference the following month. This was unusual. Bell Labs did not typically hold press conferences for pure mathematics papers. But Karmarkar’s result, combined with Bell’s aggressive publicity, produced one of the most remarkable media events in the history of applied mathematics. The New York Times ran a front-page story. Business Week ran a cover. The claim was that Karmarkar’s algorithm would solve linear programs fifty to one hundred times faster than the simplex method, and that this would transform every industry that used LP.

The reaction from the operations research community was a mixture of excitement and skepticism. The excitement was genuine: a polynomial-time algorithm for LP had theoretical implications that went well beyond practical speed. The skepticism was also genuine: the simplex method, despite its exponential worst case, had decades of practical refinement behind it, and raw algorithmic speed in benchmark tests was not the same as practical superiority on real problems.

9.2 Polynomial Time and What It Means

The complexity theory context is necessary to understand why Karmarkar’s result was theoretically significant regardless of practical speed.

An algorithm runs in polynomial time if its running time is bounded by a polynomial in the size of the input. An algorithm runs in exponential time if its running time can grow exponentially with input size. For small inputs, exponential algorithms can be fast. For large inputs, they become intractable — there is no hardware improvement that compensates for exponential growth.

The simplex method, as Klee and Minty had shown in 1972, has exponential worst-case complexity. It visits $2^n$ vertices in the worst case. For $n = 100$ design variables, this is $10^{30}$ iterations — more than the age of the universe at a trillion iterations per second. In practice, Klee-Minty instances never appear, and the simplex method solves real problems efficiently. But the theoretical guarantee of polynomial time had been missing.

Karmarkar provided it. His algorithm solves an LP in $O(n^{3.5} L)$ arithmetic operations, where $n$ is the number of variables and $L$ is the number of bits needed to encode the input. The polynomial guarantee means that as problems scale, the algorithm remains tractable — a property the simplex method cannot claim in theory.

9.3 The Algorithm

Karmarkar’s algorithm belongs to the family of interior point methods. Rather than walking along the boundary of the feasible polytope (as simplex does), it moves through the interior, approaching the optimum along the central path.

The key idea: transform the LP so that the current iterate is at the center of the feasible set, apply a projective transformation that maps the feasible set to a standard simplex, take a step along the projected gradient, and invert the transformation. At each step, the algorithm makes geometric progress — reduces the objective by a constant fraction of the gap to optimality.

Karmarkar’s specific transformation was projective (using the full projective group), which was more general than necessary. Later researchers showed that affine scaling — a simpler transformation — achieved the same polynomial complexity and was easier to implement. The modern interior point methods in practical solvers (IPOPT, KNITRO, Mosek) descend from these primal-dual algorithms, which were developed in the late 1980s and early 1990s and are significantly more efficient than Karmarkar’s original formulation.

9.4 The Patent and the Controversy

In January 1988, AT&T filed a patent on Karmarkar’s algorithm. This was not, by the standards of the time, unusual — Bell Labs patented algorithms routinely. But it created a storm of controversy in the mathematical community.

The operations research community depended on linear programming solvers. Several commercial solvers implemented Karmarkar-type algorithms. If AT&T enforced the patent aggressively, it could restrict academic and commercial use of interior point methods. The debate about patenting mathematical algorithms — which had been ongoing since the 1970s — became more pointed.

In practice, AT&T did not enforce the patent broadly, and it expired in 2006. But the controversy shaped attitudes in the optimization community toward intellectual property and open-source software. The development of IPOPT as a fully open-source implementation, released by Wächter and Laird in 2006, was in part a response to the perceived risk of patent encumbrances on commercial solvers.

9.5 From LP to NLP: The Legacy

Karmarkar’s algorithm, and the interior point revolution it triggered, turned out to be far more consequential for nonlinear programming than for linear programming. The simplex method remained competitive for LP in practice (CPLEX’s simplex implementation is faster than its interior point implementation on many LP instances). But for NLP — where the feasible set is curved and the simplex method does not apply — interior point methods are dominant.

The extension from LP to NLP, accomplished by Mehrotra, El-Ghaoui, Vanderbei, and others in the early 1990s, and culminating in Wächter and Laird’s IPOPT in 2006, gave engineers a solver that could handle problems with hundreds of thousands of variables and sparse constraint Jacobians — problems that SQP methods could not approach. Structural optimization, power grid optimization, trajectory optimization, and computational chemistry all became tractable.

The lesson is characteristic of the history of optimization: a theoretical advance in a simple setting (LP complexity) generates practical tools in a much harder setting (NLP for engineering) through a decade of subsequent engineering work.

9.6 Summary

Karmarkar’s 1984 paper established the first polynomial-time algorithm for linear programming, launching the interior point revolution. The algorithm moves through the interior of the feasible polytope rather than along its boundary, achieving geometric progress toward the optimum at each step. The AT&T patent created controversy but did not prevent the method’s development. The true legacy of Karmarkar’s work was not in LP — where simplex remains competitive — but in NLP, where interior point methods now dominate large-scale constrained optimization.

9.7 Further Reading

Karmarkar (1984) is the original paper. For the controversy and context, Robert Bland’s “New Finite Pivoting Rules for the Simplex Method” (Mathematics of Operations Research, 1977) and the discussions in Schrijver (1998) provide background. For the path from Karmarkar’s LP algorithm to modern NLP interior point methods, Nocedal and Wright (2006) Chapter 19 is the standard reference.

--- title: "The Interior Revolution" --- ::: {.callout-note} ## Learning Objectives - Understand Karmarkar's 1984 polynomial-time LP algorithm and why it was revolutionary - Grasp the complexity-theoretic significance of polynomial vs. exponential algorithms - Understand the AT&T context and the patent controversy - Connect Karmarkar's algorithm to the modern interior point methods in IPOPT ::: ## The Announcement On August 13, 1984, Narendra Karmarkar submitted a paper to the journal *Combinatorica* titled "A new polynomial-time algorithm for linear programming." He was 28 years old, working at Bell Laboratories in Murray Hill, New Jersey. The paper was seven pages long. Bell Labs held a press conference the following month. This was unusual. Bell Labs did not typically hold press conferences for pure mathematics papers. But Karmarkar's result, combined with Bell's aggressive publicity, produced one of the most remarkable media events in the history of applied mathematics. The *New York Times* ran a front-page story. *Business Week* ran a cover. The claim was that Karmarkar's algorithm would solve linear programs fifty to one hundred times faster than the simplex method, and that this would transform every industry that used LP. The reaction from the operations research community was a mixture of excitement and skepticism. The excitement was genuine: a polynomial-time algorithm for LP had theoretical implications that went well beyond practical speed. The skepticism was also genuine: the simplex method, despite its exponential worst case, had decades of practical refinement behind it, and raw algorithmic speed in benchmark tests was not the same as practical superiority on real problems. ## Polynomial Time and What It Means The complexity theory context is necessary to understand why Karmarkar's result was theoretically significant regardless of practical speed. An algorithm runs in polynomial time if its running time is bounded by a polynomial in the size of the input. An algorithm runs in exponential time if its running time can grow exponentially with input size. For small inputs, exponential algorithms can be fast. For large inputs, they become intractable — there is no hardware improvement that compensates for exponential growth. The simplex method, as Klee and Minty had shown in 1972, has exponential worst-case complexity. It visits $2^n$ vertices in the worst case. For $n = 100$ design variables, this is $10^{30}$ iterations — more than the age of the universe at a trillion iterations per second. In practice, Klee-Minty instances never appear, and the simplex method solves real problems efficiently. But the theoretical guarantee of polynomial time had been missing. Karmarkar provided it. His algorithm solves an LP in $O(n^{3.5} L)$ arithmetic operations, where $n$ is the number of variables and $L$ is the number of bits needed to encode the input. The polynomial guarantee means that as problems scale, the algorithm remains tractable — a property the simplex method cannot claim in theory. ## The Algorithm Karmarkar's algorithm belongs to the family of interior point methods. Rather than walking along the boundary of the feasible polytope (as simplex does), it moves through the interior, approaching the optimum along the central path. The key idea: transform the LP so that the current iterate is at the center of the feasible set, apply a projective transformation that maps the feasible set to a standard simplex, take a step along the projected gradient, and invert the transformation. At each step, the algorithm makes geometric progress — reduces the objective by a constant fraction of the gap to optimality. Karmarkar's specific transformation was projective (using the full projective group), which was more general than necessary. Later researchers showed that affine scaling — a simpler transformation — achieved the same polynomial complexity and was easier to implement. The modern interior point methods in practical solvers (IPOPT, KNITRO, Mosek) descend from these primal-dual algorithms, which were developed in the late 1980s and early 1990s and are significantly more efficient than Karmarkar's original formulation. ## The Patent and the Controversy In January 1988, AT&T filed a patent on Karmarkar's algorithm. This was not, by the standards of the time, unusual — Bell Labs patented algorithms routinely. But it created a storm of controversy in the mathematical community. The operations research community depended on linear programming solvers. Several commercial solvers implemented Karmarkar-type algorithms. If AT&T enforced the patent aggressively, it could restrict academic and commercial use of interior point methods. The debate about patenting mathematical algorithms — which had been ongoing since the 1970s — became more pointed. In practice, AT&T did not enforce the patent broadly, and it expired in 2006. But the controversy shaped attitudes in the optimization community toward intellectual property and open-source software. The development of IPOPT as a fully open-source implementation, released by Wächter and Laird in 2006, was in part a response to the perceived risk of patent encumbrances on commercial solvers. ## From LP to NLP: The Legacy Karmarkar's algorithm, and the interior point revolution it triggered, turned out to be far more consequential for nonlinear programming than for linear programming. The simplex method remained competitive for LP in practice (CPLEX's simplex implementation is faster than its interior point implementation on many LP instances). But for NLP — where the feasible set is curved and the simplex method does not apply — interior point methods are dominant. The extension from LP to NLP, accomplished by Mehrotra, El-Ghaoui, Vanderbei, and others in the early 1990s, and culminating in Wächter and Laird's IPOPT in 2006, gave engineers a solver that could handle problems with hundreds of thousands of variables and sparse constraint Jacobians — problems that SQP methods could not approach. Structural optimization, power grid optimization, trajectory optimization, and computational chemistry all became tractable. The lesson is characteristic of the history of optimization: a theoretical advance in a simple setting (LP complexity) generates practical tools in a much harder setting (NLP for engineering) through a decade of subsequent engineering work. --- ## Summary Karmarkar's 1984 paper established the first polynomial-time algorithm for linear programming, launching the interior point revolution. The algorithm moves through the interior of the feasible polytope rather than along its boundary, achieving geometric progress toward the optimum at each step. The AT&T patent created controversy but did not prevent the method's development. The true legacy of Karmarkar's work was not in LP — where simplex remains competitive — but in NLP, where interior point methods now dominate large-scale constrained optimization. ## Further Reading @karmarkar1984new is the original paper. For the controversy and context, Robert Bland's "New Finite Pivoting Rules for the Simplex Method" (*Mathematics of Operations Research*, 1977) and the discussions in @schrijver1998theory provide background. For the path from Karmarkar's LP algorithm to modern NLP interior point methods, @nocedal2006numerical Chapter 19 is the standard reference.