Takeaway

Interior-point methods follow a central path defined by barrier functions to solve large LP/QP/SDP problems efficiently with polynomial-time guarantees.

The problem (before → after)

  • Before: Simplex can be exponential in worst case; naive constraints handling is brittle.
  • After: Barrier functions keep iterates strictly feasible and well-conditioned, converging rapidly.

Mental model first

Imagine sliding down a smooth canyon that avoids scraping the walls (constraints) by inflating a cushion that keeps you away from the edges while guiding you to the floor.

Just-in-time concepts

  • Log barrier: φ(x) = −∑ log(−g_i(x)).
  • Central path: minimize t f(x) + φ(x); increase t to tighten approximation.
  • Newton steps on the barrier objective.

First-pass solution

Initialize strictly feasible x; set t; iterate Newton steps; update t (e.g., multiply by μ>1) until duality gap is small.

Iterative refinement

  1. Primal–dual methods improve robustness.
  2. Sparse linear algebra and preconditioning dominate runtime.
  3. Self-concordant barriers yield complexity bounds.

Principles, not prescriptions

  • Maintain strict feasibility for stability.
  • Use problem structure (sparsity, cones) to scale.

Common pitfalls

  • Poor line search and step sizes stall progress.
  • Ignoring numerical conditioning in KKT solves.

Connections and contrasts

  • See also: [/blog/convex-optimization], [/blog/branch-and-bound], [/blog/benders-decomposition].

Quick checks

  1. Why barriers? — Turn constrained problems into smooth unconstrained ones.
  2. What is the duality gap? — Certificate of suboptimality; target for stopping.
  3. Why primal–dual? — Better conditioning and step acceptance.

Further reading

  • Nesterov & Nemirovski; Wright (book above)