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)
“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)
“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)
“Women stand related to beautiful nature around us, and the enamoured youth mixes their form with moon and stars, with woods and waters, and the pomp of summer. They heal us of awkwardness by their words and looks. We observe their intellectual influence on the most serious student. They refine and clear his mind: teach him to put a pleasing method into what is dry and difficult.”
—Ralph Waldo Emerson (1803–1882)