1
$\begingroup$

I have implemented a Quasi-Newton method based on the Hessian approximation. I am noticing that the algorithm takes too many iterations to converge, even though it does converge. What I am not able to understand is the really small step size ($l_{\infty} \text{norm} \le 10^{-5}$) for many of these iterations. The problem is ill-conditioned and I read that Quasi-Newton can degenerate to steepest descent for ill-conditioned problems. Is that what is happening? If so, is there any intuition about the step size being so small? I have tried the damping modification given in section 18.3 from Nocedal and Wright. However, it is not improving the step length, since, the damping criterion itself becomes very small. Is there some other principled way to ensure larger step size? Will larger step size help with faster convergence?

$\endgroup$
  • $\begingroup$ There are many "quasi-Newton" methods. Which one are you using? $\endgroup$ – Wolfgang Bangerth Jun 14 '16 at 18:42
  • $\begingroup$ I have implemented limited memory BFGS. I am using the Hessian approximation formulation, not the approximation of the Hessian inverse. $\endgroup$ – haripkannan Jun 14 '16 at 19:14
  • $\begingroup$ It is possible that full NR takes small steps when approaching a critical point of multiplicity more than one. Perhaps the Hessian approximation is singular, or nearly so. $\endgroup$ – hardmath Jun 14 '16 at 20:16
  • $\begingroup$ The problem is supposed to have an unique minimizer. Since, the problem is strictly convex. Yes, the Hessian approximation can be singular. It is only positive semidefinite away from the optimum. I am working under a trust region framework (by adding a Levenberg-Marquardt like damping matrix). But I see the damping parameter going to zero in the first few iterations (which is another unexpected behavior) and after that the algorithm proceeds as a plain Quasi-Newton method. $\endgroup$ – haripkannan Jun 15 '16 at 5:02
  • $\begingroup$ @hardmath I am wondering whether a singular Hessian approximation will lead to a huge step, instead of a very small step. $\endgroup$ – haripkannan Jun 15 '16 at 9:40

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.