Next: Minimizing the Huber function
Up: Algorithm for minimizing the
Previous: The limited memory BFGS
The solver works as follows:
- 1.
- Choose
, l,
. Set k=0.
- 2.
- Compute
| ![\begin{eqnarray}
\bold{d}_k&=&-\bold{B}_k\nabla f(\bold{m}_k),\\ \bold{m}_{k+1}&=&\bold{m}_k+\lambda_k\bold{d}_k,
\end{eqnarray}](img253.gif) |
(79) |
| (80) |
where
meets the Wolfe conditions.
- 3.
- Let
=min
,
. Update
times using the pairs
,
i.e., let
| ![\begin{eqnarray}
\bold{B}_{k+1}&=&\bold{v}_k'\bold{v}_{k-1}'\cdots\bold{v}_{k-\h...
...}_{k-1}'\bold{v}_k \nonumber\\ & &+\rho_k\bold{s}_k\bold{s}_k'.
\end{eqnarray}](img259.gif) |
|
| |
| (81) |
| |
| (82) |
- 4.
- Set k=k+1 and go to 2 if the residual power is not small enough.
The update
is not formed explicitly; instead we compute
with an iterative formula
Nocedal (1980). Liu and Nocedal (1989) propose scaling the initial
symmetric positive definite
at each iteration as follows:
| ![\begin{displaymath}
\bold{B}_k^0=\frac{\bold{y}_k'\bold{s}_k}{\parallel\bold{y}_k\parallel_2^2}\bold{B}_0.\end{displaymath}](img262.gif) |
(83) |
This scaling greatly improves the performances of the method.
Liu and Nocedal (1989) show that the storage limit for large-scale problems
has little effects.
A common choice for l is l=5. In practice, the initial guess
for the Hessian is the identity matrix
;
then it might be scaled as proposed in equation (
). The
nonlinear solver as detailed in the previous algorithm converges to
a local minimizer
of
.
Next: Minimizing the Huber function
Up: Algorithm for minimizing the
Previous: The limited memory BFGS
Stanford Exploration Project
5/5/2005