Description of The Method
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. The gradient of this approximation (with respect to ) is
and setting this gradient to zero 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 under determined. 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 matrix that defines the norm. An approximate initial value of is often sufficient to achieve rapid convergence. 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:
| Method | ||
|---|---|---|
| DFP | ||
| BFGS |  |
|
| Broyden | ||
| Broyden family | ||
| SR1 |
Read more about this topic: Quasi-Newton Method
Famous quotes containing the words description of the, description of, description and/or method:
“Why does philosophy use concepts and why does faith use symbols if both try to express the same ultimate? The answer, of course, is that the relation to the ultimate is not the same in each case. The philosophical relation is in principle a detached description of the basic structure in which the ultimate manifests itself. The relation of faith is in principle an involved expression of concern about the meaning of the ultimate for the faithful.”
—Paul Tillich (1886–1965)
“It is possible—indeed possible even according to the old conception of logic—to give in advance a description of all ‘true’ logical propositions. Hence there can never be surprises in logic.”
—Ludwig Wittgenstein (1889–1951)
“A sound mind in a sound body, is a short, but full description of a happy state in this World: he that has these two, has little more to wish for; and he that wants either of them, will be little the better for anything else.”
—John Locke (1632–1704)
“Methinks the human method of expression by sound of tongue is very elementary, & ought to be substituted for some ingenious invention which should be able to give vent to at least six coherent sentences at once.”
—Virginia Woolf (1882–1941)