betaFeedback

WorksMathematics

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)∣+∑i=2nx(i)f(x)=a|x^{(1)}|+\sum_{i=2}^n x^{(i)}, where n≥2n\ge2 and a≥n−1a \geq \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≥2n−1a\ge2\sqrt{n-1} to a≥3(n−1)a\ge\sqrt{3(n-1)}. For the unscaled version, we prove success for every aa: 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.

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

f(x)=a∣x(1)∣+∑i=2nx(i),n≥2,r:=n−1,a≥r.(1)f(x)=a|x^{(1)}|+\sum_{i=2}^{n}x^{(i)},\qquad n\ge2,\qquad r:=n-1,\qquad a\ge\sqrt{r}. \tag*{(1)}

This function is convex and unbounded below. It is differentiable precisely when x(1)≠0x^{(1)}\ne0, with

g(x):=∇f(x)=[asgn⁡(x(1))1],1∈Rr.(2)g(x):=\nabla f(x)=\begin{bmatrix}a\operatorname{sgn}(x^{(1)})\\1\end{bmatrix},\qquad\mathbf{1}\in\mathbb{R}^{r}. \tag*{(2)}

Here 1\mathbf{1} denotes the all-ones vector. Note that although ff is unbounded below, it is bounded below along the line defined by the negative gradient direction from any point xx with x(1)≠0x^{(1)}\ne0, since a≥ra\ge\sqrt{r}. The case a<ra<\sqrt{r} is of no interest since ff 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 ff is unbounded below, we say that a method to minimize ff is successful if it generates function values diverging to −∞-\infty and fails otherwise.

Theorem 3.1 of [2] proves convergence of the absolute normalized search directions of the scaled method when a≥2ra\ge2\sqrt{r}. 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 a≥3ra\ge\sqrt{3r} suffices. Section 2 of this article proves this stronger result and gives a geometric error estimation for a≥3ra \ge\sqrt{3r}. 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 a≥ra \ge\sqrt{r}.

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 gk=g(xk)g_k = g(x_k) as defined in (1.2) and start with x0(1)≠0x_0^{(1)} \ne0 and d0=−g0d_0 = -g_0. After accepting a step tk−1>0t_{k-1} > 0, define

xk=xk−1+tk−1dk−1,sk−1=xk−xk−1,yk−1=gk−gk−1.(3)x_k = x_{k-1} + t_{k-1}d_{k-1}, \qquad s_{k-1} = x_k - x_{k-1}, \qquad y_{k-1} = g_k - g_{k-1}. \tag*{(3)}

For k≥1k \ge1, memoryless BFGS computes

ρk−1=(sk−1Tyk−1)−1,Vk−1=I−ρk−1yk−1sk−1T,\rho_{k-1} = \left(s_{k-1}^{T}y_{k-1}\right)^{-1}, \qquad V_{k-1} = I - \rho_{k-1}y_{k-1}s_{k-1}^{T},
Hk=Vk−1THk0Vk−1+ρk−1sk−1sk−1T,dk=−Hkgk.(4)H_k = V_{k-1}^{T}H_k^0V_{k-1} + \rho_{k-1}s_{k-1}s_{k-1}^{T}, \qquad d_k = -H_kg_k. \tag*{(4)}

Thus only the latest correction pair is used. The two choices considered here are

Hk0={γkI,γk=sk−1Tyk−1yk−1Tyk−1,scaled,I,unscaled.(5)H_k^0 = \begin{cases} \gamma_k I, & \gamma_k = \dfrac{s_{k-1}^{T}y_{k-1}}{y_{k-1}^{T}y_{k-1}}, \quad\text{scaled},\\ I, & \text{unscaled}. \end{cases} \tag*{(5)}

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 tk>0t_k > 0 satisfies the Armijo-Wolfe conditions if

f(xk+tkdk)≤f(xk)+c1tkgkTdk,(6)f(x_k + t_kd_k) \le f(x_k) + c_1t_kg_k^{T}d_k, \tag*{(6)}
g(xk+tkdk) exists, and g(xk+tkdk)Tdk≥c2gkTdk.(7)g(x_k + t_kd_k)\text{ exists, and }g(x_k + t_kd_k)^{T}d_k \ge c_2g_k^{T}d_k. \tag*{(7)}

with 0<c1<c2<10 < c_1 < c_2 < 1.

As in [2 Section 2], we say that memoryless BFGS succeeds if it identifies the fact that ff is unbounded below either because it generates a direction dd for which no steplength tt satisfying the Armijo-Wolfe conditions exists (in which case the function must be unbounded below) or, alternatively, that it generates a sequence {xk}\{x_k\} for which Armijo-Wolfe steps always exist, with f(xk)↓−∞f(x_k) \downarrow-\infty. If neither event takes place, {f(xk)}\{f(x_k)\} is bounded below, which is regarded as failure, since ff is unbounded below.

A sharpened convergence bound for scaled L-BFGS-1

For scaled L-BFGS-1, [2 Lemma 2.1] shows that if a≥3ra \ge\sqrt{3r}, then

bk:=dk(i)dk(1)(i=2,…,n)b_k := \frac{d_k^{(i)}}{d_k^{(1)}} \quad(i=2,\ldots,n)

alternates in sign with ∣bk∣≤1/a|b_k| \le1/a and that βk:=∣bk∣\beta_k := |b_k| satisfies

β0=1a,βk+1=T(βk),T(β):=1+rβ2a−rβ−β=1−aβ+2rβ2a−rβ.(8)\beta_0 = \frac{1}{a}, \qquad\beta_{k+1}=T(\beta_k), \qquad T(\beta):=\frac{1+r\beta^2}{a-r\beta}-\beta=\frac{1-a\beta+2r\beta^2}{a-r\beta}. \tag*{(8)}

Note that the recurrence in (8) is exactly equation (27) of [2]. Then [2 Theorem 2.3] guarantees that consequently, provided a≥3ra \ge\sqrt{3r}, 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 {βk}={∣bk∣}\{\beta_k\}=\{|b_k|\} converges when a≥2ra \ge2\sqrt{r}. We now weaken this assumption to a≥3ra \ge\sqrt{3r} 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 a≥3ra \ge\sqrt{3r}. The sequence βk+1=T(βk)\beta_{k+1}=T(\beta_k) converges to

b=a−a2−3r3r=1a+a2−3r.(9)b=\frac{a-\sqrt{a^2-3r}}{3r}=\frac{1}{a+\sqrt{a^2-3r}}. \tag*{(9)}

Proof. As is shown in [2 Lemma 2.1], 0<T(βk)≤1/a0<T(\beta_k)\le1/a for k=0,1,…k=0,1,\ldots, so all iterates lie in J:=[0,1/a]J:=[0,1/a]. Clearly bb in (9) satisfies 0<b≤1/a0<b\le1/a and T(b)=bT(b)=b. That is, bb is a fixed-point of T(β)T(\beta). It is easy to see that 1−ab=−3rb2+ab1-ab=-3rb^2+ab with some rearrangement of (9). Substituting 1−ab1-ab by −3rb2+ab-3rb^2+ab as well as rbβrb\beta by 3rbβ−2rbβ3rb\beta-2rb\beta in the numerator of

T(β)−b=2rβ2+rbβ−aβ+1−aba−rβT(\beta)-b=\frac{2r\beta^2+rb\beta-a\beta+1-ab}{a-r\beta}

we arrive at the following factorization

T(β)−b=(β−b)2rβ+3rb−aa−rβ.(10)T(\beta)-b=(\beta-b)\frac{2r\beta+3rb-a}{a-r\beta}. \tag*{(10)}

Now define the right factor in (10) as

R(β)=2rβ+3rb−aa−rβ.R(\beta)=\frac{2r\beta+3rb-a}{a-r\beta}.

Hence, T(β)−b=(β−b)R(β)T(\beta)-b=(\beta-b)R(\beta). For β∈J\beta\in J, it is easy to check that

1+R(β)=r(β+3b)a−rβ>0.1+R(\beta)=\frac{r(\beta+3b)}{a-r\beta}>0.

Suppose first that a>3ra>\sqrt{3r}. Since β,b≤1/a\beta,b\le1/a,

3r(β+b)≤6ra<2a,3r(\beta+b)\le\frac{6r}{a}<2a,

and hence

1−R(β)=2a−3r(β+b)a−rβ>0.1-R(\beta)=\frac{2a-3r(\beta+b)}{a-r\beta}>0.

Together with 1+R(β)>01+R(\beta)>0, this shows that ∣R(β)∣<1|R(\beta)|<1 throughout JJ. Moreover, a−rβ≥a−r/a>0a-r\beta\ge a-r/a>0 on JJ, so RR is continuous on the compact interval JJ. Therefore its maximum absolute value is attained and satisfies

κ:=max⁡β∈J∣R(β)∣<1.\kappa:=\max_{\beta\in J}|R(\beta)|<1.

Applying (10) repeatedly gives

∣βk−b∣≤κk∣β0−b∣⟶0,|\beta_k-b|\le\kappa^k|\beta_0-b|\longrightarrow0,

which proves convergence for a>3ra>\sqrt{3r}.

If a=3ra=\sqrt{3r}, then b=1/ab=1/a and R(b)=1R(b)=1, so the preceding strict contraction bound does not apply. However, the prescribed initial value in (8) is β0=1/a=b\beta_0=1/a=b. Since T(b)=bT(b)=b, it follows that βk=b\beta_k=b for every k≥0k\ge0. 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 βk\beta_k 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 a≥3ra\ge\sqrt{3r} as follows.

For an arbitrary Armijo–Wolfe line search, add the additional condition

1c1−1<arb,equivalentlyc1>rba+rb.(11)\frac{1}{c_1}-1<\frac{a}{rb},\qquad\text{equivalently}\qquad c_1>\frac{rb}{a+rb}. \tag*{(11)}

To see why this suffices, set uk:=∣sk(1)∣u_k:=|s_k^{(1)}|,

φk:=c1(a+rβk)+a−rβk2aandφ:=c1(a+rb)+a−rb2a.\varphi_k:=\frac{c_1(a+r\beta_k)+a-r\beta_k}{2a} \qquad\text{and}\qquad \varphi:=\frac{c_1(a+rb)+a-rb}{2a}.

The Armijo inequality gives φkuk≤∣xk(1)∣\varphi_k u_k\le|x_k^{(1)}|, see [2 Lemma 3.3]. Adding this inequality at two consecutive iterations and using the sign change uk−1=∣xk−1(1)∣+∣xk(1)∣u_{k-1}=|x_{k-1}^{(1)}|+|x_k^{(1)}| yields, as in [2 Corollary 3.5],

uk≤1−φk−1φkuk−1,1−φk−1φk⟶1−φφ<1,u_k\le\frac{1-\varphi_{k-1}}{\varphi_k}u_{k-1},\qquad \frac{1-\varphi_{k-1}}{\varphi_k}\longrightarrow\frac{1-\varphi}{\varphi}<1,

where the final inequality follows from (2.4), since φ−1/2=(c1(a+rb)−rb)/(2a)>0\varphi-1/2=(c_1(a+rb)-rb)/(2a)>0. Thus there are q∈(0,1)q\in(0,1) and KK such that uk≤quk−1u_k\le qu_{k-1} for every k≥Kk\ge K, and hence ∑k=0∞uk<∞\sum_{k=0}^{\infty}u_k<\infty. This proves the extension of [2, Theorem 3.8] to a≥3ra\ge\sqrt{3r}, including a=3ra=\sqrt{3r}, when (2.4) reduces to c1>1/4c_1>1/4.

For an Armijo–Wolfe search satisfying tk≤2t_k\le2 for k≥1k\ge1, no additional restriction on c1c_1 is needed. Indeed, the scaled update gives

uk+1=tk+1∣dk(1)∣=tk+12(1−rβka)uk≤(1−rβka)uk,u_{k+1}=t_{k+1}|d_k^{(1)}|=\frac{t_{k+1}}{2}\left(1-\frac{r\beta_k}{a}\right)u_k\le\left(1-\frac{r\beta_k}{a}\right)u_k,
1−rβka⟶1−rba<1,1-\frac{r\beta_k}{a}\longrightarrow1-\frac{rb}{a}<1,

where the second equality is the same as in [2, equation (55)]. Again we conclude ∑k=0∞uk<∞\sum_{k=0}^{\infty}u_k<\infty. The specific bracketing search in [2, Algorithm 2] has this steplength bound when a≥3ra\ge\sqrt{3r}: βk≤1/a\beta_k\le1/a implies 3rβk≤a3r\beta_k \le a, 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, ∣sk(i)∣=βkuk≤uk/a|s_k^{(i)}|=\beta_k u_k\le u_k/a for i=2,…,ni=2,\ldots,n, so

∑k=0∞∥sk∥≤1+ra2∑k=0∞uk<∞.\sum_{k=0}^{\infty}\lVert s_k\rVert\le\sqrt{1+\frac{r}{a^2}}\sum_{k=0}^{\infty}u_k<\infty.

Consequently xkx_k converges to a finite point xˉ\bar{x}. The sign changes give ∣xk(1)∣≤uk→0|x_k^{(1)}|\le u_k\to0, so xˉ(1)=0\bar{x}^{(1)}=0. By continuity, f(xk)↓f(xˉ)>−∞f(x_k)\downarrow f(\bar{x})>-\infty, establishing failure since ff 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 Hk0=IH_k^0=I using any Armijo–Wolfe line search, and starting from any point x0x_0 with x0(1)≠0x_0^{(1)}\ne0, the method always succeeds.

Proof. As in [2 Section 2], for this problem memoryless BFGS succeeds if it identifies the fact that ff is unbounded below either because it generates a direction dd for which no steplength tt satisfying the Armijo-Wolfe conditions exists (in which case the function must be unbounded below) or, alternatively, that it generates a sequence {xk}\{x_k\} for which Armijo-Wolfe steps always exist and f(xk)↓−∞f(x_k)\downarrow-\infty.

As in [2], we assume without loss of generality that the initial point has a positive first component, x0(1)>0x_0^{(1)}>0. Furthermore we assume the method generates a sequence xkx_k for which Armijo-Wolfe steps tkt_k always exist. We then proceed to prove that the resulting function values diverge to −∞-\infty.

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 xkx_k,

sgn⁡(xk(1))=−sgn⁡(xk−1(1)).\operatorname{sgn}(x_k^{(1)})=-\operatorname{sgn}(x_{k-1}^{(1)}).

see [2 equations (13) and (14)], whose derivation does not depend on the choice of Hk0H_k^0. Hence, as long as the steps are accepted, xk(1)x_k^{(1)} has the sign (−1)k(-1)^k, and xk=xk−1+sk−1x_k=x_{k-1}+s_{k-1} implies (−1)ksk−1(1)=∣sk−1(1)∣>0(-1)^k s_{k-1}^{(1)}=|s_{k-1}^{(1)}|>0. Additionally

gk=[(−1)ka1],yk−1=[2(−1)ka0],sk−1=tk−1dk−1,(12)g_k=\begin{bmatrix}(-1)^k a\\ \mathbf{1}\end{bmatrix},\qquad y_{k-1}=\begin{bmatrix}2(-1)^k a\\0\end{bmatrix},\qquad s_{k-1}=t_{k-1}d_{k-1}, \tag*{(12)}

so

sk−1Tyk−1=2a∣sk−1(1)∣.(13)s_{k-1}^{T}y_{k-1}=2a|s_{k-1}^{(1)}|. \tag*{(13)}

All tail components of each direction, and hence of each step, are equal: this holds for d0=−g0d_0=-g_0 and is preserved by (1.4). Moreover, dk−1(1)≠0d_{k-1}^{(1)}\ne0 for an accepted step. Hence, as in Section 2 and [2 equation (19)], we can write

bk−1=dk−1(i)dk−1(1)=sk−1(i)sk−1(1),i=2,…,n,so thatsk−1=sk−1(1)[1bk−11].(14)b_{k-1}=\frac{d_{k-1}^{(i)}}{d_{k-1}^{(1)}}=\frac{s_{k-1}^{(i)}}{s_{k-1}^{(1)}},\quad i=2,\ldots,n,\qquad\text{so that}\qquad s_{k-1}=s_{k-1}^{(1)}\begin{bmatrix}1\\b_{k-1}\mathbf{1}\end{bmatrix}. \tag*{(14)}

:::

For k≥1k \ge1, let γk\gamma_k be the scaling parameter of (5), which by (13) is

γk=sk−1Tyk−1yk−1Tyk−1=∣sk−1(1)∣2a.(15)\gamma_k = \frac{s_{k-1}^{T}y_{k-1}}{y_{k-1}^{T}y_{k-1}} = \frac{\left|s_{k-1}^{(1)}\right|}{2a}. \tag*{(15)}

Substituting this and (14) into (4) yields

Hk=[γkγkbk−11Tγkbk−11(1+γk)bk−1211T+Ir],(16)H_k = \left[ \begin{array}{cc} \gamma_k & \gamma_k b_{k-1}\mathbf{1}^{T} \\ \gamma_k b_{k-1}\mathbf{1} & (1+\gamma_k)b_{k-1}^{2}\mathbf{1}\mathbf{1}^{T}+I_r \end{array} \right], \tag*{(16)}

where IrI_r is the r×rr \times r identity matrix. Although the unscaled method does not use γk\gamma_k to scale Hk0H_k^0, the same quantity appears as a coefficient in the updated matrix. From dk=−Hkgkd_k=-H_kg_k, using (12) we get

dk=−[γk((−1)ka+rbk−1)((−1)kaγkbk−1+(1+γk)rbk−12+1)1]=−dk(1)[1bk−11].(17)d_k=-\left[ \frac{\gamma_k\left((-1)^k a+r b_{k-1}\right)} {\left((-1)^k a\gamma_k b_{k-1}+(1+\gamma_k)r b_{k-1}^{2}+1\right)\mathbf{1}} \right] =-d_k^{(1)} \left[ \begin{array}{c} 1\\ b_{k-1}\mathbf{1} \end{array} \right]. \tag*{(17)}

In particular, note that the sign change implies that dk(1)d_k^{(1)} must have the same sign as (−1)k+1(-1)^{k+1}, i.e.

a+(−1)krbk−1>0.(18)a+(-1)^k r b_{k-1}>0. \tag*{(18)}

If tk+1t_{k+1} is accepted, using the same argument for iteration k+1k+1 as we did for iteration kk we also get

a−(−1)krbk>0.(19)a-(-1)^k r b_k>0. \tag*{(19)}

Also from sk=tkdks_k=t_kd_k we obtain

∣sk(1)∣=tkγk(a+(−1)krbk−1).(20)\left|s_k^{(1)}\right|=t_k\gamma_k\left(a+(-1)^k r b_{k-1}\right). \tag*{(20)}

Recall

bk=(−1)kaγkbk−1+(1+γk)rbk−12+1γk((−1)ka+rbk−1)=bk−1+(−1)k1+rbk−12γk(a+(−1)krbk−1).(21)\begin{aligned} b_k&=\frac{(-1)^k a\gamma_k b_{k-1}+(1+\gamma_k)r b_{k-1}^{2}+1}{\gamma_k\left((-1)^k a+r b_{k-1}\right)}\\ &=b_{k-1}+(-1)^k\frac{1+r b_{k-1}^{2}}{\gamma_k\left(a+(-1)^k r b_{k-1}\right)}. \tag*{(21)} \end{aligned}

Plugging bkb_k into (19) we obtain

a−(−1)krbk−1>r(1+rbk−12)γk(a+(−1)krbk−1).a-(-1)^k r b_{k-1}>\frac{r(1+r b_{k-1}^{2})}{\gamma_k\left(a+(-1)^k r b_{k-1}\right)}.

The right term is positive by (18), so this inequality shows

a+(−1)krbk−1<2a,(22)a+(-1)^k r b_{k-1}<2a, \tag*{(22)}

so

1>r(1+rbk−12)γk(a−(−1)krbk−1)(a+(−1)krbk−1).1>\frac{r(1+r b_{k-1}^{2})}{\gamma_k\left(a-(-1)^k r b_{k-1}\right)\left(a+(-1)^k r b_{k-1}\right)}.

Moving γk\gamma_k to the left side and using (15) we get

∣sk−1(1)∣>2ar(1+rbk−12)(a+(−1)krbk−1)(a−(−1)krbk−1).\left|s_{k-1}^{(1)}\right|>\frac{2ar(1+r b_{k-1}^{2})}{\left(a+(-1)^k r b_{k-1}\right)\left(a-(-1)^k r b_{k-1}\right)}.

Since sk−1s_{k-1} is in the direction of descent, −tk−1gk−1Tdk−1=−gk−1Tsk−1=∣gk−1Tsk−1∣-t_{k-1}g_{k-1}^{T}d_{k-1}=-g_{k-1}^{T}s_{k-1}=\lvert g_{k-1}^{T}s_{k-1}\rvert and

∣gk−1Tsk−1∣=(−1)ksk−1(1)(a+(−1)k−1rbk−1)=∣sk−1(1)∣(a+(−1)k−1rbk−1)>2ar(1+rbk−12)(a+(−1)k−1rbk−1)(a−(−1)k−1rbk−1)(a+(−1)k−1rbk−1)=2ar(1+rbk−12)a+(−1)krbk−1>2ar(1+rbk−12)2a≥r.\begin{aligned} \lvert g_{k-1}^{T}s_{k-1}\rvert &=(-1)^k s_{k-1}^{(1)}\left(a+(-1)^{k-1}rb_{k-1}\right)\\ &=\lvert s_{k-1}^{(1)}\rvert\left(a+(-1)^{k-1}rb_{k-1}\right)\\ &>\frac{2ar\left(1+rb_{k-1}^{2}\right)\left(a+(-1)^{k-1}rb_{k-1}\right)} {\left(a-(-1)^{k-1}rb_{k-1}\right)\left(a+(-1)^{k-1}rb_{k-1}\right)}\\ &=\frac{2ar\left(1+rb_{k-1}^{2}\right)} {a+(-1)^krb_{k-1}}\\ &>\frac{2ar\left(1+rb_{k-1}^{2}\right)}{2a}\ge r. \end{aligned}

The second equality comes from recalling ∣sk−1(1)∣=(−1)ksk−1(1)\lvert s_{k-1}^{(1)}\rvert=(-1)^ks_{k-1}^{(1)}. The last strict inequality is from (22).

By the Armijo condition (6),

f(xk+1)≤f(xk)+c1tkgkTdk≤f(xk)−c1r,f(x_{k+1})\le f(x_k)+c_1t_kg_k^{T}d_k\le f(x_k)-c_1r,

where the second inequality uses −tkgkTdk≥r-t_kg_k^{T}d_k\ge r. Summing over k=1,…,N−1k=1,\ldots,N-1 gives

f(xN)≤f(x1)−Nc1r⟶−∞,f(x_N)\le f(x_1)-Nc_1r\longrightarrow-\infty,

since c1>0c_1>0 and r=n−1≥1r=n-1\ge1.

Thus, if Armijo–Wolfe steps exist at every iteration, the function values diverge to −∞-\infty. If instead no Armijo–Wolfe step exists at some iteration, the method succeeds by identifying a direction along which ff is unbounded below, as discussed in § 1.2. These two alternatives establish that the unscaled method always succeeds.

References

  1. [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. [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. [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

Paper details

vlnc:W_9j4cj6j7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents