Interior-Point Methods

Solve linear and convex programs by following a smooth central path through the interior of the feasible region.

A different route to the optimum

Where the simplex method walks along the boundary from vertex to vertex, interior-point methods stay strictly inside the feasible region and approach the optimum from within. They solve linear and many convex programs in polynomial time, a theoretical guarantee the simplex method lacks.

The barrier idea

Replace inequality constraints with a logarithmic barrier added to the objective: minimize c dot x - mu * sum log(s_i), where s_i are slacks and mu > 0 controls how strongly the barrier repels iterates from the boundary. As mu decreases toward zero, the minimizer of the barrier problem traces a smooth central path that ends at the true optimum.

Path following

• Start with a moderate mu and a point near the central path.
• Take a Newton step toward the current barrier minimizer.
• Reduce mu geometrically and repeat, following the path to the boundary optimum.

Primal-dual variants

The most effective implementations solve the primal and dual simultaneously, applying Newton's method to the perturbed KKT conditions. Primal-dual interior-point methods converge in a number of iterations that grows very slowly (typically 20 to 50) even for large problems, with each iteration solving a linear system.

Trade-offs versus simplex

Interior-point methods excel on large, sparse problems and have predictable iteration counts, but each iteration is expensive because it factorizes a matrix. The simplex method warm-starts easily and gives exact vertex solutions, which matters for integer programming. Modern solvers include both and choose based on problem structure.

# Barrier subproblem: min c^T x - mu * sum(log(s)),  Ax + s = b
# Newton on perturbed KKT, decrease mu -> 0 along central path.

Interior-point solvers handle the large convex subproblems that arise in control, design optimization, and constrained model fitting.