Interior-Point Method and Barrier Functions

Idea: how to circumvent constraints?

A constrained optimization problem: min f(x) subject to gᵢ(x) ≤ 0. One approach is to "forget" about the constraints, but add a large penalty for their violation. The logarithmic barrier does this elegantly: it goes to +∞ as x approaches the boundary of the feasible set. The interior-point method (IPM) systematically uses this barrier, gradually "decreasing" its influence until an exact solution is obtained. Theoretical complexity of IPM is polynomial, and it was the first polynomial algorithm for linear programming (Khachiyan, 1979; Karmarkar, 1984).

Logarithmic Barrier

For the problem min f(x) subject to gᵢ(x) ≤ 0 we introduce the logarithmic barrier:

φ(x) = − Σᵢ log(−gᵢ(x))

Meaning: When gᵢ(x) → 0 (approaching the constraint boundary), −gᵢ(x) → 0⁺ → log → −∞ → φ(x) → +∞. The barrier "repels" from the boundary.

For gᵢ(x) = −t (x is strictly inside, gap = t): φ(x) = − log t. When the gap doubles, the barrier decreases by log 2.

Barrier problem: min f(x) + (1/t) φ(x)

The parameter t > 0 is "precision". As t → ∞ the barrier term (1/t)φ(x) → 0, and the solution converges to the original.

Central Path

For every t > 0 there exists a unique solution to the barrier problem x*(t) — this is the central path of the problem.

The optimality condition for the barrier problem (KKT condition without constraints):

∇f(x*(t)) + (1/t) Σᵢ (1/(−gᵢ(x*(t)))) ∇gᵢ(x*(t)) = 0

If we denote λᵢ*(t) = 1/(−t gᵢ(x*(t))), then this is precisely the KKT stationarity condition for the original problem! The central path comprises "softened" KKT conditions.

Duality gap on the central path: f(x*(t)) − d* = m/t, where m is the number of constraints. Precision ε is achieved at t = m/ε.

IPM Algorithm

1. Start with t = t₀, x⁰ strictly inside (gᵢ(x⁰) < 0)
2. Solve the barrier problem using Newton’s method: x^+ = x − (∇²L)⁻¹ ∇L (several Newton steps)
3. Increase t: t ← μt (μ > 1, typically μ = 10−20)
4. Repeat until precision ε is reached

Complexity: O(√m) iterations of the "outer" loop, each — one Newton step O(n³) (inverting a matrix). In total: O(√m · n³).

For LP: O(√n log(1/ε)) iterations — polynomial!

Self-Concordant Barriers

A barrier φ is called ν-self-concordant if the following holds:

|D³φ(x)[h,h,h]| ≤ 2(D²φ(x)[h,h])^{3/2}

This is the "self-concordance condition": the third derivative is controlled by the second. With this condition, Newton's method comes with special convergence guarantees.

Self-concordance parameters:

• For LP: φ(x) = −Σ log xᵢ, ν = n (constraints x ≥ 0)
• For SDP: φ(X) = −log det X, ν = n (n×n matrix)
• For SOCP: φ = −log(t² − ‖x‖²), ν = 2

Number of Newton steps: O(√ν log(1/ε)). The smaller ν, the faster IPM.

Full Analysis: LP via IPM

Problem: min cᵀx subject to Ax = b, x ≥ 0 (standard LP form).

Barrier problem: min cᵀx − (1/t) Σᵢ log xᵢ subject to Ax = b.

KKT conditions: c − (1/t)X⁻¹e + Aᵀλ = 0, Ax = b. Here X = diag(x).

Newton step: Solve the linear system: [X⁻² Aᵀ] [Δx] [c + Aᵀλ − (1/t)X⁻¹e] [A 0 ] [Δλ] = [0]

System size is (n+m)×(n+m). With structured A — solution in O(n · m²) (if m << n).

Example: Transportation problem 100×100 (10,000 variables): IPM solves in ~50 iterations (~50 linear systems), simplex method — in ~10,000 vertex steps.

Applications

IPM is the foundation of most industrial solvers (MOSEK, Gurobi, CPLEX). For large LPs — preferable to simplex (fewer iterations). For SDP — the only practically useful paradigm. In control theory, IPM solves LMI problems for H∞ regulator synthesis and Lyapunov stability problems.

Algorithmic Implementation

In practice, the interior-point method requires careful implementation:

1. Starting point: must be strictly within the feasible set. Often, a phase I is used — a separate problem to find such a point.
2. Line search: after computing the Newton direction, a backtracking step is made to ensure remaining inside.
3. Updating the barrier parameter: t ← μt with μ ≈ 10. Too large μ speeds up but destabilizes; too small — slows down.
4. Stopping criterion: by duality gap — the guaranteed distance to the optimum.

Modern Packages

The interior-point method is implemented in industrial solvers: MOSEK, Gurobi (for QP/SOCP), CVXOPT, IPOPT (for nonlinear problems). For semidefinite programming (SDP), specialized versions are used: SDPT3, SeDuMi, COSMO. In machine learning, SDP is used for metric learning, clustering relaxations, and robot control with stability constraints. The interior-point method outperforms the simplex method on large sparse problems, especially when the number of constraints is comparable to the number of variables.