Damped Newton method

Let $d\ge 1$, let $U\subseteq {\mathbb{R}}^d$ be open, and let $f:U\to \mathbb{R}$ be twice continuously Fréchet differentiable. Write $g(x)=\mathrm{\nabla }f(x)$ and $H(x)={\mathrm{\nabla }}^{2}f(x)$ using The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case and The Hessian matrix and critical points of a scalar field. The Hessian is symmetric by The Hessian of a $C^2$ scalar field is symmetric.

Inputs: $x_0\in U$, a Newton-decrement tolerance $\epsilon >0$, and line-search parameters $\alpha \in (0,1\mathrm{/}2)$ and $\beta \in (0,1)$. Output: when the procedure stops, return the last valid iterate $x_k$ and one of the statuses stationary, decrement, or positive-definite solve unavailable. If none of these stopping conditions occurs, the sequence continues and there is no finite return.

At iteration $k$ with current iterate $x_k$:

1. Compute $g_k:=g(x_k)$. If $g_k=0$, return $(x_k,\mathtt{\text{stationary}})$.
2. If $H_k:=H(x_k)$ is not positive definite, return $(x_k,\mathtt{\text{positive-definite}}\mathtt{\text{solve}}\mathtt{\text{unavailable}})$ without a Newton update. Otherwise compute its Cholesky factorization $H_k=L_k{L}_k^T$, solve $L_{k}w=-g_k$ and $L_k^T{p}_k=w$, and set ${\lambda }_k^2:=-⟨g_k,p_k⟩=g_k^T{H}_k^{-1}{g}_k>0.$
3. Before line search, if ${\lambda }_k^2\mathrm{/}2\le \epsilon$, return $(x_k,\mathtt{\text{decrement}})$. This is the Newton-decrement stopping test.
4. Start with $t=1$ and repeatedly replace $t$ by $\beta t$ until $x_k+t{p}_k\in U$ and $f(x_k+t{p}_k)\le f(x_k)+\alpha t⟨g_k,p_k⟩$.
5. Set $x_{k+1}:=x_k+t{p}_k$ and continue at iteration $k+1$.

The Cholesky factor exists and is unique when the symmetric Hessian is positive definite by A matrix admits a Cholesky factorisation with positive diagonal exactly when it is Hermitian positive definite, and that factor is unique. Its positive diagonal makes both triangular solves unique. The backtracking branch terminates whenever it is reached, since $g_k\mathrm{\ne }0$ and $H_k$ is positive definite, by Armijo backtracking terminates for strict descent directions ↗. This procedure makes no global-optimality claim.