2
$\begingroup$

I was trying to find results about the rate of convergence for the L-BFGS algorithm (in the nonlinear case).

What I end up with so far is that

  • the BFGS-Algorithm converges Q-superlinearly
  • this 50 year old Paper characterizing superlinear convergence of quasi-newton methods
  • Theorem 3.5. (and 3.6.) in Nocedal's Numerical Optimization which do not give conditions that make sure the step length equals one for all but finitely many iterations.

Is there maybe a known negative result which I did not find?

Any help is appreciated, thank you in advance!

$\endgroup$
  • $\begingroup$ @Alvaro Maggiar No, this is wrong. Do not forget to watch equation (3.32), too. I cite: "Hence, we have the surprising (and delightful) result that a superlinear convergence rate can be attained even if the sequence of quasi-Newton matrices $B_k$ does not converge to $\nabla^2f (x ^∗)$; it suffices that the $B_k$ become increasingly accurate approximations to $\nabla^2f (x^*)$ along the search directions $p_k$." $\endgroup$ – Max Oct 14 '15 at 20:54
  • $\begingroup$ my comment sounds so rude^^ sorry fo that. it was not meant rude in any way :-) thank you for you time. $\endgroup$ – Max Oct 14 '15 at 21:01
  • $\begingroup$ I have linked the wrong version of his book. I edited the link, now it's the correct one. That explains why you didnt find what I meant. (The equations and theorems have slightly different numbers) $\endgroup$ – Max Oct 14 '15 at 21:25

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.