Interior Point Methods

Interior point methods are a family of algorithms for convex optimization that solve constrained problems by traversing the interior of the feasible region rather than marching along its boundary. The central idea, developed by Karmarkar and refined by Nesterov and Nemirovski, is to transform a constrained problem into a sequence of unconstrained problems via a barrier function that repels the iterates from the boundary. The method follows a central path — a smooth curve through the interior that converges to the optimum as the barrier weight is reduced to zero.

Interior point methods are polynomial-time for linear programming, semidefinite programming, and a broad class of convex programs. They outperformed the simplex method on large structured problems and remain the algorithm of choice for problems with thousands to millions of variables. The barrier framework also generalizes to second-order cone programming and hyperbolic programming, revealing a unified geometry of convex computation.

The elegance of interior point methods conceals a systems-level fragility: they require the feasible region to have a non-empty interior, and they fail catastrophically when constraints are nearly active or the problem is ill-conditioned — conditions that arise precisely in the most consequential real-world applications.