Interior-Point Methods: The Barrier Method, Central Path, and Primal-Dual Algorithms

Intuition Beginner

Imagine you must find the lowest point of a tilted floor inside a fenced yard, but you are forbidden to touch the fence. One way to obey the rule without ever thinking about it: pretend the fence glows red-hot, so the closer you get the more it pushes you back. Add that imaginary heat to the real tilt of the floor and walk downhill on the combined feeling. You settle at a compromise point — low on the floor, but held a safe distance from the fence by the heat.

That imaginary heat is a barrier. It is a smooth penalty that grows without bound as you approach the edge of the allowed region and is gentle deep inside. Adding a barrier to the true cost turns a problem with hard walls into a smooth, wall-free problem you can solve by the curvature-aware steps of the previous unit. The catch is that the barrier also pulls the answer away from the true best point, which usually sits right on a wall.

The fix is to turn the heat down gradually. Solve the heated problem, then make the barrier weaker, then solve again starting from where you just were, and repeat. As the heat fades the compromise point slides toward the true optimum, tracing a smooth curve through the inside of the region. That curve is the central path, and following it is how interior-point methods reach the answer from within, never walking the edges the way corner-hopping methods do.

Visual Beginner

Picture a triangular yard (the feasible region) on a gently tilted floor. The true lowest point is a corner of the triangle, sitting on the fence. Start somewhere in the middle. With a strong barrier the heated low point sits near the center of the triangle, far from any edge. Turn the heat down and the low point creeps toward the optimal corner; turn it down again and it creeps further. Connecting all these low points draws a smooth curve from the center to the corner — the central path.

   feasible triangle (the yard)              the central path

        *-----------------*                  *-----------------*
         \               /                    \   . <- strong   /
          \   . o . .   /                      \   .  barrier  /
           \   inside  /                        \   .         /
            \  region /                          \   .       /
             \       /                            \  .      /
              \     /                              \ .     /
               \   /                                \.    /  weak barrier
                \ /                                  o  <- (near optimum)
                 *  <- optimum (a corner)            *  <- optimum

As the barrier weakens, the heated minimum (marked o) slides along the dotted curve from deep inside toward the optimal corner. Each o is one solved sub-problem; the solver jumps from one to the next.

Worked example Beginner

We trace the central path of a one-variable problem by hand. Minimize the cost $x$ over the allowed region $x\ge 0$. The true answer is plainly $x=0$, sitting right on the wall. Watch the barrier method reach it from inside.

Step 1. Add the barrier. The standard barrier for the rule $x\ge 0$ is $-\log x$, which blows up as $x$ shrinks to zero. Weight the true cost by a knob $t$ and add the barrier: minimize $tx-\log x$ for a chosen positive $t$. A bigger $t$ means we trust the true cost more and the barrier less.

Step 2. Find the heated minimum. The combined function $tx-\log x$ is a smooth bowl for $x>0$. Its lowest point is where its slope is zero: the slope is $t-\frac{1}{x}$, which is zero when $x=\frac{1}{t}$. So the heated answer is $x^{\star }(t)=\frac{1}{t}$.

Step 3. Turn the heat down by turning $t$ up. At $t=1$ the answer is $x=1$. At $t=10$ it is $x=0.1$. At $t=1000$ it is $x=0.001$. Each larger $t$ pushes the answer closer to the wall at $x=0$.

Step 4. Read the gap. The leftover error here is exactly $x^{\star }(t)-0=\frac{1}{t}$. To get within $0.001$ of the true answer you need $t=1000$. The central path is the set of points $x=\frac{1}{t}$ as $t$ ranges upward — a curve sliding into the wall from inside.

What this tells us. The barrier keeps every iterate strictly inside the allowed region, and the single knob $t$ controls how close to the boundary you land. Driving $t$ up drives the gap $\frac{1}{t}$ to zero, so the method reaches the boundary optimum without ever standing on the boundary. That controlled approach from inside is the whole idea.

Check your understanding Beginner

Formal definition Intermediate+

Consider the convex conic program of 44.05.01 in standard primal-dual form,

$$p^{\star }=\underset{x}{\inf }{c}^{\top }x\text{ s.t. }Ax=b,x\in K,d^{\star }=\underset{y,s}{\sup }{b}^{\top }y\text{ s.t. }{A}^{\top }y+s=c,s\in K^{\ast },$$

with $K\subseteq {\mathbb{R}}^N$ a proper cone and $K^{\ast }$ its dual cone. The interior-point machinery is built on a barrier for $K$.

Definition (logarithmically-homogeneous self-concordant barrier). A function $F:\mathrm{int}K\to \mathbb{R}$ is a $\nu$-self-concordant barrier for $K$ if it is $C^3$ and strictly convex on the interior, blows up at the boundary ($F(x_k)\to +\infty$ whenever $x_k\to \partial K$), satisfies the self-concordance inequality of 44.03.03,

$$|D^{3}F(x)[h,h,h]|\le 2(D^{2}F(x)[h,h]{)}^{3/2}\text{for all }x\in \mathrm{int}K,h\in {\mathbb{R}}^N,$$

and has barrier (complexity) parameter $\nu$ controlling the gradient through ${\sup }_h(2DF(x)[h]-D^{2}F(x)[h,h])\le \nu$. The canonical cone barriers are logarithmically homogeneous of degree $\nu$: $F(\tau x)=F(x)-\nu \log \tau$ for $\tau >0$. The three workhorse cones carry

$$F_{{\mathbb{R}}_{+}^n}(x)=-\sum _{i=1}^n\log x_i(\nu =n),F_{{\mathcal{L}}^{n+1}}(u,t)=-\log (t^2-\Vert u{\Vert }_2^2)(\nu =2),F_{{\mathbb{S}}_{+}^n}(X)=-\log \det X(\nu =n).$$

Definition (central path). For barrier parameter $t>0$, the central point $x^{\star }(t)$ is the minimizer of the barrier-augmented objective,

$$x^{\star }(t)=\arg \underset{Ax=b,x\in \mathrm{int}K}{\min }t{c}^{\top }x+F(x),$$

a strictly convex equality-constrained problem solved by the Newton method of 44.03.03. The central path is the curve $\{x^{\star }(t):t>0\}$. As $t\to \infty$ the barrier's weight fades and $x^{\star }(t)\to$ an optimal $x^{\star }$; as $t\to 0^{+}$ the central point tends to the analytic center of the feasible set.

Definition (barrier / SUMT method). The barrier method (sequential unconstrained minimization) fixes an increase factor $\mu >1$ and a tolerance $\epsilon$. Starting from a strictly feasible $x$ and $t=t_0$: (i) centering — compute $x^{\star }(t)$ by Newton's method started at the current $x$; (ii) update — set $x\leftarrow x^{\star }(t)$ and $t\leftarrow \mu t$; (iii) stop when the duality bound $\nu /t\le \epsilon$. Each pass is an outer iteration; the Newton steps inside it are inner iterations.

Definition (perturbed KKT system). Writing $X=\mathrm{diag}(x)$, $S=\mathrm{diag}(s)$ and $1$ the all-ones vector in the orthant case, the central point is the unique solution of the perturbed KKT (optimality) system

$$Ax=b,A^{\top }y+s=c,XS1=\mu 1,(x,s)>0,$$

where $\mu =1/t$. The third block replaces exact complementarity $x_i{s}_i=0$ by the perturbed complementarity $x_i{s}_i=\mu$; sending $\mu \to 0$ recovers the genuine KKT conditions. The conic generalization replaces $XS1=\mu 1$ by $x\circ s=\mu e$ in the Euclidean Jordan algebra of the cone ($e$ the identity element, $\circ$ the Jordan product). A primal-dual interior-point method applies Newton's method directly to this system in the variables $(x,y,s)$, taking damped steps that keep $(x,s)$ strictly inside the cones.

Counterexamples to common slips

• "Any barrier that blows up at the boundary works." Polynomial-time guarantees need self-concordance; a merely-convex barrier such as ${\sum }_{i}1/x_i$ for the orthant gives no constant-free Newton analysis and no $O(\sqrt{\nu })$ bound. The logarithmic barrier is special because it is self-concordant.
• "The barrier parameter $\nu$ equals the dimension." Only for the orthant ($\nu =n$) and PSD cone ($\nu =n$). The Lorentz cone in ${\mathbb{R}}^{n+1}$ has $\nu =2$ regardless of $n$ — the source of SOCP's efficiency advantage over its SDP embedding.
• "The central path is the segment from the analytic center to the optimum." It is a smooth curve, generally not a straight line, defined by the perturbed KKT system; only for special data is it affine.

Key theorem with proof Intermediate+

The result that makes the barrier method work and that quantifies its accuracy is the central-path duality bound: each central point comes with a dual certificate whose duality gap is exactly $\nu /t$.

Theorem (central-path duality gap). Let $F$ be a $\nu$-logarithmically-homogeneous self-concordant barrier for the proper cone $K$, and let $x^{\star }(t)$ be the central point for $t>0$ of the strictly-feasible conic program. Then there is a dual-feasible pair $(y^{\star }(t),s^{\star }(t))$ with $s^{\star }(t)=-\frac{1}{t}\nabla F(x^{\star }(t))\in \mathrm{int}{K}^{\ast }$, and the primal-dual duality gap along the central path is

$$c^{\top }{x}^{\star }(t)-b^{\top }{y}^{\star }(t)=⟨x^{\star }(t),s^{\star }(t)⟩=\frac{\nu }{t}.$$

Consequently $0\le c^{\top }{x}^{\star }(t)-p^{\star }\le \nu /t$, and driving $t\to \infty$ drives the central point to optimality.

Proof. Fix $t$ and abbreviate $x=x^{\star }(t)$. The centering problem $\min \{t{c}^{\top }x+F(x):Ax=b\}$ is convex with a strictly feasible interior point, so its optimality condition is stationarity of the Lagrangian $t{c}^{\top }x+F(x)+(y^{\prime }{)}^{\top }(b-Ax)$ over the affine constraint. There is a multiplier $y^{\star }(t)$ (set $y^{\prime }=-t{y}^{\star }$ after scaling) with

$$tc+\nabla F(x)-A^{\top }(t{y}^{\star })=0,\text{i.e.}\nabla F(x)=-t(c-A^{\top }{y}^{\star })=-t{s}^{\star },$$

where $s^{\star }:=c-A^{\top }{y}^{\star }$. Thus $s^{\star }=-\frac{1}{t}\nabla F(x)$. For a logarithmically-homogeneous barrier the gradient satisfies $-\nabla F(x)\in \mathrm{int}{K}^{\ast }$ (the negative gradient of the barrier is the canonical map $\mathrm{int}K\to \mathrm{int}{K}^{\ast }$), so $s^{\star }\in \mathrm{int}{K}^{\ast }$ and $(y^{\star },s^{\star })$ is strictly dual feasible because $A^{\top }{y}^{\star }+s^{\star }=c$ by construction.

The duality gap is the conic pairing of 44.05.01. Using $Ax=b$ and $A^{\top }{y}^{\star }+s^{\star }=c$,

$$c^{\top }x-b^{\top }{y}^{\star }=c^{\top }x-(Ax{)}^{\top }{y}^{\star }=(c-A^{\top }{y}^{\star }{)}^{\top }x=⟨s^{\star },x⟩=⟨-\frac{1}{t}\nabla F(x),x⟩=-\frac{1}{t}⟨\nabla F(x),x⟩.$$

Logarithmic homogeneity $F(\tau x)=F(x)-\nu \log \tau$ differentiated in $\tau$ at $\tau =1$ gives the Euler identity $⟨\nabla F(x),x⟩=-\nu$. Substituting, $c^{\top }x-b^{\top }{y}^{\star }=-\frac{1}{t}(-\nu )=\nu /t$. Weak duality of 44.02.01 gives $b^{\top }{y}^{\star }\le p^{\star }\le c^{\top }x$, so $0\le c^{\top }x-p^{\star }\le c^{\top }x-b^{\top }{y}^{\star }=\nu /t$. $\square$

Bridge. This identity builds toward the polynomial complexity bound of the Advanced results and appears again in the stopping rule $\nu /t\le \epsilon$ of every barrier-method and primal-dual implementation. This is exactly the conic complementary slackness of 44.05.01 read off the path: exact complementarity $⟨x,s⟩=0$ is the $t\to \infty$ limit of the perturbed complementarity $⟨x^{\star }(t),s^{\star }(t)⟩=\nu /t$, so the dual slack $s^{\star }(t)=-\frac{1}{t}\nabla F$ is dual to the primal central point through the barrier gradient, the canonical interior-to-interior cone map. The foundational reason the method is well posed is that the negative barrier gradient lands in $\mathrm{int}{K}^{\ast }$ automatically, manufacturing a strictly feasible dual point at every $t$ for free, which generalises the per-coordinate slack $s_i=1/(t{x}_i)$ of the orthant barrier to an arbitrary self-concordant cone. Putting these together, the central path is the homotopy that deforms the analytic center into the optimum as $t$ runs from $0$ to $\infty$, the Newton centering of 44.03.03 is the engine that follows it, and the gap $\nu /t$ is the odometer reading off the remaining distance — three views of the single perturbed-KKT system.

Exercises Intermediate+

Advanced results Master

The short-step path-following bound and the $O(\sqrt{\nu }\log (1/\epsilon ))$ complexity

The polynomial-time theorem is the centerpiece of the Nesterov-Nemirovski theory ^{[Nesterov & Nemirovski 1994]}. A short-step path-following method keeps the iterate inside a Dikin/Newton neighborhood $\{x:{\lambda }_F(x;t)\le \beta \}$ of the central path, where ${\lambda }_F$ is the Newton decrement of the centered objective in the barrier's Hessian metric. Increasing $t$ by the conservative factor $\mu =1+\gamma /\sqrt{\nu }$ moves the target central point by an amount the next single Newton step recenters, so each outer iteration costs one damped Newton step. Because $t$ multiplies by $1+\gamma /\sqrt{\nu }$ per step, reaching $t=\nu /\epsilon$ from $t_0$ takes

$$O\left(\sqrt{\nu }\log \frac{\nu }{t_0\epsilon }\right)$$

Newton iterations in total — the bound that makes interior-point methods polynomial. The $\sqrt{\nu }$ factor is sharp for the short-step scheme; long-step and predictor-corrector variants take $O(\nu )$ worst-case steps but far fewer in practice, and Mehrotra's predictor-corrector is the algorithm in production solvers. For LP and SDP, $\nu =n$, giving $O(\sqrt{n}\log (1/\epsilon ))$; for SOCP with $m$ Lorentz cones, $\nu =2m$, the structural reason SOCP solves faster than its SDP reformulation.

The universal barrier and the limits of tractability

Nesterov and Nemirovski proved that every closed convex domain in ${\mathbb{R}}^n$ admits a self-concordant barrier with parameter $\nu =O(n)$ — the universal barrier, built from the logarithm of the volume of the polar set, $F(x)=O(1)\cdot \log \mathrm{vol}((K-x{)}^{\circ })$ ^{[Nesterov & Nemirovski 1994]}. This is an existence theorem: it certifies that interior-point methods are in principle applicable to any convex program, but the universal barrier is rarely computable. Tractability is therefore not about existence of a barrier but about a barrier that is efficiently evaluable together with its gradient and Hessian. The orthant, Lorentz, and PSD barriers are the cases where the Newton system is cheap, which is why the LP/SOCP/SDP triad of 44.05.01 is the practical reach of the theory; the copositive and nonnegative-polynomial cones have universal barriers but no efficient ones, and optimizing over them is NP-hard. Güler later showed the canonical cone barriers are exactly the characteristic functions of the symmetric cones from the Koecher-Vinberg classification, tying the complexity parameter to Euclidean Jordan algebra rank.

Self-concordant calculus and the centering subproblem

The barrier method's correctness rests on a calculus of self-concordance ^{[Renegar 2001]}: sums of self-concordant functions are self-concordant (parameters add), composition with an affine map preserves self-concordance, and a self-concordant barrier composed with the linear objective yields a self-concordant centered objective whose Newton method enjoys the constant-free two-phase behavior of 44.03.03. Within the region of quadratic convergence ${\lambda }_F<\eta$ (an absolute constant near $(3-\sqrt{5})/2$) the pure Newton step recenters in a number of iterations bounded independently of dimension and conditioning, and outside it each damped step reduces the centered objective by an absolute constant. This is why each outer iteration of the barrier method needs only $O(1)$ (short-step) or $O(\log \log (1/\epsilon ))$ (per warm-started recentering) inner Newton steps, and it is the precise sense in which the Newton analysis of 44.03.03 is the inner loop of the interior-point method.

Primal-dual methods, neighborhoods, and superlinear local convergence

Production interior-point solvers are primal-dual: they apply Newton's root-finder of 43.02.03 to the perturbed KKT system $F(x,y,s)=(Ax-b,A^{\top }y+s-c,x\circ s-\mu e)=0$ in the joint variables, rather than minimizing the primal barrier alone ^{[Wright 1997]}. The surrogate duality gap $\eta =⟨x,s⟩$ is measured directly and $\mu$ is set to $\sigma \eta /\nu$ for a centering parameter $\sigma \in [0,1]$ ($\sigma =0$ a pure Newton/affine-scaling predictor step toward optimality, $\sigma =1$ a pure corrector step toward the central path). Wide neighborhoods ${\mathcal{N}}_{-\infty }(\gamma )=\{(x,s)>0:x_i{s}_i\ge \gamma \eta /n\}$ permit long steps; the narrow ${\mathcal{N}}_2$ neighborhood gives the cleanest $O(\sqrt{n}L)$ LP bound. Near the solution, under strict complementarity, the Mehrotra predictor-corrector achieves superlinear (indeed quadratic) local convergence of the gap, combining the global polynomial bound with the local speed of 44.03.03 — the empirical reason primal-dual methods converge in $20$-$50$ iterations almost independently of problem size.

Synthesis. The interior-point method is exactly the conic program of 44.05.01 solved by deforming it: a self-concordant barrier $F$ for the cone is added to the objective with weight $t$, and the central insight is that the minimizers trace the central path, a smooth homotopy whose perturbed-KKT defining system $x\circ s=\mu e$ interpolates between the analytic center ($\mu \to \infty$ gap) and the optimum (exact complementarity $⟨x,s⟩=0$). The foundational reason the method is polynomial is the marriage of two facts: the Euler identity pins the central-path gap to $\nu /t$, so $O(\log (1/\epsilon ))$ outer multiplications of $t$ suffice, while self-concordance of 44.03.03 makes each Newton centering step constant-free, and the short-step choice $\mu =1+\gamma /\sqrt{\nu }$ converts these into the $O(\sqrt{\nu }\log (1/\epsilon ))$ total. This is exactly the Newton-for-root-finding of 43.02.03 applied to the stationarity-and-complementarity map in the primal-dual reading, which generalises the barrier method's primal-only Newton centering and is dual to it through the slack $s=-\frac{1}{t}\nabla F$. Putting these together, the complexity parameter $\nu$ — $n$ for the orthant and PSD cones, $2$ per Lorentz cone — is the single number that generalises the dimension and governs both the gap odometer and the iteration count, the bridge is the self-concordant barrier, the object through which conic duality, the central-path homotopy, and the constant-free Newton analysis become one polynomial-time algorithm, and it appears again in the nonlinear-programming interior-point method of 44.04.04 and as the polynomial-time foil to the simplex method of 44.05.02.

Full proof set Master

Proposition 1 (the three canonical cone barriers are self-concordant with the stated parameters). The functions $-{\sum }_i\log x_i$ on ${\mathbb{R}}_{++}^n$, $-\log (t^2-\Vert u{\Vert }_2^2)$ on $\mathrm{int}{\mathcal{L}}^{n+1}$, and $-\log \det X$ on ${\mathbb{S}}_{++}^n$ are self-concordant barriers with parameters $n$, $2$, and $n$ respectively.

Proof. For the orthant, $-\log x$ on ${\mathbb{R}}_{++}$ is self-concordant with $|f^{\prime \prime \prime }|=2(f^{\prime \prime }{)}^{3/2}$ (Exercise 8); separable sums of self-concordant functions are self-concordant with parameters adding, giving $\nu =n$. Logarithmic homogeneity and the Euler identity (Exercise 1) confirm $\nu =n$. For $-\log \det X$, homogeneity and $⟨\nabla F,X⟩=-n$ are Exercise 7; self-concordance follows because along any line $X+\tau H$ with $X\succ 0$, putting $\tilde{H}=X^{-1/2}H{X}^{-1/2}$, $D^{2}F[H,H]=\mathrm{tr}({\tilde{H}}^2)={\sum }_i{\tilde{\lambda }}_i^2$ and $D^{3}F[H,H,H]=-2\mathrm{tr}({\tilde{H}}^3)=-2{\sum }_i{\tilde{\lambda }}_i^3$, and $|\sum {\tilde{\lambda }}_i^3|\le (\sum {\tilde{\lambda }}_i^2{)}^{3/2}$ by the power-mean inequality on the eigenvalues ${\tilde{\lambda }}_i$ of $\tilde{H}$, whence $|D^{3}F|\le 2(D^{2}F{)}^{3/2}$. For the Lorentz cone, write $g(u,t)=t^2-\Vert u{\Vert }_2^2$, a concave quadratic positive on the cone interior; $-\log g$ is self-concordant with parameter $2$ because $g$ is a nondegenerate concave quadratic and $-\log$ of such a quadratic has barrier parameter $2$ (the codimension-counting computation of the second/third derivatives of $-\log g$ yields the $2(\cdot {)}^{3/2}$ bound with $\nu =2$). Homogeneity $g(\tau u,\tau t)={\tau }^{2}g(u,t)$ gives $F(\tau \cdot )=F(\cdot )-2\log \tau$, so $\nu =2$. $\square$

Proposition 2 (existence and uniqueness of the central point). If the conic program is strictly primal feasible and $c^{\top }x$ is bounded below on the feasible set, then for every $t>0$ the centering problem $\min \{t{c}^{\top }x+F(x):Ax=b,x\in \mathrm{int}K\}$ has a unique minimizer $x^{\star }(t)$.

Proof. The centered objective $h_t(x)=t{c}^{\top }x+F(x)$ is strictly convex on $\mathrm{int}K\cap \{Ax=b\}$ because $F$ is strictly convex (its Hessian is positive definite, self-concordance requires $D^{2}F\succ 0$) and the linear term adds nothing to the Hessian. A strictly convex function has at most one minimizer. For existence, $F$ is a barrier, so $h_t(x)\to +\infty$ as $x\to \partial K$; combined with boundedness below of $c^{\top }x$ and the closedness of the feasible affine slice, $h_t$ is a closed strictly convex function with bounded sublevel sets on the strictly feasible set (the barrier forces sublevel sets to stay in a compact interior subset), so a minimizer exists. Uniqueness from strict convexity completes the claim. $\square$

Proposition 3 (central-path gap, restated and proved in full). Along the central path, $⟨x^{\star }(t),s^{\star }(t)⟩=\nu /t$ with $s^{\star }(t)=-\frac{1}{t}\nabla F(x^{\star }(t))\in \mathrm{int}{K}^{\ast }$.

Proof. This is the Key theorem; the two ingredients are the stationarity condition $\nabla F(x)=-t{s}^{\star }$ from the Lagrangian of the centering problem (Proposition 2 supplies the minimizer at which it holds) and the Euler identity $⟨\nabla F(x),x⟩=-\nu$ from logarithmic homogeneity. That $s^{\star }\in \mathrm{int}{K}^{\ast }$ uses the fact that for a logarithmically-homogeneous self-concordant barrier the map $x\mapsto -\nabla F(x)$ sends $\mathrm{int}K$ into $\mathrm{int}{K}^{\ast }$, which holds because $-\nabla F(x)$ is the gradient of the Legendre conjugate barrier $F^{\ast }$ on $K^{\ast }$ evaluated at the dual central point, and $F^{\ast }$ is itself a $\nu$-self-concordant barrier for $K^{\ast }$. Pairing $x$ with $s^{\star }=-\frac{1}{t}\nabla F(x)$ gives $⟨x,s^{\star }⟩=-\frac{1}{t}⟨x,\nabla F(x)⟩=\nu /t$. $\square$

Proposition 4 (barrier-method outer-iteration count). With increase factor $\mu >1$, starting at $t_0$, the barrier method reaches a guaranteed duality gap $\le \epsilon$ after $\lceil {\log }_{\mu }\left(\frac{\nu }{t_0\epsilon }\right)\rceil$ outer iterations.

Proof. After $k$ outer iterations the barrier parameter is $t_k=t_0{\mu }^k$, and by Proposition 3 the duality gap at the corresponding central point is $\nu /t_k=\nu /(t_0{\mu }^k)$. The stopping condition $\nu /(t_0{\mu }^k)\le \epsilon$ rearranges to ${\mu }^k\ge \nu /(t_0\epsilon )$, i.e. $k\ge {\log }_{\mu }(\nu /(t_0\epsilon ))$. The least such integer is the stated ceiling. The total Newton-step count multiplies this by the per-outer-iteration inner-step count, which the self-concordant analysis of 44.03.03 bounds by a constant depending on $\mu$ and the neighborhood, giving the $O(\sqrt{\nu }\log (1/\epsilon ))$ total in the short-step regime $\mu =1+\gamma /\sqrt{\nu }$. $\square$

Proposition 5 (the primal-dual Newton system is nonsingular near the central path). At a strictly feasible primal-dual point $(x,y,s)$ with $(x,s)>0$ for the LP perturbed-KKT system, the Newton Jacobian $\left[\begin{array}{ccc}A& 0& 0\\ 0& A^{\top }& I\\ S& 0& X\end{array}\right]$ is nonsingular when $A$ has full row rank.

Proof. Suppose the Jacobian annihilates $(\Delta x,\Delta y,\Delta s)$: then $A\Delta x=0$, $A^{\top }\Delta y+\Delta s=0$, and $S\Delta x+X\Delta s=0$. From the third equation $\Delta s=-X^{-1}S\Delta x$ (using $X\succ 0$). Substitute into the inner product of $\Delta x$ with the second equation: $\Delta x^{\top }{A}^{\top }\Delta y+\Delta x^{\top }\Delta s=(A\Delta x{)}^{\top }\Delta y+\Delta x^{\top }\Delta s=0+\Delta x^{\top }\Delta s$, and $\Delta x^{\top }\Delta s=-\Delta x^{\top }{X}^{-1}S\Delta x=-{\sum }_i\frac{s_i}{x_i}\Delta x_i^2\le 0$ with equality only if $\Delta x=0$ (since $s_i,x_i>0$). But the same quantity equals $\Delta x^{\top }\Delta s$, and from $A^{\top }\Delta y+\Delta s=0$ we get $\Delta x^{\top }\Delta s=-\Delta x^{\top }{A}^{\top }\Delta y=-(A\Delta x{)}^{\top }\Delta y=0$. Hence ${\sum }_i(s_i/x_i)\Delta x_i^2=0$, forcing $\Delta x=0$, then $\Delta s=-X^{-1}S\Delta x=0$, and finally $A^{\top }\Delta y=0$ with $A$ full row rank gives $\Delta y=0$. The kernel contains only the zero vector, so the Jacobian is nonsingular. $\square$

Connections Master

• Conic optimization over LP, SOCP, and SDP cones 44.05.01 is the problem class this unit solves: the generalized inequalities, the dual cone $K^{\ast }$, conic weak/strong duality, and the self-dual orthant/Lorentz/PSD triad are exactly the structure the self-concordant barriers $-\sum \log x_i$, $-\log (t^2-\Vert u{\Vert }^2)$, $-\log \det X$ are built for, and the central-path duality gap $\nu /t$ is the conic complementarity $⟨x,s⟩=0$ of that unit relaxed by the barrier parameter. The conic Slater condition there is the strict-feasibility hypothesis that makes the central path and the dual central point exist here.

• Newton's method for optimization 44.03.03 is the inner engine: each centering step is the equality-constrained Newton step on $t{c}^{\top }x+F(x)$ over $Ax=b$, its KKT block system is solved per inner iteration, and the self-concordance inequality $|f^{\prime \prime \prime }|\le 2(f^{\prime \prime }{)}^{3/2}$ introduced there is precisely the property that makes the centering Newton method constant-free, which is what converts the $\nu /t$ gap odometer into a dimension- and conditioning-independent iteration count. The affine invariance and the Newton decrement of that unit are the metric in which the short-step neighborhood is measured.

• Lagrangian duality and Slater's condition 44.02.01 supplies the dual certificate machinery: the central point's stationarity condition $\nabla F(x)=-t{s}^{\star }$ is the Lagrangian optimality of the centering problem, weak duality $b^{\top }{y}^{\star }\le p^{\star }\le c^{\top }{x}^{\star }(t)$ is what turns the pairing $⟨x,s⟩=\nu /t$ into the accuracy guarantee, and the strict-feasibility Slater hypothesis is what the barrier requires to keep iterates in $\mathrm{int}K$.

• The interior-point method is the polynomial-time alternative to the simplex method 44.05.02, cutting through the relative interior of the polyhedron along the central path rather than walking vertices, sidestepping the Klee-Minty exponential worst case; and it is the conic specialization of the nonlinear-programming interior-point method 44.04.04, which replaces the linear conic objective and cone barrier with a barrier on nonlinear inequality constraints and the same primal-dual perturbed-KKT Newton step. The primal-dual reading applies the root-finding Newton method 43.02.03 to the perturbed KKT map.

Historical & philosophical context Master

The barrier idea predates the polynomial-time theory: the logarithmic and inverse barrier methods were developed for nonlinear programming by Anthony Fiacco and Garth McCormick in the 1960s under the name SUMT (sequential unconstrained minimization technique), but fell out of favor because the centering subproblems became badly conditioned as the barrier weakened. The modern era opened with Narendra Karmarkar's 1984 projective-scaling algorithm for linear programming ^{[Karmarkar 1984]}, the first interior-point method proved polynomial and competitive in practice, following Leonid Khachiyan's 1979 ellipsoid method that settled LP's membership in P without practical speed.

The structural explanation of why interior-point methods are polynomial is due to Yurii Nesterov and Arkadi Nemirovski, whose 1994 monograph ^{[Nesterov & Nemirovski 1994]} isolated self-concordance as the affine-invariant property of the barrier, defined the complexity parameter $\nu$, proved the $O(\sqrt{\nu }\log (1/\epsilon ))$ path-following bound, and established the universal-barrier existence theorem extending the method to all of convex programming. The primal-dual viewpoint that dominates production solvers was synthesized by Stephen Wright ^{[Wright 1997]} and the pedagogical conic treatment by James Renegar ^{[Renegar 2001]} and by Boyd and Vandenberghe ^{[Boyd & Vandenberghe 2004]}; Sanjay Mehrotra's 1992 predictor-corrector algorithm remains the default heuristic in solvers, and Osman Güler connected the canonical barriers to the Euclidean Jordan algebras of symmetric cones.

Bibliography Master

@book{boydvandenberghe2004ipm,
  author    = {Boyd, Stephen and Vandenberghe, Lieven},
  title     = {Convex Optimization},
  publisher = {Cambridge University Press},
  year      = {2004}
}

@book{nesterovnemirovski1994,
  author    = {Nesterov, Yurii and Nemirovski, Arkadi},
  title     = {Interior-Point Polynomial Algorithms in Convex Programming},
  series    = {SIAM Studies in Applied Mathematics},
  volume    = {13},
  publisher = {SIAM},
  year      = {1994}
}

@book{nocedalwright2006ipm,
  author    = {Nocedal, Jorge and Wright, Stephen J.},
  title     = {Numerical Optimization},
  edition   = {2},
  series    = {Springer Series in Operations Research and Financial Engineering},
  publisher = {Springer},
  year      = {2006}
}

@book{renegar2001,
  author    = {Renegar, James},
  title     = {A Mathematical View of Interior-Point Methods in Convex Optimization},
  series    = {MPS-SIAM Series on Optimization},
  publisher = {SIAM},
  year      = {2001}
}

@article{karmarkar1984,
  author  = {Karmarkar, Narendra},
  title   = {A New Polynomial-Time Algorithm for Linear Programming},
  journal = {Combinatorica},
  volume  = {4},
  number  = {4},
  pages   = {373--395},
  year    = {1984}
}

@book{wright1997primaldual,
  author    = {Wright, Stephen J.},
  title     = {Primal-Dual Interior-Point Methods},
  publisher = {SIAM},
  year      = {1997}
}

@book{fiaccomccormick1968,
  author    = {Fiacco, Anthony V. and McCormick, Garth P.},
  title     = {Nonlinear Programming: Sequential Unconstrained Minimization Techniques},
  publisher = {John Wiley \& Sons},
  year      = {1968}
}

@article{mehrotra1992,
  author  = {Mehrotra, Sanjay},
  title   = {On the Implementation of a Primal-Dual Interior Point Method},
  journal = {SIAM Journal on Optimization},
  volume  = {2},
  number  = {4},
  pages   = {575--601},
  year    = {1992}
}