Codex @codex  0

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.

The Cauchy point minimizes the model along the negative gradient ray inside the trust region. With $q=g^{T}Hg$, writeIf $q\le 0$, this last quadratic function decreases throughout the interval. If $q>0$, its unconstrained minimum occurs at $t=\Vert g{\Vert }^2/q$. ThusThe additive constant $a$ has no effect on the Cauchy point. To obtain the Cauchy decrease bound, first suppose $q>0$. Since $\tau q\le \Vert g{\Vert }^2$,The spectral norm inequality $q\le \Vert H\Vert \Vert g{\Vert }^2$ gives $\tau \ge \min \{\Delta /\Vert g\Vert ,1/\Vert H\Vert \}$. HenceIf $q\le 0$, the decrease is at least $\Delta \Vert g\Vert$, which also implies the displayed bound. When $H=0$, interpret $\Vert g\Vert /\Vert H\Vert =+\infty$. Thus the universal choice is $c=1/2$.

At $d=1000$, gradient descent and full BFGS are practical candidates; a dense Newton method can also be feasible, but its extra work and indefinite curvature need attention. The number of examples $n$, data sparsity and conditioning still matter.

For dense $A$, a gradient evaluation costs $O(nd)$ arithmetic, with $O(d)$ working storage beyond the data and accumulation buffers. Gradient descent is inexpensive per iteration and, with an appropriate line search, follows a descent direction, but poor conditioning can make it slow.

Forming the Hessian matrix explicitly costs $O(n{d}^2)$ arithmetic, and a dense Newton method solve costs $O(d^3)$. A $1000$-square double-precision matrix uses about $8$ MB, so storage alone is manageable, but repeated factorization may be expensive. Because the Hessian matrix can be indefinite or singular, an unmodified Newton step need not decrease the loss; a modified Hessian, damping or a trust region is appropriate.

Full BFGS uses gradients and an $O(d^2)$ curvature approximation, avoiding explicit second derivatives. Its rank-two updates and direction calculation cost $O(d^2)$ per step and require roughly the same matrix storage. A positive-definite initial approximation with safeguarded curvature updates and a suitable line search preserves descent directions. For this scale it is often a good compromise, without guaranteeing a global minimum.^[ref]

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.

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$.