Introduction

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.

Follow the Central Path

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">A 2-D linear program: maximize <b>cx + dy</b> subject to the constraints that form the shaded polygon. Press <b>Run interior-point</b> to watch the algorithm start inside the region and follow the <b>central path</b> to the optimal corner.</p>
<canvas id="canvas" width="360" height="300"></canvas>
<div class="info" id="info">Press Run to trace the central path.</div>
<div class="btns">
  <button id="run" type="button">Run interior-point</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="slider-row">
  <label for="angle">Objective direction: <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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Interior-point central-path demo.
// LP: maximize c*x + d*y
//   subject to: x >= 0, y >= 0, x <= 7, y <= 7, x + y <= 10
// Feasible region corners: (0,0),(7,0),(7,3),(3,7),(0,7)
// Barrier: -c*x - d*y + mu*(log(x)+log(y)+log(7-x)+log(7-y)+log(10-x-y))
// Newton steps reduce mu -> 0, tracing the central path to the optimum corner.

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;
const PAD = 38;
const SCALE = (W - 2*PAD) / 11; // 11 units wide

// World -> canvas
function wx(x) { return PAD + x * SCALE; }
function wy(y) { return H - PAD - y * SCALE; }

// Feasible region corners
const corners = [[0,0],[7,0],[7,3],[3,7],[0,7]];

let angleRad = 30 * Math.PI / 180;
let pathPts = [];
let animFrame = null;

function getCD() {
  return [Math.cos(angleRad), Math.sin(angleRad)];
}

function findOptVertex() {
  const [c, d] = getCD();
  let best = -Infinity, bv = corners[0];
  for (const [vx, vy] of corners) {
    const val = c*vx + d*vy;
    if (val > best) { best = val; bv = [vx, vy]; }
  }
  return bv;
}

// One Newton step of the log-barrier for the 5-constraint LP.
function newtonStep(x, y, mu, c, d) {
  const s1 = 7 - x;       // x <= 7
  const s2 = 7 - y;       // y <= 7
  const s3 = 10 - x - y;  // x + y <= 10
  if (x <= 0 || y <= 0 || s1 <= 0 || s2 <= 0 || s3 <= 0) return null;
  // Gradient of barrier (we minimize: -(obj) + mu*sum_barriers)
  const gx = -c + mu*(1/x - 1/s1 - 1/s3);
  const gy = -d + mu*(1/y - 1/s2 - 1/s3);
  // Hessian (diagonal terms + cross term from s3)
  const hxx = mu*(1/(x*x) + 1/(s1*s1) + 1/(s3*s3));
  const hyy = mu*(1/(y*y) + 1/(s2*s2) + 1/(s3*s3));
  const hxy = mu/(s3*s3);
  const det = hxx*hyy - hxy*hxy;
  if (Math.abs(det) < 1e-15) return null;
  const dx = (-gx*hyy + gy*hxy) / det;
  const dy = ( gx*hxy - gy*hxx) / det;
  return [dx, dy];
}

function feasible(x, y) {
  return x > 1e-9 && y > 1e-9 && 7-x > 1e-9 && 7-y > 1e-9 && 10-x-y > 1e-9;
}

function computePath() {
  const [c, d] = getCD();
  let x = 2.5, y = 2.5;  // start near analytic center
  const pts = [[x, y]];
  let mu = 3.0;
  for (let mi = 0; mi < 60; mi++) {
    for (let si = 0; si < 10; si++) {
      const step = newtonStep(x, y, mu, c, d);
      if (!step) break;
      const [dx, dy] = step;
      let alpha = 1.0;
      for (let ls = 0; ls < 50; ls++) {
        const nx = x + alpha*dx, ny = y + alpha*dy;
        if (feasible(nx, ny)) { x = nx; y = ny; break; }
        alpha *= 0.5;
      }
      pts.push([x, y]);
    }
    mu *= 0.45;
  }
  return pts;
}

function drawScene(pathSoFar) {
  ctx.clearRect(0, 0, W, H);

  // Grid lines (light)
  ctx.strokeStyle = '#e4e8ed'; ctx.lineWidth = 1;
  for (let i = 1; i <= 10; i++) {
    ctx.beginPath(); ctx.moveTo(wx(i), wy(0)); ctx.lineTo(wx(i), wy(10)); ctx.stroke();
    ctx.beginPath(); ctx.moveTo(wx(0), wy(i)); ctx.lineTo(wx(10), wy(i)); ctx.stroke();
  }

  // Axes
  ctx.strokeStyle = '#aaa'; ctx.lineWidth = 1.2;
  ctx.beginPath(); ctx.moveTo(wx(0), wy(0)); ctx.lineTo(wx(10.3), wy(0)); ctx.stroke();
  ctx.beginPath(); ctx.moveTo(wx(0), wy(0)); ctx.lineTo(wx(0), wy(10.3)); ctx.stroke();
  ctx.fillStyle = '#888'; ctx.font = '10px system-ui';
  for (let i = 2; i <= 10; i += 2) {
    ctx.fillText(i, wx(i)-4, wy(0)+14);
    ctx.fillText(i, wx(0)-16, wy(i)+4);
  }
  ctx.fillText('x', wx(10.1), wy(0)+13);
  ctx.fillText('y', wx(0)-13, wy(10.1));

  // Feasible region fill
  ctx.beginPath();
  ctx.moveTo(wx(corners[0][0]), wy(corners[0][1]));
  for (const [vx, vy] of corners) ctx.lineTo(wx(vx), wy(vy));
  ctx.closePath();
  ctx.fillStyle = 'rgba(29,53,87,0.10)';
  ctx.fill();
  ctx.strokeStyle = '#1d3557'; ctx.lineWidth = 1.8;
  ctx.stroke();

  // Objective contour lines (dashed)
  const [c, d] = getCD();
  const optV = findOptVertex();
  const objOpt = c*optV[0] + d*optV[1];
  ctx.setLineDash([5, 4]);
  ctx.strokeStyle = '#e63946'; ctx.lineWidth = 1.1;
  for (const frac of [0.25, 0.55, 0.82]) {
    const v = objOpt * frac;
    ctx.beginPath();
    if (Math.abs(d) > 1e-9) {
      ctx.moveTo(wx(0), wy(v / d));
      ctx.lineTo(wx(10), wy((v - c*10) / d));
    } else {
      ctx.moveTo(wx(v / c), wy(0));
      ctx.lineTo(wx(v / c), wy(10));
    }
    ctx.stroke();
  }
  ctx.setLineDash([]);

  // Optimal vertex (star)
  ctx.fillStyle = '#e63946';
  ctx.beginPath(); ctx.arc(wx(optV[0]), wy(optV[1]), 7, 0, 2*Math.PI); ctx.fill();
  ctx.fillStyle = '#fff'; ctx.font = '700 11px system-ui';
  ctx.fillText('★', wx(optV[0])-6, wy(optV[1])+4);

  // Central path trace
  if (pathSoFar && pathSoFar.length > 1) {
    ctx.strokeStyle = '#f4a261'; ctx.lineWidth = 2.4;
    ctx.beginPath();
    ctx.moveTo(wx(pathSoFar[0][0]), wy(pathSoFar[0][1]));
    for (const [px, py] of pathSoFar) ctx.lineTo(wx(px), wy(py));
    ctx.stroke();
    // Current position dot
    const last = pathSoFar[pathSoFar.length - 1];
    ctx.fillStyle = '#f4a261';
    ctx.beginPath(); ctx.arc(wx(last[0]), wy(last[1]), 5, 0, 2*Math.PI); ctx.fill();
  }

  // Starting point
  ctx.fillStyle = '#1d6fa8';
  ctx.beginPath(); ctx.arc(wx(2.5), wy(2.5), 5, 0, 2*Math.PI); ctx.fill();
  ctx.fillStyle = '#1d3557'; ctx.font = '11px system-ui';
  ctx.fillText('start', wx(2.5)+8, wy(2.5)+4);
}

function setInfo(t, cls) {
  const el = document.getElementById('info');
  el.textContent = t; el.className = 'info ' + (cls || '');
}

function runAnim() {
  if (animFrame) cancelAnimationFrame(animFrame);
  pathPts = computePath();
  let i = 0;
  const optV = findOptVertex();
  function step() {
    i = Math.min(i + 4, pathPts.length);
    drawScene(pathPts.slice(0, i));
    if (i < pathPts.length) {
      animFrame = requestAnimationFrame(step);
    } else {
      const last = pathPts[pathPts.length - 1];
      const [c, d] = getCD();
      const objEnd = c*last[0] + d*last[1];
      const objOpt = c*optV[0] + d*optV[1];
      // Verification assertion (logged to console)
      const err = Math.abs(objEnd - objOpt);
      console.assert(err < 0.15,
        'interior-point-demo: final obj ' + objEnd.toFixed(4) +
        ' should be within 0.15 of opt ' + objOpt.toFixed(4) + ', got err=' + err.toFixed(4));
      setInfo(
        fmt('✓ Reached (%v%, %v2%) — obj %objEnd% (optimum %objOpt%)', { v: last[0].toFixed(2), v2: last[1].toFixed(2), objEnd: objEnd.toFixed(3), objOpt: objOpt.toFixed(3) }),
        'ok'
      );
    }
  }
  animFrame = requestAnimationFrame(step);
  setInfo('Tracing the central path…');
}

function resetDemo() {
  if (animFrame) cancelAnimationFrame(animFrame);
  pathPts = [];
  drawScene([]);
  setInfo('Press Run to trace the central path.');
}

document.getElementById('run').addEventListener('click', runAnim);
document.getElementById('reset').addEventListener('click', resetDemo);
document.getElementById('angle').addEventListener('input', function () {
  angleRad = parseInt(this.value) * Math.PI / 180;
  document.getElementById('angleVal').textContent = this.value + '°';
  if (animFrame) cancelAnimationFrame(animFrame);
  pathPts = [];
  drawScene([]);
  setInfo('Press Run to trace the central path.');
});

drawScene([]);
Result
Console

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.

The Real Complexity

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(n6L2)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(n3⋅5L)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(n3L)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(n3)O(n^{3}) but you need only O(nL)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/interior-point/Content licensed under CC BY-NC 4.0.