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)
“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)
“No method nor discipline can supersede the necessity of being forever on the alert. What is a course of history or philosophy, or poetry, no matter how well selected, or the best society, or the most admirable routine of life, compared with the discipline of looking always at what is to be seen? Will you be a reader, a student merely, or a seer? Read your fate, see what is before you, and walk on into futurity.”
—Henry David Thoreau (1817–1862)