Trust-region subproblem (${\min }_{\Vert s\Vert \le \Delta }\{a+g^{T}s+\frac{1}{2}{s}^{T}Hs\}$)

The trust-region subproblem minimizes a quadratic function on a closed Euclidean ball. Even if $H$ has a negative eigenvalue, the compactness of this ball guarantees a global minimum. An exact answer is often unnecessary: a fixed fraction of the Cauchy decrease bound supplies a useful inexpensive standard.

For $g\ne 0$, the Cauchy point minimizes the quadratic model along the feasible part of the negative gradient ray. Writing $q=g^{T}Hg$, its step size isIndeed $m(-tg)=a-t\Vert g{\Vert }^2+\frac{1}{2}{t}^{2}q$ on $0\le t\le \Delta /\Vert g\Vert$. For $q\le 0$ it decreases throughout that interval; otherwise its unconstrained minimum occurs at $t=\Vert g{\Vert }^2/q$. The constant $a$ does not affect the minimizing step.

Use the induced spectral norm for the symmetric matrix $H$ and interpret $\Vert g\Vert /\Vert H\Vert =+\infty$ when $H=0$. If $q=g^{T}Hg\le 0$, the Cauchy point gives a decrease at least $\Delta \Vert g\Vert$. If $q>0$, its step size satisfies $\tau q\le \Vert g{\Vert }^2$ and $q\le \Vert H\Vert \Vert g{\Vert }^2$, soThus the numerical constant $1/2$ is independent of the model data. The bound links a nonzero gradient to a definite predicted decrease, including for an indefinite matrix $H$.

A feasible trial step $s_k$ achieves a fixed Fraction of Cauchy decrease if $m_k(0)-m_k(s_k)\ge \kappa [m_k(0)-m_k(s_{C,k})]$ for one constant $\kappa \in (0,1]$ independent of $k$. The Cauchy decrease bound then supplies a quantitative model decrease without solving the trust-region subproblem exactly. Both the fraction and the relevant model regularity must be controlled in a convergence argument.