Interior-point method
An interior-point method is an algorithmic framework for solving constrained optimization problems by maintaining iterates within the interior of the feasible region and approaching an optimal solution through a sequence of smooth auxiliary problems. The term applies most prominently to algorithms for linear programming, although the same mathematical principles extend to quadratic programming, semidefinite programming, and general convex optimization.
Unlike the simplex method, which moves between vertices of a polyhedron, an interior-point method ordinarily follows a curved trajectory through its interior. This trajectory is associated with a barrier-parameterized family of optimization problems and is known as the central path. The method does not generally reach the boundary during finite-precision computation; instead, its iterates converge toward boundary points that satisfy the optimality conditions.
Interior-point methods became a central subject in mathematical programming after the publication of Narendra Karmarkar’s polynomial-time algorithm for linear programming in 1984. Their subsequent development connected earlier barrier methods with complexity theory, numerical linear algebra, and the geometry of convex cones.
Mathematical formulation
A linear program in standard primal form is written as
[ \begin{aligned} \text{minimize}\quad & c^{\mathsf T}x,\ \text{subject to}\quad & Ax=b,\ &x\geq 0, \end{aligned} ]
where (A\in\mathbb{R}^{m\times n}), (b\in\mathbb{R}^{m}), and (c\in\mathbb{R}^{n}). Its dual problem is
[ \begin{aligned} \text{maximize}\quad & b^{\mathsf T}y,\ \text{subject to}\quad & A^{\mathsf T}y+s=c,\ &s\geq 0. \end{aligned} ]
The vectors (x) and (s) are respectively the primal variables and dual slack variables. Under the standard regularity assumptions of linear programming, optimal solutions satisfy primal feasibility, dual feasibility, and the complementary-slackness equations
[ x_i s_i=0 \qquad\text{for each }i. ]
These equations place an optimum on the boundary because at least one member of every complementary pair must vanish. Interior-point methods replace exact complementarity with the perturbed condition
[ x_i s_i=\mu, ]
where (\mu>0) is the barrier parameter. Together with the feasibility equations, this condition defines the primal-dual central path:
[ Ax=b,\qquad A^{\mathsf T}y+s=c,\qquad XSe=\mu e, ]
with (X=\operatorname{diag}(x)), (S=\operatorname{diag}(s)), and (e) denoting the all-ones vector. As (\mu) approaches zero, points on the central path approach the set of primal-dual optimal solutions.
For a strictly feasible primal problem, an equivalent barrier formulation is
[ \text{minimize}\quad c^{\mathsf T}x-\mu\sum_{i=1}^{n}\log x_i \quad\text{subject to}\quad Ax=b. ]
The logarithmic term diverges as any component of (x) approaches zero. It therefore represents the nonnegativity boundary within a differentiable objective while the barrier parameter remains positive.
Newton systems and primal-dual search directions
Most modern interior-point algorithms obtain their search directions by applying Newton's method to the perturbed optimality equations. At an interior iterate ((x,y,s)), the residuals are
[ r_p=Ax-b, ]
[ r_d=A^{\mathsf T}y+s-c, ]
and
[ r_c=XSe-\sigma\mu e, ]
where (\sigma) specifies a target level of complementarity. Linearization produces the system
[ \begin{bmatrix} A&0&0\ 0&A^{\mathsf T}&I\ S&0&X \end{bmatrix} \begin{bmatrix} \Delta x\ \Delta y\ \Delta s \end{bmatrix}
\begin{bmatrix} r_p\ r_d\ r_c \end{bmatrix}. ]
Eliminating variables yields a reduced system whose coefficient matrix commonly has the form
[ A D A^{\mathsf T}, \qquad D=X S^{-1}. ]
Consequently, the numerical cost of an interior-point iteration is largely determined by the factorization or approximate solution of a structured system of linear equations. Sparse-matrix ordering, scaling, and preconditioning affect this computation because the reduced matrix can become increasingly ill-conditioned as complementarity decreases.
The resulting direction combines movement toward primal feasibility with movement toward dual feasibility and lower complementarity. A step length preserves the strict inequalities (x>0) and (s>0). The barrier parameter is then reduced, causing later iterates to occupy progressively narrower neighborhoods of the central path.
The widely used predictor-corrector formulation computes an initial direction associated with the unperturbed complementarity equations and then incorporates a correction for the nonlinear error predicted by that direction. This construction is associated with Sanjay Mehrotra’s 1992 algorithm and is distinct from the polynomial-complexity analyses that originally established the theoretical status of interior-point methods.
Historical development
Logarithmic barrier functions were studied systematically during the 1950s and 1960s. Anthony Fiacco and Garth McCormick developed sequential unconstrained minimization techniques in which constrained problems were represented by parameterized penalty or barrier objectives. These methods established much of the analytic framework later used to interpret central-path algorithms.
In 1967, I. I. Dikin introduced an affine-scaling method for linear programming based on ellipsoidal geometry inside the feasible polyhedron. Dikin’s construction used local scaling to define a direction that remained compatible with the surrounding inequalities. Although its initial presentation differed from later primal-dual methods, it supplied an important geometric predecessor to them.
The complexity-theoretic context changed after Leonid Khachiyan proved in 1979 that linear programming could be solved in polynomial time by the ellipsoid method. Narendra Karmarkar introduced a different polynomial-time algorithm in 1984. Karmarkar’s projective transformation and potential function generated interior iterates and produced a complexity bound that prompted extensive research into barrier-based and affine-scaling algorithms.
During the late 1980s, Masakazu Kojima, Shinji Mizuno, Akiko Yoshise, and You Watanabe developed a unified primal-dual potential-reduction analysis in which feasibility and complementarity were represented within a common neighborhood of the central path. Their formulation clarified the relationship between projective algorithms and Newton systems derived from perturbed optimality conditions. It also established a direct route from potential-function decrease to polynomial iteration bounds for primal-dual linear programming.
Yurii Nesterov and Arkadi Nemirovski subsequently developed the theory of self-concordant functions. Their framework explained why Newton steps behave predictably for a broad class of barrier functions and extended polynomial-time interior-point theory beyond polyhedral feasible regions. The resulting treatment includes optimization over convex cones and provides a common analysis for logarithmic barriers associated with several structured domains.
Complexity and convergence
Polynomial-time analyses classify interior-point methods according to the neighborhood of the central path that their iterates preserve. A short-step method remains in a narrow neighborhood and takes comparatively conservative Newton steps. Its analysis usually gives an iteration bound proportional to
[ O!\left(\sqrt{n}\log\frac{1}{\varepsilon}\right) ]
for a linear program with (n) nonnegative variables and target duality gap (\varepsilon). Long-step methods permit a wider neighborhood and require a different bound on the progress achieved by each iteration.
The iteration count does not alone determine computational cost. Each iteration requires the solution of one or more linear systems, and the factorization cost depends on the dimensions and sparsity structure of the constraint matrix. In large sparse problems, the pattern of fill-in during factorization may dominate both memory use and running time. For problems possessing exploitable block structure, elimination can instead reduce the Newton system to smaller coupled components.
Convergence analysis commonly uses either a potential function or a neighborhood measure. A potential function combines the primal-dual gap with a term measuring the distribution of componentwise complementarity. A neighborhood analysis directly bounds the distance between (XSe) and the scalar vector (\mu e). Both approaches prevent the iterates from approaching the boundary in an excessively uneven manner before the aggregate duality gap has decreased.
Finite-precision implementations terminate at a point satisfying numerical tolerances rather than exact complementarity. Residual norms quantify the accuracy of the equality constraints and dual equations, while the normalized duality gap measures the remaining discrepancy between primal and dual objective values. These quantities can be affected by scaling and by rank deficiency in the constraint matrix.
Conic interpretation
Interior-point theory extends naturally from nonnegative vectors to convex cones. A conic program has the form
[ \begin{aligned} \text{minimize}\quad & \langle c,x\rangle,\ \text{subject to}\quad & \mathcal{A}x=b,\ &x\in K, \end{aligned} ]
where (K) is a closed convex cone and (\mathcal{A}) is a linear operator. The dual variables belong to the dual cone (K^\ast). Complementarity is expressed through the pairing between primal and dual cone elements.
For the nonnegative orthant, the standard logarithmic barrier is (-\sum_i\log x_i). For the cone of positive-definite matrices, the corresponding barrier is
[ -\log\det X. ]
This matrix barrier underlies interior-point algorithms for semidefinite programming. Its Hessian reflects the geometry of the positive-definite cone, while its divergence near singular matrices prevents finite barrier iterates from leaving the cone’s interior.
The general complexity of a conic interior-point method depends on the barrier parameter associated with a self-concordant barrier for (K). This parameter replaces the ordinary variable count in iteration bounds and connects analytic curvature with algorithmic complexity. Symmetric cones permit particularly structured primal-dual formulations through Euclidean Jordan algebras.
Relation to other optimization methods
Interior-point methods differ from active-set methods in how they represent inequality constraints. An active-set method estimates which constraints are binding at the solution and solves a sequence of equality-constrained subproblems. An interior-point method instead represents all inequality boundaries through positive slack variables or barrier terms until convergence.
The simplex method maintains a basic feasible solution and changes the associated basis through pivot operations. Its iterates usually lie on vertices or lower-dimensional faces of the feasible polyhedron. Interior-point iterates generally lack a simplex basis, so a separate crossover computation may be used when a basic optimal solution is required for post-solution analysis.
First-order methods rely principally on gradient information and comparatively inexpensive matrix-vector operations. Interior-point methods ordinarily use second-order information, either explicitly through Hessians or implicitly through Newton systems. The resulting distinction concerns the amount of linear algebra performed per iteration and the attainable local accuracy, rather than the class of objective values represented by the algorithms.