## Understanding Taylor’s Theorem

Classical methods as gradient descent and Newton can be justified from Taylor’s theorem. It is a powerful tool to have at handy when doing convergence analysis of optimization methods. We try to develop here the necessary background in order to master this important tool.

## Fundamental Results

Rolle’s Theorem: Let $a,b \in \mathbb{R}$ and $f:[a,b]\rightarrow \mathbb{R}$ a continuous function differentiable at the interval $(a,b)$. Let $c,d \in [a,b]$ such that $f(c)=f(d)$. Then there exists $\alpha \in (a,b)$ such that $f^\prime(\alpha) = 0$.

Proof: Assume, without loss of generality (w.l.o.g.), that $d$ is the first value greater than $c$ such that $f(c) = f(d)$. Furter, w.l.o.g., assume that $f(x) \geq 0 \quad \forall x \in [c,d]$. Since $[c,d]$ is a compact set, it attains a maximum at some point $\alpha \in [c,d]$. Therefore, $f^\prime(\alpha) = 0$. $\hfill \square$

## Principles of Fixed Point Algorithms – Theory and Practice

A fixed-point algorithm is easy to explain: Given a fixed-point function $f$ suited to your problem,  choose any point $x_0$ from $dom(f)$ and compute $f(x_0)$ to obtain the next point $x_1$. Proceed until find point $x_k = f(x_k)$.

In the following, we expose the conditions in which this strategy works and the reason why. The famous gradient-method can be seen as a fixed-point algorithm.

## A simple example

Let’s say you have $n$ pairs of socks that are initially stored in $n$ different drawers. The drawer in which the pair $s$ is stored is given by $d(s)$. Let’s assume that we start with $d(s)=s \quad \forall s$. Now we wish to change the drawers of each pair $s$ such that $d(s) \neq s \quad \forall s.$. Is it possible? Sure it is!

$d(s) = \left\{ \begin{array}{ll} s+1 & s < n\\[0.15in] 1 & s=n \end{array}\right.$

The function $d$ is a permutation and it does not have any fixed-point, i.e., there exists no $s$ such that $d(s) = s$. Functions with no fixed-points can be generated similarly for any countable set (See Hilbert’s Hotel). Let’s see what we can do with uncountable sets.