# Gradient descent versus fixed point iteration

## Fixed-point iteration

Say I have the iteration

$$x^{(k+1)} \leftarrow x^{(k)} + \alpha f(x^{(k)})$$

to find $$x^\ast$$, the root of $$f$$, i.e. $$f(x^\ast)=0$$, where $$f:(a,b) \to \mathbb{R}$$, $$\exists f'$$ on $$(a,b)$$, and $$\{x \in (a,b):f(x)=0\} \neq \emptyset$$. $$\alpha$$ is given constant.

Say $$f$$ is twice differentiable. Then we can find the root of $$f$$ by minimizing $$F= \int f$$, and since we have $$\nabla F(x^{(k)}) = f(x^{(k)})$$, the minimizing iteration is as follows.

$$x^{(k+1)} \leftarrow x^{(k)} - \alpha_k f(x^{(k)})$$

This is indeed very similar to the above fixed-point iteration, except $$-\alpha_k$$ is dependent upon $$k$$ such that

$$F(x^{(k+1)}) < F(x^{(k)})$$

thus $$\alpha_k$$ is usually found using the line search.

## Question

So are these two methods really different? In other words, is there any difference in convergence speed or stability?

Since I'm stuck at showing even one of those, I would like to ask for a help. Looking forward to learn about the potential dangers of regarding the above as same.

## Edit

The fixed-point iteration converges when absolute value of the derivative of the RHS function is less than 1, i.e.

$$\left| 1 + \alpha f'(x) \right| < 1, \ \ \forall x \in X$$

where $$X$$ is the set where the iterates and the root lie.

For the gradient descent case, the iteration converges when

$$\left| 1 - \alpha_k f'(x) \right| < 1, \ \ \forall x \in X$$

but the line search itself does not guarantee this convergence criterion.

• In your first expression, set $f(x) = -10x$ and $\alpha = 0.2$. Start at $x=1$. Will you converge at all? – jbowman Apr 29 at 2:23
• @jbowman of course the convergence criterion for the fixed-point iteration is $|1 + \alpha f'(x)| < 1|$ for $x \in X$ where iterates and the root lie. – moreblue Apr 29 at 2:37