Interior-Point Methods and Self-Concordant Barriers

The simplex method worked for decades, yet nobody could prove it was polynomial. In 1984 Khachian gave a theoretical proof, and Nesterov and Nemirovskii delivered a practically efficient polynomial algorithm through barrier functions.

• CVXPY: used in 1600+ papers in 2023, solves LP/QP/SDP in polynomial time via interior-point methods with a unified interface
• Portfolio optimization: Markowitz QP with n=10,000 assets is solved in seconds by interior-point vs. hours for the simplex method
• H-infinity control: robust controller synthesis for aerospace reduces to SDP, solved by interior-point in O(n^{3.5}) operations
• Program verification: checking safety properties through abstract interpretation requires solving thousands of LPs per second

Предварительные знания

• Convex sets and functions
• KKT conditions
• Newton's method

• Convex Functions
• KKT Optimality Conditions

Barrier Method: Logarithmic Barrier

The barrier method is the first branch of interior-point methods, going back to Fiacco-McCormick (1968). The idea is to replace a constrained problem by a sequence of unconstrained ones with a penalty term that goes to infinity near the feasible boundary. The logarithmic barrier is the canonical choice that delivers polynomial complexity for linear and quadratic programs.

The increment of t is a key parameter. Usually t_{k+1} = mu * t_k with mu in 10 to 100. Large mu means fewer outer iterations but harder inner problems. The theoretical optimum mu ~ exp(O(sqrt(m))) gives O(sqrt(m) * log(1/eps)) total Newton steps.

Primal-Dual Methods

Primal-dual methods (Mehrotra 1992) drop the strict outer-loop structure of the barrier method. They work simultaneously with the primal variable x, the dual lambda, and the centering parameter t. Newton steps solve the perturbed KKT conditions, delivering excellent practical performance on large problems.

Mehrotra's predictor-corrector is the industry standard (CPLEX, Gurobi). The predictor steps toward the boundary, the corrector reduces complementarity imbalance. Empirically 2 to 3 times faster than a plain predictor.

Unlike a pure barrier method, primal-dual does not require a strict interior starting point - infeasible-start variants work with arbitrary x and lambda > 0. That is critical for large industrial problems where finding a feasible point is itself nontrivial.

Convergence Theory and Complexity

Complexity theory of interior-point methods is revolutionary: Karmarkar (1984) showed linear programming is solvable in polynomial time, overturning the belief that all non-simplex methods are subexponential. Modern theory (Nesterov-Nemirovski 1994) gives a unified proof for a wide class of self-concordant functions.

Self-concordant barriers exist for every closed convex set with nonempty interior, but explicit formulas are known only for canonical cones - the nonnegative orthant (log-barrier), Lorentz cone (log of a quadratic), positive semidefinite cone (log det). Symmetric cones cover all practical classes.

Problems with weak duality gap or poor conditioning may suffer numerical issues near the boundary. Mehrotra-style regularization (slack variables, perturbation) restores stability; modern solvers use iterative refinement and presolve to prepare the problem.

Empirically, modern IPM solvers (CPLEX, Gurobi, Mosek) solve LPs with millions of variables in seconds and SDPs with thousands of variables in minutes. For very large problems (n > 10^7) first-order methods (ADMM, accelerated gradient) replace IPM, trading precision for memory scalability.

Key ideas

• The log-barrier -sum ln s_i(x) replaces inequality constraints with a penalty that tends to infinity at the boundary
• Self-concordance |F'''| <= 2(F'')^{3/2} guarantees quadratic convergence of Newton's step without line search
• Barrier parameter nu: n for LP and n x n SDP; iteration count O(sqrt(nu) * ln(1/eps))
• The central path {x*(t)} is an analytic curve connecting the interior to the optimum as t increases
• Mehrotra predictor-corrector is the practical implementation in CPLEX/Gurobi: 30-50 iterations for million-variable problems

Connections to Other Areas

Interior-point methods unite convex analysis, numerical linear algebra, and computational complexity theory.

• Semidefinite Programming (SDP) — Interior-point methods are the standard SDP solver via the log-determinant barrier
• Interior Point Method — Introductory chapter on barriers and self-concordant functions
• Stochastic Optimization and Adaptive Methods — Stochastic analogues of barrier methods are an active research area

Вопросы для размышления

• Why does the SDP barrier -ln det(X) have parameter nu = n (not n^2, even though an n x n matrix has n^2 entries)?
• How does the central path relate to the complementary slackness KKT conditions of the original problem?
• Why does the Mehrotra predictor-corrector need half as many iterations in practice compared to the theoretical analysis?