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:
“As they are not seen on their way down the streams, it is thought by fishermen that they never return, but waste away and die, clinging to rocks and stumps of trees for an indefinite period; a tragic feature in the scenery of the river bottoms worthy to be remembered with Shakespeare’s description of the sea-floor.”
—Henry David Thoreau (1817–1862)
“Once a child has demonstrated his capacity for independent functioning in any area, his lapses into dependent behavior, even though temporary, make the mother feel that she is being taken advantage of....What only yesterday was a description of the child’s stage in life has become an indictment, a judgment.”
—Elaine Heffner (20th century)
“An intentional object is given by a word or a phrase which gives a description under which.”
—Gertrude Elizabeth Margaret Anscombe (b. 1919)
“I have a new method of poetry. All you got to do is look over your notebooks ... or lay down on a couch, and think of anything that comes into your head, especially the miseries.... Then arrange in lines of two, three or four words each, don’t bother about sentences, in sections of two, three or four lines each.”
—Allen Ginsberg (b. 1926)