In this paper
AbstractIntroductionScaled and unscaled memoryless BFGSLine search conditions and basic factsA sharpened convergence bound for scaled L-BFGS-1Success of unscaled L-BFGS-1ReferencesWorksMathematics
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 , where and . This function is unbounded below, so the method is successful if it generates function values diverging to , 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 to . For the unscaled version, we prove success for every : either the method generates a direction along which no Armijo-Wolfe step exists, certifying unboundedness below, or its function values diverge to . 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.
Introduction
Asl and Overton [2] studied the effect of scaling on memoryless BFGS, also called L-BFGS-1, using an Armijo-Wolfe line search, applied to the nonsmooth function
This function is convex and unbounded below. It is differentiable precisely when , with
Here denotes the all-ones vector. Note that although is unbounded below, it is bounded below along the line defined by the negative gradient direction from any point with , since . The case is of no interest since is unbounded below along such negative gradient directions. Throughout the rest of this article we continue to use the same definitions and notation as in [2] and introduce a notation only if it is new. Since is unbounded below, we say that a method to minimize is successful if it generates function values diverging to and fails otherwise.
Theorem 3.1 of [2] proves convergence of the absolute normalized search directions of the scaled method when . With some additional assumptions on the line search, this guarantees failure of L-BFGS-1. The experiments in Section 4 of that paper suggest that suffices. Section 2 of this article proves this stronger result and gives a geometric error estimation for . These results also apply to the corresponding Theorem 3.2.1 in the first author’s dissertation [1].
§ 3 addresses the contrasting behavior of the unscaled method. Figure 5 of [2] reports no failures for unscaled memoryless BFGS in the experiments considered there, and Section 5 leaves open whether the unscaled method can converge to a nonoptimal point. We resolve the application of scaled L-BFGS-1 to (1.1) with an Armijo–Wolfe line search; a bounded-below infinite run is impossible. The result holds for all .
These results form an addendum to [2]; the original theorems remain valid. The new proof replaces the monotone-subsequence argument of Appendix B with a direct estimate of the error relative to a fixed point. This particular convergence argument was not familiar to the authors at the time. The two proofs arose through the first author’s directed discussions with GPT 6 agents. The proofs were later corrected, verified and rephrased by the authors.
Scaled and unscaled memoryless BFGS
Write as defined in (1.2) and start with and . After accepting a step , define
For , memoryless BFGS computes
Thus only the latest correction pair is used. The two choices considered here are
These are the standard definitions; see Nocedal and Wright [3 Section 7.2, equations (7.20) and (7.22)]. In particular, unscaled L-BFGS resets the initial matrix to the identity at every iteration.
Line search conditions and basic facts
We use the convention of [2 Section 2], that a step satisfies the Armijo-Wolfe conditions if
with .
As in [2 Section 2], we say that memoryless BFGS succeeds if it identifies the fact that is unbounded below either because it generates a direction for which no steplength satisfying the Armijo-Wolfe conditions exists (in which case the function must be unbounded below) or, alternatively, that it generates a sequence for which Armijo-Wolfe steps always exist, with . If neither event takes place, is bounded below, which is regarded as failure, since is unbounded below.
A sharpened convergence bound for scaled L-BFGS-1
For scaled L-BFGS-1, [2 Lemma 2.1] shows that if , then
alternates in sign with and that satisfies
Note that the recurrence in (8) is exactly equation (27) of [2]. Then [2 Theorem 2.3] guarantees that consequently, provided , the L-BFGS-1 method generates a sequence of iterates and search directions for which Armijo–Wolfe steps always exist and hence the method is well-defined.
Theorem 3.1 of [2] proves that the sequence converges when . We now weaken this assumption to for any Armijo–Wolfe line search. At the end of this section we state and justify the resulting failure guarantees, distinguishing arbitrary Armijo–Wolfe line searches from the specific bracketing search in [2 Algorithm 2].
Theorem 2.1 (Sharpening of [2 Theorem 3.1]). Let . The sequence converges to
Proof. As is shown in [2 Lemma 2.1], for , so all iterates lie in . Clearly in (9) satisfies and . That is, is a fixed-point of . It is easy to see that with some rearrangement of (9). Substituting by as well as by in the numerator of
we arrive at the following factorization
Now define the right factor in (10) as
Hence, . For , it is easy to check that
Suppose first that . Since ,
and hence
Together with , this shows that throughout . Moreover, on , so is continuous on the compact interval . Therefore its maximum absolute value is attained and satisfies
Applying (10) repeatedly gives
which proves convergence for .
If , then and , so the preceding strict contraction bound does not apply. However, the prescribed initial value in (8) is . Since , it follows that for every . Thus convergence also holds in this boundary case. □
Theorem 2.1 applies to any line search satisfying (1.6)–(1.7); it does not require the bracketing search of [2, Algorithm 2]. Convergence of alone does not establish failure of the method. The two distinct sufficient conditions for failure in [2, Theorems 3.8 and 3.11] extend to as follows.
For an arbitrary Armijo–Wolfe line search, add the additional condition
To see why this suffices, set ,
The Armijo inequality gives , see [2 Lemma 3.3]. Adding this inequality at two consecutive iterations and using the sign change yields, as in [2 Corollary 3.5],
where the final inequality follows from (2.4), since . Thus there are and such that for every , and hence . This proves the extension of [2, Theorem 3.8] to , including , when (2.4) reduces to .
For an Armijo–Wolfe search satisfying for , no additional restriction on is needed. Indeed, the scaled update gives
where the second equality is the same as in [2, equation (55)]. Again we conclude . The specific bracketing search in [2, Algorithm 2] has this steplength bound when : implies , so the proofs of [2 Lemmas 3.4, 3.9 and 3.10] remain valid. This proves the extension of [2 Theorem 3.11] to the sharpened range, independently of the Armijo parameter.
Under either sufficient condition, for , so
Consequently converges to a finite point . The sign changes give , so . By continuity, , establishing failure since is unbounded below. The iterate-convergence conclusion of [2 Corollary 3.12] also holds under either set of assumptions.
Success of unscaled L-BFGS-1
Theorem 3.1. If we apply unscaled L-BFGS-1 to (1.1), defined by (1.3)–(1.4) with using any Armijo–Wolfe line search, and starting from any point with , the method always succeeds.
Proof. As in [2 Section 2], for this problem memoryless BFGS succeeds if it identifies the fact that is unbounded below either because it generates a direction for which no steplength satisfying the Armijo-Wolfe conditions exists (in which case the function must be unbounded below) or, alternatively, that it generates a sequence for which Armijo-Wolfe steps always exist and .
As in [2], we assume without loss of generality that the initial point has a positive first component, . Furthermore we assume the method generates a sequence for which Armijo-Wolfe steps always exist. We then proceed to prove that the resulting function values diverge to .
For the function (1.1), the Wolfe condition (1.7) forces every accepted step to change the sign of the first component of the update ,
see [2 equations (13) and (14)], whose derivation does not depend on the choice of . Hence, as long as the steps are accepted, has the sign , and implies . Additionally
so
All tail components of each direction, and hence of each step, are equal: this holds for and is preserved by (1.4). Moreover, for an accepted step. Hence, as in Section 2 and [2 equation (19)], we can write
:::
For , let be the scaling parameter of (5), which by (13) is
Substituting this and (14) into (4) yields
where is the identity matrix. Although the unscaled method does not use to scale , the same quantity appears as a coefficient in the updated matrix. From , using (12) we get
In particular, note that the sign change implies that must have the same sign as , i.e.
If is accepted, using the same argument for iteration as we did for iteration we also get
Also from we obtain
Recall
Plugging into (19) we obtain
The right term is positive by (18), so this inequality shows
so
Moving to the left side and using (15) we get
Since is in the direction of descent, and
The second equality comes from recalling . The last strict inequality is from (22).
By the Armijo condition (6),
where the second inequality uses . Summing over gives
since and .
Thus, if Armijo–Wolfe steps exist at every iteration, the function values diverge to . If instead no Armijo–Wolfe step exists at some iteration, the method succeeds by identifying a direction along which is unbounded below, as discussed in § 1.2. These two alternatives establish that the unscaled method always succeeds.
References
- [1]A. Asl. Behavior of the Limited-Memory BFGS Method on Nonsmooth Optimization Problems in Theory and Practice. Ph.D. dissertation, Department of Computer Science, New York University, May 2020. https://cs.nyu.edu/media/publications/asl_thesis_final_UtpolSlu.pdf.
- [2]A. Asl and M. L. Overton. Analysis of limited-memory BFGS on a class of nonsmooth convex functions. IMA Journal of Numerical Analysis, 41(1):1–27, 2021. doi:10.1093/imanum/drz052.
- [3]J. Nocedal and S. J. Wright. Numerical Optimization. Springer Series in Operations Research and Financial Engineering. Springer, New York, second edition, 2006. doi:10.1007/978-0-387-40065-5.DOI