Next: Solving the Huber problem
Up: A quasiNewton method for
Previous: Proof
For the sake of completeness, I give the updating formulas of the Hessian as presented
by Nocedal (1980). We define first
In addition, we pose .As described above, when k, the number of iterations, obeys , where m is the storage limit, we
have the usual BFGS update
For k+1 > m we have the special limitedmemory update
 

 
 
 (5) 
 
 
 
It is easy to show that the special updated Hessian is also spd. The LBFGS algorithm is then
Algorithm1
 1.
 Choose , m, , and a symmetric positive definite . Set k=0
 2.
 Compute
 
(6) 
 (7) 
where verifies the Wolfe conditions More and Thuente (1994):
 
(8) 
 (9) 
We always try steplength first.
 3.
 Let =min,. Check if .
 If no: (steepest descent step) and delete the pairs .
 If yes: Update times using the pairs ,
i.e., let
 

 
 
 (10) 
 
 
 
 4.
 Set k:=k+1 and go to 2.
The update is not formed explicitly; instead, we compute with an iterative formula Nocedal (1980).
Liu and Nocedal (1989) propose that we scale the initial symmetric positive definite at each iteration:
 
(11) 
This scaling greatly improves the performances of the method. Liu and Nocedal (1989) show that
the storage limit for largescale problems has little effect on the method's performances.
A common choice for m is m=5 (this is the default in my implementation as well).
Conditions (8) and (9) are satisfied if we use an appropriate line search algorithm. I programmed a
MoreThuente line search algorithm More and Thuente (1994), which ensures sufficient decrease of the objective
function (equation 8) and obeys the curvature condition given in equation (9). We do not describe this
program here. In practice, the initial guess for the Hessian can be the identity matrix ;
then it might be scaled as proposed above.
Liu and Nocedal (1989) prove that the LBFGS algorithm converges to the local minimizer
and that the family of solutions converges Rlinearly
^{}
(remember that the usual BFGS gives qsuperlinear convergence, which is better).
Next: Solving the Huber problem
Up: A quasiNewton method for
Previous: Proof
Stanford Exploration Project
4/27/2000