Quadratic trust-region models and the actual-to-predicted reduction ratio

Let $n\ge 1$, let $f:{\mathbb{R}}^n\to \mathbb{R}$ be differentiable at $x\in {\mathbb{R}}^n$, and put $g:=\mathrm{\nabla }f(x)$ using the gradient convention of The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case. Let $B\in {\mathbb{R}}^{n\times n}$ be a symmetric matrix and let $\mathrm{\Delta }>0$. A quadratic model at $x$ is

$m(p):=f(x)+⟨g,p⟩+\frac{1}{2}{p}^{T}Bp,p\in {\mathbb{R}}^n,$

with the Euclidean inner product and norm of The Euclidean inner product $⟨x,y⟩={\sum }_{k<n}{x}_k{y}_k$ on ${\mathbb{R}}^n$ and matrix products as in Rectangular matrix multiplication and the identity matrix $I_n$, including zero-sized shapes. The trust-region ball is ${\mathcal{B}}_{\mathrm{\Delta }}:=\{p:\mathrm{\parallel }p{\mathrm{\parallel }}_2\le \mathrm{\Delta }\}$. The predicted reduction of a feasible step $p\in {\mathcal{B}}_{\mathrm{\Delta }}$ is $\mathrm{pred}(p):=m(0)-m(p)$. Its actual reduction is $\mathrm{ared}(p):=f(x)-f(x+p)$. When $\mathrm{pred}(p)>0$, the actual-to-predicted reduction ratio is

$\rho (p):=\frac{\mathrm{ared}(p)}{\mathrm{pred}(p)}\mathrm{.}$

The quantity $\mathrm{\parallel }B{\mathrm{\parallel }}_2$ means the matrix norm induced by the Euclidean vector norm, namely the $p=2$ case of The matrix norm induced by a published vector p-norm. It is not required that $B={\mathrm{\nabla }}^{2}f(x)$ in this definition; exact Hessians and symmetric model approximations are both admitted. The ratio is undefined when predicted reduction is nonpositive, so an algorithm must use a separately justified fallback or return a failure status in that case.