2
$\begingroup$

I am trying to implement BFGS. The purpose is to approximate Hessian matrix only (not using the quasi-newton optimization steps), so i am using steepest ascent for optimization. What I observe is that the final Hessian approximate is very sensitive to the initial guess of Hessian. If I start with Identity matrix, most of the singular values of final hessian is closed to 1. Similarly if I start with any multiple of identity (let's say 5*I), the singular values of final Hessian is closed to 5.

It is a maximization problem, and also the solution is not unique so i expect a negative semi-definite Hessian matrix.

I hope my question is clear.

Thanks in advance.

| cite | improve this question | |
$\endgroup$
3
$\begingroup$

There are two standard choices for the initial approximation of $B$ in BFGS: Either you choose $B=\frac{\|g_0\|}{\delta} I$ where $\|g_0\|$ is the gradient in the very first iteration and $\delta$ a "typical step size" from $x_k$ to $x_{k+1}$. Or you choose $B=\frac{y_1^T y_1}{y_1^T s_1}I$ using the standard notation used for BFGS.

The (excellent) book by Nocedal and Wright has more details.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Many thanks for your answer. But is it normal to observe such initial guess effect on final estimate of Hessian? I felt like something is wrong with my implementation, my line search was ad-hoc (not based on Wolfe criteria) so I implemented Damped BFGS method but it doesn't help and the results are same. Can you also comment on that? Thanks $\endgroup$ – Mohsin Apr 10 '14 at 9:22
  • $\begingroup$ If you do a few hundred BFGS iterations (in particular, many times the number of variables), then the effect of the initial guess for $B$ may have disappeared, but if you only do a few iterations, then the initial guess will still be prominent. $\endgroup$ – Wolfgang Bangerth Apr 10 '14 at 12:59
  • $\begingroup$ By the way, BFGS always constructs positive definite matrices, regardless of the fact that the Hessian of your objective function may be indefinite or negative definite. $\endgroup$ – Wolfgang Bangerth Apr 10 '14 at 13:00
  • $\begingroup$ Thanks again, but from 'BFGS always constructs positive definite matrices' do you also mean that the curvature condition should always be 's_k^\top y_k > 0' or it should be 's_k^\top y_k < 0' where 's_k = u_{k+1} - u_k' and 'y_k = \nabla J_{k+1} - \nabla J_{k}' $\endgroup$ – Mohsin Apr 11 '14 at 8:13
  • $\begingroup$ What I mean is that if you apply BFGS to a minimization problem and you choose the step length appropriately, the matrix $B$ will always be positive definite even if the Hessian $H$ is not. Nocedal and Wright have much more material on this, I would recommend taking a look at their book. $\endgroup$ – Wolfgang Bangerth Apr 11 '14 at 12:30

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.