Fast log-decon with a quasi-Newton solver

An efficient algorithm for solving nonlinear problems

The solver works as follows:

1. Choose $\bold{m}_0$ , $l$ , $\bold{B}_0$ . Set $k=0$ .
2. Compute
   

   $$\bold{d}_k = -\bold{B}_k\nabla f(\bold{m}_k),$$ (8)

   $$\bold{m}_{k+1} = \bold{m}_k+\lambda_k\bold{d}_k,$$ (9)

   
   where $\lambda_k$ meets the Wolfe conditions.
3. Let $\hat{l}$ =min$\{k$ , $l-1\}$ . Update $\bold{B}_0$ $\hat{l}+1$ times using the pairs $\{\bold{y}_i,\bold{s}_i\}_{j=k-\hat{l}}^k$ , i.e., let
   

   $$\bold{B}_{k+1} = \bold{v}_k'\bold{v}_{k-1}'\cdots\bold{v}_{k-\hat{l}}'\bold{B}_0\bold{v}_{k-\hat{l}} \cdots\bold{v}_{k-1}\bold{v}_k$$

   $$+\bold{v}_k'\cdots\bold{v}_{k-\hat{l}+1}'\rho_{k-\hat{l}}\bold{s}_{k-\hat{l}} \bold{s}_{k-\hat{l}}'\bold{v}_{k-\hat{l}+1}\cdots\bold{v}_k$$

   $$\vdots$$ (10)

   $$+\bold{v}_k'\rho_{k-1}\bold{s}_{k-1}\bold{s}_{k-1}'\bold{v}_k$$

   $$+\rho_k\bold{s}_k\bold{s}_k'.$$ (11)

   
   
4. Set $k=k+1$ and go to 2 if the residual power is not small enough.

The update $\bold{B}_{k+1}$ is not formed explicitly; instead we compute $\bold{d}_k=-\bold{B}_k\nabla f(\bold{x}_k)$ with an iterative formula Nocedal (1980). Liu and Nocedal (1989) propose scaling the initial symmetric positive definite $\bold{B}_0$ at each iteration as follows:

$$\bold{B}_k^0=\frac{\bold{y}_k'\bold{s}_k}{\parallel\bold{y}_k\parallel_2^2}\bold{B}_0.$$ (12)

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 $\bold{B}_0$ for the Hessian is the identity matrix $\bold{I}$ ; then it might be scaled as proposed in equation (12). The nonlinear solver as detailed in the previous algorithm converges to a local minimizer $\bold{m}^*$ of $f({\bf m})$ .

Fast log-decon with a quasi-Newton solver