1
$\begingroup$

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.


Gradient descent

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.

$\endgroup$
  • 1
    $\begingroup$ In your first expression, set $f(x) = -10x$ and $\alpha = 0.2$. Start at $x=1$. Will you converge at all? $\endgroup$ – jbowman Apr 29 at 2:23
  • $\begingroup$ @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. $\endgroup$ – moreblue Apr 29 at 2:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.