Global trust-region minimizers satisfy the shifted-Hessian conditions, including the hard case

By [F2], choose an orthogonal matrix $U$ such that $D:=U^{T}BU=\mathrm{diag}({\mu }_1,\dots ,{\mu }_n)$ with ${\mu }_1\le \cdots \le {\mu }_n$. Put $c:=U^{T}g$ and write $p=Uy$. Then $q(Uy)={\sum }_i(c_i{y}_i+\frac{1}{2}{\mu }_i{y}_i^2)$ and $\mathrm{\parallel }Uy{\mathrm{\parallel }}_2=\mathrm{\parallel }y{\mathrm{\parallel }}_2$, so it suffices to construct a minimizer in these coordinates.

Set ${\lambda }_0:=\max (0,-{\mu }_1)$ and, for $\lambda >{\lambda }_0$, define $\phi (\lambda ):={\sum }_i{c}_i^2\mathrm{/}({\mu }_i+\lambda {)}^2$ and $y_i(\lambda ):=-c_i\mathrm{/}({\mu }_i+\lambda )$. Every denominator is positive, so [F5] gives continuity of $\phi$. Let $Z:=\{i:{\mu }_i+{\lambda }_0=0\}$. If some $i\in Z$ has $c_i\mathrm{\ne }0$, choose ${\lambda }_a>{\lambda }_0$ with ${\lambda }_a-{\lambda }_0<\mathrm{\mid }{c}_i\mathrm{\mid }\mathrm{/}\mathrm{\Delta }$; its single term gives $\phi ({\lambda }_a)>{\mathrm{\Delta }}^2$. Otherwise $c_i=0$ for $i\in Z$. Then ${\phi }_0:={\sum }_{i\mathrm{\notin }Z}\frac{c_i^2}{({\mu }_i+{\lambda }_0{)}^2}$ is finite. If ${\phi }_0>{\mathrm{\Delta }}^2$, each term with $i\mathrm{\notin }Z$ is continuous at ${\lambda }_0$ by [F5], while each term with $i\in Z$ is zero for $\lambda >{\lambda }_0$ and extends as the constant zero. Thus the extension with value ${\phi }_0$ is continuous at ${\lambda }_0$, so choose ${\lambda }_a>{\lambda }_0$ close enough that $\phi ({\lambda }_a)>{\mathrm{\Delta }}^2$. In either case with $\phi ({\lambda }_a)>{\mathrm{\Delta }}^2$, put $S:={\sum }_i\mathrm{\mid }{\mu }_i\mathrm{\mid }$ and choose $R>\max \{{\lambda }_a,S+2\mathrm{\parallel }c{\mathrm{\parallel }}_2\mathrm{/}\mathrm{\Delta }\}$. Then ${\mu }_i+R>2\mathrm{\parallel }c{\mathrm{\parallel }}_2\mathrm{/}\mathrm{\Delta }$ for every $i$, giving $\phi (R)<{\mathrm{\Delta }}^2\mathrm{/}4<{\mathrm{\Delta }}^2$. By [F4] on $[{\lambda }_a,R]$, choose $\lambda >{\lambda }_0$ with $\phi (\lambda )={\mathrm{\Delta }}^2$. The vector $y_i=-c_i\mathrm{/}({\mu }_i+\lambda )$ then has norm $\mathrm{\Delta }$, $(D+\lambda I)y=-c$, and $D+\lambda I$ is positive definite.

In the remaining case every $i\in Z$ has $c_i=0$ and the finite sum ${\phi }_0$ in step 2.1 satisfies ${\phi }_0\le {\mathrm{\Delta }}^2$. Set $y_i^0=-c_i\mathrm{/}({\mu }_i+{\lambda }_0)$ for $i\mathrm{\notin }Z$ and $y_i^0=0$ for $i\in Z$. If ${\lambda }_0=0$, take $y=y^0$; then $D$ is positive semidefinite, $Dy=-c$, and $\mathrm{\parallel }y{\mathrm{\parallel }}_2\le \mathrm{\Delta }$. If ${\lambda }_0>0$, the zero-denominator coordinates form the least-eigenvalue eigenspace. Add a vector $z$ supported on those coordinates with $\mathrm{\parallel }z{\mathrm{\parallel }}_2^2={\mathrm{\Delta }}^2-\mathrm{\parallel }{y}^0{\mathrm{\parallel }}_2^2$ and take $y=y^0+z$. Such a vector exists by scaling a unit eigenvector; it is orthogonal to $y^0$. Then $(D+{\lambda }_{0}I)y=-c$, $D+{\lambda }_{0}I⪰0$, and $\mathrm{\parallel }y{\mathrm{\parallel }}_2=\mathrm{\Delta }$. This is the hard-case construction.

In either construction, returning to $p=Uy$ gives a feasible vector and a $\lambda \ge 0$ with $(B+\lambda I)p=-g$, $B+\lambda I⪰0$, and $\lambda (\mathrm{\Delta }-\mathrm{\parallel }p{\mathrm{\parallel }}_2)=0$. For every feasible $v$, direct expansion gives $q(v)-q(p)=\frac{1}{2}(v-p{)}^T(B+\lambda I)(v-p)+\frac{\lambda }{2}(\mathrm{\parallel }p{\mathrm{\parallel }}_2^2-\mathrm{\parallel }v{\mathrm{\parallel }}_2^2)\ge 0,$ because the first term is nonnegative by [F3] and the second is zero if $\lambda =0$ and nonnegative otherwise. Thus the constructed vector is a global minimizer.

Conversely, let $p_{\ast }$ be any global minimizer. Then $q(p_{\ast })=q(p)$, where $p$ is the constructed minimizer, and $p_{\ast }$ is feasible. Applying the identity in step 4.1 with $v=p_{\ast }$ expresses zero as the sum of two nonnegative terms. In particular, for $H:=B+\lambda I$, $(p_{\ast }-p{)}^{T}H(p_{\ast }-p)=0$. By [F2], diagonalize the symmetric positive semidefinite matrix $H$ from step 4.1. In these coordinates the last quadratic form is ${\sum }_i{\nu }_i{w}_i^2=0$ with every ${\nu }_i\ge 0$, so ${\nu }_i{w}_i=0$ for every $i$ and $H(p_{\ast }-p)=0$. Since $Hp=-g$, this gives $H{p}_{\ast }=-g$. If $\lambda >0$, the other nonnegative term in the identity vanishes only when $\mathrm{\parallel }{p}_{\ast }{\mathrm{\parallel }}_2=\mathrm{\Delta }$; if $\lambda =0$, complementarity is automatic. Thus $p_{\ast }$ satisfies all three conditions.

The constructed case ${\lambda }_0>0$ has $g\perp E_{\mu }$ and adds exactly the missing boundary component in $E_{\mu }$; when its length is positive, opposite choices of $z$ are distinct and the same inequality in step 4.1 proves both globally minimizing. This verifies the stated hard-case clause.