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:
“God damnit, why must all those journalists be such sticklers for detail? Why, they’d hold you to an accurate description of the first time you ever made love, expecting you to remember the color of the room and the shape of the windows.”
—Lyndon Baines Johnson (1908–1973)
“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)
“The type of fig leaf which each culture employs to cover its social taboos offers a twofold description of its morality. It reveals that certain unacknowledged behavior exists and it suggests the form that such behavior takes.”
—Freda Adler (b. 1934)
“The insidiousness of science lies in its claim to be not a subject, but a method. You could ignore a subject; no subject is all-inclusive. But a method can plausibly be applied to anything within the field of consciousness.”
—Katharine Fullerton Gerould (1879–1944)