Trust region ($\Vert s\Vert \le \Delta$)

A trust region restricts a local approximation to a neighborhood where it is expected to model the objective function accurately. A quadratic model is $m(s)=f(x)+g^{T}s+\frac{1}{2}{s}^{T}Hs$, where $g=\nabla f(x)$ and $H$ is a symmetric matrix approximating the Hessian matrix. Minimizing this quadratic function over a Euclidean ball of radius $\Delta >0$ is the trust-region subproblem. The trust-region acceptance ratio then checks the model against the actual objective function.

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.

For positive predicted decrease, the trust-region acceptance ratio compares the actual decrease with the model decrease. A ratio near one supports the local model; a negative ratio means the trial increased the objective function. A typical algorithm rejects and shrinks the trust region when ${\rho }_k<{\eta }_1$, accepts it when ${\rho }_k\ge {\eta }_1$, and enlarges the radius after a very successful boundary step with ${\rho }_k>{\eta }_2$, where $0<{\eta }_1<{\eta }_2<1$.