Interior-Point Methods

Every time an airline decides how many seats to sell at each price, or a power grid balances supply against demand, it is solving a linear program (LP): optimize a linear objective subject to linear constraints. The answer is always a corner of a polytope — a high-dimensional version of a polygon.

For decades, the only practical way to find that corner was the Simplex method (Dantzig, 1947): start at one corner, walk along an edge to a better neighbor, repeat until no improvement is possible. It works brilliantly in practice but in the worst case visits exponentially many corners.

In 1984, Narendra Karmarkar announced a completely different approach. Instead of walking the boundary, his algorithm starts inside the polytope — in the interior — and follows a curved path straight toward the optimum, staying away from the walls at every step. It proved polynomial time in theory and was fast enough to challenge Simplex in practice. A new era of optimization had begun.

The demo below shows a simple 2-D linear program. The shaded polygon is the feasible region — all (x, y) satisfying the constraints. The red dot marks the optimum (the corner that maximizes the objective). The dashed line is the objective contour.

<p class="hint">{{hint}}</p>
<canvas id="canvas" width="360" height="300"></canvas>
<div class="info" id="info">{{press_run}}</div>
<div class="btns">
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="slider-row">
  <label for="angle">{{label_angle}} <span id="angleVal">30°</span></label>
  <input type="range" id="angle" min="5" max="85" value="30" step="5">
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px;
         background: #f7f9fb; max-width: 100%; }
.info { font-size: .95rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.info.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.slider-row { display: flex; flex-direction: column; gap: .25rem; font-size: .88rem; }
input[type=range] { width: 220px; accent-color: #1d3557; }

// Code not found

Press Run interior-point to watch the algorithm trace the central path from a starting point deep inside the region toward the optimum. The path deliberately curves to stay away from every boundary — that avoidance is what makes the math tractable. Press Reset to start over, or drag the objective slider to change the direction of optimization.

Linear programming's complexity status was murky for decades:

• Simplex is fast in practice but exponential in theory. No polynomial-time bound was known — Klee and Minty (1972) gave an LP where Simplex visits every vertex of a hypercube.
• The ellipsoid method (Khachiyan, 1979) gave the first polynomial-time LP algorithm — $O(n^{6} L^{2})$ — but it was too slow for real use. It settled the theoretical question (LP is in P) without solving the practical one.
• Karmarkar's projective algorithm (1984) ran in $O(n^{3} \cdot ^{5} L)$ steps — polynomial and practical. AT&T reported it outperforming Simplex on telephone-network problems with hundreds of thousands of variables.
• Modern interior-point methods (barrier methods, primal-dual path-following) run in $O(n^{3} L)$ or better with warm starts. They dominate large-scale LP and semidefinite programming (SDP).

The key idea is the logarithmic barrier: add a term −μ Σ log(xᵢ) to the objective. As μ → 0, the solution follows the central path to the optimum. Each Newton step of the barrier problem costs $O(n^{3})$ but you need only $O(\sqrt{n} L)$ steps — a product that beats Simplex's worst case.

Interior-point methods also extended naturally to convex optimization beyond LP: second-order cone programs (SOCP), semidefinite programs (SDP), and general self-concordant barriers, unlocking polynomial-time guarantees for entire new problem families. See also linear programming and non-convex optimization.

Interior-point methods are the engine behind much of the optimization that runs the modern world:

• Operations research: airline crew scheduling, supply chain routing, and power dispatch all use LP/MIP solvers (CPLEX, Gurobi, HiGHS) whose LP relaxations rely on interior-point.
• Control and signal processing: model predictive control (MPC) solves small LPs or QPs at every time step — interior-point handles hundreds of variables in milliseconds.
• Machine learning: support vector machines (SVMs) solve a quadratic program; LASSO uses an LP reformulation; compressed sensing is an ℓ1-minimization LP.
• Semidefinite programming (SDP): the Goemans–Williamson MAX-CUT approximation, sum-of-squares relaxations, and combinatorial bounds all need SDP — solved exclusively by interior-point.
• Finance: portfolio optimization (Markowitz), risk-parity, and regulatory stress tests are QPs or SDPs run daily by every major bank.
• Chip design: placement and routing of VLSI circuits reduce to huge LP/QP instances — barrier methods handle millions of variables.

Karmarkar's geometric insight — that the interior is friendlier than the boundary — turned out to be one of the most broadly applicable ideas in twentieth-century mathematics.

Before 1984, optimization lived on the boundary: every practical solver hugged the walls of the feasible polytope, moving from corner to corner. Karmarkar's insight was to ignore the walls entirely and drive straight through the middle, letting a logarithmic barrier gently push the solution away from the boundary as it converged.

The result was the first algorithm that was simultaneously polynomial in theory and competitive in practice — proof that the geometry of the interior carries information the boundary never reveals. Today interior-point methods solve LP, QP, SOCP, and SDP instances with millions of variables, powering everything from airline scheduling to deep learning. The shortcut through the middle turned out to be the fastest road to the answer.