Interior-Point Methods — HPIPM & IPOPT

1 · Motivation — a smoother way through constraints

Most real decisions are constrained. You want the cheapest, lightest, fastest, or most stable design, subject to limits on mass, stress, energy, actuator force, or timing. Interior-point methods (IPMs) are the dominant family of algorithms for solving such problems, and they take a deliberately indirect route: instead of walking along the constraint boundary, they tunnel through the interior of the feasible region and steer a parameter to zero.

The two solvers this page teaches share that single idea but sit at opposite ends of the spectrum:

HPIPM Convex quadratic programs (QPs) — the subproblems of model-predictive control (MPC). Dense, optimal-control-structured, and tree-structured QPs. Coded in C on BLASFEO for embedded, real-time use.

IPOPT General nonlinear programs (NLPs) with thousands–millions of variables and constraints. C++, exact or quasi-Newton Hessians, and a filter line search for global robustness.

Before IPM, the standard tool for a QP or NLP was an active-set method: guess which constraints are tight, solve an equality-constrained subproblem, then shuffle one constraint in or out. That combinatorial guess-and-flip is efficient in warm-started control loops but can explode in the worst case, and it is brittle on large problems. IPM replaces the combinatorics with a smooth homotopy: a single Newton solve per iteration on a system whose only job is to follow a curve.

Why it matters. IPM gives polynomial-time guarantees for linear and convex quadratic programs, scales to huge NLP instances, and converges in a predictable ~20–60 iterations almost regardless of problem size. HPIPM and IPOPT are the industrial-strength realizations of this idea for two very different regimes.

feasible set objective contours active-set path interior-point (central) path

Figure 1. Two philosophies for constrained optimization. An active-set method commits to a set of binding constraints and marches along the boundary; an interior-point method keeps a positive margin from every boundary and lets that margin shrink to zero in the limit.

Takeaway. IPM converts a combinatorial "which constraints are active?" problem into a smooth "follow this curve as \(\mu\to 0\)" problem — one Newton step per iteration, no guessing.

2 · The problem each solver is built to solve

Both solvers reduce their target problem to the same standard shape, so we can teach one algorithm and then specialize. HPIPM works on a convex quadratic program:

\[ \min_{y}\ \tfrac{1}{2}y^{T}H y + g^{T}y \qquad \text{s.t.} \qquad Ay=b,\qquad Cy \ge d, \tag{QP} \]

with \(y\in\mathbb{R}^{n_y}\) the decision variables, \(H\succeq 0\) the Hessian, \(g\) the linear cost, \(Ay=b\) the equalities, and \(Cy\ge d\) the inequalities. IPOPT instead handles the general nonlinear program, which it casts into the form

\[ \min_{x}\ f(x) \qquad \text{s.t.} \qquad c(x)=0,\qquad x\ge 0, \tag{NLP} \]

where \(x\in\mathbb{R}^{n}\), \(f:\mathbb{R}^{n}\to\mathbb{R}\) is the (possibly nonconvex) objective, and \(c:\mathbb{R}^{n}\to\mathbb{R}^{m}\) collects the equalities. Any general inequality \(g(x)\ge 0\) is converted to a bound by introducing a slack: \(g(x)-s=0,\ s\ge 0\). So in both cases the "hard" constraints are of the simple nonnegativity kind — and that is the only part the barrier must handle.

Why this matters. By pushing every inequality into a single variable bound \(x\ge 0\) (or \(Cy-d\ge 0\)), the entire difficulty collapses into one question — how do we keep variables positive while optimizing? — which the log barrier answers uniformly.

Takeaway. Every constrained problem is a nonnegativity problem in disguise; the IPM is a machine purpose-built for that one disguise.

3 · The barrier idea and the central path

The obstacle is the hard constraint \(x_i\ge 0\). The barrier trick replaces it with a smooth penalty that blows up as \(x_i\downarrow 0\), so that a minimizer of the penalized problem is automatically kept strictly positive. The workhorse penalty is the logarithmic barrier:

\[ \varphi_{\mu}(x) \;=\; f(x) - \mu\sum_{i=1}^{n}\ln(x_i), \qquad \mu>0. \tag{barrier} \]

As \(x_i\to 0^{+}\), \(-\ln(x_i)\to +\infty\), erecting an infinitely tall "wall" at the boundary; deep in the interior the penalty is small and \(-(\text{small})\cdot\mu\) barely perturbs \(f\). The scalar \(\mu>0\) is the barrier parameter: it weighs the wall's influence against the real objective.

μ large: wall dominates μ medium μ small: near the boundary

Figure 2. The log barrier \(-\mu\ln x\) for decreasing \(\mu\). The wall at \(x=0\) is always infinite, but as \(\mu\) shrinks the minimizer is pushed ever closer to the boundary — the barrier's grip relaxes.

For each fixed \(\mu\), the barrier problem \(\min_x \varphi_{\mu}(x)\ \text{s.t.}\ c(x)=0\) has a (generically unique) minimizer. As \(\mu\) varies, these minimizers trace a curve — the central path — that starts deep inside the feasible region and ends at the true solution of the original problem in the limit \(\mu\to 0\):

\[ x^{\star}(\mu)\ \xrightarrow{\ \mu\to 0^{+}\ }\ x^{\star}. \]

Why follow a path instead of attacking \(\mu=0\) directly? At \(\mu=0\) the barrier disappears and we are back to the original, hard, nondifferentiable-at-the-boundary problem. A sequence of easier, well-posed problems with \(\mu\downarrow 0\) is numerically far more stable — this is a homotopy, and it is the whole essence of the interior-point method.

Takeaway. The barrier turns a hard inequality into an infinite-but-smooth wall; shrinking the wall's strength \(\mu\) to zero traces the central path from the interior to the constrained optimum.

4 · Primal–dual form — turn the path into an equation system

We could just minimize \(\varphi_{\mu}\) with a barrier-only method. But the state of the art — and what both HPIPM and IPOPT actually implement — is the primal–dual formulation, which is cleaner, faster, and more robust. The idea: write the first-order optimality conditions of the barrier problem as a square system of equations and drive it with Newton's method.

Attach a multiplier \(\lambda\in\mathbb{R}^{m}\) to \(c(x)=0\). The stationarity of the barrier Lagrangian gives, together with feasibility, the barrier KKT conditions:

\[ \nabla f(x) + \nabla c(x)\,\lambda - z = 0, \qquad c(x) = 0, \qquad X z = \mu\, e . \tag{barrier-KKT} \]

Here \(z\in\mathbb{R}^{n}\) is the multiplier for the bound \(x\ge 0\), \(X=\operatorname{diag}(x)\), \(Z=\operatorname{diag}(z)\), and \(e=(1,\dots,1)\). The third line, written componentwise, is \(x_i z_i = \mu\) for every \(i\). This is the single most important equation in the whole subject.

Why this is the key insight. The true optimality condition is complementarity \(x_i z_i = 0\) with \(x_i, z_i\ge 0\). The barrier relaxes "\(=0\)" to "\(=\mu\)", forcing both \(x_i\) and \(z_i\) to be strictly positive and making the system smooth. At \(\mu=0\) we recover the exact KKT conditions of the original problem. So "solve the NLP" becomes "solve this smooth system while driving \(\mu\downarrow 0\)."

HPIPM arrives at exactly the same system from a different door — it writes the KKT conditions of the QP directly and relaxes the complementarity \(t_i\lambda_i=0\) to \(t_i\lambda_i=\tau\) (their notation for the barrier parameter). The two viewpoints are identical; they differ only in emphasis: barrier theory (IPOPT) vs. Newton-on-KKT (HPIPM).

hyperbola \(xz=\mu\) (large μ) \(xz=\mu\) (small μ) central path \(\{(x(\mu),z(\mu))\}\)

Figure 3. The relaxed complementarity \(xz=\mu\) is a family of hyperbolas in the primal–dual plane. The central path is the curve of points where stationarity + feasibility are also satisfied; it rides the hyperbolas toward the corner \((x^\star,z^\star)\) where \(xz=0\).

Takeaway. The primal–dual method turns "optimize" into "solve \(F_\mu(x,\lambda,z)=0\) with a one-line relaxation \(Xz=\mu e\)," and everything after this is just Newton plus a schedule for \(\mu\).

5 · The Newton step — one linear solve per iteration

We have a system of equations \(F_\mu(w)=0\) in the stacked variable \(w=(x,\lambda,z)\). Newton's method linearizes it at the current iterate \(w_k\) and solves for a direction. For IPOPT's barrier-KKT system this gives the primal–dual (KKT) linear system:

\[ \begin{bmatrix} W_k + \Sigma_k & A_k \\ A_k^{T} & 0 \end{bmatrix} \begin{bmatrix} d_x \\ d_\lambda \end{bmatrix} \;=\; -\begin{bmatrix} \nabla f(x_k) + A_k\lambda_k - z_k \\ c(x_k) \end{bmatrix}, \qquad \Sigma_k = X_k^{-1}Z_k . \tag{Newton} \]

Here \(W_k = \nabla^2_{xx}\bigl(f(x_k)+\lambda_k^{T}c(x_k)\bigr)\) is the Hessian of the Lagrangian, \(A_k = \nabla c(x_k)\) is the constraint Jacobian, and \(\Sigma_k\) is the diagonal "barrier curvature." The \(d_z\) direction is then recovered from the linearized complementarity equation. The matrix is symmetric but indefinite — a KKT matrix — which is why both solvers lean on specialized factorizations.

HPIPM's generic QP produces a directly comparable system. Writing \(t=Cy-d\ge 0\) for the inequality slacks and \(\lambda\ge 0\) for their multipliers, the relaxed Newton system is (their delta form):

\[ \underbrace{\begin{bmatrix} H & -A^{T} & -C^{T} & 0 \\ -A & 0 & 0 & 0 \\ -C & 0 & 0 & I \\ 0 & 0 & T_k & \Lambda_k \end{bmatrix}}_{\nabla F_{\tau_k}} \begin{bmatrix} \Delta y \\ \Delta\pi \\ \Delta\lambda \\ \Delta t \end{bmatrix} = -\begin{bmatrix} r_g \\ r_b \\ r_d \\ r_m \end{bmatrix}, \qquad \begin{aligned} r_g &= Hy_k+g-A^{T}\pi_k-C^{T}\lambda_k,\\ r_b &= -Ay_k+b,\\ r_d &= -Cy_k+t_k+d,\\ r_m &= \Lambda_k T_k e - \tau_k e . \end{aligned} \tag{HPIPM-Newton} \]

Notice the shared anatomy: a Hessian (or \(H\)) in the \((1,1)\) block, constraint matrices in the off-diagonal blocks, and a diagonal complementarity block \(T_k,\Lambda_k\) (or \(\Sigma_k\)) in the corner. The diagonal complementarity block is the IPM's signature.

Why eliminate the complementarity variables? The \(4\times4\) system is sparse but larger than necessary. Because \(\Lambda_k\) and \(T_k\) are diagonal, \(\Delta t\) and \(\Delta\lambda\) can be solved for explicitly and substituted out. HPIPM does exactly this, collapsing the system to the equality-constrained-QP KKT form

\[ \begin{bmatrix} H + C^{T}T_k^{-1}\Lambda_k C & -A^{T} \\ -A & 0 \end{bmatrix} \begin{bmatrix} \Delta y \\ \Delta\pi \end{bmatrix} = -\begin{bmatrix} r_g - C^{T}\bigl(T_k^{-1}\Lambda_k r_d - T_k^{-1} r_m\bigr) \\ r_b \end{bmatrix}. \tag{reduced-KKT} \]

The \((1,1)\) block \(H + C^{T}T_k^{-1}\Lambda_k C\) is the QP's answer to IPOPT's \(W_k+\Sigma_k\): the objective Hessian plus a barrier term that grows as any inequality slack \(t_i\to 0\). This "blown-up Hessian" is what keeps the step pointed into the interior.

Figure 4. Eliminating the diagonal complementarity variables shrinks the KKT system to a symmetric indefinite matrix whose \((1,1)\) block is the Hessian augmented by the barrier term \(C^{T}T^{-1}\Lambda C\). This is the matrix HPIPM factorizes every iteration.

Takeaway. One IPM iteration = build the Hessian + Jacobian, add the barrier curvature, solve one symmetric-indefinite linear system, and update all variables.

6 · Mehrotra's predictor–corrector — the fast, standard variant

A naive IPM recomputes \(\mu\), solves the Newton system once, and steps. Mehrotra's insight — used by both HPIPM (as its default "fast" variant) and IPOPT (optional, and the model for its correction machinery) — is that you can get a much better direction with one extra right-hand-side solve, reusing the same factorization.

Predictor (affine-scaling step). Solve the Newton system with \(\mu=0\), i.e. target exact complementarity. This pure step \(\Delta_{\mathrm{aff}}\) aggressively tries to reach the solution.
Step to the boundary. Find the largest \(\alpha_{\mathrm{aff}}\) that keeps \(x,z\) positive. This reveals how much progress toward \(xz=0\) is actually possible.
Set the centering parameter. Compare the achievable duality gap \(\mu_{\mathrm{aff}}=\frac{(x+\alpha\Delta x)^{T}(z+\alpha\Delta z)}{n}\) with the current \(\mu\), and set \(\sigma = \left(\mu_{\mathrm{aff}}/\mu\right)^{3}\). If the pure step made big progress, \(\sigma\) is small (aggressive); if it made little, \(\sigma\approx 1\) (center instead).
Corrector. Solve once more with the target \(\sigma\mu e\) and a second-order term \(-\Delta X_{\mathrm{aff}}\,\Delta z_{\mathrm{aff}}\, e\) on the complementarity right-hand side. This term compensates for the curvature of the hyperbola \(xz=\mu\) that the linearization dropped.

\[ \text{combined direction} = \Delta_{\mathrm{aff}} + \Delta_{\mathrm{cor}} . \]

Why it works so well. The predictor measures how far we can go; the adaptive \(\sigma\) turns that into a balanced "progress vs. safety" knob; the corrector cancels the dominant nonlinearity. The net effect is a near-quadratic convergence rate for the price of two triangular solves on one factorization. This is why IPM beats naive barrier methods by an order of magnitude.

central path predictor corrector combined

Figure 5. The affine predictor shoots straight for the solution but leaves the central path's neighborhood; the corrector, computed on the same factorization, bends the step back onto the path. The combined direction inherits the predictor's speed and the corrector's centering.

Takeaway. Predictor–corrector gets two "views" for one factorization: an aggressive step to gauge progress, then a curvature correction that keeps the iterate centered — the standard recipe for fast IPMs.

7 · Staying inside — fraction-to-boundary and line search

Newton's direction is only a direction; taking the full step can drive \(x\) or \(z\) negative, which kills the log barrier (log of a negative number is undefined). Both solvers therefore clip the step and then decide how much of it to accept. The clipping is the fraction-to-boundary rule: keep a fixed fraction \((1-\tau)\) of the distance to the boundary, with

\[ \tau_j = \max\bigl\{\tau_{\min},\ 1-\mu_j\bigr\}, \qquad \alpha_x^{\max} = \max\bigl\{\alpha\in(0,1] : x_k+\alpha d_x \ge (1-\tau_j)\,x_k\bigr\}. \tag{ftb} \]

HPIPM applies exactly this rule to its slacks \(t\) and multipliers \(\lambda\) (keeping both strictly positive), then runs a line search on a merit function. IPOPT is more elaborate, because it must handle nonconvex NLPs where a pure merit function can fail.

IPOPT's filter line search

The core difficulty: when the problem is nonconvex, reducing the objective and reducing the constraint violation can conflict. IPOPT treats the two as a bi-objective problem — \((\theta,\varphi) = (\|c(x)\|_1,\ \varphi_{\mu}(x))\) — and maintains a filter: a set of pairs that are "forbidden" because an earlier iterate already beat them on both counts. A trial point is accepted if it improves either the constraint violation or the objective (sufficiently), while not being dominated by anything in the filter.

Why a filter? A single merit function \(\varphi_{\mu}(x)+\rho\|c(x)\|\) needs a penalty \(\rho\) tuned well enough to dominate curvature — a classic failure mode. The filter sidesteps the penalty entirely: it accepts a step if it helps at least one of the two goals, which is exactly the right contract for nonconvex problems.

filter points (already achieved) forbidden (dominated) region acceptable step rejected step

Figure 6. The IPOPT filter. Each point marks a previously achieved \((\theta,\varphi)\); the hatched upper-right region of every filter point is forbidden (a trial point there is worse on both axes). A trial point below-and-left of everything in the filter, or improving one axis enough, is accepted.

If the line search shrinks the step below a threshold without finding an acceptable point, IPOPT enters a feasibility-restoration phase: it temporarily abandons the objective and minimizes \(\theta(x)\) alone to claw its way back into a region where progress is possible, then resumes. It also applies second-order corrections — extra steps that reduce constraint violation using the constraint curvature — to rescue a good primal step that was rejected only because it overshot a nonlinear constraint.

Takeaway. Every IPM clips its step to stay strictly interior; IPOPT adds a filter (accept if either objective or feasibility improves) plus a restoration phase, which is what makes it reliable on nonconvex NLPs.

8 · Shrinking the barrier — the \(\mu\) schedule

The last ingredient is when and how fast to reduce \(\mu\). IPOPT's update rule (with constants \(\kappa_\mu\in(0,1)\), \(\theta_\mu\in(1,2)\); defaults \(0.2\) and \(1.5\)) is:

\[ \mu_{j+1} \;=\; \max\Bigl\{\ \tfrac{\epsilon_{\mathrm{tol}}}{10},\ \min\bigl\{\kappa_\mu\,\mu_j,\ \mu_j^{\ \theta_\mu}\bigr\}\Bigr\}. \tag{mu-update} \]

The inner \(\min\) gives superlinear decrease of \(\mu\) once the barrier subproblem is solved accurately; the outer \(\max\) floors \(\mu\) at a small multiple of the tolerance so the algorithm never chases a barrier value far smaller than the requested accuracy (which would only invite numerical trouble at the very end). A barrier subproblem is considered "solved" when its own KKT error is below \(\kappa\,\mu_j\), at which point \(\mu\) drops and the filter is reset.

Why the two-speed schedule? Shrinking \(\mu\) too fast leaves the iterate far off the central path (hard to recover); too slow wastes iterations. The \(1.5\)-power rule accelerates as \(\mu\to 0\), which is exactly what produces the method's fast tail convergence.

Takeaway. Solve each barrier problem to moderate accuracy, then drop \(\mu\) superlinearly (but never below a tolerance floor) — a few dozen such rounds is a typical IPM run.

9 · HPIPM — exploiting QP structure for real-time speed

HPIPM is not "IPM, but faster hardware." It is a family of IPMs whose distinguishing feature is structure exploitation: it knows the QP is a chain (optimal control) or a tree, and it uses that knowledge to factorize the KKT matrix in linear time in the horizon instead of cubically.

The optimal-control QP and its banded KKT

An OCP-structured QP has dynamics \(x_{n+1}=A_n x_n+B_n u_n+b_n\) coupling consecutive stages \(n=0,\dots,N\). When we stack all stage variables and write the KKT system, the equality (dynamics) blocks form a banded, arrow-shaped matrix — consecutive stages only talk to their neighbors:

Figure 7. HPIPM's OCP KKT matrix is banded because dynamics only couple neighboring stages. A backward Riccati recursion factorizes it by sweeping from the last stage \(N\) back to \(0\) with no fill-in, giving linear complexity in the horizon \(N\).

The Riccati recursion is the same machinery as the discrete-time LQR/Riccati equation: it eliminates stage variables one at a time, propagating a cost-to-go \(P_n\). HPIPM offers a classical version (needs the reduced Hessian positive definite, allows an indefinite full-space Hessian) and a square-root version (Cholesky-based, fewer flops, needs the full-space Hessian positive definite). For constant state/input dimensions the cost is \(O\bigl(N(n_x+n_u)^3\bigr)\) — linear in the horizon.

Two more HPIPM features worth knowing

Delta vs. absolute formulation. The "delta" system solves for the step; the "absolute" system solves for the next iterate directly, avoiding the residual matrix–vector products and making each solve \(O(n)\) cheaper in the vector part — a real win on small problems. The trade-off is cancellation error near the solution, so HPIPM picks per problem. It also offers a few iterative refinement steps to clean up the Newton direction when the KKT system is ill-conditioned (late iterations). And its slack variables carry diagonal Hessians, so soft constraints (L1/L2 penalties) are added essentially for free.

Condensing. HPIPM can also "condense" an OCP QP into a dense QP (eliminating the states) or partially condense it to a shorter horizon, then solve with the dense IPM and expand back. This lets an application choose the speed/robustness point on the condense-vs-structure spectrum.

Takeaway. HPIPM's edge is not a different algorithm but a different linear algebra: banded KKT → Riccati recursion → \(O(N)\) solves, plus delta/absolute forms and slack elimination tuned for embedded QPs.

10 · IPOPT — robustness machinery for general NLPs

IPOPT must survive problems that are nonconvex, poorly scaled, and potentially infeasible — a much harsher world than HPIPM's convex QPs. Four mechanisms do the heavy lifting.

Inertia correction

The reduced KKT matrix must factor as \(L D L^{T}\) with a specific inertia — for a system with \(n\) primal variables and \(m\) equality multipliers, the correct inertia is \(n\) positive and \(m\) negative eigenvalues — or else the Newton direction is not a descent direction. When the actual Hessian \(W_k\) is nonconvex or the iterate is far from a solution, the matrix can have the wrong inertia. IPOPT corrects it by shifting the diagonal:

\[ \begin{bmatrix} W_k + \Sigma_k + \delta_w I & A_k \\ A_k^{T} & -\delta_c I \end{bmatrix}, \]

increasing \(\delta_w,\delta_c\) until the factorization reports the right inertia. This guarantees the direction is a legitimate descent step even when the local curvature is "wrong."

Hessian choice

If exact second derivatives are supplied (via automatic differentiation), IPOPT uses them — this is what gives superlinear local convergence. Otherwise it falls back to a BFGS quasi-Newton approximation of the Lagrangian Hessian, which is cheaper per iteration but only linearly convergent.

Scaling and the dual step

IPOPT scales the variables, objective, and constraints (NLP scaling) so the error estimate is well-balanced, and it may take a different step length for the bound multipliers \(z\) than for the primal variables \(x\) — keeping the dual positive without over-restricting the primal.

Why this resilience matters. HPIPM can assume a nice convex QP and pour every cycle into speed. IPOPT cannot; its users hand it nonconvex, ill-scaled, sometimes infeasible NLPs, so it spends cycles on inertia correction, filters, restoration, and scaling to finish at all, then to finish fast.

Takeaway. IPOPT = the same primal–dual Newton core as HPIPM, armored with inertia correction, a filter line search, second-order corrections, restoration, and adaptive scaling for the general-NLP battlefield.

11 · Side by side

	HPIPM	IPOPT
Problem class	Convex QP (dense / OCP / tree)	General NLP (nonconvex)
Derivation viewpoint	Newton on relaxed KKT	Barrier method + KKT
Core step	Riccati / Cholesky on reduced KKT	\(LDL^{T}\) + inertia correction on reduced KKT
Complementarity relax	\(t_i\lambda_i=\tau\)	\(x_i z_i=\mu\)
Step control	Fraction-to-boundary + merit line search	Fraction-to-boundary + filter + SOC + restoration
Hessian	Exact \(H\) (problem data)	Exact or BFGS
Specialty	Structure: \(O(N)\) Riccati, condensing, BLASFEO	Robustness: inertia correction, scaling, restoration
Typical home	Embedded MPC (acados), real-time	Offline large-scale NLP (AMPL, CasADi, Pyomo…)

Takeaway. Same engine, two tunings: HPIPM optimizes for known convex structure, IPOPT for unknown general structure.

12 · A worked example, end to end

Let's solve the tiny QP

\[ \min_{x_1,x_2}\ \tfrac{1}{2}\bigl[(x_1-2)^2+(x_2-1)^2\bigr] \qquad \text{s.t.} \qquad x_1+x_2 \le 1 . \tag{ex} \]

The unconstrained optimum is \((2,1)\), but it violates the constraint \((2+1>1)\), so the true answer lies on the line \(x_1+x_2=1\). Introduce slack \(s=1-x_1-x_2\ge 0\) and multiplier \(\lambda\ge 0\). The barrier-KKT conditions (with barrier parameter \(\mu\)) are:

\[ x_1-2+\lambda = 0,\qquad x_2-1+\lambda = 0,\qquad s=1-x_1-x_2,\qquad \lambda\,s = \mu . \tag{ex-KKT} \]

Substituting \(x_1=2-\lambda,\ x_2=1-\lambda\) into the slack gives \(s=1-(3-2\lambda)=2\lambda-2\). Complementarity then reads \(\lambda(2\lambda-2)=\mu\), i.e. \(\lambda = \tfrac{1+\sqrt{1+2\mu}}{2}\). The central path is therefore

\[ x_1(\mu)=2-\lambda(\mu),\qquad x_2(\mu)=1-\lambda(\mu), \qquad \lambda(\mu)=\frac{1+\sqrt{1+2\mu}}{2}, \qquad s(\mu)=2\lambda(\mu)-2 . \tag{central-path} \]

As \(\mu\to 0\), \(\lambda\to 1\), so \(x\to(1,0)\), \(s\to 0\) — the constraint is tight, exactly the projection of \((2,1)\) onto the line. The reader can confirm the KKT sign conditions hold. The demo below sweeps \(\mu\) and shows the barrier landscape morphing and the central path marching to that boundary point.

μ =

Takeaway. A worked QP reduces the whole IPM to a one-line hyperbola \(\lambda s=\mu\); the central path is that hyperbola's intersection with the stationarity/feasibility equations, and \(\mu\to 0\) lands exactly on the boundary optimum.

13 · Complexity, theory, and the bigger picture

Why does IPM scale so well? The answer is captured by the theory of self-concordant barriers (Nesterov–Nemirovskii). A barrier function whose third derivative is bounded by its second derivative to the \(3/2\) power — the log barrier is the canonical example — guarantees that Newton's method converges in a number of iterations independent of the problem's conditioning, as long as the step stays within a fixed fraction of the boundary.

\[ \text{iterations} = O\!\left(\sqrt{\nu}\,\log\!\frac{1}{\epsilon}\right), \qquad \nu = \text{the barrier's self-concordance parameter}. \]

For a linear program in standard form the log barrier has \(\nu=n\) (the number of inequalities), so a path-following IPM needs \(O(\sqrt{n}\log(1/\epsilon))\) iterations — polynomial time, in sharp contrast to the simplex method's exponential worst case. This theoretical guarantee is why IPMs became the default for large LPs and QPs, and why they generalize to conic optimization (semidefinite programs, second-order cones) with the log-determinant and analogous barriers.

Where IPM sits in the landscape. For a convex QP you have three families: active-set (great with warm starts, combinatorial worst case), first-order / ADMM (e.g. OSQP — cheap per iteration, only \(O(1/\epsilon)\) convergence), and interior-point (few, expensive iterations, \(O(\log(1/\epsilon))\), structure-exploitable). HPIPM occupies the IPM corner of the QP world and beats the others when a structured, exact, fast-converging solve is what real-time control needs.

Takeaway. IPM's fast, predictable convergence is not an accident — it is the self-concordance of the log barrier, which makes Newton's method converge in \(O(\sqrt{n})\) homotopy rounds regardless of conditioning.

14 · The whole picture

1 · Barrierreplace \(x\ge 0\) with \(-\mu\ln x\)

2 · Primal–dualwrite KKT, relax \(xz=\mu e\)

3 · Newtonone symmetric-indefinite solve

4 · Correctpredictor–corrector, keep positive

5 · Shrink μsuperlinearly to a tolerance floor

HPIPM runs steps 3–5 with a Riccati-recursion linear algebra tuned to OCP QPs; IPOPT runs the same loop with a filter line search, inertia correction, and restoration for general NLPs. Once you see the shared core — barrier + relaxed complementarity + Newton — both solvers become variations on a single, elegant theme.