2
$\begingroup$

In the BFGS method we perform iterations by calculating an approximation $\boldsymbol{H}_k$ to the inverse Hessian $\boldsymbol{H}$ of the objective function. This method belongs to a family of methods in which $\boldsymbol{H}_k$ is guaranteed to preserve the positive definite nature of $\boldsymbol{H}$ for all $k$, provided the line search is exact.

Now, suppose the Hessian is a banded matrix, can we assure that $\boldsymbol{H}_k$ will also be banded? If not - is there any other quasi-Newton method that guarantees this?

$\endgroup$
5
  • $\begingroup$ The inverse Hessian being banded sounds like it is quite an unusual property to have. $\endgroup$ – Federico Poloni Apr 2 '20 at 13:55
  • $\begingroup$ "Inverse Hessian" still appears in the first row. Is $H_k$ an approximation of $H$ or of $H^{-1}$? Note that: (1) typical BFGS implementations construct an approximation to $H^{-1}$ (2) in general there is no reason to expect the inverse of a banded matrix to be banded, (3) it is unclear what your goal is here. Speed up BFGS? But it already uses a (different) compact representation of $H_k$ and should have a cost that scales linearly with $n$ (at least until the number of steps $k$ becomes significant). $\endgroup$ – Federico Poloni Apr 2 '20 at 15:40
  • $\begingroup$ BFGS can be implemented either in terms of a factorization of the Hessian that is updated at each iteration or an approximate inverse Hessian that is updated at each iteration. Either way, these matrices are typically fully dense, even if the actual Hessian of the objective function is sparse or banded. $\endgroup$ – Brian Borchers Apr 2 '20 at 15:52
  • 1
    $\begingroup$ There are also "limited memory" versions of the BFGS method that keep only the last $m$ update vectors where $m$ is typically something like 10 to 20. $\endgroup$ – Brian Borchers Apr 2 '20 at 15:55
  • $\begingroup$ There are results on approximating Hessians solving the secant equation while imposing some sparsity structure but I do not know if such methods will still be categorized under BFGS. Some searches for "sparsity preserving quasi newton" should lead you in the right direction $\endgroup$ – whpowell96 Apr 2 '20 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.