Site Search

On Sizing and Shifting the BFGS Update within the Sized-Broyden Family of Secant Updates

scientific

Special Seminar Talk - Richard Tapia
September 22, 2005 2:30 PM to 3:30 PM

Summary:

 In the 35 years since it's birth the BFGS Secant method has become the secant method ofchoice in algorithmic methods for unconstrained optimization. Its popularity is a directresult of its observed superior numerical behavior. However, there are situations where theBFGS secant method is not effective and the Hessian approximations that it generateshave excessively large eigenvalues. In a numerical study, Contreras and Tapia demonstratedthat in these situations there is value in sizing the BFGS secant update using the Oren-Luenberger sizing factor, i.e., multiplying the Hessian approximation by a constant before updating. Aconclusion of the current study is that there is value in following an Oren-Luenberger sizing of the BFGS update with a shift of the BFGS in the Broyden class of secant updates. Our motivationfor such a strategy comes from the fact that if the BFGS update is producing updates with large eigenvalues, then sizing may contribute to near singularity, and shifting can help compensate for thisdeficiency. Our main contribution is that we obtain a shift formula in closed form by minimizing a weighted form of the Byrd--Nocedal measure over a sized Broyden family of secant updates.Numerically, our most effective shift is the one that gives the member of the class which is closest to steepest descent in the Byrd--Nocedal measure. While this choice is a surprise it is supported bynumerical experimentation.

Lecture #tapia2

Supplements
Note: If extra notes were made available, they may appear at the end of the presentation materials in the supplement file.
Streaming Video
This is a high-quality streaming video encoded with MPEG-4 and with 640x480 resolution.
  • Windows and Mac users, QuickTime 7 or later required Get QuickTime
  • Linux users, please see our Linux Help Page on how to view our streaming videos.

QuickTime and the QuickTime Logo are trademarks of Apple Inc., registered in the U.S. and other countries. The Get QuickTime Badge is a trademark of Apple Inc., used with permission.
Buy the DVD
If none of the options work for you, you can always buy the DVD of this lecture. The videos are sold at cost for $20USD (shipping included). Please click here to send an email to MSRI to purchase the DVD.