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

Continue reading

Advertisements

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!

countable
Red dots represents d(x)=x

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.

Continue reading