Quasi-Newton method

Quasi-Newton methods are methods used to either find zeroes or local maxima and minima of functions, as an alternative to Newton's method. They can be used if the Jacobian or Hessian is unavailable or is too expensive to compute at every iteration. The "full" Newton's method requires the Jacobian in order to search for zeros, or the Hessian for finding extrema.

Search for zeros: root findingEdit

Newton's method to find zeroes of a function   of multiple variables is given by  , where   is the left inverse of the Jacobian matrix   of   evaluated for  .

Strictly speaking, any method that replaces the exact Jacobian   with an approximation is a quasi-Newton method.[1] For instance, the chord method (where   is replaced by   for all iterations) is a simple example. The methods given below for optimization 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 the column-updating method, the inverse 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]

Search for extrema: optimizationEdit

Noting that the search for a minimum or maximum of a scalar-valued function is nothing else than the search for the zeroes of the gradient of that function, quasi-Newton methods can be readily applied to find extrema of a function. In other words, if   is the gradient of  , then searching for the zeroes of the vector-valued function   corresponds to the search for the extrema of the scalar-valued function  ; the Jacobian of   now becomes the Hessian of  . The main difference is that the Hessian matrix is a symmetric matrix, unlike the Jacobian when searching for zeroes. Most quasi-Newton methods used in optimization exploit this property.

In optimization, quasi-Newton methods (a special case of variable-metric methods) are algorithms for finding local maxima and minima of functions. Quasi-Newton methods are based on Newton's method to find the stationary point of a function, where the gradient is 0. Newton's method assumes that the function can be locally approximated as a quadratic 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 the Hessian matrix of second derivatives 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 the secant method to find the root of the first derivative for multidimensional problems. In multiple dimensions the secant equation is under-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 by William C. Davidon, a physicist working at Argonne National Laboratory. He developed the first quasi-Newton algorithm in 1959: the DFP 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 the SR1 formula (for "symmetric rank-one"), the BHHH method, the widespread BFGS method (suggested independently by Broyden, Fletcher, Goldfarb, and Shanno, in 1970), and its low-memory extension L-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 maintain positive-definiteness and can be used for indefinite problems. The Broyden'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 the Jacobian (rather than the Hessian).

One of the chief advantages of quasi-Newton methods over Newton's method is that the Hessian matrix (or, in the case of quasi-Newton methods, its approximation)   does not need to be inverted. Newton's method, and its derivatives such as interior point methods, require the Hessian to be inverted, which is typically implemented by solving a system of linear equations and is often quite costly. In contrast, quasi-Newton methods usually generate an estimate of   directly.

As in Newton's method, one uses a second-order approximation to find the minimum of a function  . The Taylor series of   around an iterate is


where ( ) is the gradient, and   an approximation to the Hessian matrix.[4] The gradient of this approximation (with respect to  ) is


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


The Hessian approximation   is chosen to satisfy


which is called the secant equation (the Taylor series of the gradient itself). In more than one dimension   is underdetermined. In one dimension, solving for   and applying the Newton's step with the updated value is equivalent to the secant 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 as Broyden's method) seek a symmetric solution ( ); furthermore, the variants listed below can be motivated by finding an update   that is as close as possible to   in some norm; that is,  , where   is some positive-definite matrix that defines the norm. An approximate initial value   is often sufficient to achieve rapid convergence, although there is no general strategy to choose  .[5] Note that   should be positive-definite. The unknown   is updated applying the Newton's step calculated using the current approximate Hessian matrix  :

  •  , with   chosen to satisfy the Wolfe conditions;
  •  ;
  • The gradient computed at the new point  , and

is used to update the approximate Hessian  , or directly its inverse   using the Sherman–Morrison formula.

  • A key property of the BFGS and DFP updates is that if   is positive-definite, and   is chosen to satisfy the Wolfe conditions, then   is also positive-definite.

The most popular update formulas are:

Broyden family  

Other methods are Pearson's method, McCormick's method, the Powell symmetric Broyden (PSB) method and Greenstadt's method.[2]

Relationship to matrix inversionEdit

When   is a convex quadratic function with positive-definite Hessian  , one would expect the matrices   generated by a quasi-Newton method to converge to the inverse Hessian  . This is indeed the case for the class of quasi-Newton methods based on least-change updates.[6]

Notable implementationsEdit

Implementations of quasi-Newton methods are available in many programming languages. Notable implementations include:

  • GNU Octave uses a form of BFGS in its fsolve function, with trust region extensions.
  • Mathematica includes quasi-Newton solvers.[7]
  • The NAG Library contains several routines[8] for minimizing or maximizing a function[9] which use quasi-Newton algorithms.
  • In MATLAB's Optimization Toolbox, the fminunc function uses (among other methods) the BFGS quasi-Newton method.[10] Many of the constrained methods of the Optimization toolbox use BFGS and the variant L-BFGS.[11]
  • R's optim general-purpose optimizer routine uses the BFGS method by using method="BFGS".[12]
  • Scipy.optimize has fmin_bfgs. In the SciPy extension to Python, the scipy.optimize.minimize function includes, among other methods, a BFGS implementation.[13]

See alsoEdit


  1. ^ Broyden, C. G. (1972). "Quasi-Newton Methods". In Murray, W. (ed.). Numerical Methods for Unconstrained Optimization. London: Academic Press. pp. 87–106. ISBN 0-12-512250-0.
  2. ^ a b c Haelterman, Rob (2009). "Analytical study of the Least Squares Quasi-Newton method for interaction problems". PhD Thesis, Ghent University. Retrieved 2014-08-14.
  3. ^ Rob Haelterman, Dirk Van Eester, Daan Verleyen (2015). "Accelerating the solution of a physics model inside a tokamak using the (Inverse) Column Updating Method". Journal of Computational and Applied Mathematics. 279: 133–144. doi:10.1016/j.cam.2014.11.005.CS1 maint: uses authors parameter (link)
  4. ^ https://mathinsight.org/taylors_theorem_multivariable_introduction
  5. ^ Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization. New York: Springer. pp. 142. ISBN 0-387-98793-2.
  6. ^ Robert Mansel Gower; Peter Richtarik (2015). "Randomized Quasi-Newton Updates are Linearly Convergent Matrix Inversion Algorithms". arXiv:1602.01768 [math.NA].
  7. ^ http://reference.wolfram.com/mathematica/tutorial/UnconstrainedOptimizationQuasiNewtonMethods.html
  8. ^ The Numerical Algorithms Group. "Keyword Index: Quasi-Newton". NAG Library Manual, Mark 23. Retrieved 2012-02-09.
  9. ^ The Numerical Algorithms Group. "E04 – Minimizing or Maximizing a Function" (PDF). NAG Library Manual, Mark 23. Retrieved 2012-02-09.
  10. ^ http://www.mathworks.com/help/toolbox/optim/ug/fminunc.html
  11. ^ http://www.mathworks.com/help/toolbox/optim/ug/brnoxzl.html
  12. ^ [1]
  13. ^ http://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize.html

Further readingEdit