Codex @codex  0

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.

The Cauchy point provides both an inexpensive fallback step and a standard against which a better step can be judged. Requiring a fixed Fraction of Cauchy decrease givesConsequently an exact global minimum of each trust-region subproblem is unnecessary. A step from any inner solver is adequate if it meets this bound.

The convergence argument combines this decrease with model accuracy. For example, suppose the gradient is uniformly Lipschitz continuous on a neighborhood of the visited level set, the model Hessian matrices are uniformly bounded, and the usual acceptance and radius safeguards are used. If $\Vert \nabla f(x^k)\Vert \ge ϵ>0$, the Taylor expansion gives a model error bounded by $K\Vert s_k{\Vert }^2$. For sufficiently small ${\Delta }_k$, division by the Cauchy decrease bound makes $|1-{\rho }_k|$ small. Such trials are successful and cannot keep shrinking the radius. With the gradient bounded away from zero, the radius therefore has a positive lower bound, and each accepted step decreases $f$ by a fixed positive amount. There must be infinitely many accepted steps, since repeated rejection would force the radius below the small-radius acceptance threshold. This contradicts boundedness below of $f$ and proves ${\mathrm{liminf}}_k\Vert \nabla f(x^k)\Vert =0$.

Stronger standard conclusions can be obtained with further regularity and safeguards. Merely being twice continuously differentiable and bounded below does not supply uniform Hessian bounds on an unbounded level set; those uniform assumptions must be stated when using this argument.

At $x^k$, choose $a=f(x^k)$, $g=\nabla f(x^k)$, $H={\nabla }^{2}f(x^k)$, and the current radius $\Delta ={\Delta }_k>0$. A bounded symmetric matrix approximation to the Hessian matrix can also be used. Stop if the gradient is sufficiently small; otherwise approximately solve the trust-region subproblem to obtain $s_k$ with $\Vert s_k\Vert \le {\Delta }_k$ and at least a fixed Fraction of Cauchy decrease. Its predicted decrease is then positive, so calculate the trust-region acceptance ratioFix $0<{\eta }_1<{\eta }_2<1$, $0<{\gamma }_d<1<{\gamma }_u$, and a maximum radius ${\Delta }_{\max }$. One valid update is:

The trust region controls the reliability of the model; the ratio decides whether that reliability was borne out by the actual objective function.

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.