Newton's Method for Optimization: Unconstrained and Equality-Constrained

Intuition Beginner

Steepest descent looks only at the slope: it heads straight downhill and decides how far to walk. That works, but on a stretched, valley-shaped landscape it zig-zags badly, because the steepest direction is rarely the direction that points at the bottom. Newton's method fixes this by using a second piece of information — how the slope itself is changing, the curvature of the landscape — to aim better and to guess the right distance in one shot.

Here is the idea. At your current point, replace the true landscape with the best matching bowl: a curved surface that agrees with the real one in height, in slope, and in curvature. A bowl has an exact lowest point you can compute directly. Walk straight to the bottom of that matching bowl, and call it your next guess. Near a genuine minimum the matching bowl hugs the true landscape so closely that this one jump lands almost on the true bottom, and the next jump squares the remaining error — the same digit-doubling speed that makes Newton's root-finder famous.

Two cautions come with the speed. First, the matching bowl is only trustworthy nearby; from far away it can point you uphill or send you flying, so in practice you take a fraction of the Newton step, shortened by the same line search used in the previous unit. Second, the trick needs a bowl that actually holds water — curving up in every direction. Where the landscape curves down, the "matching bowl" is a saddle or a dome and its lowest point is meaningless, so the curvature must be repaired before you trust the step.

Visual Beginner

Picture a one-dimensional slice of the landscape: height plotted against position. Steepest descent reads only the tilt of the curve at your point. Newton reads the tilt and the bend, then fits a parabola that matches both, and jumps to the bottom of that parabola.

The wider the valley, the longer the Newton jump; the tighter the valley, the shorter. That automatic scaling by curvature is exactly what steepest descent lacks, and it is why one Newton step can cross a long flat valley that would take steepest descent hundreds of small zig-zag steps.

method	information used	step direction	step length	speed near a minimum
steepest descent	slope only	straight downhill	guessed by line search	slow, zig-zag
Newton	slope and curvature	toward bottom of fitted bowl	set by curvature	digits roughly double

The takeaway: by matching curvature, Newton turns the direction and the distance into a single computed jump, and near the bottom that jump is almost perfect.

Worked example Beginner

Take the stretched bowl $f(x_1,x_2)=\frac{1}{2}{x}_1^2+\frac{9}{2}{x}_2^2$, whose bottom is at the origin. Its slope pair (the gradient) is $(x_1,9x_2)$, and its curvature is captured by the two numbers $1$ and $9$ — the bowl curves up nine times faster in the second direction than the first. Start at $x=(9,1)$.

Steepest descent would head along the negative slope $(-9,-9)$, a direction tilted away from the origin because the two coordinates are scaled so differently, and would zig-zag. Newton instead divides each slope component by its own curvature: the step is

$$p=\left(-\frac{9}{1},-\frac{9}{9}\right)=(-9,-1).$$

Adding this to the start gives $x+p=(9-9,1-1)=(0,0)$ — the exact bottom, in a single step.

Why exact here? Because $f$ is itself a perfect bowl (a quadratic), so the matching bowl is the true landscape, and jumping to the bottom of the model jumps to the true minimum. For a curved, non-quadratic landscape the match is not perfect, but near the bottom it is so close that the leftover error after one step is roughly the square of the error before.

Check the curvature numbers: the second direction's curvature $9$ shortens that component of the step (dividing the slope $9$ by $9$ gives $1$), while the first direction's curvature $1$ leaves its component long. That per-direction rescaling is the whole point.

What this tells us: Newton converts the slope into a step by dividing out the curvature, and on a genuine bowl it reaches the minimum in one jump no matter how stretched the bowl is — the cure for the zig-zag that condition number inflicts on steepest descent.

Check your understanding Beginner

Formal definition Intermediate+

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be twice continuously differentiable with gradient $g(x)=\nabla f(x)$ and Hessian $H(x)={\nabla }^{2}f(x)$, the symmetric matrix of second partial derivatives. The second-order Taylor model 02.05.05 of $f$ about $x$ is

$$m_x(p)=f(x)+g(x{)}^{\top }p+\frac{1}{2}{p}^{\top }H(x)p.$$

When $H(x)\succ 0$ (positive definite), $m_x$ is a strictly convex quadratic with a unique minimiser; setting ${\nabla }_p{m}_x(p)=g(x)+H(x)p=0$ gives the Newton step

$$p^{\mathrm{nt}}(x)=-H(x{)}^{-1}g(x),\text{equivalently the solution of}H(x)p^{\mathrm{nt}}=-g(x).$$

This is the central distinction from Newton's method for root-finding 43.02.03: there the Newton step solves $f^{\prime }(x)p=-f(x)$ for a root of $g$; here it solves the linear system $H(x)p=-g(x)$ to minimise $f$, i.e. it is Newton's root-finder applied to the stationarity equation $g(x)=0$ with $H=\nabla g$ in the role of the Jacobian. Newton's method for minimisation iterates

$$x_{k+1}=x_k+{\alpha }_k{p}^{\mathrm{nt}}(x_k),{\alpha }_k>0,$$

with ${\alpha }_k$ chosen by a line search 44.03.01; the pure (undamped) Newton method takes ${\alpha }_k=1$.

The Newton decrement at $x$ is

$$\lambda (x)=(g(x{)}^{\top }H(x{)}^{-1}g(x){)}^{1/2}=(p^{\mathrm{nt}\top }H(x)p^{\mathrm{nt}}{)}^{1/2}=\Vert H(x{)}^{1/2}{p}^{\mathrm{nt}}\Vert .$$

It is the norm of the Newton step in the local Hessian metric, and $\frac{1}{2}\lambda (x{)}^2=f(x)-{\min }_p{m}_x(p)$ is the predicted decrease; the directional derivative of $f$ along the Newton step is $g^{\top }{p}^{\mathrm{nt}}=-\lambda (x{)}^2\le 0$, so a positive-definite Hessian makes $p^{\mathrm{nt}}$ a descent direction. The quantity $\lambda (x{)}^2$ is the standard stopping criterion: stop when $\frac{1}{2}\lambda (x{)}^2\le \epsilon$.

When $H(x)$ is not positive definite, $p^{\mathrm{nt}}$ need not be a descent direction (and may not exist if $H$ is singular). A modified Newton method replaces $H(x)$ by $B(x)=H(x)+E(x)\succ 0$, with $E(x)$ chosen so $B(x)$ is positive definite with a bounded condition number $\kappa (B)$, and uses $p=-B(x{)}^{-1}g(x)$. Two standard choices: a modified Cholesky factorisation that adds to diagonal pivots during factorisation to keep them positive, and an eigenvalue (spectral) modification that diagonalises $H=Q\Lambda Q^{\top }$ by the spectral theorem 01.01.13 and floors the eigenvalues, $B=Q\max (\Lambda ,\delta I)Q^{\top }$ for some $\delta >0$.

For the equality-constrained problem ${\min }_{x}f(x)$ subject to $Ax=b$ with $A\in {\mathbb{R}}^{p\times n}$ of full row rank, the optimality (KKT) conditions are $\nabla f(x^{\ast })+A^{\top }{\nu }^{\ast }=0$ and $A{x}^{\ast }=b$. At a feasible point $x$ (so $Ax=b$), the equality-constrained Newton step is the solution $(p^{\mathrm{nt}},w)$ of the KKT system

$$\left[\begin{array}{cc}H(x)& A^{\top }\\ A& 0\end{array}\right]\left[\begin{array}{c}{p}^{\mathrm{nt}}\\ w\end{array}\right]=\left[\begin{array}{c}-g(x)\\ 0\end{array}\right],$$

the stationarity conditions of the quadratic model $m_x(p)$ restricted to $\{p:Ap=0\}$. The new symbols $H$ (Hessian), $p^{\mathrm{nt}}$ (Newton step), $\lambda (x)$ (Newton decrement), and the KKT block matrix are recorded in _meta/NOTATION.md.

Counterexamples to common slips Intermediate+

• "The Newton step is always a descent direction." Only when $H(x)\succ 0$. If $H(x)$ is indefinite, $g^{\top }{p}^{\mathrm{nt}}=-g^{\top }{H}^{-1}g$ can be positive, so the step heads uphill; if $H(x)$ is singular the step may not exist. This is the entire reason modified-Newton methods exist.

• "Newton's method always converges to a minimiser." Pure Newton solves $g(x)=0$; it is attracted to any stationary point, including saddles and maxima, where $H$ is indefinite or negative definite. Convergence to a minimiser requires either positive-definite curvature along the path or an explicit modification plus a line search that enforces decrease.

• "The full Newton step ${\alpha }_k=1$ is safe from any start." Far from the solution the quadratic model is inaccurate and the unit step can increase $f$. The damped phase uses a backtracking line search; only once the iterate is close does the analysis guarantee the unit step is accepted and quadratic convergence begins.

• "Equality-constrained Newton needs the full Hessian to be positive definite." It needs $H$ positive definite only on the null space of $A$ (the reduced Hessian $Z^{\top }HZ\succ 0$ for a basis $Z$ of $\ker A$). The KKT matrix is nonsingular under that weaker condition together with $A$ full row rank, even when $H$ is indefinite on all of ${\mathbb{R}}^n$.

Key theorem with proof Intermediate+

The signature result is the local quadratic convergence of the pure Newton method at a strong minimiser: it certifies the digit-doubling speed and isolates the two hypotheses — a positive-definite Hessian at the solution and a Lipschitz Hessian nearby — that the entire globalised theory is built to deliver.

Theorem (local quadratic convergence of Newton's method for minimisation). Let $f\in C^2$ on a neighbourhood of a point $x^{\ast }$ with $\nabla f(x^{\ast })=0$ and ${\nabla }^{2}f(x^{\ast })\succ 0$, and suppose ${\nabla }^{2}f$ is Lipschitz continuous with constant $L$ near $x^{\ast }$. Then there is $\delta >0$ such that for every $x_0$ with $\Vert x_0-x^{\ast }\Vert \le \delta$ the pure Newton iterates $x_{k+1}=x_k-{\nabla }^{2}f(x_k{)}^{-1}\nabla f(x_k)$ are well defined, remain within $\delta$ of $x^{\ast }$, converge to $x^{\ast }$, and satisfy

$$\Vert x_{k+1}-x^{\ast }\Vert \le \frac{L\Vert {\nabla }^{2}f(x^{\ast }{)}^{-1}\Vert }{1-L\Vert {\nabla }^{2}f(x^{\ast }{)}^{-1}\Vert \Vert x_k-x^{\ast }\Vert }\Vert x_k-x^{\ast }{\Vert }^2,$$

so the convergence is quadratic.

Proof. Write $g=\nabla f$, $H={\nabla }^{2}f$, $e_k=x_k-x^{\ast }$, and $\gamma =\Vert H(x^{\ast }{)}^{-1}\Vert$. Since $H(x^{\ast })\succ 0$ is invertible and $x\mapsto H(x)$ is continuous, there is ${\delta }_0>0$ such that $H(x)$ is invertible with $\Vert H(x{)}^{-1}\Vert \le 2\gamma$ for $\Vert x-x^{\ast }\Vert \le {\delta }_0$; on this ball the Newton step exists. Because $g(x^{\ast })=0$, the iteration gives

$$e_{k+1}=e_k-H(x_k{)}^{-1}g(x_k)=H(x_k{)}^{-1}(H(x_k)e_k-(g(x_k)-g(x^{\ast }))).$$

The fundamental theorem of calculus applied to $g$ along the segment from $x^{\ast }$ to $x_k$ 02.05.05 gives $g(x_k)-g(x^{\ast })={\int }_0^{1}H(x^{\ast }+t{e}_k)e_{k}dt$, hence

$$H(x_k)e_k-(g(x_k)-g(x^{\ast }))={\int }_0^1(H(x_k)-H(x^{\ast }+t{e}_k))e_{k}dt.$$

The displacement from $x_k$ to $x^{\ast }+t{e}_k$ has length $(1-t)\Vert e_k\Vert$, so the Lipschitz bound on $H$ gives $\Vert H(x_k)-H(x^{\ast }+t{e}_k)\Vert \le L(1-t)\Vert e_k\Vert$, and integrating, the bracketed term has norm at most $\frac{1}{2}L\Vert e_k{\Vert }^2$. Therefore

$$\Vert e_{k+1}\Vert \le \Vert H(x_k{)}^{-1}\Vert \cdot \frac{1}{2}L\Vert e_k{\Vert }^2\le \gamma L\Vert e_k{\Vert }^2.$$

Choosing $\delta \le \min \{{\delta }_0,1/(2\gamma L)\}$ makes $\gamma L\Vert e_k\Vert \le \frac{1}{2}$, so $\Vert e_{k+1}\Vert \le \frac{1}{2}\Vert e_k\Vert$ keeps the iterates in the ball and forces $e_k\to 0$; the displayed sharper bound follows from $\Vert H(x_k{)}^{-1}\Vert \le \gamma /(1-\gamma L\Vert e_k\Vert )$ via the Banach perturbation lemma applied to $H(x_k)=H(x^{\ast })(I+H(x^{\ast }{)}^{-1}(H(x_k)-H(x^{\ast })))$. $\square$

Bridge. This is the foundational reason Newton's method anchors the fast end of unconstrained optimization, and it builds toward the equality-constrained theory by exhibiting Newton-for-minimisation as Newton-for-root-finding 43.02.03 applied to the stationarity map $g$, with the Hessian playing the Jacobian's role — the simple-root condition $f^{\prime }(x^{\ast })\ne 0$ generalises to the strong-minimiser condition ${\nabla }^{2}f(x^{\ast })\succ 0$, which is exactly the invertibility that makes each linearised solve well posed. The central insight is that the quadratic rate is purchased entirely by curvature: the positive-definite Hessian both supplies the descent direction $g^{\top }{p}^{\mathrm{nt}}=-{\lambda }^2$ and bounds $\Vert H^{-1}\Vert$, so the line-search globalisation of the previous unit 44.03.01 need only carry the iterate into this basin, after which the unit step is accepted and the analysis here takes over. Putting these together, the affine invariance recorded in the Advanced results is dual to this estimate — quadratic convergence is a coordinate-free statement — and the same bound appears again, with the reduced Hessian on $\ker A$ in place of $H$, in the equality-constrained convergence theorem and, through self-concordance, in the iteration-count guarantees of interior-point methods.

Exercises Intermediate+

Advanced results Master

Newton's method for minimisation is the root-finder 43.02.03 applied to $\nabla f=0$ with the Hessian as Jacobian, and the results below organise its theory around three invariances: the affine invariance that makes the iteration coordinate-free, the curvature condition that turns the model into a descent direction, and the null-space reduction that carries the unconstrained analysis to the equality-constrained KKT system, with self-concordance the bridge to interior-point complexity.

Theorem 1 (descent property and the decrement identity). For $H(x)\succ 0$ the Newton step $p^{\mathrm{nt}}=-H^{-1}g$ satisfies $g^{\top }{p}^{\mathrm{nt}}=-g^{\top }{H}^{-1}g=-\lambda (x{)}^2\le 0$, with equality only at a stationary point, so $p^{\mathrm{nt}}$ is a descent direction whenever $g\ne 0$. The decrement equals the Hessian-norm of the step, $\lambda (x)=\Vert p^{\mathrm{nt}}{\Vert }_{H(x)}$, and measures the suboptimality of the quadratic model: $f(x)-{\min }_p{m}_x(p)=\frac{1}{2}\lambda (x{)}^2$. Both $g^{\top }{p}^{\mathrm{nt}}$ and $\lambda (x)$ are affine invariant, so the standard stopping test $\frac{1}{2}\lambda (x{)}^2\le \epsilon$ does not depend on the coordinate system — a structural advantage over the gradient-norm test $\Vert g\Vert \le \epsilon$, which is not ^{[Boyd, S. & Vandenberghe, L. — Convex Optimization]}.

Theorem 2 (two-phase convergence of damped Newton). For a strictly convex $f$ with ${\nabla }^{2}f$ Lipschitz, the damped Newton method with backtracking line search exhibits exactly two phases. In the damped phase, while $\Vert g(x)\Vert$ exceeds a threshold, each step decreases $f$ by at least a fixed positive amount $\gamma >0$, so this phase lasts at most $(f(x_0)-f^{\ast })/\gamma$ steps; in this phase the backtracking step length may be less than one. In the quadratically convergent phase, once $\Vert g(x)\Vert$ is small enough, the line search always accepts the unit step $\alpha =1$, and the iterates obey $\Vert g(x_{k+1})\Vert \le C\Vert g(x_k){\Vert }^2$, so the residual squares each step and the total number of Newton steps to reach accuracy $\epsilon$ is $(f(x_0)-f^{\ast })/\gamma +O(\log \log (1/\epsilon ))$. The line search of the previous unit 44.03.01 is precisely the globalisation that carries the iterate from the first phase into the second ^{[Boyd, S. & Vandenberghe, L. — Convex Optimization]}.

Theorem 3 (modified Newton: guaranteed descent under indefinite curvature). When $H(x_k)$ is indefinite or ill-conditioned, replace it by $B_k=H(x_k)+E_k$ with $E_k$ chosen so that $B_k\succ 0$ and $\kappa (B_k)\le \bar{\kappa }$ uniformly. The modified-Cholesky factorisation of Gill, Murray, and Wright computes $B_k=L_k{D}_k{L}_k^{\top }$ while increasing pivots as needed, with $\Vert E_k\Vert$ no larger than a multiple of the most negative eigenvalue of $H(x_k)$ and zero when $H(x_k)$ is already sufficiently positive definite, so the modification is inactive near a strong minimiser and the quadratic rate is preserved there. The spectral alternative $B_k=Q_k\max ({\Lambda }_k,\delta I)Q_k^{\top }$ uses the eigendecomposition 01.01.13 and floors eigenvalues at $\delta$. Either choice makes $p_k=-B_k^{-1}{g}_k$ a descent direction with $\cos {\theta }_k\ge \delta /\bar{\kappa }$ bounded below, so the angle condition holds and the Zoutendijk theorem of 44.03.01 gives global convergence to a stationary point, while the inactivity of $E_k$ near the solution restores the local quadratic phase ^{[Nocedal, J. & Wright, S. J. — Numerical Optimization (2nd ed.)]}.

Theorem 4 (equality-constrained Newton: feasible and infeasible start). For $\min f(x)$ subject to $Ax=b$ with $A$ full row rank and the reduced Hessian $Z^{\top }HZ\succ 0$, the KKT matrix is nonsingular and the feasible-start Newton step, the solution of $\left[\begin{array}{cc}H& A^{\top }\\ A& 0\end{array}\right]\left[\begin{array}{c}{p}^{\mathrm{nt}}\\ w\end{array}\right]=\left[\begin{array}{c}-g\\ 0\end{array}\right]$, equals the reduced step $-Z(Z^{\top }HZ{)}^{-1}{Z}^{\top }g$ and inherits the unconstrained quadratic convergence with $H$ replaced by the reduced Hessian, since feasibility $A{p}^{\mathrm{nt}}=0$ is preserved so all iterates stay on $\{Ax=b\}$. The infeasible-start variant does not require $A{x}_0=b$: it applies Newton's root-finder to the full KKT residual $r(x,\nu )=(\nabla f(x)+A^{\top }\nu ,Ax-b)$, and the Newton step solves $\left[\begin{array}{cc}H& A^{\top }\\ A& 0\end{array}\right]\left[\begin{array}{c}\Delta x\\ \Delta \nu \end{array}\right]=-\left[\begin{array}{c}\nabla f(x)+A^{\top }\nu \\ Ax-b\end{array}\right]$; the primal residual $Ax-b$ then decreases geometrically to zero and once feasibility is attained the method coincides with the feasible variant. Both are quadratically convergent under the same nonsingularity hypotheses ^{[Boyd, S. & Vandenberghe, L. — Convex Optimization]}.

Theorem 5 (self-concordance and affine-invariant complexity). A thrice-differentiable convex $f$ is self-concordant if $|D^{3}f(x)[h,h,h]|\le 2(D^{2}f(x)[h,h]{)}^{3/2}$ for all $x,h$ — the multivariable form of $|f^{\prime \prime \prime }|\le 2(f^{\prime \prime }{)}^{3/2}$. For such $f$ the pure Newton method satisfies a constant-free bound: there is an absolute $\eta \in (0,1)$ (e.g. $\eta =(3-\sqrt{5})/2$) such that whenever $\lambda (x)\le \eta$ the unit step gives $\lambda (x^{+})\le 2\lambda (x{)}^2$, and whenever $\lambda (x)>\eta$ the backtracking step decreases $f$ by at least an absolute constant $\gamma >0$. The total number of Newton steps to reach accuracy $\epsilon$ is bounded by $(f(x_0)-f^{\ast })/\gamma +O(\log \log (1/\epsilon ))$ with no dependence on $n$, the condition number, or any Lipschitz constant. This affine-invariant count is the analytic core of the Nesterov-Nemirovskii interior-point complexity theory, where a self-concordant barrier composes with the objective and Newton's method solves each centering subproblem in a uniformly bounded number of steps ^{[Boyd, S. & Vandenberghe, L. — Convex Optimization]}.

Synthesis. Newton's method for optimization is one construction — minimise the second-order model $m_x(p)=f+g^{\top }p+\frac{1}{2}{p}^{\top }Hp$ — and the entire theory descends from a single invariance: the Newton step $-H^{-1}g$, the decrement $\lambda =\Vert p^{\mathrm{nt}}{\Vert }_H$, and the self-concordance inequality are all unchanged by an invertible linear change of variables, which is the foundational reason the convergence and complexity statements carry no conditioning constants. The central insight is the division of labour inherited from the previous unit: curvature owns the rate while the line search owns globalisation — the positive-definite Hessian simultaneously supplies the descent direction $g^{\top }{p}^{\mathrm{nt}}=-{\lambda }^2$ and the bound on $\Vert H^{-1}\Vert$ that powers quadratic convergence, and the damped phase merely carries the iterate into the basin where the unit step is accepted.

This is exactly the same role the strong-minimiser condition ${\nabla }^{2}f(x^{\ast })\succ 0$ plays that the simple-root condition $f^{\prime }(x^{\ast })\ne 0$ played for the root-finder 43.02.03; Newton-for-minimisation is dual to Newton-for-roots through the identification $\nabla f=0$, with the Hessian as Jacobian. Putting these together, the unconstrained analysis generalises to the equality-constrained KKT system by replacing $H$ with the reduced Hessian on $\ker A$, and self-concordance is the bridge from this local theory to the polynomial-time complexity of interior-point methods, where the same Newton solve becomes the centering step. The bridge forward is therefore explicit: indefinite curvature is repaired by the modified-Newton surrogate, the secant approximation of $H$ produces quasi-Newton 44.03.04, the trust-region alternative 44.03.05 absorbs indefiniteness without a modification, and the self-concordant barrier carries the method into interior-point optimization.

Full proof set Master

Proposition 1 (descent property and decrement identity). If $H(x)\succ 0$ then $g^{\top }{p}^{\mathrm{nt}}=-\lambda (x{)}^2\le 0$ and $f(x)-{\min }_p{m}_x(p)=\frac{1}{2}\lambda (x{)}^2$.

Proof. With $p^{\mathrm{nt}}=-H^{-1}g$, $g^{\top }{p}^{\mathrm{nt}}=-g^{\top }{H}^{-1}g=-\lambda (x{)}^2$, nonpositive since $H^{-1}\succ 0$, and zero only if $g=0$. The model value at its minimiser is $m_x(p^{\mathrm{nt}})=f+g^{\top }{p}^{\mathrm{nt}}+\frac{1}{2}(p^{\mathrm{nt}}{)}^{\top }H{p}^{\mathrm{nt}}=f-g^{\top }{H}^{-1}g+\frac{1}{2}{g}^{\top }{H}^{-1}H{H}^{-1}g=f-g^{\top }{H}^{-1}g+\frac{1}{2}{g}^{\top }{H}^{-1}g=f-\frac{1}{2}{\lambda }^2$, so $f(x)-{\min }_p{m}_x(p)=\frac{1}{2}{\lambda }^2$. $\square$

Proposition 2 (local quadratic convergence). Under $\nabla f(x^{\ast })=0$, ${\nabla }^{2}f(x^{\ast })\succ 0$, and ${\nabla }^{2}f$ Lipschitz of constant $L$ near $x^{\ast }$, the pure Newton iterates from a sufficiently close start converge with $\Vert e_{k+1}\Vert \le \gamma L\Vert e_k{\Vert }^2$, $\gamma =\Vert {\nabla }^{2}f(x^{\ast }{)}^{-1}\Vert$ (up to the factor $2$ from $\Vert H(x_k{)}^{-1}\Vert \le 2\gamma$ on the working ball).

Proof. As in the Key theorem. Continuity of $H$ and invertibility of $H(x^{\ast })$ give a ball where $\Vert H(x{)}^{-1}\Vert \le 2\gamma$. From $g(x^{\ast })=0$, $e_{k+1}=H(x_k{)}^{-1}(H(x_k)e_k-(g(x_k)-g(x^{\ast })))$, and $g(x_k)-g(x^{\ast })={\int }_0^{1}H(x^{\ast }+t{e}_k)e_{k}dt$ gives $H(x_k)e_k-(g(x_k)-g(x^{\ast }))={\int }_0^1(H(x_k)-H(x^{\ast }+t{e}_k))e_{k}dt$, of norm $\le \frac{1}{2}L\Vert e_k{\Vert }^2$ by the Lipschitz bound. Hence $\Vert e_{k+1}\Vert \le 2\gamma \cdot \frac{1}{2}L\Vert e_k{\Vert }^2=\gamma L\Vert e_k{\Vert }^2$; shrinking the ball so $\gamma L\Vert e_k\Vert \le \frac{1}{2}$ gives contraction and convergence. $\square$

Proposition 3 (KKT-matrix nonsingularity). If $A\in {\mathbb{R}}^{p\times n}$ has full row rank and $Z^{\top }HZ\succ 0$ for a basis $Z$ of $\ker A$, then $K=\left[\begin{array}{cc}H& A^{\top }\\ A& 0\end{array}\right]$ is nonsingular.

Proof. Suppose $K(u,v{)}^{\top }=0$: then $Hu+A^{\top }v=0$ and $Au=0$. From $Au=0$, $u=Zw$. Left-multiplying the first equation by $u^{\top }$ and using $u^{\top }{A}^{\top }v=(Au{)}^{\top }v=0$ gives $u^{\top }Hu=0$, i.e. $w^{\top }(Z^{\top }HZ)w=0$, so $w=0$ by positive-definiteness, whence $u=0$. The first equation reduces to $A^{\top }v=0$, and full row rank of $A$ (the kernel of $A^{\top }$ is only the zero vector) gives $v=0$. $\square$

Proposition 4 (equality-constrained Newton step equals the reduced step and preserves feasibility). At a feasible $x$ (so $Ax=b$), the solution $p^{\mathrm{nt}}$ of the KKT system satisfies $A{p}^{\mathrm{nt}}=0$ and equals $-Z(Z^{\top }HZ{)}^{-1}{Z}^{\top }g$.

Proof. The bottom block of the KKT system reads $A{p}^{\mathrm{nt}}=0$, so $x+p^{\mathrm{nt}}$ remains feasible and $p^{\mathrm{nt}}=Zu$ for some $u$. The top block $H{p}^{\mathrm{nt}}+A^{\top }w=-g$ left-multiplied by $Z^{\top }$ kills $A^{\top }w$ (since $Z^{\top }{A}^{\top }=(AZ{)}^{\top }=0$), leaving $Z^{\top }HZu=-Z^{\top }g$, so $u=-(Z^{\top }HZ{)}^{-1}{Z}^{\top }g$ and $p^{\mathrm{nt}}=Zu=-Z(Z^{\top }HZ{)}^{-1}{Z}^{\top }g$. This is the unique minimiser of $m_x$ over $\ker A$ by Proposition 1 applied to the reduced quadratic. $\square$

Proposition 5 (modified-Newton step is a descent direction with a bounded angle). If $B=H+E\succ 0$ with $\delta I⪯B⪯MI$ (so $\kappa (B)\le M/\delta$), then $p=-B^{-1}g$ satisfies $g^{\top }p<0$ for $g\ne 0$ and $\cos \theta =\frac{-g^{\top }p}{\Vert g\Vert \Vert p\Vert }\ge \delta /M$.

Proof. $g^{\top }p=-g^{\top }{B}^{-1}g<0$ since $B^{-1}\succ 0$. With $p=-B^{-1}g$, $-g^{\top }p=g^{\top }{B}^{-1}g\ge \Vert g{\Vert }^2/M$ (since $B^{-1}⪰(1/M)I$), and $\Vert p\Vert =\Vert B^{-1}g\Vert \le \Vert g\Vert /\delta$ (since $\Vert B^{-1}\Vert \le 1/\delta$). Therefore

$$\cos \theta =\frac{-g^{\top }p}{\Vert g\Vert \Vert p\Vert }\ge \frac{\Vert g{\Vert }^2/M}{\Vert g\Vert \cdot \Vert g\Vert /\delta }=\frac{\delta }{M}>0.$$

The uniform lower bound is the angle condition, so by the Zoutendijk theorem 44.03.01 the modified-Newton method converges globally to a stationary point. $\square$

Proposition 6 (self-concordant Newton: the basic step bound). Let $f$ be self-concordant and strictly convex, with Newton decrement $\lambda (x)$. If $\lambda (x)<1$ then the pure Newton step $x^{+}=x+p^{\mathrm{nt}}$ satisfies $\lambda (x^{+})\le (\lambda (x)/(1-\lambda (x)){)}^2$.

Proof (sketch, in the one-dimensional reduction along $p^{\mathrm{nt}}$). Self-concordance makes $u(t)=f^{\prime \prime }(x+t{p}^{\mathrm{nt}}{)}^{-1/2}$ $1$-Lipschitz in the metric induced by $H(x)$, so the Hessian varies in a controlled band: for $\Vert s{\Vert }_{H(x)}<1$, $(1-\Vert s{\Vert }_{H(x)}{)}^{2}H(x)⪯H(x+s)⪯(1-\Vert s{\Vert }_{H(x)}{)}^{-2}H(x)$. Applying these inequalities to the gradient identity $g(x^{+})=g(x^{+})-g(x)-H(x)p^{\mathrm{nt}}$ (using $g(x)+H(x)p^{\mathrm{nt}}=0$) and expressing $\lambda (x^{+})=\Vert g(x^{+}){\Vert }_{H(x^{+}{)}^{-1}}$ yields, after the standard integral estimate with $\Vert p^{\mathrm{nt}}{\Vert }_{H(x)}=\lambda (x)$, the bound $\lambda (x^{+})\le (\lambda (x)/(1-\lambda (x)){)}^2$. The quadratic right-hand side is the constant-free local rate; full detail is in the cited self-concordance theory. $\square$

Connections Master

• Line-search methods and the Wolfe conditions 44.03.01 supply the globalisation that turns local Newton into a method convergent from any start: the damped Newton phase is exactly a Wolfe (backtracking) line search applied to the Newton direction, the angle-condition hypothesis of Zoutendijk's theorem is what Proposition 5 verifies for the modified-Newton direction, and the curvature condition's guarantee that the unit step is eventually accepted is what hands control to the quadratic-convergence analysis of this unit. Steepest descent's condition-number-dependent rate $((\kappa -1)/(\kappa +1){)}^2$ from that unit is precisely the baseline Newton's affine-invariant quadratic rate removes by dividing out the Hessian.

• Newton's and the secant method for root-finding 43.02.03 is the parent construction: Newton-for-minimisation is Newton-for-roots applied to the stationarity map $\nabla f=0$, with the Hessian ${\nabla }^{2}f$ in the role of the Jacobian and the strong-minimiser condition ${\nabla }^{2}f(x^{\ast })\succ 0$ generalising the simple-root condition $f^{\prime }(x^{\ast })\ne 0$. The quadratic-convergence proof here is the systems Newton-Kantorovich estimate of that unit specialised to a symmetric positive-definite Jacobian, and the quasi-Newton secant idea of that unit becomes the Hessian-approximation strategy that defines BFGS.

• The spectral theorem for symmetric operators 01.01.13 is the analytic engine of the modified-Newton constructions: the eigenvalue (spectral) modification $B=Q\max (\Lambda ,\delta I)Q^{\top }$ diagonalises the indefinite Hessian and floors its eigenvalues to manufacture a positive-definite surrogate with controlled condition number, and the very definition of "strong minimiser" — ${\nabla }^{2}f(x^{\ast })\succ 0$ — is the statement that all eigenvalues of the Hessian are positive. Multivariable Taylor expansion 02.05.05 provides the integral-remainder identity $g(x_k)-g(x^{\ast })={\int }_0^{1}H(x^{\ast }+t{e}_k)e_{k}dt$ that converts the Lipschitz-Hessian hypothesis into the quadratic error bound.

• Quasi-Newton/BFGS 44.03.04, trust-region methods 44.03.05, and interior-point methods 44.04.04 are the downstream consumers: quasi-Newton replaces the exact Hessian solve $Hp=-g$ by a secant approximation that avoids second derivatives while retaining a superlinear rate, the trust-region framework absorbs indefinite curvature by constraining the step rather than modifying the Hessian, and the self-concordance theory of this unit's Theorem 5 is the analytic foundation that makes the Newton centering step of interior-point methods converge in an affine-invariant, dimension-independent number of iterations. The equality-constrained KKT solve here is the kernel of every primal-dual interior-point iteration.

Historical & philosophical context Master

The use of the tangent-and-curvature model to locate a minimum descends from the root-finding tradition of Isaac Newton and Joseph Raphson ^{[Raphson 1690]}, transferred to optimization by recognising that minimising $f$ is solving $\nabla f=0$, so the second derivative enters as the Jacobian of the gradient. The systematic finite-dimensional convergence theory, including the role of the Lipschitz Hessian and the positive-definite condition at the solution, was consolidated in the twentieth-century numerical-optimization literature, with the semilocal Banach-space form due to Leonid Kantorovich in 1948 ^{[Kantorovich 1948]} underlying the affine-invariant treatments later developed by Deuflhard.

The modern affine-invariant view of Newton's method for convex optimization, the Newton decrement as the natural stopping measure, and the equality-constrained KKT formulation are presented by Boyd and Vandenberghe ^{[Boyd-Vandenberghe Ch. 9-10]}, following the self-concordance theory introduced by Yurii Nesterov and Arkadi Nemirovskii in 1994 ^{[Nesterov-Nemirovskii 1994]}, which replaced problem-dependent Lipschitz constants with the affine-invariant inequality $|f^{\prime \prime \prime }|\le 2(f^{\prime \prime }{)}^{3/2}$ and thereby produced the first polynomial-time interior-point complexity bounds for general convex programming. The practical modified-Cholesky factorisation that makes indefinite-Hessian Newton steps reliable is due to Gill, Murray, and Wright, whose treatment in Practical Optimization (1981) remains a standard reference ^{[Gill-Murray-Wright 1981]}; the line-search and trust-region globalisations are synthesised in Nocedal and Wright ^{[Nocedal, J. & Wright, S. J. — Numerical Optimization (2nd ed.)]}.

Bibliography Master

@book{nocedalwright2006,
  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{boydvandenberghe2004,
  author    = {Boyd, Stephen and Vandenberghe, Lieven},
  title     = {Convex Optimization},
  publisher = {Cambridge University Press},
  year      = {2004}
}

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

@book{gillmurraywright1981,
  author    = {Gill, Philip E. and Murray, Walter and Wright, Margaret H.},
  title     = {Practical Optimization},
  publisher = {Academic Press},
  address   = {London},
  year      = {1981}
}

@article{kantorovich1948,
  author  = {Kantorovich, Leonid V.},
  title   = {Functional analysis and applied mathematics},
  journal = {Uspekhi Matematicheskikh Nauk},
  volume  = {3},
  number  = {6},
  year    = {1948},
  pages   = {89--185}
}

@book{raphson1690,
  author    = {Raphson, Joseph},
  title     = {Analysis aequationum universalis},
  publisher = {Thomas Braddyll},
  address   = {London},
  year      = {1690}
}

@book{deuflhard2004,
  author    = {Deuflhard, Peter},
  title     = {Newton Methods for Nonlinear Problems: Affine Invariance and Adaptive Algorithms},
  series    = {Springer Series in Computational Mathematics},
  volume    = {35},
  publisher = {Springer},
  year      = {2004}
}