  The motivation to study the behavior of limited-memory BFGS (L-BFGS) on
nonsmooth optimization problems is based on two empirical observations: the
widespread success of L-BFGS in solving large-scale smooth optimization
problems, and the effectiveness of the full BFGS method in solving small to
medium-sized nonsmooth optimization problems, based on using a gradient, not a
subgradient, oracle paradigm. We first summarize our theoretical results on the
behavior of the scaled L-BFGS method with one update applied to a simple convex
nonsmooth function that is unbounded below, stating conditions under which the
method converges to a non-optimal point regardless of the starting point. We
then turn to empirically investigating whether the same phenomenon holds more
generally,focusing on a difficult problem of Nesterov, as well as eigenvalue
optimization problems arising in semidefinite programming applications. We find
that when applied to a nonsmooth function directly, L-BFGS, especially its
scaled variant, often breaks down with a poor approximation to an optimal
solution, in sharp contrast to full BFGS. Unscaled L-BFGS is less prone to
breakdown but conducts far more function evaluations per iteration than scaled
L-BFGS does, and thus it is slow. Nonetheless, it is often the case that both
variants obtain better results than the provably convergent, but slow,
subgradient method. On the other hand, when applied to Nesterov's smooth
approximation of a nonsmooth function, scaled L-BFGS is generally much more
efficient than unscaled L-BFGS, often obtaining good results even when the
problem is quite ill-conditioned. Summarizing, for large-scale nonsmooth
optimization problems for which full BFGS and other methods for nonsmooth
optimization are not practical, it is often better to apply L-BFGS to a smooth
approximation of a nonsmooth problem than to apply it directly to the nonsmooth
problem.
