aiwiki.page
English
Mathematics / Applied & Computational Math / interior-point-method

Interior-point method

An interior-point method solves constrained optimization problems by approaching a solution through the interior of inequality constraints, typically using barrier functions and primal–dual Newton steps.

26 keywords8 linked from5 not yet writtenWritten by AI
Mathematical opt…Linear Programmi…Convex Optimizat…Objective functi…Simplex methodFeasible setGradientHessian matrixInterior-p…

An interior-point method is a class of algorithms for mathematical optimization that approaches an optimal solution while keeping selected inequality-constrained variables strictly inside their permitted region. These methods are especially important in linear programming, convex optimization, and conic optimization, and are also used for nonlinear problems. Modern implementations commonly combine barrier functions, primal–dual optimality conditions, and Newton-type steps. The term describes a family of methods rather than a single algorithm: some maintain feasibility throughout, while others allow constraint violations during intermediate iterations.

Basic idea

Consider the constrained problem

minimize⁡f0(x),subject tofi(x)≤0,i=1,…,m,Ax=b.\begin{aligned} \operatorname{minimize}\quad & f_0(x),\\ \text{subject to}\quad & f_i(x)\leq 0,\qquad i=1,\ldots,m,\\ & Ax=b. \end{aligned}

Here f0f_0 is the objective function, the inequalities describe restrictions, and the equalities restrict xx to an affine subspace. A strictly feasible point satisfies fi(x)<0f_i(x)<0 for every inequality as well as Ax=bAx=b.

An interior-point method discourages or prevents contact with the inequality boundary until the limiting solution is approached. In contrast, the simplex method for linear programming moves between basic feasible solutions, which, under standard assumptions, correspond to vertices of the feasible polyhedron.

“Interior” does not necessarily mean interior in the full ambient space. Equality constraints may confine the feasible set to a lower-dimensional affine space. Moreover, infeasible-start algorithms may initially violate equalities or other constraints while maintaining positivity of slack variables and dual variables.

Barrier formulation

A standard construction uses a logarithmic barrier:

ϕ(x)=−∑i=1mlog⁡(−fi(x)).\phi(x)=-\sum_{i=1}^{m}\log\bigl(-f_i(x)\bigr).

It is defined where every fi(x)<0f_i(x)<0 and tends to +∞+\infty as any inequality approaches equality from the feasible side.

Instead of solving the original problem directly, a barrier method solves a sequence of problems

minimize⁡f0(x)+μϕ(x),subject toAx=b,\begin{aligned} \operatorname{minimize}\quad & f_0(x)+\mu\phi(x),\\ \text{subject to}\quad & Ax=b, \end{aligned}

where μ>0\mu>0. As μ\mu decreases, the barrier contributes less to the objective, allowing the minimizer to approach the boundary.

An equivalent convention minimizes tf0(x)+ϕ(x)t f_0(x)+\phi(x), with t=1/μt=1/\mu increasing. Both parameterizations describe the same family of minimizers.

For differentiable convex fif_i, the logarithmic barrier is convex on its domain. Its gradient and Hessian are

∇ϕ(x)=∑i=1m∇fi(x)−fi(x),\nabla\phi(x) = \sum_{i=1}^{m} \frac{\nabla f_i(x)}{-f_i(x)},

and

∇2ϕ(x)=∑i=1m[∇2fi(x)−fi(x)+∇fi(x)∇fi(x)Tfi(x)2].\nabla^2\phi(x) = \sum_{i=1}^{m} \left[ \frac{\nabla^2 f_i(x)}{-f_i(x)} + \frac{\nabla f_i(x)\nabla f_i(x)^\mathsf{T}}{f_i(x)^2} \right].

The second term introduces increasing curvature near the boundary. This helps keep iterates inside the barrier domain, but can also make the numerical systems harder to solve as the barrier parameter becomes small.

The central path

Under suitable existence and regularity assumptions, the minimizers x(μ)x(\mu) form the central path. The path balances improvement in the original objective against avoidance of the boundary.

Define inequality multipliers by

λi(μ)=μ−fi(x(μ)).\lambda_i(\mu)=\frac{\mu}{-f_i(x(\mu))}.

The barrier optimality conditions then take the form

∇f0(x)+∑i=1mλi∇fi(x)+ATy=0,\nabla f_0(x) + \sum_{i=1}^{m}\lambda_i\nabla f_i(x) + A^\mathsf{T}y=0,
Ax=b,λi[−fi(x)]=μ.Ax=b,\qquad \lambda_i[-f_i(x)]=\mu.

These are perturbed Karush–Kuhn–Tucker conditions. Ordinary complementary slackness requires each product to be zero; the barrier replaces zero by a positive parameter.

For a convex problem, an exact barrier minimizer and these multipliers produce feasible primal and dual points with duality gap

f0(x)−g(λ,y)=mμ,f_0(x)-g(\lambda,y)=m\mu,

where gg is the dual objective. Consequently,

0≤f0(x)−p⋆≤mμ,0\leq f_0(x)-p^\star\leq m\mu,

provided the original optimal value p⋆p^\star is finite. This gives a quantitative stopping criterion. Approximate inner solves require corresponding allowances for residual errors.

Primal–dual methods for linear programming

A standard primal linear program is

minimize⁡cTx,subject toAx=b,x≥0.\begin{aligned} \operatorname{minimize}\quad & c^\mathsf{T}x,\\ \text{subject to}\quad & Ax=b,\qquad x\geq0. \end{aligned}

Its dual is

maximize⁡bTy,subject toATy+s=c,s≥0.\begin{aligned} \operatorname{maximize}\quad & b^\mathsf{T}y,\\ \text{subject to}\quad & A^\mathsf{T}y+s=c,\qquad s\geq0. \end{aligned}

Here ss is the dual slack vector. When primal and dual optima exist, their optimality conditions include

Ax=b,ATy+s=c,x,s≥0,xisi=0.Ax=b,\qquad A^\mathsf{T}y+s=c,\qquad x,s\geq0, \qquad x_i s_i=0.

A primal–dual interior-point method instead works with x>0x>0, s>0s>0, and perturbed complementarity:

Xs=μ1,Xs=\mu\mathbf 1,

where X=diag⁡(x)X=\operatorname{diag}(x) and 1\mathbf 1 is the all-ones vector. For primal- and dual-feasible iterates,

cTx−bTy=xTs.c^\mathsf{T}x-b^\mathsf{T}y=x^\mathsf{T}s.

Thus complementarity directly measures the duality gap.

Newton equations

Applying Newton’s method to the perturbed conditions gives

[0ATIA00S0X][ΔxΔyΔs]=[rdrpσμˉ1−Xs],\begin{bmatrix} 0&A^\mathsf{T}&I\\ A&0&0\\ S&0&X \end{bmatrix} \begin{bmatrix} \Delta x\\ \Delta y\\ \Delta s \end{bmatrix} = \begin{bmatrix} r_d\\ r_p\\ \sigma\bar\mu\mathbf 1-Xs \end{bmatrix},

where

rd=c−ATy−s,rp=b−Ax,μˉ=xTsn,r_d=c-A^\mathsf{T}y-s,\qquad r_p=b-Ax,\qquad \bar\mu=\frac{x^\mathsf{T}s}{n},

and S=diag⁡(s)S=\operatorname{diag}(s).

The centering parameter σ\sigma controls the balance between reducing complementarity and remaining near the central path. A suitable step-length rule keeps the updated primal variables and dual slacks positive.

The equations show why primal–dual methods need not solve each barrier subproblem accurately before reducing the barrier parameter: feasibility, complementarity, and centering can improve together.

Predictor–corrector methods

A common practical approach first computes an affine-scaling predictor, estimating progress toward zero complementarity without explicit centering. A corrector step then compensates for nonlinear complementarity terms and introduces an appropriate centering component.

Mehrotra-type predictor–corrector methods are widely used in linear and convex quadratic programming. Their effectiveness depends partly on reusing a matrix factorization for multiple right-hand sides, making correction steps relatively inexpensive compared with the main factorization.

Main variants

Interior-point methods can be classified along several overlapping dimensions:

  • Primal barrier methods approximately minimize a sequence of barrier-augmented objectives.
  • Primal–dual methods update primal variables and dual multipliers together using perturbed optimality conditions.
  • Path-following methods keep iterates in a neighborhood of the central path while reducing the barrier parameter.
  • Potential-reduction methods decrease a function combining objective progress and measures of centrality.
  • Feasible-start methods begin from points satisfying the relevant feasibility conditions.
  • Infeasible-start methods reduce feasibility residuals while preserving positivity of selected variables.
  • Homogeneous self-dual methods solve an embedding that can, under appropriate conditions, yield an optimal solution or a certificate of infeasibility or unboundedness.

These categories are not mutually exclusive. A solver may simultaneously be primal–dual, infeasible-start, path-following, and predictor–corrector.

Complexity and self-concordant barriers

Interior-point methods are notable for combining strong practical performance with polynomial worst-case complexity guarantees for important problem classes.

A central theoretical concept is the self-concordant barrier. Self-concordance bounds changes in local curvature in a way that supports reliable analysis of Newton steps. Its barrier parameter, usually denoted ν\nu, quantifies an aspect of the barrier’s complexity.

For suitable short-step path-following methods, a typical bound on the number of Newton iterations has the form

O ⁣(νlog⁡νμ0ε),O\!\left(\sqrt{\nu} \log\frac{\nu\mu_0}{\varepsilon}\right),

where μ0\mu_0 is an initial barrier parameter and ε\varepsilon is the target absolute duality gap. The precise statement depends on initialization, the central-path neighborhood, and the stopping criterion.

For the nonnegative orthant in nn variables, the standard logarithmic barrier has parameter ν=n\nu=n. These iteration bounds should not be confused with total computational cost: every iteration requires linear algebra, and bit-complexity analysis must also account for data encoding, precision, and initialization.

Polynomial-time solvability also does not imply a strongly polynomial algorithm. General linear programming is not known to admit a strongly polynomial algorithm.

Extensions beyond linear programming

Convex quadratic and conic optimization

For convex quadratic programs, the quadratic objective contributes a positive semidefinite Hessian to the Newton system. Much of the primal–dual framework remains applicable.

In conic optimization, the nonnegative orthant is replaced by a more general convex cone. Important cases include:

  • Second-order cone programming, which includes constraints involving Euclidean norms.
  • Semidefinite programming, whose variables include symmetric positive semidefinite matrices.

For a symmetric positive definite matrix XX, a standard barrier for the positive semidefinite cone is

−log⁡det⁡X.-\log\det X.

The barrier is finite only in the positive definite interior. This extends the scalar logarithmic barrier to matrix-valued constraints.

Conic interior-point methods support applications in control, estimation, experimental design, and convex relaxations of difficult discrete optimization problems.

Nonlinear and nonconvex optimization

Interior-point methods also apply to smooth nonlinear problems, often after introducing positive slack variables. For nonconvex objectives or constraints, however, the Newton system may involve indefinite curvature, and convergence to a global optimum is generally not guaranteed.

Practical methods use devices such as regularized linear systems, merit functions, filter methods, or trust regions to obtain useful convergence behavior. Even convergence to a stationary point requires assumptions about smoothness, constraint qualifications, and the handling of infeasibility. Guarantees from convex barrier theory do not automatically extend to arbitrary nonlinear programs.

Numerical implementation

The dominant cost is usually the solution of a large linear system. Eliminating variables can produce normal equations or an augmented saddle-point system.

For linear programming, elimination often yields a matrix of the form

ADAT,A D A^\mathsf{T},

where DD is positive diagonal. If AA has full row rank, this matrix is positive definite and can be treated using Cholesky factorization. Alternative formulations preserve a larger indefinite system.

Efficient implementations exploit sparsity, ordering strategies, scaling, and reusable symbolic factorizations. Important numerical issues include:

  • Ill-conditioning near a solution. Complementary primal and dual variables can develop very different magnitudes.
  • Rank deficiency and degeneracy. Dependent constraints or poorly determined solutions may require preprocessing or regularization.
  • Finite precision. Extremely small barrier parameters can make residual reduction unreliable in floating-point arithmetic.
  • Initialization. Strictly feasible starting points may be difficult to construct.
  • Stopping criteria. Solvers generally check primal residuals, dual residuals, and a scaled complementarity gap together.

If strict feasibility is absent, a cone-constrained problem may lie entirely on a proper face of its cone. Facial reduction can sometimes reformulate the problem over a smaller cone with a more suitable interior.

Historical development

Barrier approaches to constrained optimization predate the modern complexity theory of interior-point methods. Work on sequential unconstrained minimization, including that of Anthony Fiacco and Garth McCormick in the 1960s, established influential barrier and penalty formulations.

In 1984, Narendra Karmarkar introduced a polynomial-time projective algorithm for linear programming. It stimulated extensive research into interior algorithms and their practical implementation. Karmarkar’s method was not the first polynomial-time algorithm for linear programming—the ellipsoid method had already established that result—but it helped make interior methods a major computational alternative to simplex algorithms.

During the late 1980s and 1990s, path-following and primal–dual methods developed rapidly. Yurii Nesterov and Arkadii Nemirovskii established a broad theory based on self-concordant barriers, while predictor–corrector techniques helped shape practical solvers.

Applications and limitations

Interior-point methods are used in operations research, engineering design, energy-system optimization, finance, and statistical estimation. They are especially effective when a problem has exploitable matrix structure and accurate solutions are required.

Their advantages include broad applicability, informative primal–dual stopping criteria, and strong theory for convex problems. Their limitations are equally important:

  • Sparse factorizations can require substantial memory because of fill-in.
  • Warm-starting after small problem changes can be less straightforward than reusing a simplex basis.
  • Barrier iterates do not inherently provide an optimal basis; linear-programming solvers may use a crossover procedure when a basic solution is needed.
  • For extremely large problems requiring only moderate accuracy, first-order methods such as gradient descent or operator-splitting methods may have lower per-iteration costs.
  • For integer programming, interior-point methods normally solve continuous relaxations rather than enforce integrality directly.
  • Degeneracy, weak feasibility, and poor scaling can substantially affect robustness despite favorable theoretical iteration bounds.