Interior-Point Methods for Nonlinear Programming

Intuition Beginner

A constrained problem has walls — the inequality rules you must not cross. One way to handle them is to march right up to the walls and figure out which ones you press against, the active-set idea. Interior-point methods do the opposite: they refuse to touch any wall at all, staying strictly inside the allowed room, and let a slowly weakening force push them toward the corner where the answer lives.

The force is a barrier. Imagine adding to the cost a term that blows up to infinity as you approach any wall, like a repelling fog that gets thicker the closer you get. With the fog turned up high, the cheapest point sits comfortably in the middle of the room, far from every wall. Now turn the fog down a little. The cheapest point drifts toward the walls, because the true cost matters more and the fog matters less. Keep turning the fog down. The point traces a smooth curve through the room, heading straight for the constrained optimum, which it reaches only in the limit as the fog vanishes.

That smooth curve is the central path, and the fog strength is one number, the barrier parameter. The whole method is: pick a fog level, find the cheapest foggy point, lower the fog, repeat. Each foggy subproblem is smooth and has no walls to bump into, so an ordinary downhill solver handles it. Lowering the fog in steps is a homotopy — a continuous deformation from an easy problem you can solve to the hard problem you want, with the answer carried along the path.

Visual Beginner

Picture the allowed room as the inside of a triangle. The true best point sits in a corner where two walls meet. With strong fog the cheapest point sits near the middle; as the fog weakens, that point slides along a smooth curve toward the corner.

        wall A                         wall B
          \                            /
           \      central path        /
            \    *  (mu large)       /
             \    \                  /
              \    \                /
               \    *  (mu medium) /
                \    \            /
                 \    \          /
                  \    *        /     <- (mu small)
                   \    \      /
                    \    o    /        <- x* (mu -> 0): the corner,
                     \   |   /            pressed against both walls
                      \  |  /
                       \ | /
                  ------ V ------  wall C (floor)

   strong fog  -> cheapest point sits deep inside, far from walls
   weaken fog  -> point slides toward the constrained optimum
   fog -> 0    -> point reaches x*, the true answer, in the limit

fog (barrier) level	where the cheapest point sits	distance to walls
very strong	deep in the interior	large
medium	drifting toward a wall	shrinking
weak	close to the optimal corner	small
zero (limit)	at the constrained optimum	touching

The takeaway: interior-point methods never walk along the walls. They follow a smooth interior curve, lowering one barrier number until the curve arrives at the answer.

Worked example Beginner

Minimize the cost $f(x)=x$ subject to the single rule $x\ge 1$. The answer is plainly $x=1$, pressed against the wall, but let us watch the barrier method find it so the central path becomes concrete.

Step 1. Add the fog. Replace the rule by a barrier that blows up as $x$ nears $1$. The foggy cost is $x-\mu \log (x-1)$, where $\mu >0$ is the fog strength and $\log (x-1)$ rushes to minus infinity as $x\to 1$, so subtracting it builds a wall of cost near $x=1$.

Step 2. Find the cheapest foggy point. The foggy cost is smallest where its slope is zero. The slope is $1-\mu /(x-1)$. Setting it to zero gives $\mu /(x-1)=1$, so $x-1=\mu$, that is $x=1+\mu$.

Step 3. Read off the central path. For each fog level $\mu$ the cheapest point is $x(\mu )=1+\mu$. This is the central path: a straight line in this simple case, sitting a distance $\mu$ inside the wall.

Step 4. Lower the fog. Take $\mu =1$: point at $x=2$. Take $\mu =0.1$: point at $x=1.1$. Take $\mu =0.001$: point at $x=1.001$. As $\mu$ shrinks toward zero, $x(\mu )=1+\mu$ marches down to $x=1$.

What this tells us. The barrier method never sets $x=1$ directly; it keeps $x$ strictly bigger than $1$ at every stage and lets the limit $\mu \to 0$ deliver the boundary answer. The path $x(\mu )=1+\mu$ shows the central path explicitly, and the distance to the wall is exactly the fog strength $\mu$ — the hallmark of an interior-point method.

Check your understanding Beginner

Formal definition Intermediate+

Consider the nonlinear program over $x\in {\mathbb{R}}^n$,

$$\underset{x}{\min }f(x)\text{subject to}{c}_i(x)=0(i\in \mathcal{E}),c_i(x)\ge 0(i\in \mathcal{I}),$$

with $f,c_i$ twice continuously differentiable. Introduce a slack vector $s\in {\mathbb{R}}^{|\mathcal{I}|}$ and replace each inequality by $c_i(x)-s_i=0$, $s_i\ge 0$, so the only inequalities left are the simple bounds $s\ge 0$.

Definition (logarithmic barrier and barrier problem). For a barrier parameter $\mu >0$ the barrier problem is

$$\underset{x,s}{\min }f(x)-\mu \sum _{i\in \mathcal{I}}\log s_i\text{subject to}{c}_i(x)=0(i\in \mathcal{E}),c_i(x)-s_i=0(i\in \mathcal{I}),s>0,$$

where $-\mu {\sum }_i\log s_i$ is the logarithmic barrier, finite on $s>0$ and tending to $+\infty$ as any $s_i\downarrow 0$. The barrier confines minimizers to the strict interior of the inequality set, and the equalities are kept by Lagrange multipliers, exactly as in the constrained-Newton setting of 44.03.03.

Definition (perturbed KKT system and the central path). Let $\nu$ be the multipliers for the equalities $c_i(x)=0$ ($i\in \mathcal{E}$) and $\lambda$ the multipliers for $c_i(x)-s_i=0$ ($i\in \mathcal{I}$). Writing the KKT conditions of the barrier problem 44.02.02 and eliminating the barrier gradient $\mu /s_i$ in favor of ${\lambda }_i$ gives the perturbed KKT system

$$\nabla f(x)-A_{\mathcal{E}}(x{)}^{\top }\nu -A_{\mathcal{I}}(x{)}^{\top }\lambda =0,S\Lambda e=\mu e,c_{\mathcal{E}}(x)=0,c_{\mathcal{I}}(x)-s=0,$$

with $(s,\lambda )>0$, where $A_{\mathcal{E}},A_{\mathcal{I}}$ are the constraint Jacobians, $S=\mathrm{diag}(s)$, $\Lambda =\mathrm{diag}(\lambda )$, and $e=(1,\dots ,1{)}^{\top }$. The central path is the trajectory $\{(x(\mu ),s(\mu ),\lambda (\mu ),\nu (\mu )):\mu >0\}$ of solutions, the only departure from the genuine KKT conditions being the relaxed perturbed complementarity $s_i{\lambda }_i=\mu$ in place of $s_i{\lambda }_i=0$. As $\mu \to 0$ the path approaches a KKT point. The new symbols $\mu$ (barrier parameter), $S=\mathrm{diag}(s)$, $\Lambda =\mathrm{diag}(\lambda )$, $e$ (all-ones vector), and the duality measure ${\mu }_k=s_k^{\top }{\lambda }_k/|\mathcal{I}|$ are recorded in _meta/NOTATION.md.

Definition (primal-dual Newton step). Collecting $w=(x,s,\nu ,\lambda )$, the perturbed KKT system is $F_{\mu }(w)=0$. One Newton step solves the linearized system $F_{\mu }^{\prime }(w)\Delta w=-F_{\mu }(w)$, the primal-dual system

$$\left[\begin{array}{cccc}{\nabla }_{xx}^{2}L& 0& -A_{\mathcal{E}}^{\top }& -A_{\mathcal{I}}^{\top }\\ 0& \Lambda & 0& S\\ A_{\mathcal{E}}& 0& 0& 0\\ A_{\mathcal{I}}& -I& 0& 0\end{array}\right]\left[\begin{array}{c}\Delta x\\ \Delta s\\ \Delta \nu \\ \Delta \lambda \end{array}\right]=-\left[\begin{array}{c}\nabla f-A_{\mathcal{E}}^{\top }\nu -A_{\mathcal{I}}^{\top }\lambda \\ S\Lambda e-\mu e\\ c_{\mathcal{E}}\\ c_{\mathcal{I}}-s\end{array}\right],$$

with ${\nabla }_{xx}^{2}L={\nabla }^{2}f-{\sum }_i{\nu }_i{\nabla }^2{c}_i-{\sum }_i{\lambda }_i{\nabla }^2{c}_i$ the Lagrangian Hessian. Eliminating $\Delta s$ and $\Delta \lambda$ condenses this to a symmetric saddle-point system in $(\Delta x,\Delta \nu )$ of the same form as the constrained-Newton KKT matrix of 44.03.03.

Definition (fraction-to-the-boundary rule). Given a step $(\Delta s,\Delta \lambda )$, the fraction-to-the-boundary rule with parameter $\tau \in (0,1)$ (typically $\tau =0.995$) sets the step length

$$\alpha =\max \{\alpha \in (0,1]:s+\alpha \Delta s\ge (1-\tau )s,\lambda +\alpha \Delta \lambda \ge (1-\tau )\lambda \},$$

keeping $(s,\lambda )$ strictly positive and bounded away from the boundary by a fixed fraction, so the iterates remain interior.

Counterexamples to common slips

• The barrier minimizer is not the constrained minimizer for any fixed $\mu >0$. The central-path point $x(\mu )$ sits strictly interior; it equals the boundary optimum only in the limit $\mu \to 0$. Stopping at a fixed $\mu$ and reporting $x(\mu )$ leaves an $O(\mu )$ error in the objective.
• Perturbed complementarity is $s_i{\lambda }_i=\mu$, not $s_i{\lambda }_i\approx 0$. Driving every product to a common positive value $\mu$ is what keeps the iterate centered; letting the products spread (some near zero, some large) pushes the iterate toward a corner of the boundary where the Newton step degrades, the role the neighborhood/centering condition guards against.
• The primal barrier Hessian is ill-conditioned; the primal-dual system is not. The pure primal barrier function has Hessian ${\nabla }^{2}f+\mu A^{\top }{S}^{-2}A$, whose $S^{-2}=O({\mu }^{-2})$ blows up as $\mu \to 0$. The primal-dual system treats $\lambda$ as an independent variable and avoids forming $S^{-2}$, which is why primal-dual methods are numerically preferred over the original SUMT barrier method.

Key theorem with proof Intermediate+

The signature result is the existence, uniqueness, and limiting behavior of the central path for a convex program: under strict feasibility the perturbed KKT system has a unique solution for each $\mu >0$, these solutions form a smooth trajectory, and as $\mu \to 0$ they converge to a KKT point of the original program. This is what licenses the homotopy: a well-defined curve to follow, ending at the answer.

Theorem (central path: existence, uniqueness, limit — convex case). Let $f$ and $-c_i$ ($i\in \mathcal{I}$) be convex and twice differentiable, the equalities $c_i(x)=a_i^{\top }x-b_i$ affine, the feasible set have nonempty strict interior (Slater), and the optimal set be nonempty and bounded. Then for each $\mu >0$ the barrier problem has a unique minimizer $(x(\mu ),s(\mu ))$ with multipliers $(\lambda (\mu ),\nu (\mu ))$ solving the perturbed KKT system with $s_i(\mu ){\lambda }_i(\mu )=\mu$; the map $\mu \mapsto (x(\mu ),s(\mu ),\lambda (\mu ),\nu (\mu ))$ is continuously differentiable on $(0,\infty )$; and as $\mu \to 0$ every limit point of $x(\mu )$ is a minimizer of the original program, with the objective gap bounded by $f(x(\mu ))-p^{\star }\le |\mathcal{I}|\mu$.

Proof. Fix $\mu >0$. On the strict interior the barrier objective ${\varphi }_{\mu }(x,s)=f(x)-\mu {\sum }_i\log s_i$ restricted to the affine feasible manifold $\{c_{\mathcal{E}}(x)=0,c_i(x)=s_i\}$ is strictly convex in $(x,s)$: $f$ is convex, each $-\log s_i$ is strictly convex on $s_i>0$, and the constraints are affine in the convex case, so the restriction is a strictly convex function on a convex set. Slater gives a strictly interior feasible point, and the barrier $\to +\infty$ on the boundary of the slack orthant forces the sublevel sets to be compact (boundedness of the optimal set rules out escape to infinity along the recession directions). A strictly convex function with compact sublevel sets on a convex set attains a unique minimizer, giving $(x(\mu ),s(\mu ))$; its KKT conditions 44.02.02 are stationarity $\nabla f-A_{\mathcal{E}}^{\top }\nu -A_{\mathcal{I}}^{\top }\lambda =0$ together with the barrier-gradient identity $\mu /s_i={\lambda }_i$, i.e. $s_i{\lambda }_i=\mu$, and primal feasibility — the perturbed KKT system, with ${\lambda }_i=\mu /s_i>0$ automatically.

Smoothness: the perturbed-KKT map $F_{\mu }(w)=0$ has Jacobian the primal-dual matrix, which under Slater and convexity is nonsingular on the path (its condensed form is the constrained-Newton KKT matrix with the positive-definite-on-the-null-space inertia condition of 44.03.03, here guaranteed by ${\nabla }^{2}f⪰0$ plus the strictly positive diagonal $S^{-1}\Lambda \succ 0$). The implicit function theorem applied to $F_{\mu }(w)=0$, treating $\mu$ as the parameter, yields a continuously differentiable solution map $\mu \mapsto w(\mu )$.

Limit and gap: along the path, weak duality gives $f(x(\mu ))-p^{\star }\le f(x(\mu ))-g(\lambda (\mu ),\nu (\mu ))$, the duality gap, where $g$ is the Lagrangian dual of 44.02.02. For the barrier solution the gap equals ${\sum }_i{s}_i(\mu ){\lambda }_i(\mu )={\sum }_i\mu =|\mathcal{I}|\mu$ (each complementarity product is exactly $\mu$, and the equality terms vanish on the affine manifold). Hence $f(x(\mu ))-p^{\star }\le |\mathcal{I}|\mu \to 0$. The path lies in a compact sublevel set (boundedness of the optimal set plus the gap bound), so it has limit points, and any limit point satisfies the unperturbed KKT system ($s_i{\lambda }_i=\mu \to 0$ recovers complementary slackness, the other equations pass to the limit), hence is a minimizer by convex sufficiency of 44.02.02. $\square$

Bridge. This central-path theorem builds toward the path-following algorithm — take one Newton step toward $(x(\mu ),s,\lambda ,\nu )$, decrease $\mu$, repeat — and it appears again in the conic and semidefinite interior-point methods 44.05.04, where the same $S\Lambda e=\mu e$ relaxation reappears with a self-concordant barrier delivering polynomial complexity. This is exactly the homotopy reading of the KKT conditions of 44.02.02: the perturbation $\mu$ deforms complementary slackness $s_i{\lambda }_i=0$ into the smooth $s_i{\lambda }_i=\mu$, turning the combinatorial active-set question into a continuous curve, so that following the curve to $\mu =0$ is following a deformation of an easy strictly-interior problem into the hard boundary problem. The foundational reason the path is well defined is strict convexity of the barrier on the feasible manifold under Slater, which makes each barrier subproblem uniquely solvable, and nonsingularity of the primal-dual Jacobian, which is the constrained-Newton inertia condition of 44.03.03 applied along the path. Putting these together, the interior-point method generalises the unconstrained Newton iteration of 44.03.03 to inequality constraints by replacing the active-set decision with a barrier, and is dual to the active-set approach: where active-set methods of 44.04.01 guess which constraints are tight and walk the boundary, the interior-point method keeps all inequalities strictly slack and lets $\mu \to 0$ discover the active set in the limit, the two strategies meeting at the same KKT point from opposite sides of the feasible region.

Exercises Intermediate+

Advanced results Master

The barrier, the perturbed KKT system, and the central path

The slacked nonlinear program $\min f(x)$ s.t. $c_{\mathcal{E}}(x)=0$, $c_{\mathcal{I}}(x)-s=0$, $s\ge 0$ has barrier subproblem $\min f(x)-\mu {\sum }_i\log s_i$ on the equality manifold, and its KKT conditions are the perturbed KKT system with $s_i{\lambda }_i=\mu$ ^{[Nocedal & Wright §19.1]}. The single structural fact is that the barrier deforms complementary slackness: the disjunction "$s_i=0$ or ${\lambda }_i=0$" of 44.02.02 becomes the smooth surface $s_i{\lambda }_i=\mu$, and the central path is the set of its solutions over $\mu >0$. The path is the trajectory of analytic centers of the feasible region weighted by the objective, and its tangent at $\mu$ is the primal-dual Newton direction toward decreasing $\mu$. The original sequential-unconstrained-minimization (SUMT) view of Fiacco and McCormick ^{[Fiacco & McCormick 1990]} solved the barrier subproblem to high accuracy at each $\mu$; the modern primal-dual view takes a single Newton step per $\mu$, following the path rather than landing on it, which is both faster and better-conditioned.

The primal-dual Newton step and its reductions

Newton's method on $F_{\mu }(w)=0$ gives the unsymmetric primal-dual system, symmetrized by scaling the complementarity row to $S\Delta \lambda +\Lambda \Delta s=-(S\Lambda e-\mu e)$ ^{[Forsgren-Gill-Wright 2002]}. Two reductions are standard. The augmented (symmetric indefinite) form eliminates $\Delta s,\Delta \lambda$ to the $(\Delta x,\Delta \nu )$ saddle-point system \begin{psmallmatrix} W & A_{\mathcal{E}}^\top \\ A_{\mathcal{E}} & 0\end{psmallmatrix} with $W={\nabla }_{xx}^{2}L+A_{\mathcal{I}}^{\top }{S}^{-1}\Lambda A_{\mathcal{I}}$, solved by a symmetric-indefinite $LD{L}^{\top }$ factorization whose inertia is monitored. The condensed (normal-equations) form further eliminates $\Delta x$ when $W\succ 0$, producing a smaller positive-definite system in $\Delta \nu$ at the cost of squaring the conditioning. The inertia of the augmented matrix is exactly the inertia condition of the constrained-Newton KKT solve of 44.03.03: correct inertia $(n,|\mathcal{E}|,0)$ holds when $A_{\mathcal{E}}$ has full row rank and $W$ is positive definite on $\ker A_{\mathcal{E}}$. The fraction-to-the-boundary step keeps $(s,\lambda )>0$, and a centering parameter $\sigma \in [0,1]$ targets $\sigma {\mu }_k$ (with ${\mu }_k=s_k^{\top }{\lambda }_k/|\mathcal{I}|$ the duality measure) rather than $0$, balancing the predictor pull toward optimality against the corrector pull toward the path's center — the Mehrotra predictor-corrector heuristic in its nonlinear form.

Nonconvexity, regularization, and globalization

For convex programs every central-path point is well defined and the path converges to the global optimum; for nonconvex programs neither holds without intervention. The Lagrangian Hessian ${\nabla }_{xx}^{2}L$ can be indefinite, so $W$ may fail positive-definiteness on $\ker A_{\mathcal{E}}$ and the augmented matrix loses the correct inertia. Hessian regularization adds $\delta I$ to $W$ (inertia correction), increasing $\delta$ until the $LD{L}^{\top }$ factorization reports inertia $(n,|\mathcal{E}|,0)$, the modified-Cholesky/eigenvalue-flooring device of 44.03.03 applied to the primal-dual matrix; a $(2,2)$-block regularization $-\gamma I$ handles rank-deficient $A_{\mathcal{E}}$. Global convergence from arbitrary strictly-interior starts requires a globalization: a line search on a barrier merit function (the barrier objective augmented by a constraint-violation penalty, e.g. an ${\ell }_1$ or augmented-Lagrangian penalty), or a trust-region/filter approach that accepts a step if it improves either the objective or the constraint violation without a penalty parameter (the Fletcher-Leyffer filter, used in IPOPT) ^{[Nocedal & Wright §19.5]}. The interaction of the barrier with globalization is delicate — the Maratos effect and the loss of the fraction-to-the-boundary step near the boundary motivate second-order corrections and the filter.

Local convergence, comparison with SQP, and the conic specialization

Under LICQ, strict complementarity, and the second-order sufficient condition of 44.02.02, the primal-dual Newton iteration with $\mu$ driven to zero superlinearly attains superlinear (and, with the right $\mu$-update, quadratic) local convergence ^{[Nocedal & Wright §19.7]}, because strict complementarity keeps the active ${\lambda }_i$ bounded away from $0$, making the primal-dual matrix uniformly well-conditioned in the limit and the Newton step asymptotically exact. The comparison with sequential quadratic programming 44.04.03 is structural: SQP solves a QP subproblem with an explicit active-set determination at each outer iteration and converges in few, expensive iterations with excellent warm-starting; interior-point methods replace the active-set combinatorics by the barrier homotopy, keeping all inequalities strictly inactive and converging in more, cheaper iterations that scale better with the number of constraints but warm-start poorly. The convex specialization is the cleanest case: for conic and semidefinite programs 44.05.04 the barrier is self-concordant in the sense of Nesterov and Nemirovski, and the same $S\Lambda e=\mu e$ relaxation yields a polynomial-iteration complexity bound $O(\sqrt{\vartheta }\log (1/ϵ))$ in the barrier parameter $\vartheta$ — a guarantee the general nonlinear method forgoes, since a general barrier is not self-concordant and the path need not stay short.

Synthesis. The interior-point method is exactly the homotopy reading of the KKT conditions of 44.02.02: the barrier parameter $\mu$ deforms complementary slackness $s_i{\lambda }_i=0$ into the smooth surface $s_i{\lambda }_i=\mu$, and the central insight is that following the resulting central path from a strictly-interior start to $\mu =0$ converts the combinatorial active-set question into the continuous problem of tracking a smooth curve with Newton's method. The foundational reason the curve is well defined for convex programs is strict convexity of the barrier on the feasible manifold under Slater, which makes each subproblem uniquely solvable, together with nonsingularity of the primal-dual Jacobian, which is exactly the constrained-Newton inertia condition of 44.03.03 applied along the path; nonconvexity attacks precisely this inertia, and Hessian regularization restores it. Putting these together, the method generalises the unconstrained Newton iteration of 44.03.03 to inequality constraints by replacing the active-set decision with a barrier and an independent dual variable that cures the $O({\mu }^{-2})$ ill-conditioning of the pure barrier, and is dual to the active-set strategy of 44.04.01, reaching the same KKT point from the strict interior rather than along the boundary. This is exactly the engine that appears again in conic and semidefinite interior-point methods 44.05.04, where the self-concordant barrier upgrades the same perturbed-complementarity homotopy to a polynomial-iteration complexity guarantee, and in the comparison with SQP 44.04.03, the two dominant nonlinear-programming paradigms that linearize the same KKT system from opposite sides of the feasible region.

Full proof set Master

Proposition 1 (perturbed KKT = barrier-problem KKT). The KKT conditions 44.02.02 of the barrier problem $\min f(x)-\mu {\sum }_i\log s_i$ s.t. $c_{\mathcal{E}}(x)=0$, $c_i(x)-s_i=0$, $s>0$, are precisely the perturbed KKT system with $s_i{\lambda }_i=\mu$.

Proof. Form the Lagrangian $L_{\mu }=f(x)-\mu {\sum }_i\log s_i-{\nu }^{\top }{c}_{\mathcal{E}}(x)-{\lambda }^{\top }(c_{\mathcal{I}}(x)-s)$ (the bound $s>0$ is inactive at an interior minimizer, so its multiplier is zero). Stationarity in $x$: $\nabla f-A_{\mathcal{E}}^{\top }\nu -A_{\mathcal{I}}^{\top }\lambda =0$. Stationarity in $s_i$: $-\mu /s_i+{\lambda }_i=0$, i.e. ${\lambda }_i=\mu /s_i$, equivalently $s_i{\lambda }_i=\mu$. Primal feasibility is $c_{\mathcal{E}}(x)=0$ and $c_i(x)=s_i$. Since $s_i>0$, the stationarity-in-$s$ relation forces ${\lambda }_i=\mu /s_i>0$. These are exactly the four blocks of the perturbed KKT system, with $\lambda >0$ automatic. $\square$

Proposition 2 (existence and uniqueness of the central-path point, convex case). Under the convexity, affine-equality, Slater, and bounded-optimal-set hypotheses, the barrier problem has a unique minimizer for each $\mu >0$.

Proof. Restrict the barrier objective ${\varphi }_{\mu }(x,s)=f(x)-\mu {\sum }_i\log s_i$ to the convex feasible manifold $\mathcal{M}=\{(x,s):c_{\mathcal{E}}(x)=0,c_i(x)=s_i,s>0\}$, convex because the $c_{\mathcal{E}}$ are affine and $c_i(x)-s_i$ is concave-minus-linear with $-c_i$ convex (the inequality $c_i\ge 0$ convex case), so the manifold is the intersection of affine sets with the convex graph constraint; in the standard convex NLP it is convex. On $\mathcal{M}$, $f$ is convex and $-\mu \log s_i$ is strictly convex in $s_i$, so ${\varphi }_{\mu }$ is strictly convex in $s$ and convex in $x$; combined with the requirement that distinct feasible points differ in $s$ whenever they differ in the active $c_i$, the restriction is strictly convex on $\mathcal{M}$ (strict convexity in the $\log$ arguments). Slater provides a point of $\mathcal{M}$ with $s>0$, so $\mathcal{M}\ne \varnothing$. As any $s_i\downarrow 0$, ${\varphi }_{\mu }\to +\infty$; boundedness of the optimal set rules out a recession direction along which ${\varphi }_{\mu }$ stays bounded, so every sublevel set $\{{\varphi }_{\mu }\le \beta \}\cap \mathcal{M}$ is compact. A strictly convex lower-semicontinuous function with a nonempty compact sublevel set on a convex set attains its infimum at a unique point. $\square$

Proposition 3 (smoothness of the central path). Under the hypotheses of Proposition 2, the solution map $\mu \mapsto w(\mu )=(x(\mu ),s(\mu ),\nu (\mu ),\lambda (\mu ))$ is continuously differentiable on $(0,\infty )$.

Proof. The path solves $F_{\mu }(w)=0$ with $F_{\mu }$ smooth jointly in $(w,\mu )$. Its Jacobian $F_{\mu }^{\prime }(w)$ is the primal-dual matrix. Its condensed form is \begin{psmallmatrix} W & A_{\mathcal{E}}^\top \\ A_{\mathcal{E}} & 0\end{psmallmatrix} with $W={\nabla }_{xx}^{2}L+A_{\mathcal{I}}^{\top }{S}^{-1}\Lambda A_{\mathcal{I}}$. On the path $S^{-1}\Lambda \succ 0$ (since $s,\lambda >0$) and ${\nabla }_{xx}^{2}L⪰0$ in the convex case, so $W⪰{\nabla }^{2}f⪰0$ and, restricted to $\ker A_{\mathcal{E}}$, the strictly positive term $A_{\mathcal{I}}^{\top }{S}^{-1}\Lambda A_{\mathcal{I}}$ plus convexity gives $Z^{\top }WZ\succ 0$ wherever the active inequality gradients span enough directions; with $A_{\mathcal{E}}$ full row rank the inertia condition of 44.03.03 holds and the matrix is nonsingular. (Where $Z^{\top }WZ$ is only positive semidefinite, the strict convexity of the barrier in $s$ keeps the full primal-dual Jacobian nonsingular by the $\Lambda ,S$ diagonal blocks.) The implicit function theorem applied to $F_{\mu }(w)=0$ with parameter $\mu$ then yields a $C^1$ map $\mu \mapsto w(\mu )$. $\square$

Proposition 4 (duality-gap identity and convergence as $\mu \to 0$). On the central path of a convex program, $f(x(\mu ))-p^{\star }=|\mathcal{I}|\mu -(\text{dual slackness})\le |\mathcal{I}|\mu$, and every limit point of $x(\mu )$ as $\mu \to 0$ is a global minimizer.

Proof. As in Exercise 6, the path point is primal feasible and $(\lambda (\mu ),\nu (\mu ))$ dual feasible, and stationarity makes $x(\mu )$ the unconstrained minimizer of $L(\cdot ,\lambda (\mu ),\nu (\mu ))$ by convexity, so $g(\lambda (\mu ),\nu (\mu ))=f(x(\mu ))-{\sum }_i{s}_i{\lambda }_i=f(x(\mu ))-|\mathcal{I}|\mu$. Weak duality $g\le p^{\star }\le f(x(\mu ))$ gives $0\le f(x(\mu ))-p^{\star }\le |\mathcal{I}|\mu$. As $\mu \to 0$ the gap vanishes, so $f(x(\mu ))\to p^{\star }$. The path lies in the compact sublevel set $\{f\le p^{\star }+|\mathcal{I}|\}$ intersected with the feasible set (compact by the bounded-optimal-set hypothesis plus the gap bound), so limit points exist; at a limit point $s_i{\lambda }_i=\mu \to 0$ gives complementary slackness, the remaining perturbed-KKT equations pass to the unperturbed KKT system by continuity, and convex sufficiency of 44.02.02 makes the limit a global minimizer. $\square$

Proposition 5 (well-posedness of the regularized step in the nonconvex case). If $A_{\mathcal{E}}$ has full row rank, there is $\bar{\delta }\ge 0$ such that for all $\delta >\bar{\delta }$ the regularized matrix \begin{psmallmatrix} W + \delta I & A_{\mathcal{E}}^\top \\ A_{\mathcal{E}} & 0\end{psmallmatrix} has inertia $(n,|\mathcal{E}|,0)$, so the regularized primal-dual step is the unique minimizer of the regularized barrier model and a descent direction for it.

Proof. By the inertia formula of the constrained-Newton KKT solve 44.03.03, \mathrm{In}\begin{psmallmatrix} W+\delta I & A_{\mathcal{E}}^\top \\ A_{\mathcal{E}} & 0\end{psmallmatrix} = \mathrm{In}(Z^\top(W+\delta I)Z) + (|\mathcal{E}|,|\mathcal{E}|,0) with $Z$ a basis of $\ker A_{\mathcal{E}}$. Now $Z^{\top }(W+\delta I)Z=Z^{\top }WZ+\delta Z^{\top }Z$; since $Z^{\top }Z\succ 0$, choosing $\delta >\bar{\delta }=\max (0,-{\lambda }_{\min }(Z^{\top }WZ)/{\lambda }_{\min }(Z^{\top }Z))$ makes $Z^{\top }(W+\delta I)Z\succ 0$, so its inertia is $(n-|\mathcal{E}|,0,0)$ and the full matrix has inertia $(n,|\mathcal{E}|,0)$ — nonsingular, no negative or zero curvature on the constraint null space. The step then uniquely minimizes the quadratic model $\frac{1}{2}{p}^{\top }(W+\delta I)p+g^{\top }p$ on $\{A_{\mathcal{E}}p=0\}$ (Proposition 2 of 44.04.01 specialized), and $g^{\top }p=-p^{\top }(W+\delta I)p<0$ for $p\ne 0$ certifies descent for the regularized barrier merit function. $\square$

Connections Master

• The KKT optimality theory of 44.02.02 is the direct parent: the perturbed KKT system is the genuine KKT system with complementary slackness $s_i{\lambda }_i=0$ relaxed to $s_i{\lambda }_i=\mu$, the central path is the homotopy that recovers complementary slackness as $\mu \to 0$, and the limit of the path is a KKT point whose multipliers are the path's dual variables. Convexity is exactly what upgrades that limit KKT point to a global minimizer, and the second-order sufficient condition there is the hypothesis under which the primal-dual Newton iteration is locally superlinear. The constraint qualifications (LICQ, strict complementarity) of that unit are the regularity conditions that keep the primal-dual matrix uniformly nonsingular along the path.

• Newton's method and the constrained-Newton KKT solve of 44.03.03 supply the per-iteration machinery: the primal-dual step is Newton's method applied to the perturbed-KKT root-finding problem, the condensed step is the constrained-Newton saddle-point system with a modified Hessian block, the inertia condition for a well-posed step is inherited verbatim, and the Hessian regularization for nonconvexity is the modified-Cholesky / eigenvalue-flooring device of that unit transplanted to the primal-dual matrix. The interior-point method is the unconstrained Newton iteration of that unit extended to inequality constraints by a barrier and an independent dual variable.

• Sequential quadratic programming 44.04.03 is the principal sibling method: both linearize the KKT system of 44.02.02, but SQP determines an active set by solving a QP subproblem at each outer step while the interior-point method keeps all inequalities strictly inactive along the central path, so the comparison — SQP's few expensive warm-startable iterations against interior-point's many cheap iterations scaling with constraint count — is the standard practitioner's tradeoff. The active-set QP machinery of 44.04.01 that SQP calls is exactly the combinatorial alternative to the barrier homotopy.

• Interior-point methods for conic and semidefinite programming 44.05.04 are the convex specialization: the same slack-and-barrier construction and the same perturbed-complementarity relaxation $S\Lambda e=\mu e$ apply, but a self-concordant barrier replaces the generic logarithmic barrier, the central path stays short in the self-concordant metric, and the path-following iteration attains a polynomial complexity bound $O(\sqrt{\vartheta }\log (1/ϵ))$ that the general nonlinear method cannot promise. The nonlinear method developed here is the structural template; the conic theory is its provably-efficient instance.

Historical & philosophical context Master

Interior methods began with the barrier-function (sequential unconstrained minimization) technique of Anthony Fiacco and Garth McCormick, whose 1968 book systematized the logarithmic barrier and proved that the barrier minimizers trace a trajectory converging to a constrained minimizer as the barrier parameter tends to zero ^{[Fiacco & McCormick 1990]} (the 1990 SIAM Classics reissue of the 1968 Wiley original). The method fell out of favor through the 1970s because the barrier Hessian becomes severely ill-conditioned as the parameter shrinks, and active-set and SQP methods dominated practical nonlinear programming.

The field was reignited by Narendra Karmarkar's 1984 polynomial-time projective algorithm for linear programming, which was soon understood as a path-following method on a logarithmic barrier; the connection to Fiacco-McCormick barriers was drawn by Margaret Wright, Philip Gill, and collaborators, and the polynomial-complexity theory for the convex case was placed on rigorous self-concordance foundations by Yurii Nesterov and Arkadi Nemirovski at the end of the 1980s. The primal-dual viewpoint that cured the conditioning problem — treating the multipliers as independent variables and relaxing complementarity to $s_i{\lambda }_i=\mu$ — was developed for linear and monotone-complementarity problems and given its standard monograph treatment by Stephen Wright ^{[Wright 1997]}. The extension to general nonlinear programming, with slack variables, the fraction-to-the-boundary rule, Hessian regularization, and filter or merit-function globalization, was consolidated in the late 1990s and 2000s; the survey of Anders Forsgren, Philip Gill, and Margaret Wright ^{[Forsgren-Gill-Wright 2002]} (SIAM Review 44, 525-597) and the textbook account of Nocedal and Wright ^{[Nocedal & Wright §19]} are the standard references, and the filter line-search interior-point solver IPOPT of Wächter and Biegler is the most widely used implementation.

Bibliography Master

@book{nocedalwright2006ip,
  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{wright1997primaldual,
  author    = {Wright, Stephen J.},
  title     = {Primal-Dual Interior-Point Methods},
  publisher = {SIAM},
  address   = {Philadelphia},
  year      = {1997}
}

@book{fiaccomccormick1990,
  author    = {Fiacco, Anthony V. and McCormick, Garth P.},
  title     = {Nonlinear Programming: Sequential Unconstrained Minimization Techniques},
  series    = {Classics in Applied Mathematics},
  publisher = {SIAM},
  address   = {Philadelphia},
  year      = {1990},
  note      = {Originally published by Wiley, 1968}
}

@article{forsgrengillwright2002,
  author  = {Forsgren, Anders and Gill, Philip E. and Wright, Margaret H.},
  title   = {Interior Methods for Nonlinear Optimization},
  journal = {SIAM Review},
  volume  = {44},
  number  = {4},
  pages   = {525--597},
  year    = {2002}
}

@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{nesterovnemirovski1994,
  author    = {Nesterov, Yurii and Nemirovski, Arkadi},
  title     = {Interior-Point Polynomial Algorithms in Convex Programming},
  series    = {SIAM Studies in Applied Mathematics},
  publisher = {SIAM},
  address   = {Philadelphia},
  year      = {1994}
}

@article{wachterbiegler2006,
  author  = {W\"{a}chter, Andreas and Biegler, Lorenz T.},
  title   = {On the Implementation of an Interior-Point Filter Line-Search Algorithm for Large-Scale Nonlinear Programming},
  journal = {Mathematical Programming},
  volume  = {106},
  number  = {1},
  pages   = {25--57},
  year    = {2006}
}