2
$\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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.