Past exam of the numerical linear algebra and continuous optimisation course of the University of Oxford / 2007 / B / 5

At the current point $x$, a trust-region method approximately minimizes a local quadratic modelwhere $B$ is a symmetric Hessian approximation and $\Delta >0$ is the trust-region radius. For a step with positive predicted decrease, compare the true and predicted reductions throughChoose fixed thresholds $0<{\eta }_1<{\eta }_2<1$. If $\rho <{\eta }_1$, the step is unsuccessful: reject it and reduce the radius. If ${\eta }_1\le \rho <{\eta }_2$, accept the successful step and normally retain the radius. If $\rho \ge {\eta }_2$, the step is very successful: accept it and permit an increase in radius, especially when the step reaches its boundary. The ratio tests whether the local model is accurate enough to justify moving. An approximate subproblem solver should deliver at least the model decrease achieved at the Cauchy point.

The Cauchy point minimizes the model along the negative-gradient ray within the ball. For $g\ne 0$, write $s=-tg$, $0\le t\le \Delta /\Vert g{\Vert }_2$. Thenwhose scalar minimum occurs at $t=1$ unless the ball cuts the ray short. ThereforeIf $\Vert g{\Vert }_2\le \Delta$, its predicted decrease is $\frac{1}{2}\Vert g{\Vert }_2^2$. Otherwise it is $\Delta \Vert g{\Vert }_2-\frac{1}{2}{\Delta }^2\ge \frac{1}{2}\Delta \Vert g{\Vert }_2$. Thus every feasible step with $m(s)\le m(s_c)$ satisfies the Cauchy decrease boundFor $g=0$, take $s_c=0$; the bound reduces to zero.

The global optimality conditions for a quadratic trust-region subproblem with Hessian $B$ are: for some $\lambda \ge 0$,Here $B=I$, so the shifted matrix is positive definite. If $\Vert g{\Vert }_2\le \Delta$, choose $\lambda =0$ and $s=-g$. If $\Vert g{\Vert }_2>\Delta$, the active boundary gives $s=-g/(1+\lambda )$ and $1+\lambda =\Vert g{\Vert }_2/\Delta$. HenceThis is exactly the Cauchy point. Because the model is strictly convex, it is the unique global minimizer, including $s_{\ast }=0$ when $g=0$.

The true quadratic has $g(x)=c+Hx$ and the exact expansionSubtracting the model with Hessian $I$ yields $f(x+s)-m(s)=\frac{1}{2}{s}^T(H-I)s$. Since $H$ is symmetric positive definite and $\Vert H{\Vert }_2=1$, its eigenvalues lie in $(0,1]$, so $\Vert H-I{\Vert }_2\le 1$. ThereforeIn fact the stated assumptions give a factor one-half better than the requested bound.

Write $D=f(x)-m(s)$ for the predicted decrease, assuming a nonstationary point and a step at least as good as the Cauchy point. When $\Delta \le \Vert g{\Vert }_2$, part (ii) gives $D\ge \frac{1}{2}\Vert g{\Vert }_2\Delta$. Part (iv), using its weaker requested bound, then givesConsequently $\Delta \le \frac{1}{2}(1-\eta )\Vert g{\Vert }_2$ implies $\boxed{\rho \ge \eta }$.

For the radius conclusion, use the standard update rules from part (i). Suppose no subsequence of the generated gradient norms tends to zero. Then some $\epsilon >0$ bounds those norms below eventually. If ${\Delta }_k\to 0$, eventually ${\Delta }_k\le \frac{1}{2}(1-{\eta }_2)\epsilon$, so every subsequent step is very successful by the preceding estimate. The radius is then maintained or increased, contradicting convergence to zero. Hence a radius tending to zero forces a subsequence of gradient norms to tend to zero. The conclusion uses the trust-region update rules as well as the model estimates.