The line search criteria are as follows: Parameters $\lambda_1$, $\lambda_2$, $\sigma$, and $\delta$ are introduced where $0 < \lambda_1 < \lambda_2$ and $\sigma, \delta \in (0, 1)$, and they set $\alpha_k = \overline{\alpha_k} \sigma^{h_k}$ where $\overline{\alpha_k} \in (\lambda_1, \lambda_2)$ is the "trial step" and $h_k$ is the smallest nonnegative integer such that $$f(x_k + \alpha_k d_k) \le \max_{0 \le j \le m_k}f(x_{k-j}) + \delta\alpha_k \nabla f(x_k)d_k.\tag{1.2} \label{eq:1.2}$$ Here the gradient of $f$ at $x_k$, $\nabla f(x_k)$, is a row vector. The memory $m_k$ at step $k$ is a nondecreasing integer, bounded by some fixed integer $M$. More precisely, $m_0 = 0$ and for $k > 0$, $0 \le m_k \le \min(m_{k−1} + 1, M)$.
But why "although an iterative method is generating $\mathbb R$-linearly convergent iterations for a strongly convex function, the iterates may not satisfy the condition \eqref{eq:1.2} for $k$ sufficiently large, for any fixed bound $M$ on the memory." The example is $$f(x)=\frac{1}{2}x^2, x\in \mathbb R , x_0 \ne 0, d_k=-x_k,$$ and $α_k =1-2^{-k}x^2$, if $k = i^2$ for some integer $i$, otherwise $α_k=2$ .
The iterates converge R-superlinearly to the minimizer $x^* = 0$; however, condition \eqref{eq:1.2} is not satisfied for $k$ sufficiently large and any fixed $M$.
I can't understand why this counterexample doesn't work. Thanks.
This example can be found in Y. H. Dai, On the nonmonotone line search, J. Optim. Theory Appl., 112 (2002), pp. 315–330. Formula (51) (52) on page 324.