Interior-Point Methods

The simplex method solves linear programs by walking along the edges of the feasible region from corner to corner — reliable, but for very large problems (thousands of assets, thousands of constraints, as in a full portfolio optimization with individual position and sector limits) it can take a very large number of such steps, each corner-to-corner move only a small improvement. Interior-point methods take a completely different route to the same destination: instead of tracing the boundary, they cut straight through the interior of the feasible region, using calculus (Newton's method) to head directly toward the optimum, and only approach the boundary in the final few steps. For large problems this is often dramatically faster.

The analogy: crossing a room versus hugging the walls

If you need to get from one side of a large, oddly-shaped room to a specific point near the far wall, you could hug the walls the whole way, turning at each corner (that's simplex) — reliable, but a long walk if the room is big and irregular. Or you could walk in a straight-ish line through the open middle of the room, adjusting direction as you get better information about where you're headed, and only approach the wall right at the very end when you're already close to your destination. Interior-point methods do the second: they stay strictly inside the feasible region (never touching a constraint boundary) until the last stages of the algorithm, using local curvature information to aim efficiently toward the optimum.

The mechanics, one symbol at a time

Interior-point methods replace hard constraints with a barrier function that grows to infinity as you approach the boundary of the feasible region, gently discouraging the algorithm from ever actually touching a constraint:

$$\min_{\mathbf{x}} \; t\cdot\mathbf{c}^\top\mathbf{x} - \sum_i \ln(b_i - A_i\mathbf{x}),$$

where the logarithmic term is the barrier — it's finite deep inside the feasible region but shoots to $-\infty$'s negative (a huge penalty) as any constraint $A_i\mathbf{x} \to b_i$ is approached. In plain English: instead of forbidding the boundary outright, the barrier makes getting near it increasingly costly, so an unconstrained solver (Newton's method) applied to this penalized objective naturally stays inside the feasible region while still being pulled toward the true optimum by the $t\cdot\mathbf{c}^\top\mathbf{x}$ term.

The parameter $t$ starts small (barrier dominates, solution sits safely in the "middle" of the room) and is gradually increased across a sequence of solves (barrier's influence shrinks, true objective dominates more), tracing what's called the central path — a smooth curve through the interior that converges to the actual boundary optimum as $t\to\infty$.

Worked example 1: the barrier's effect at different $t$

For a simple one-dimensional problem, minimize $x$ subject to $x \ge 1$ (constraint written as $x - 1 \ge 0$), true optimum at $x=1$. The barrier-penalized objective is $t\cdot x - \ln(x-1)$. Taking a derivative and setting to zero: $t - \frac{1}{x-1} = 0 \Rightarrow x = 1 + \frac1t$. At $t=1$: $x=2$ — far from the true optimum $x=1$, deep in the interior. At $t=10$: $x=1.1$ — much closer. At $t=100$: $x=1.01$. As $t\to\infty$, $x\to1$: the central path converges smoothly to the true constrained optimum, always staying strictly on the feasible side ($x>1$) along the way.

Worked example 2: iteration counts at scale

Simplex, in the worst case, can require a number of corner-to-corner steps that grows with the problem's combinatorial size (rarely, exponentially many, though typically fast in practice); a standard interior-point method's iteration count instead grows roughly with $\sqrt{n}$, largely independent of how many corners the region has. For a portfolio problem with 5,000 assets, simplex might take thousands of pivots in a bad case, while an interior-point method routinely reaches high accuracy in 20–50 Newton steps — each step costlier, but far fewer of them, which is why large-scale portfolio optimizers default to interior-point solvers.

Compare the smooth, curving path a Newton-style method traces toward a minimum with the idea of hopping corner to corner — an interior-point method's central path is this same kind of smooth interior trajectory, just constrained to stay inside a feasible region the whole way.

What this means in practice

Interior-point methods are the default engine behind large-scale convex optimization solvers used for portfolio construction, risk-limit enforcement, and index replication when the number of assets and constraints runs into the thousands — and they're essential (not just faster) for second-order cone and semidefinite programs, where there's no exact analogue of a simplex "corner" to hop between at all. Any modern commercial or open-source convex solver handling SOCP or SDP problems is, under the hood, running some variant of an interior-point method.