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 mathematician associated with Broyden's method and quasi-Newton methods in numerical analysis. An institutional portrait is catalogued by the University of Essex Library Services: www.flickr.com/photos/149590996@N07/31601668406/

For a convergent quasi-Newton method sequence $x_k\to x_{\ast }$ with $\nabla f(x_{\ast })=0$, nonsingular $H_{\ast }={\nabla }^{2}f(x_{\ast })$, and continuous Hessian nearby, the displayed condition implies q-superlinear convergence. Here $B_k{s}_k=-\nabla f(x_k)$ and $s_k=x_{k+1}-x_k$. The condition requires Hessian accuracy only along the actual steps, rather than convergence of the full matrix approximations. It is associated with John E. Dennis and Jorge Moré.

Indeed, the first-order expansion of the gradient gives $\nabla f(x_{k+1})=-(B_k-H_{\ast })s_k+o(\Vert s_k\Vert )=o(\Vert s_k\Vert )$. Nonsingularity of $H_{\ast }$ gives $\Vert x-x_{\ast }\Vert \le C\Vert \nabla f(x)\Vert$ locally. Consequently $\Vert e_{k+1}\Vert \le {\epsilon }_k(\Vert e_k\Vert +\Vert e_{k+1}\Vert )$ with ${\epsilon }_k\to 0$. Rearrangement proves $\Vert e_{k+1}\Vert /\Vert e_k\Vert \to 0$. Finite termination is understood separately from ratios with zero denominators.

A mathematician whose research includes mathematical optimization. The Dennis-Moré condition concerns superlinear convergence of quasi-Newton methods.

Homepage: www.cmor-faculty.rice.edu/~dennis/

A mathematician working on mathematical optimization algorithms and software. The Dennis-Moré condition concerns superlinear convergence of quasi-Newton methods.

Homepage: www.mcs.anl.gov/~more/

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]

For fixed vectors $a_1,\dots ,a_m$ in a finite-dimensional Euclidean space, defineThe gradient and Hessian matrix of $\Phi =\log F$ areTo derive the first identity, differentiate each exponential function and divide the sum of its gradients by $F$. For the second, differentiating a normalized weight gives $\nabla w_i=2w_i(\bar{a}-a_i)$. Thus $J_{\bar{a}}=-2{\mathrm{Cov}}_w(a_i)$, where the weighted covariance matrix is the sum in the displayed Hessian matrix. Differentiating $2(x-\bar{a})$ completes the calculation.

The weighted covariance matrix is positive semidefinite, so ${\nabla }^2\Phi ⪰2I$. Also $\Phi (x)\ge \Vert x-a_1{\Vert }^2\to \infty$ as $\Vert x\Vert \to \infty$. Therefore $F$ and $\Phi$ share a unique global minimizer, characterized by $x=\bar{a}(x)$. The weights place that minimizer in the convex hull of the centres.

For stable numerical evaluation, subtract the largest exponent before computing the normalized weights. This is the log-sum-exp principle and avoids floating-point overflow without changing the gradient. A naive iteration $x_{n+1}=\bar{a}(x_n)$ need not converge: in one dimension, centres $-1,1$ give $\bar{a}(x)=-\tanh (2x)$ with derivative $-2$ at its unique fixed point. A Newton root-finding iteration or a suitable quasi-Newton method instead uses the positive curvature of $\Phi$.

Set $p=x^{k+1}-x^k={\alpha }^k{s}^k$ and $y=\nabla f(x^{k+1})-\nabla f(x^k)$. The Quasi-Newton secant equation is $B^{k+1}p=y$. If $B^{k+1}$ is a positive-definite symmetric matrix and $p\ne 0$, it follows thatThe weak curvature part of the Wolfe conditions ensures precisely this necessary condition:The last product is positive because ${\alpha }^k>0$, ${\beta }_2-1<0$, and $s^k$ is a descent direction. This explains why a Quasi-Newton method often uses the Wolfe conditions rather than only the Armijo condition.

Two reasons to prefer more advanced methods for smooth, high-accuracy optimization are:

The question's blanket wording is too strong: the steepest descent method and related gradient algorithms are used in practice, especially when problem size, cheap gradients or simplicity make curvature-based alternatives costly. The objections describe limitations, not universal nonuse.

A quasi-Newton method replaces the Hessian in the Newton system by an efficiently updated approximation $B_n$:The matrices must be nonsingular for the step to exist. Symmetry reflects the true Hessian, and positive definiteness makes every nonzero step a descent direction, since $\nabla f(x_n{)}^T{s}_n=-s_n^T{B}_n{s}_n<0$. Secant updates often enforce the Quasi-Newton secant equation $B_{n+1}{s}_n=\nabla f(x_{n+1})-\nabla f(x_n)$.

Q-superlinear convergence means $\Vert x_{n+1}-x_{\ast }\Vert /\Vert x_n-x_{\ast }\Vert \to 0$, unless the sequence terminates exactly. A sufficient Dennis-Moré condition isassuming $x_n\to x_{\ast }$, $\nabla f(x_{\ast })=0$, continuous Hessian near $x_{\ast }$ and nonsingular $H_{\ast }$. Only accuracy on the actual step direction is required; full matrix convergence $B_n\to H_{\ast }$ is sufficient but stronger.

To prove the assertion, continuity of the Hessian along the short segment from $x_n$ to $x_{n+1}$ givesNonsingularity of $H_{\ast }$ and $\nabla f(x_{\ast }+e)=H_{\ast }e+o(\Vert e\Vert )$ give a constant $C$ with $\Vert e\Vert \le C\Vert \nabla f(x_{\ast }+e)\Vert$ near zero. Writing $e_n=x_n-x_{\ast }$, we obtainThus $\Vert e_{n+1}\Vert /\Vert e_n\Vert \le {\epsilon }_n/(1-{\epsilon }_n)\to 0$. This proves sufficiency. It is a local rate result for an already convergent sequence, not a claim that arbitrary unmodified quasi-Newton iterations converge from every starting point.

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]

A Quasi-Newton method replaces the Hessian matrix in Newton's method in optimization by a matrix $B_k$ learned from successive gradients. Solving $B_k{s}_k=-\nabla f(x_k)$ gives a descent direction whenever $B_k$ is a positive-definite symmetric matrix and the gradient is nonzero. After choosing a step size, one updates $B_k$ to satisfy the Quasi-Newton secant equation, rather than calculating every second derivative again.

The NEOS Guide's mathematical account of quasi-Newton methods, deriving the secant condition from an integrated Hessian matrix and describing low-rank updating, including BFGS. The related nonlinear-equation account is neos-guide.org/guide/algorithms/broyden/ and discusses Broyden's method.