  


Behavior of BFGS with an Exact Line Search on Nonsmooth Examples
Adrian S. Lewis(aslewisorie.cornell.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 Qlinear 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, quasiNewton, nonsmooth, exact line search, Broyden class, Qlinear convergence Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization ) Citation: Submitted to SIAM J. Optimization Download: [PDF] Entry Submitted: 12/14/2008 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  