Optimization Online


Behavior of BFGS with an Exact Line Search on Nonsmooth Examples

Adrian S. Lewis(aslewis***at***orie.cornell.edu)
Michael L. Overton(overton***at***cs.nyu.edu)

Abstract: We investigate the behavior of the BFGS algorithm with an exact line search on nonsmooth functions. We show that it may fail on a simple polyhedral example, but that it apparently always succeeds on the Euclidean norm function, spiraling into the origin with a Q-linear rate of convergence; we prove this in the case of two variables. Dixon's theorem implies that the result for the norm holds for all methods in the Broyden class of variable metric methods; we investigate how the limiting behavior of the steplengths depends on the Broyden parameter. Numerical experiments indicate that the convergence properties for $\|x\|$ extend to $\|Ax\|$, where $A$ is an $n \times n$ nonsingular matrix, and that the rate of convergence is independent of $A$ for fixed $n$. Finally, we show that steepest descent with an exact line search converges linearly for any positively homogeneous function that is $C^2$ everywhere except at the origin, but its rate of convergence for $\|Ax\|$ depends on the condition number of $A$, in contrast to BFGS.

Keywords: BFGS, quasi-Newton, nonsmooth, exact line search, Broyden class, Q-linear convergence

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Citation: Submitted to SIAM J. Optimization

Download: [PDF]

Entry Submitted: 12/14/2008
Entry Accepted: 12/15/2008
Entry Last Modified: 12/14/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society