# Effect of Initial guess B (approximate Hessian) on BFGS algorithm

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.

## 1 Answer

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.

• 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 – Mohsin Apr 10 '14 at 9:22
• 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. – Wolfgang Bangerth Apr 10 '14 at 12:59
• 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. – Wolfgang Bangerth Apr 10 '14 at 13:00
• 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}' – Mohsin Apr 11 '14 at 8:13
• 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. – Wolfgang Bangerth Apr 11 '14 at 12:30