1
$\begingroup$

I have implemented BFGS myself from scratch in order to solve minimization problems. Part of BFGS, as I understand it, is that the approximation to the Hessian is supposed to be positive definite, which means it is supposed to be invertible. I have been following the algorithm outlined here: https://en.wikipedia.org/wiki/Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm#Algorithm . This is how we update our approximation to the Hessian:

$$ B_{k+1} = B_k + \frac{ y_k y_k ^T }{y_k^T s_k} – \frac{ B_k s_k s_k^T B_k}{s_k^T B_k s_k} $$

where $ y_k = \nabla f(x_k) - \nabla f(x_{k-1}) $ and

$s_k = -1 * B_k^{-1} \nabla f (x_k)$

I made a few slight modifications to the standard BFGS algorithm in my implementation:

1) I check to see if $y_k^T s_k$ is negative. If it is, then this has the potential to make the next update $B_k$ negative, too. So, I switch to an alternative update when that term is negative:

$$ B_{k+1} = B_k + \frac{ y_k y_k ^T }{y_k^T y_k} – \frac{ B_k s_k s_k^T B_k}{s_k^T B_k s_k} $$ 2) I have a check for when the direction it is about to step $d_k$ might be too large or too small compared to the magnitude of the gradient: if either $||d_k|| \ge 100*||\nabla f|| $ or $||\nabla f^T * d_k|| \le 10^{-4} * ||\nabla f||*||d_k||$. If either one of those are true, then I just use the gradient step, $d_k = \nabla f $.

Now I am running into an issue where the gradient somehow becomes very large: $\nabla f$ becomes very large. So, when I go to update $s_k$, it becomes very large: $s_k = -1 * B_k^{-1} \nabla f$. Then, this causes the next iterate of $B_k$ to be very large. Eventually, the matrix becomes so large that np.linalg.inv(B_k) throws an error and will not be inverted.

How do I protect against this happening? Do I need another check, and why isn’t my existing preventative measure working for this?

$\endgroup$
  • 3
    $\begingroup$ You haven't told us anything about your particular function and its gradient. A standard trick in the BFGS method whenever you get into numerical trouble is to restart the method with $B=I$ and a gradient descent step. $\endgroup$ – Brian Borchers May 28 '18 at 14:26
  • 1
    $\begingroup$ Once $B_{k}$ is nearly singular, you get crazy search directions. Thus it''s wise to restart the method with a steepest descent step as soon as $B_{k}$ becomes nearly singular. $\endgroup$ – Brian Borchers May 28 '18 at 23:50
  • 2
    $\begingroup$ Given you are not sharing the objective function, some trivial suggestions: 1) is the gradient computed correctly? 2) have you tried with finite differences? 3) Does the update matrix get singular (look at the eigenvalues...)? $\endgroup$ – AndreaCassioli May 29 '18 at 20:04
  • 1
    $\begingroup$ There is a chance that for your problem the Hessian is ill conditioned or is nearly singular. In such cases, you will get huge Newton steps. Try to put your BFGS algorithm within a trust-region framework. Refer, Nocedal and Wright or if possible the book Trust region methods by Conn et al. $\endgroup$ – haripkannan May 30 '18 at 14:09
  • 1
    $\begingroup$ @Hunle Did you look into trust-region methods? You need to "dampen" the Newton step with a trust-region. $\endgroup$ – haripkannan Jun 7 '18 at 15:17

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.