If the iteration $x^{k+1}=x^k-t_kH_k^{-1}\nabla f(x^k)$ converges superlinearly to a stationary point $x^*\ne x^k$, then $t_k\to 1$ Let


*

*$f\in C^2(\mathbb{R}^n)$

*$(H_k)_{k\in\mathbb{N}_0}\subseteq\text{GL}_n(\mathbb{R})$

*$x^0\in\mathbb{R}^n$ and $$x^{k+1}:=x^k+t_k d^k\;\;\;\text{for }k\in\mathbb{N}_0\tag{1}$$ with $(t_k)_{k\in\mathbb{N}_0}\subseteq (0,\infty)$ and $$H_kd^k+\nabla f(x^k)=0\;\;\;\text{for all }k\in\mathbb{N}_0\tag{2}$$

*$x^\ast\in\mathbb{R}^n\setminus\left\{x^k:k\in\mathbb{N}_0\right\}$ with $x_k\stackrel{k\to\infty}{\to}x^*$ and $\nabla^2f(x^*)\in\text{GL}_n(\mathbb{R})$


Suppose $x_k\stackrel{k\to\infty}{\to}x^*$ superlinearly, i.e. $$\frac{\left\|x^{k+1}-x^*\right\|}{\left\|x^k-x^*\right\|}\stackrel{k\to\infty}{\to}0\tag{3}$$ and $x^*$ is stationary, i.e. $$\nabla f(x^*)=0\tag{4}$$
How can we conclude, that we must have $t_k\stackrel{k\to\infty}{\to}1$?

Clearly, by $(1)$ and $(2)$ we've got $$-t_kH_k^{-1}\nabla f(x^k)=x^{k+1}-x^k\stackrel{k\to\infty}{\to}0\tag{5}\;,$$ but is that the right track? Unfortunately, I'm unable to proceed.

EDIT: If someone can prove the statement under further restrictions, e.g. $\left\|\;\cdot\;\right\|$-boundedness of all $H_k^{-1}$, I would be happy too.
 A: It is just incomplete. I will illustrate the argument using the Newton method, and sketch it for the usual quasi Newton framework. 
For Newton method:
Assume $\nabla^2 f(x^*)$ is non-singular and $x^0$ is sufficiently near $x^*$ such that $H_k = \nabla^2 f(x^k)$ is non-singular for every $k\ge 0$ (the usual assumptions for local convergence analysis of the Newton method).
Then, we have
$$ x^{k+1} - x^* = (x^k + d^k - x^*) - (1-t_k)d^k.$$
The left hand side is $\mathcal o(\|x^k - x^*\|)$ by assumption.
On the right hand side, the first term 
\begin{align} 
x^k + d^k - x^*
&= x^k - x^* - H_k^{-1}\nabla f(x^k) \\
&= x^k - x^* - H_k^{-1}\int_0^1 \nabla^2 f(x^* + t(x^k - x^*))(x^k - x^*) \;\mathrm dt \\
&= H_k^{-1} \underbrace{\left(\int_0^1 H_k - \nabla^2 f(x^* + t(x^k - x^*)) \;\mathrm dt  \right)}_{=\mathcal o(1)} (x^k - x^*)\\
\end{align} 
is $\mathcal o(\|x^k - x^*\|)$ by continuity of $\nabla^2 f$ at $x^*$.
Therefore the second term $(1-t_k)d^k$ must be $\mathcal o(\|x^k - x^*\|)$. 
On other hand, we have
$$ \frac{\| x^k - x^* + d^k \|}{\|x^k - x^*\|} \ge 1 - \frac{\|d^k\|}{\|x^k -x^* \|}. $$
Thus, $\liminf_{k\to\infty} \|d^k\| / \|x^k -x^* \| \ge 1$ and
$1-t_k$ tends to 0. That is, $t_k\to 1$.
For Quasi Newton method:
In that case, we need the additional assumption that $\limsup_{k\to\infty} \| H_k^{-1} \| < \infty$.
The essential part in proof for the Newton method was, that the Newton method converges superlinearly even without the step size $t_k$. 
A sufficient condition for the property at quasi Newton framework is for example
$$  \tag{*} (H_k - \nabla^2 f(x^*))d^k = \mathcal o(\| d^k \|).$$
Since $H_k^{-1}$ is bounded and $x^k\to x^*$ 
we have $d^k = -H_k \nabla f(x^*)\to 0$ and obtain
$$ \nabla f(x^{k}+d^k) = \underbrace{\left(\int_0^1 \nabla^2 f(x^* + t(x^{k} + d^k - x^*)) \;\mathrm d t\right)}_{=: G_k}(x^{k} + d^k - x^*). $$
For $k$ sufficiently large, $G_k$ is non-singular and we have $G_k^{-1}\to \left(\nabla^2 f(x^*)\right)^{-1}$.
Thus, without loss of generality assume $\|G_k^{-1}\| \le \gamma$ for all $k$.
On other hand, notice that
\begin{align}
\nabla f(x^{k} + d^k) 
&= (\nabla f(x^k + d^k) - \nabla f(x^{k})) - H_k d^k \\
&= \underbrace{(\nabla^2 f(x^*) - H_k)d^k}_{=\mathcal o(\|d^k\|)}
+ \underbrace{\nabla f(x^{k}+d^k) - (\nabla f(x^k) + \nabla^2 f(x^*) d^k)}_{=\mathcal o(\|d^k\|)}.
\end{align}
Now, for $\gamma_k = \|\nabla f(x^{k} + d^k)\| / \|d^k\|$ we have
\begin{align} 
\|x^{k} + d^k - x^* \|
&\le \gamma \|\nabla f(x^{k} + d^k)\| \\
&= \gamma \gamma_k \|d^k\| \\
&\le \gamma \gamma_k (\|x^k + d^k - x^* \| + \| x^k - x^* \|) 
\end{align}
and
$$ \frac{\| x^k + d^k - x^* \|}{\| x^k - x^* \|} \le \frac{\gamma\gamma_k}{1-\gamma\gamma_k} \to 0. $$
Note: The condition (*) implies also that $x^k\to x^*$ super linearly.
A: This is incorrect. You can always replace $t_k$ with $\tilde t_k = \lambda_kt_k$ and $H_k$ with $\tilde H_k = \lambda_kH_k$ and get the exact same sequence $x_k$. But now $\tilde t_k$ can have any behavior you want, the sequence can even diverge. And you can certainly arrange for $\lim_{k \to \infty} t_k = c$ for any $c \ne 0$, just by changing $H_k$ to $c t_k^{-1}H_k$ and replacing all $t_k$ with the constant $c$.
A statement like this cannot be proved. You cannot infer convergence properties of a factor in a product from assumptions about the convergence of the product.  
