This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Quasi-Newton method" – news ·newspapers ·books ·scholar ·JSTOR(January 2025) (Learn how and when to remove this message)

Innumerical analysis, aquasi-Newton method is aniterative numerical method used either tofind zeroes or tofind local maxima and minima of functions via an iterativerecurrence formula much like the one forNewton's method, except using approximations of thederivatives of the functions in place of exact derivatives. Newton's method requires theJacobian matrix of allpartial derivatives of a multivariate function when used to search for zeros or theHessian matrix when usedfor finding extrema. Quasi-Newton methods, on the other hand, can be used when the Jacobian matrices or Hessian matrices are unavailable or are impractical to compute at every iteration.

Someiterative methods that reduce to Newton's method, such assequential quadratic programming, may also be considered quasi-Newton methods.

Newton's method to find zeroes of a function${\displaystyle g}$ of multiple variables is given by${\displaystyle x_{n+1}=x_n-[J_g(x_n){]}^{-1}g(x_n)}$, where${\displaystyle [J_g(x_n){]}^{-1}}$ is theleft inverse of theJacobian matrix${\displaystyle J_g(x_n)}$ of${\displaystyle g}$ evaluated for${\displaystyle x_n}$.

Strictly speaking, any method that replaces the exact Jacobian${\displaystyle J_g(x_n)}$ with an approximation is a quasi-Newton method.^[1] For instance, the chord method (where${\displaystyle J_g(x_n)}$ is replaced by${\displaystyle J_g(x_0)}$ for all iterations) is a simple example. The methods given below foroptimization refer to an important subclass of quasi-Newton methods,secant methods.^[2]

Using methods developed to find extrema in order to find zeroes is not always a good idea, as the majority of the methods used to find extrema require that the matrix that is used is symmetrical. While this holds in the context of the search for extrema, it rarely holds when searching for zeroes.Broyden's "good" and "bad" methods are two methods commonly used to find extrema that can also be applied to find zeroes. Other methods that can be used are thecolumn-updating method, theinverse column-updating method, the quasi-Newton least squares method and the quasi-Newton inverse least squares method.

More recently quasi-Newton methods have been applied to find the solution of multiple coupled systems of equations (e.g. fluid–structure interaction problems or interaction problems in physics). They allow the solution to be found by solving each constituent system separately (which is simpler than the global system) in a cyclic, iterative fashion until the solution of the global system is found.^[2][3]

The search for a minimum or maximum of a scalar-valued function is closely related to the search for the zeroes of thegradient of that function. Therefore, quasi-Newton methods can be readily applied to find extrema of a function. In other words, if${\displaystyle g}$ is the gradient of${\displaystyle f}$, then searching for the zeroes of the vector-valued function${\displaystyle g}$ corresponds to the search for the extrema of the scalar-valued function${\displaystyle f}$; the Jacobian of${\displaystyle g}$ now becomes the Hessian of${\displaystyle f}$. The main difference is thatthe Hessian matrix is a symmetric matrix, unlike the Jacobian whensearching for zeroes. Most quasi-Newton methods used in optimization exploit this symmetry.

Inoptimization,quasi-Newton methods (a special case ofvariable-metric methods) are algorithms for finding localmaxima and minima offunctions. Quasi-Newton methods for optimization are based onNewton's method to find thestationary points of a function, points where the gradient is 0. Newton's method assumes that the function can be locally approximated as aquadratic in the region around the optimum, and uses the first and second derivatives to find the stationary point. In higher dimensions, Newton's method uses the gradient and theHessian matrix of secondderivatives of the function to be minimized.

In quasi-Newton methods the Hessian matrix does not need to be computed. The Hessian is updated by analyzing successive gradient vectors instead. Quasi-Newton methods are a generalization of thesecant method to find the root of the first derivative for multidimensional problems. In multiple dimensions the secant equation isunder-determined, and quasi-Newton methods differ in how they constrain the solution, typically by adding a simple low-rank update to the current estimate of the Hessian.

The first quasi-Newton algorithm was proposed byWilliam C. Davidon, a physicist working atArgonne National Laboratory. He developed the first quasi-Newton algorithm in 1959: theDFP updating formula, which was later popularized by Fletcher and Powell in 1963, but is rarely used today. The most common quasi-Newton algorithms are currently theSR1 formula (for "symmetric rank-one"), theBHHH method, the widespreadBFGS method (suggested independently byBroyden,Fletcher,Goldfarb, andShanno, in 1970), and its low-memory extensionL-BFGS. The Broyden's class is a linear combination of the DFP and BFGS methods.

The SR1 formula does not guarantee the update matrix to maintainpositive-definiteness and can be used for indefinite problems. TheBroyden's method does not require the update matrix to be symmetric and is used to find the root of a general system of equations (rather than the gradient) by updating theJacobian (rather than the Hessian).

One of the chief advantages of quasi-Newton methods overNewton's method is that theHessian matrix (or, in the case of quasi-Newton methods, its approximation)${\displaystyle B}$ does not need to be inverted. Newton's method, and its derivatives such asinterior point methods, require the Hessian to be inverted, which is typically implemented by solving asystem of linear equations and is often quite costly. In contrast, quasi-Newton methods usually generate an estimate of${\displaystyle B^{-1}}$ directly.

As inNewton's method, one uses a second-order approximation to find the minimum of a function${\displaystyle f(x)}$. TheTaylor series of${\displaystyle f(x)}$ around an iterate is

${\displaystyle f(x_k+\mathrm{\Delta }x)\approx f(x_k)+\mathrm{\nabla }f(x_k{)}^{\mathrm{T}}\mathrm{\Delta }x+\frac{1}{2}\mathrm{\Delta }{x}^{\mathrm{T}}B\mathrm{\Delta }x,}$

where (${\displaystyle \mathrm{\nabla }f}$) is thegradient, and${\displaystyle B}$ an approximation to theHessian matrix.^[4] The gradient of this approximation (with respect to${\displaystyle \mathrm{\Delta }x}$) is

${\displaystyle \mathrm{\nabla }f(x_k+\mathrm{\Delta }x)\approx \mathrm{\nabla }f(x_k)+B\mathrm{\Delta }x,}$

and setting this gradient to zero (which is the goal of optimization) provides the Newton step:

${\displaystyle \mathrm{\Delta }x=-B^{-1}\mathrm{\nabla }f(x_k).}$

The Hessian approximation${\displaystyle B}$ is chosen to satisfy

${\displaystyle \mathrm{\nabla }f(x_k+\mathrm{\Delta }x)=\mathrm{\nabla }f(x_k)+B\mathrm{\Delta }x,}$

which is called thesecant equation (the Taylor series of the gradient itself). In more than one dimension${\displaystyle B}$ isunderdetermined. In one dimension, solving for${\displaystyle B}$ and applying the Newton's step with the updated value is equivalent to thesecant method. The various quasi-Newton methods differ in their choice of the solution to the secant equation (in one dimension, all the variants are equivalent). Most methods (but with exceptions, such asBroyden's method) seek a symmetric solution (${\displaystyle B^T=B}$); furthermore, the variants listed below can be motivated by finding an update${\displaystyle B_{k+1}}$ that is as close as possible to${\displaystyle B_k}$ in somenorm; that is,${\displaystyle B_{k+1}={\mathrm{argmin}}_B\Vert B-B_k{\Vert }_V}$, where${\displaystyle V}$ is somepositive-definite matrix that defines the norm. An approximate initial value${\displaystyle B_0=\beta I}$ is often sufficient to achieve rapid convergence, although there is no general strategy to choose${\displaystyle \beta }$.^[5] Note that${\displaystyle B_0}$ should be positive-definite. The unknown${\displaystyle x_k}$ is updated applying the Newton's step calculated using the current approximate Hessian matrix${\displaystyle B_k}$:

• ${\displaystyle \mathrm{\Delta }{x}_k=-{\alpha }_k{B}_k^{-1}\mathrm{\nabla }f(x_k)}$, with${\displaystyle \alpha }$ chosen to satisfy theWolfe conditions;
• ${\displaystyle x_{k+1}=x_k+\mathrm{\Delta }{x}_k}$;
• The gradient computed at the new point${\displaystyle \mathrm{\nabla }f(x_{k+1})}$, and

${\displaystyle y_k=\mathrm{\nabla }f(x_{k+1})-\mathrm{\nabla }f(x_k)}$

is used to update the approximate Hessian${\displaystyle B_{k+1}}$, or directly its inverse${\displaystyle H_{k+1}=B_{k+1}^{-1}}$ using theSherman–Morrison formula.

• A key property of the BFGS and DFP updates is that if${\displaystyle B_k}$ is positive-definite, and${\displaystyle {\alpha }_k}$ is chosen to satisfy the Wolfe conditions, then${\displaystyle B_{k+1}}$ is also positive-definite.

The most popular update formulas are:

Method	${\displaystyle {\displaystyle B_{k+1}=}}$	${\displaystyle H_{k+1}=B_{k+1}^{-1}=}$
BFGS	${\displaystyle B_k+\frac{y_k{y}_k^{\mathrm{T}}}{y_k^{\mathrm{T}}\mathrm{\Delta }{x}_k}-\frac{B_k\mathrm{\Delta }{x}_k(B_k\mathrm{\Delta }{x}_k{)}^{\mathrm{T}}}{\mathrm{\Delta }{x}_k^{\mathrm{T}}{B}_k\mathrm{\Delta }{x}_k}}$	${\displaystyle \left(I-\frac{\mathrm{\Delta }{x}_k{y}_k^{\mathrm{T}}}{y_k^{\mathrm{T}}\mathrm{\Delta }{x}_k}\right)H_k\left(I-\frac{y_k\mathrm{\Delta }{x}_k^{\mathrm{T}}}{y_k^{\mathrm{T}}\mathrm{\Delta }{x}_k}\right)+\frac{\mathrm{\Delta }{x}_k\mathrm{\Delta }{x}_k^{\mathrm{T}}}{y_k^{\mathrm{T}}\mathrm{\Delta }{x}_k}}$
Broyden	${\displaystyle B_k+\frac{y_k-B_k\mathrm{\Delta }{x}_k}{\mathrm{\Delta }{x}_k^{\mathrm{T}}\mathrm{\Delta }{x}_k}\mathrm{\Delta }{x}_k^{\mathrm{T}}}$	${\displaystyle H_k+\frac{(\mathrm{\Delta }{x}_k-H_k{y}_k)\mathrm{\Delta }{x}_k^{\mathrm{T}}{H}_k}{\mathrm{\Delta }{x}_k^{\mathrm{T}}{H}_k{y}_k}}$
Broyden family	${\displaystyle (1-{\phi }_k)B_{k+1}^{\text{BFGS}}+{\phi }_k{B}_{k+1}^{\text{DFP}},\phi \in [0,1]}$
DFP	${\displaystyle \left(I-\frac{y_k\mathrm{\Delta }{x}_k^{\mathrm{T}}}{y_k^{\mathrm{T}}\mathrm{\Delta }{x}_k}\right)B_k\left(I-\frac{\mathrm{\Delta }{x}_k{y}_k^{\mathrm{T}}}{y_k^{\mathrm{T}}\mathrm{\Delta }{x}_k}\right)+\frac{y_k{y}_k^{\mathrm{T}}}{y_k^{\mathrm{T}}\mathrm{\Delta }{x}_k}}$	${\displaystyle H_k+\frac{\mathrm{\Delta }{x}_k\mathrm{\Delta }{x}_k^{\mathrm{T}}}{\mathrm{\Delta }{x}_k^{\mathrm{T}}{y}_k}-\frac{H_k{y}_k{y}_k^{\mathrm{T}}{H}_k}{y_k^{\mathrm{T}}{H}_k{y}_k}}$
SR1	${\displaystyle B_k+\frac{(y_k-B_k\mathrm{\Delta }{x}_k)(y_k-B_k\mathrm{\Delta }{x}_k{)}^{\mathrm{T}}}{(y_k-B_k\mathrm{\Delta }{x}_k{)}^{\mathrm{T}}\mathrm{\Delta }{x}_k}}$	${\displaystyle H_k+\frac{(\mathrm{\Delta }{x}_k-H_k{y}_k)(\mathrm{\Delta }{x}_k-H_k{y}_k{)}^{\mathrm{T}}}{(\mathrm{\Delta }{x}_k-H_k{y}_k{)}^{\mathrm{T}}{y}_k}}$

Other methods are Pearson's method, McCormick's method, the Powell symmetric Broyden (PSB) method and Greenstadt's method.^[2] These recursive low-rank matrix updates can also represented as an initial matrix plus a low-rank correction. This is theCompact quasi-Newton representation, which is particularly effective forconstrained and/or large problems.

When${\displaystyle f}$ is a convex quadratic function with positive-definite Hessian${\displaystyle B}$, one would expect the matrices${\displaystyle H_k}$ generated by a quasi-Newton method to converge to the inverse Hessian${\displaystyle H=B^{-1}}$. This is indeed the case for the class of quasi-Newton methods based on least-change updates.^[6]

Implementations of quasi-Newton methods are available in many programming languages.

Notable open source implementations include:

• GNU Octave uses a form of BFGS in itsfsolve function, withtrust region extensions.
• GNU Scientific Library implements the Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm.
• ALGLIB implements (L)BFGS in C++ and C#
• R'soptim general-purpose optimizer routine uses theBFGS method by usingmethod="BFGS".^[7]
• Scipy.optimize has fmin_bfgs. In theSciPy extension toPython, thescipy.optimize.minimize function includes, among other methods, aBFGS implementation.^[8]

Notable proprietary implementations include:

• Mathematica includes quasi-Newton solvers.^[9]
• TheNAG Library contains several routines^[10] for minimizing or maximizing a function^[11] which use quasi-Newton algorithms.
• In MATLAB'sOptimization Toolbox, thefminunc function uses (among other methods) theBFGS quasi-Newton method.^[12] Many of the constrained methods of the Optimization toolbox useBFGS and the variantL-BFGS.^[13]

• Bonnans, J. F.; Gilbert, J. Ch.;Lemaréchal, C.;Sagastizábal, C. A. (2006).Numerical Optimization : Theoretical and Numerical Aspects (Second ed.). Springer.ISBN 3-540-35445-X.
• Fletcher, Roger (1987),Practical methods of optimization (2nd ed.), New York:John Wiley & Sons,ISBN 978-0-471-91547-8.
• Nocedal, Jorge; Wright, Stephen J. (1999)."Quasi-Newton Methods".Numerical Optimization. New York: Springer. pp. 192–221.ISBN 0-387-98793-2.
• Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. (2007)."Section 10.9. Quasi-Newton or Variable Metric Methods in Multidimensions".Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press.ISBN 978-0-521-88068-8.
• Scales, L. E. (1985).Introduction to Non-Linear Optimization. New York: MacMillan. pp. 84–106.ISBN 0-333-32552-4.

• Quasi-Newton methods

• Articles with short description
• Short description matches Wikidata
• Articles needing additional references from January 2025
• All articles needing additional references