Interior-Point Method

Constrained optimisation

A typical constrained optimisation problem has the form

minimise   f(x)
subject to g_i(x) ≤ 0,   i = 1, …, m

where f and the g_i are smooth (typically convex). The feasible region is the intersection of the m half-spaces {x : g_i(x) ≤ 0}, often a polytope or a convex body. The simplex method walks the vertices of that body; interior-point methods take a different path, cutting through the interior of the feasible region without ever touching the boundary, and reaching the optimum through Newton solves on a smoothed problem.

The logarithmic barrier

The idea is to replace the hard inequality constraints with a smooth penalty that diverges as you approach the boundary. The standard choice is the logarithmic barrier:

B(x) = − Σ log(−g_i(x))

For a point strictly inside the feasible region (g_i(x) < 0 for all i), B is finite. As any g_i → 0 from below — the iterate approaches the boundary — −log(−g_i) → +∞. The barrier-augmented problem is:

minimise   f(x) + μ B(x)
            (unconstrained — but the barrier confines x to the strictly feasible interior)

For each μ > 0 this has a unique minimiser x*(μ) inside the feasible region. As μ → 0, the barrier weight shrinks and x*(μ) converges to the constrained optimum of the original problem. Interior-point methods solve a sequence of barrier problems with shrinking μ, using Newton's method for each. Iterates are always strictly feasible — interior — hence the name.

The central path

The curve {x*(μ) : μ > 0} is the central path. It starts (at μ = ∞) at the analytic center of the feasible region — the point that maximises Σ log(−g_i(x)), i.e. is as far from every boundary as possible. As μ shrinks the path bends toward the constrained optimum, typically a vertex of the feasible region for linear problems or a face for quadratic ones. The central path is smooth (continuous and infinitely differentiable in μ for log-barriers on convex programs), and interior-point methods approximately follow it.

Each iteration takes a Newton step on the current barrier problem and shrinks μ. The polynomial complexity proof tracks how fast μ can shrink while keeping iterates inside a "neighbourhood" N(μ) of the central path. Karmarkar's 1984 paper, the path-following methods of Renegar (1988) and Gonzaga (1989), and the modern primal-dual approach of Mehrotra (1992) all build on this template.

The algorithm sketch

choose x_0 strictly feasible, μ_0 large
for k = 0, 1, 2, …
    solve (approximately) min f(x) + μ_k B(x) via Newton starting at x_k
    set x_{k+1} = approximate minimiser
    if μ_k · m < tol: stop
    μ_{k+1} = θ μ_k    where θ ∈ (0, 1) (typically 0.1 to 0.5)

For LP and QP, "one Newton step per μ" suffices — the so-called short-step method gives the cleanest polynomial bound. In practice long-step methods take aggressive μ-reductions and rely on Mehrotra's predictor-corrector strategy to keep iterates close to the central path. Modern solvers do something like: one predictor step, one corrector step, total 30-60 iterations for 10 digits of accuracy on problems with millions of variables.

Karmarkar 1984

Narendra Karmarkar at AT&T Bell Labs announced in November 1984 the first interior-point method with provably polynomial complexity O(n^3.5 L) for linear programming, where n is the number of variables and L is the total bit length of the input. The complexity is dramatically better than the simplex method's worst-case exponential bound (Klee-Minty 1972). Khachiyan's 1979 ellipsoid method was technically polynomial first, but its constants were so large that it never beat simplex in practice — Karmarkar's was the first algorithm that was both polynomial and competitive on real problems.

The 1984 paper caused a sensation. AT&T patented the algorithm, used it to design phone networks (KORBX system, $9 million per license), and the New York Times speculated it would replace the simplex method everywhere. In the end interior-point did not kill simplex — small to medium LPs and warm-started reoptimisation still favour simplex — but the paper triggered a forty-year research programme that produced primal-dual methods, polynomial-time semidefinite programming, conic optimisation, and the unified analysis of self-concordant barriers (Nesterov-Nemirovski 1994). Every commercial QP, SDP, and conic solver in 2026 is a direct descendant of Karmarkar's 1984 idea.

Worked example: LP with two constraints

Maximise 3x + 2y subject to x + y ≤ 4 and 2x + y ≤ 6 with x, y ≥ 0 (the LP from the simplex method example). Rewrite as minimisation: minimise −3x − 2y. There are four inequality constraints g_i ≤ 0:

g_1(x,y) = x + y − 4
g_2(x,y) = 2x + y − 6
g_3(x,y) = −x
g_4(x,y) = −y

The barrier-augmented problem is min (−3x − 2y) − μ [log(4 − x − y) + log(6 − 2x − y) + log(x) + log(y)]. Starting at the interior point (1, 1) (all four g_i are strictly negative) with μ = 1:

μ        Newton-solved x_k        objective    distance to optimum (2, 2)
─        ─────────────────        ──────────    ──────────────────────────
1.0      (1.43, 1.85)             −8.00         0.59
0.5      (1.69, 1.95)             −8.97         0.32
0.1      (1.91, 1.99)             −9.71         0.10
0.01     (1.991, 1.999)           −9.97         0.0094
0.001    (1.9991, 1.9999)         −9.997        9.4 × 10⁻⁴
0.0001   (1.99991, 1.99999)       −9.9997       9.4 × 10⁻⁵

Six μ-reductions, each absorbing one Newton step, drop the optimality gap by 6 orders of magnitude. The iterates stay strictly inside the polygon (0,0)-(3,0)-(2,2)-(0,4) at every step, converging toward the vertex (2, 2) where the objective is −10. Compare simplex on the same LP: 3 pivots, all at vertices. Interior-point pays a higher per-iteration cost (Newton solve vs pivot) but the iteration count grows much more slowly with problem size — 30-60 iterations for 10 digits regardless of n.

Interior-point vs simplex vs first-order

	Simplex	Interior-Point	Ellipsoid (Khachiyan)	First-order (ADMM, FOM)
Worst-case complexity	Exponential (Klee-Minty)	O(n^3.5 L)	O(n^6 L)	O(1/ε) iters
Typical iters	2-3 (m+n)	30-60	10⁴+	10²-10⁴
Per-iter cost	O(m) pivot	O(n³) Cholesky	O(n²) update	O(n²) or O(nnz)
Iterates stay where?	On vertices	Strictly interior	Inside shrinking ellipsoid	Anywhere
Warm starts	Excellent	Poor	Very poor	Good
Best at	Small-to-medium LP, B&B inner	Huge LP/QP/SDP	Theory only	Approximate solutions
Real-world use	Production LPs, MILP	Production LPs/QPs/SDPs	None	ML, learning rates

The right-hand columns tell the story. Interior-point dominates simplex on huge LPs (n > 10⁵), on QP/SDP/SOCP/conic, and on any problem where warm starts don't help. Simplex dominates on small LPs, on integer programming via branch-and-bound (where you re-solve LP relaxations after adding a single cut), and on linear sensitivity analysis. First-order methods dominate when low accuracy is fine and per-iteration cost must be tiny. Every commercial solver ships interior-point AND simplex AND first-order, picking automatically by problem size and structure.

Where interior-point actually runs

• Commercial LP/QP solvers. CPLEX (IBM), Gurobi, MOSEK, HiGHS all ship interior-point as their default for large LPs and as the only option for QPs and SOCPs. Solving a million-variable QP in seconds is interior-point territory.
• IPOPT — Interior Point OPTimizer. The open-source NLP solver from CMU (Wächter & Biegler 2006). Backbone of nonlinear programming in JuMP, Pyomo, GAMS, AMPL. Runs interior-point on the KKT conditions with a filter line-search for global convergence.
• Model predictive control. Real-time QPs in robotics, automotive ADAS, drones. OSQP (Stellato et al. 2020) and qpOASES are the standard solvers; both use interior-point or active-set inner loops to solve QP sub-problems at 100-1000 Hz.
• Semidefinite programming. SDP problems (max-cut relaxations, sum-of-squares optimisation, control LMIs) are solved exclusively by interior-point in the form of MOSEK, SDPA, COPT, and the SCS first-order solver. The interior-point machinery of Nesterov-Nemirovski 1994 is unique to SDP.
• Power-grid optimal power flow. ISO New England, MISO, ERCOT all run interior-point on AC optimal power flow (a non-convex problem, solved by interior-point on convex relaxations) every 5 minutes. Tens of thousands of buses and lines.
• Portfolio optimisation and quant finance. Mean-variance portfolio QPs with thousands of assets, sector constraints, turnover bounds, transaction costs. Standard practice is MOSEK or Gurobi barrier on the QP.

Variants and extensions

• Path-following methods (Renegar 1988, Gonzaga 1989). The first polynomial-time interior-point methods after Karmarkar; explicitly track the central path with controlled neighbourhood radius. Cleaner complexity proofs.
• Primal-dual methods (Mehrotra 1992). Treat primal x, dual y, slacks s symmetrically; apply Newton to perturbed KKT conditions. The state of the art in commercial solvers. Predictor-corrector strategy gives super-linear convergence in practice.
• Self-concordant barriers (Nesterov-Nemirovski 1994). Generalises the log-barrier idea: any self-concordant barrier B yields a polynomial-time interior-point method. Extends the framework to SDP, SOCP, conic optimisation, and the entire convex world.
• Filter interior-point (IPOPT). Uses an acceptance "filter" instead of a merit function to combine constraint reduction and objective decrease without ad-hoc penalty parameters. State of the art for nonlinear programming.
• Infeasible-start interior-point. Most modern solvers don't require a strictly feasible starting point; they relax constraints and converge to feasibility and optimality simultaneously.
• Splitting conic solver (SCS). First-order method (ADMM) for conic problems, runs on GPUs, scales to millions of variables. The complement to interior-point at the very large end.

Common pitfalls

• Bad starting point. Strictly feasible interior starts are easy on LP (use the analytic center) but harder on general NLP. Phase-I problems or infeasible-start variants are essential.
• μ shrinks too fast. Iterates leave the neighbourhood of the central path, Newton breaks down, recovery is slow or impossible. Modern solvers use careful predictor-corrector schedules.
• Treating the linear-system solve as cheap. Each Newton step requires factorising an n × n matrix (or solving with Krylov). For 10⁷ × 10⁷ that's not free. Exploit sparsity, use specialised solvers (KLU, MUMPS, Pardiso).
• Forgetting to scale. Like simplex, interior-point is sensitive to bad scaling. Solvers automatically scale rows and columns, but custom code often forgets.
• Confusing interior-point with first-order. Interior-point is second-order (Newton steps); ADMM, ISTA, FOM are first-order. They have completely different convergence rates and accuracy regimes.

Why interior-point reshaped optimisation

For thirty-seven years the simplex method was the only practical algorithm for linear programming. Karmarkar's 1984 paper broke that monopoly and proved that polynomial-time complexity was possible without sacrificing real-world performance. Within a decade interior-point had been extended to QP, SOCP, SDP, and the whole self-concordant convex world; within two decades it was the only practical algorithm for SDP and the dominant choice for huge LPs and all QPs.

The cultural shift was as big as the algorithmic one. Optimisation was no longer "simplex for LP, ad-hoc for everything else"; it became a unified theory where any convex problem with a self-concordant barrier admitted polynomial-time solution. CVXPY, JuMP, Yalmip — the modelling-language ecosystem of the 2010s and 2020s — exists because interior-point made all convex problems tractable. Today every robotics startup writing model-predictive control, every quantitative-finance firm solving portfolio QPs, every power-grid operator clearing day-ahead markets is running interior-point under the hood. Karmarkar 1984 is one of the most cited algorithmic papers of the 20th century, and forty-two years later it shapes every optimisation tool you've heard of.