Interior-point method

An interior-point method solves constrained mathematical optimization problems by maintaining variables in the interiors of their feasible cones or inequality domains. Barrier derivatives are defined there, and damped Newton methods keep subsequent iterates in their domains. A central path gives a family of barrier-regularized optima whose duality gap approaches zero; a conic phase-I problem can supply a strict feasible starting point.

An auxiliary conic optimization problem searches for strict feasibility before following a central path. Given $e\in \mathrm{int}K$, minimizing $t$ subject to $Ax-b+te\in K$ and $t\ge -1$ has a strict feasible start for sufficiently large $t$. Any feasible solution with $t<0$ certifies $Ax-b\in \mathrm{int}K$. If the original problem is strictly feasible, a small negative $t$ is feasible. Equality constraints and dual feasibility require their corresponding auxiliary procedures.

A convex three-times differentiable barrier $F$ is self-concordant whenA barrier of parameter $\nu$ additionally satisfies $|DF(x)[h]|\le \sqrt{\nu D^{2}F(x)[h,h]}$ and diverges at the domain boundary. Logarithmically homogeneous cone barriers satisfy $F(tx)=F(x)-\nu \log t$. The orthant barrier $-{\sum }_i\log x_i$ has parameter equal to the dimension, while the Lorentz-cone barrier $-\log (t^2-\Vert z{\Vert }^2)$ on $t>\Vert z\Vert$ has parameter two. Their Hessians define Dikin ellipsoids and control interior Newton steps.

For a nondegenerate self-concordant barrier, the open local Hessian ballis contained in its barrier domain. This is the Dikin ellipsoid. It supplies a quantitative way to ensure that a damped Newton method stays interior, without relying on Euclidean distance to a possibly curved boundary.

For a strictly feasible primal-dual conic optimization problem and a logarithmically homogeneous barrier, the central path consists of solutionsThe primal-dual gap is $⟨s,y⟩=\nu \mu$. Existence requires appropriate feasibility and boundedness hypotheses, rather than merely a full-rank constraint matrix. Linearizing these equations gives a central-path Newton system.

At a target barrier parameter $\mu$, let $r_p=Ax-b-s$, $r_d=A^{\top }y-c$, $r_c=y+\mu \nabla F(s)$. The Newton direction solvesFull column rank of $A$ and a positive-definite barrier Hessian give a positive-definite reduced matrix. Backtracking must keep both cone variables interior; solving the linear equations alone does not guarantee that a full step stays inside the cones.