Memoryless BFGS on a nonsmooth convex function: two new results

Abstract

We extend the analysis of Asl and Overton~\cite{AO2021} for memoryless BFGS (also known as L-BFGS-1) using an Armijo-Wolfe line search and applied to the nonsmooth convex function $f(x)=a|x^{(1)}|+{\sum }_{i=2}^n{x}^{(i)}$, where $n\ge 2$ and $a\ge \sqrt{n-1}$. This function is unbounded below, so the method is successful if it generates function values diverging to $-\infty$, and fails otherwise. For scaled L-BFGS-1, we sharpen the sufficient condition for % az{convergence of the absolute normalized search directions} in Theorem~3.1 of failure in \cite{AO2021} from $a\ge 2\sqrt{n-1}$ to $a\ge \sqrt{3(n-1)}$. For the unscaled version, we prove success for every $a$: either the method generates a direction along which no Armijo-Wolfe step exists, certifying unboundedness below, or its function values diverge to $-\infty$. Both results are consistent with the numerical experiments in \cite{AO2021}. Both proofs given here were derived with help from GPT 6 in discussions directed by the first author and corrected and rephrased afterward.