1
$\begingroup$

I am considering a proof that would require a certain connection between convergence of iterates and corresponding function values: Consider an algorithm with iterates $\left\{{\mathbf{x}}^k\right\}_{k\in \mathbb{N}}$ and a continuously differentiable function ${\mathbf{f}}:\mathbb{R}^{n} \to \mathbb{R}^{m}$. Assume that ${\mathbf x}^k \xrightarrow{k \to \infty} {\mathbf{x}}^+$, but $\mathbf{f}(\mathbf{x}^k)\neq \mathbf{f}({\mathbf{x}}^+) \forall k$.

Can we show that

  1. monotone decrease in the distance between iterates will eventually yield monotone decrease in distance of function values, i.e., \begin{align} \exists K &\in \mathbb{N}: \forall k>K: \\ &\lVert {\mathbf x}^{k+1} - {\mathbf x}^{k}\rVert \le \lVert {\mathbf x}^{k} - {\mathbf x}^{k-1}\rVert \implies \lVert {\mathbf{f}} ({\mathbf x}^{k+1}) - {\mathbf{f}}({\mathbf x}^{k})\rVert \le c \lVert {\mathbf{f}}({\mathbf x}^{k}) - {\mathbf{f}}({\mathbf x}^{k-1})\rVert \end{align} with $c=1$ or $1<c\le2$ ?
  2. linear convergence of the residuals follows from the linear convergence of iterates, i.e., $$ \lim \limits_{k \to \infty} \frac{\lVert {\mathbf x}^{+} - {\mathbf x}^{k}\rVert}{\lVert {\mathbf x}^{+} - {\mathbf x}^{k-1}\rVert} = \mu\in (0,1) \implies \lim \limits_{k \to \infty} \frac{\lVert {\mathbf{f}} ({\mathbf x}^{+}) - {\mathbf{f}}({\mathbf x}^{k})\rVert}{\lVert {\mathbf{f}} ({\mathbf x}^{k+1}) - {\mathbf{f}}({\mathbf x}^{k})\rVert} < \nu\in (0,1) \;? $$

So far, I have only been able to make progress on (1.): I was able to convince myself for (1.) in the case of a function $f:\mathbb{R}\to \mathbb{R}$, because it is either constant equal $0$ near $x^+$ or is monotone in a small area around $0$. I tried constructing a counterexample for (1.) in the linear case (using eigenvectors with eigenvalue 0 and 1), but failed because of the assumption that $\mathbf{f}(\mathbf{x}^k)\neq \mathbf{f}({\mathbf{x}}^+)$.

I was able to find some loosely connected literature here talking about Ostrowki’s convergence theorem and a connected result by Meyer.

However, I have hope that these questions are not novel and have been answered (considering one might seek such a connection between iterate convergence and residual convergence for, e.g., Newton's method. Does anybody have pointers on this?

$\endgroup$

1 Answer 1

1
$\begingroup$

I found a counter example in the linear case:

Consider $\boldsymbol{f}(\boldsymbol{x})= \begin{pmatrix} \frac{1}{3} & 0 \\ 0 & 1 \end{pmatrix} \boldsymbol{x}$ and the sequence $x^i=\begin{cases} 0.5^i\begin{pmatrix} 1 \\ 0\end{pmatrix} & \text{if $i$ is odd,} \\ 0.5^i\begin{pmatrix} 0 \\ 1\end{pmatrix} & \text{if $i$ is even.}\end{cases}$

It is clear that $\left\{\boldsymbol{x}^i\right\}$ converges q-linear with factor 0.5 to $\begin{pmatrix} 0 \\ 0\end{pmatrix}$. However, the corresponding function values do not.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.