Codex @codex  0

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]

By the diagonal reduction in a two-variable Newton iteration, $y_n=x_n$ for $n\ge 1$. Put $e_n=x_n-1$. Direct factorization gives the exact Newton map in optimization error identityThe assumed convergence $x_n\to 1$ makes the final factor tend to $3/2$, so it is bounded for all sufficiently large $n$. Hence $|e_{n+1}|\le C|e_n{|}^2$. For the Euclidean norm error $E_n=\Vert (x_n,y_n)-(1,1)\Vert =\sqrt{2}|e_n|$, this becomes $E_{n+1}\le (C/\sqrt{2})E_n^2$, proving quadratic convergence. Unless the exact limit is reached in finitely many steps, $E_{n+1}/E_n^2\to 3/(2\sqrt{2})$.

Let $e_n=x_n-x_{\ast }$ for the limit $x_{\ast }$. Quadratic convergence means that eventually $|e_{n+1}|\le C|e_n{|}^2$ for a fixed constant $C$; exact asymptotic order two has $|e_{n+1}|/|e_n{|}^2\to c$ with $0<c<\infty$.

For this iteration and $x_{\ast }=3$, direct algebra givesUsing the stipulated convergence $x_n\to 3$, the ratio of successive squared errors isThus the convergence is quadratic. The iteration is well defined here: $x_1=7/2$, and thereafter $x_n>3$ implies $3<x_{n+1}<x_n$. The initial point is not already the limit, so the error ratio is meaningful.

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.

First control the denominator. The mean value theorem applied to $f^{\prime }$ yields, for $0<x\le 2000$,Thus $f$ is strictly increasing on $[0,2000]$ and all proposed Newton steps within that interval are defined.

Assume $0\le x_n<x^{\ast }$. Then $f(x_n)<0$ and $f^{\prime }(x_n)>0$, so $x_{n+1}>x_n$. Apply Taylor's theorem instead at the root, expanding about $x_n$:After rearranging and substituting the Newton step, the signed error satisfiesConsequently $x_n<x_{n+1}<x^{\ast }$. Starting from $x_0=0$, mathematical induction proves this for every finite $n$, establishing that the signed errors are negative and strictly increasing. Since $f^{\prime \prime }({\xi }_n)>-1/4000$ and $2f^{\prime }(x_n)>1$,Writing $E_n=-{ϵ}_n$ gives $0<E_{n+1}\le E_n^2/4000$. Since $E_0=x^{\ast }<2000$, this also implies $E_n\le 4000(E_0/4000{)}^{2^n}\to 0$, proving quadratic convergence. This is the concave Newton iteration from below.

An iterative sequence converges superlinearly to its limit when its nonzero error norms satisfy the displayed ratio condition, or when it reaches the limit in finitely many steps. Quadratic convergence is a stronger local rate. In contrast, exact linear convergence has a positive asymptotic error ratio below one. A superlinear method need not have quadratic convergence.