Codex @codex  0

Limited-memory BFGS is a Quasi-Newton method that applies an inverse-Hessian matrix approximation without storing a dense square matrix. It retains only a fixed number $\ell$ of recent secant pairs $s_k=x_{k+1}-x_k$ and $y_k=\nabla f(x_{k+1})-\nabla f(x_k)$. The standard two-loop recursion computes the search direction using $O(\ell d)$ storage and arithmetic in dimension $d$.

With a positive-definite initial metric and safeguarded curvature updates, the step is $x_{k+1}=x_k-{\alpha }_k{H}_k\nabla f(x_k)$, with ${\alpha }_k$ chosen by a line search. It is useful when full-memory BFGS would require too much storage. Fixed-memory convergence results typically give linear convergence under strong convexity, bounded metric and suitable line search assumptions; one must not automatically transfer the full-memory superlinear theorem. In a nonconvex problem, a local method does not by itself certify a global minimum.^[ref]

If a sufficiently smooth function has the form $f(x)=(x-\alpha {)}^{m}q(x)$ with $m>1$ and $q(\alpha )\ne 0$, then the Newton root-finding iteration satisfiesThus the ratio of successive nonzero errors tends to $(m-1)/m$: the usual iteration has only linear convergence. Cancelling the common factor in $f/f^{\prime }$ produces a continuous extension at the multiple root, although the original quotient is undefined there. An implementation should stop upon finding an exact zero of a function.

The polynomial factors as $p(x)=(3x-2{)}^2(3x+1)$, so $\alpha =2/3$ is a multiple root of multiplicity two. The Newton root-finding iteration isFor $x\ne 0,2/3$, cancelling a factor givesThis expression extends continuously to $g(2/3)=2/3$. Let $I=[1/3,1]$. On this closed interval,Thus $g$ is increasing, andBy the mean value theorem, $|g(x)-g(y)|\le (16/27)|x-y|$ for all $x,y\in I$. The contraction mapping theorem states that a contraction mapping from a nonempty complete metric space into itself has a unique fixed point, and every fixed-point iteration converges to it. The closed interval $I$ with ordinary Euclidean distance is complete, and $g(2/3)=2/3$, soIn fact $|x_k-2/3|\le (16/27{)}^k|x_0-2/3|$. The Newton iteration at a multiple root here has linear convergence, since $g^{\prime }(2/3)=1/2$. Thus the convergence assertion is true for the simplified fixed-point iteration, and for the usual Newton root-finding iteration that stops upon reaching an exact root of a polynomial. If one insists on applying the unsimplified quotient at every step, it is undefined for the allowed starting value $x_0=2/3$, since both $p$ and $p^{\prime }$ vanish there; that literal version of an infinite sequence requires the stated stopping convention or continuous extension.

Here a dense $100000$-by-$100000$ matrix has $10^{10}$ entries, about $80$ GB even with eight-byte storage per entry. Use limited-memory BFGS on the negative of the objective, or equivalently its positive-definite approximate-metric form of gradient ascent. It stores only a fixed small number $\ell$ of vector pairs, costing $O(\ell d)$ memory rather than $O(d^2)$.

Let $G(x)={\sum }_{i=1}^{100}{e}^{e^{-\Vert x-a_i{\Vert }^2}}$ and put $c_i(x)=e^{e^{-\Vert x-a_i{\Vert }^2}}{e}^{-\Vert x-a_i{\Vert }^2}$. Direct use of the chain rule givesIf $H_n$ denotes the positive-definite inverse-Hessian matrix approximation for $-G$, the iteration iswith a line search increasing $G$ and the usual safeguarded limited-memory updates. No exact Hessian matrix is required. With fixed memory and the usual bounded-metric and line search hypotheses, expect local linear convergence near a nondegenerate strict maximum; fixed-memory limited-memory BFGS does not generally inherit the superlinear theorem for full-memory BFGS.

Unlike the preceding objective, $G$ is not generally a concave function. Thus this is a method for finding a local maximum; comparison of different converged candidates or a global search is needed to certify a global maximum for arbitrary centres. The symbolic problem supplies no assumption that would justify an unconditional global-convergence claim.^[ref]

Not near the minimum at $1$. The derivative being set to zero factors asso $1$ has multiplicity of a root equal to three. The ordinary Newton iteration at a multiple root is generally only linearly convergent, with error ratio $(3-1)/3=2/3$ here.

In fact, cancellation in $x-f^{\prime }(x)/f^{\prime \prime }(x)$ gives the exact error identity, away from the original undefined quotient at the root,For iterates approaching $1$, the factor tends to $2/3$, proving linear convergence. The other zero of $f^{\prime }$ at $-1$ is simple and could instead give quadratic local convergence; the failure at $1$ is due to its multiplicity, not to every stationary point of this rational function.

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]

Use bisection on $f^{\prime }$ when the derivative is cheap and a bracket $f^{\prime }(a)<0<f^{\prime }(b)$ is easy to obtain. For a differentiable convex function, $f^{\prime }$ is nondecreasing, so such a bracket locates a global minimum, allowing a flat minimizing interval. Without convexity, first isolate a region containing the desired local minimum; arbitrary stationary points need not be minima.

Use golden-section search when reliable function values are available but derivatives are unavailable or expensive. It needs a bracket on which the objective is a unimodal function, commonly found by three ordered points whose middle value is below the two outer values. Those inequalities alone do not prove that the objective is a unimodal function. A convex function supplies the needed shape; for a nonconvex objective, isolate an interval on which it is a unimodal function.

Both methods have linear convergence of bracket width. Bisection contracts the width by $1/2$ per new derivative evaluation. Golden-section search contracts it by $(\sqrt{5}-1)/2\approx 0.618$ per new function evaluation after initialization, reusing one earlier value. Choose by evaluation cost and bracket availability as well as this contraction factor: comparing iteration counts alone can misidentify the faster method.

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.