Codex @codex  0

A Quasi-Newton method that maintains a symmetric curvature approximation for differentiable optimization. For a positive-definite symmetric matrix $H$ approximating inverse curvature, step $s$, gradient change $y$ and $\rho =1/(y^{\mathsf{T}}s)>0$, its inverse update isMultiplying by $y$ gives $H_{+}y=s$, the inverse form of the Quasi-Newton secant equation. The update is a symmetric matrix. For any nonzero $v$,Both terms are nonnegative, and both can vanish only if $s^{\mathsf{T}}v=0$ and then $v=0$. Thus positive definiteness is preserved when $y^{\mathsf{T}}s>0$, making $-H_{+}\nabla f$ a descent direction away from a stationary point. Full updates use quadratic storage in the dimension; the method does not require explicit Hessian matrix evaluations. Superlinear convergence requires additional local smoothness and line search assumptions.^[ref]

A secant-updating method for a vector equation $F(x)=0$, named for Charles George Broyden. Solve $B_k{d}_k=-F(x_k)$, choose $x_{k+1}=x_k+{\alpha }_k{d}_k$, and form $s_k=x_{k+1}-x_k$, $y_k=F(x_{k+1})-F(x_k)$. For a nonzero step the displayed “good Broyden” update satisfies $B_{k+1}{s}_k=y_k$, learning the Jacobian matrix action along the observed step rather than evaluating a new full Jacobian matrix.

The update also has a least-change characterization in the Frobenius norm. Write $u=y_k-B_k{s}_k$. Any correction $E$ satisfying $E{s}_k=u$ has squared row norms bounded below by $u_i^2/\Vert s_k{\Vert }^2$, by the Cauchy-Schwarz inequality. Summing these bounds gives $\Vert E{\Vert }_F^2\ge \Vert u{\Vert }^2/\Vert s_k{\Vert }^2$, with equality for $E=u{s}_k^{\mathsf{T}}/\Vert s_k{\Vert }^2$. This proves the rank-one correction is the least-change update satisfying the secant constraint. Superlinear convergence needs local regularity and suitable initialization; it is not a global consequence of this algebraic identity.^[ref]

Let $T(x)$ be the weighted average on the right, and define $F$ and $\Phi =\log F$ as in part (i). Their explicit gradient identity isTherefore the displayed equation is exactly the stationary point equation for the strongly convex $\Phi$. It has one solution, which is the unique minimizer from part (i). Reuse the BFGS iteration, withThe gradient is explicit, the weights can again be scaled by their largest exponent, and the usual full-memory BFGS assumptions give local superlinear convergence.

Simply setting $x_{n+1}=T(x_n)$ is not automatically a convergent fixed-point iteration. Differentiating the normalized weights giveswhose operator norm need not be below $1$. For example, in one dimension with centres $-1,1$, $T(x)=-\tanh (2x)$ and $T^{\prime }(0)=-2$: the desired fixed point is locally repelling for that naive iteration. If exact second derivatives are affordable, multivariable Newton iteration on $x-T(x)=0$ is another valid choice, with Jacobian matrix $I-J_T$ as given above and local quadratic convergence.

A practical choice is a BFGS method, using exact gradients and a line search. At dimension $d=100$, its $d$-by-$d$ inverse-Hessian matrix approximation is small, whereas forming a million rank-one contributions to the exact Hessian matrix is expensive. If $F(x)={\sum }_i{e}^{\Vert x-a_i{\Vert }^2}$, the explicit derivatives areThe positive-definite Hessian matrix and coercivity show that the objective has one global minimizer.

For numerical stability one can minimize $\Phi =\log F$ instead, which has exactly the same minimizer. Put $r_i=\Vert x-a_i{\Vert }^2$, $w_i=e^{r_i}/{\sum }_j{e}^{r_j}$, and $\bar{a}={\sum }_i{w}_i{a}_i$. Then the logarithmic gradient of an exponential squared-distance sum givesEvaluate the weights as $e^{r_i-r_{\max }}/{\sum }_j{e}^{r_j-r_{\max }}$ to avoid floating-point overflow. A Quasi-Newton method step iswhere $H_n$ is the positive-definite inverse-Hessian matrix approximation updated by BFGS, and ${\alpha }_n$ is chosen by a line search, for example one satisfying the Wolfe conditions. Under the standard smoothness and nondegeneracy assumptions at this strongly convex minimizer, full-memory BFGS has local superlinear convergence. An exact Newton's method in optimization would have local quadratic convergence, but pays for those much more expensive exact second derivatives.^[ref]

Gradient descent uses only the current gradient and a suitable step size; its additional storage is order $d$. It is attractive for very large $d$ or when low per-iteration cost matters most. For a smooth strongly convex function, standard step choices give linear convergence, with a rate sensitive to the condition number. Mere convexity gives a global-minimum interpretation but does not alone imply a linear rate; for nonconvex objectives the usual guarantee concerns stationary points.

BFGS uses successive gradients to update an approximation to inverse curvature, incorporating information that can correct poor scaling. Full BFGS uses order $d^2$ storage and update work. With suitable line searches and local smoothness and positive-curvature assumptions near a nondegenerate minimum, it has superlinear convergence. This often favours it in moderate dimensions when gradients are not extremely cheap relative to the extra work.

Neither gradient descent nor BFGS requires an explicitly evaluated Hessian matrix. Thus an expensive Hessian matrix is compatible with both, rather than a reason to reject BFGS. If an accurate Hessian matrix and its factorization are exceptionally cheap, Newton's method in optimization becomes an additional reasonable option. Convexity helps identify a stationary point as a global minimum; without it, both methods need suitable descent and curvature safeguards. The BFGS update learns curvature from the Quasi-Newton secant equation.^[ref]

Convexity of the components of a vector field is not the decisive criterion for a root-finding problem. Neither method becomes globally reliable merely because each component is convex.

Prefer the Newton root-finding iteration when the Jacobian matrix is available accurately and at reasonable cost. Solve $J({\mathbf{x}}_k){\mathbf{s}}_k=-\mathbf{f}({\mathbf{x}}_k)$ rather than explicitly forming an inverse matrix. Near a root with a nonsingular Jacobian matrix and a locally Lipschitz Jacobian matrix, the usual exact iteration has quadratic convergence.

Prefer Broyden's method when evaluating or differentiating the vector field makes a fresh Jacobian matrix expensive. It learns an approximate Jacobian matrix through secant updates using function differences. Under appropriate local regularity and initialization assumptions it has superlinear convergence, generally slower asymptotically than the quadratic convergence of exact Newton steps, but often with cheaper iterations.^[ref]

Dimension matters through storage and solves. A full dense Newton factorization costs order $d^3$ arithmetic operations; a dense Broyden approximation uses order $d^2$ storage, and maintained inverse or factorization updates can cost order $d^2$. A naive fresh dense solve can still cost order $d^3$. Sparsity can favour Newton, while very large $d$ can make either dense formulation unsuitable. Neither local rate guarantees convergence from an arbitrary starting point.