Fixed Point Problems and Methods

As we have emphasized before, the algorithms discussed in this books are all special cases of block relation methods. But block relation methods are often appropriately analyzed as fixed point methods, which define an even wider class of iterative methods. Thus we will not discuss actual fixed point algorithms that are not block relation methods, but we will use general results on fixed point methods to analyze block relaxation methods.

A (stationary, one-step) fixed point method on $\mathcal{X}\subseteq\mathbb{R}^n$ is defined as a map $A:\mathcal{X}\rightarrow\mathcal{X}$. Depending on the context we refer to $A$ as the update map or algorithmic map. Iterative sequences are generated by starting with $x^{(0)}\in\mathcal{X}$ and then setting $$x^{(k)}=A(x^{(k-1)})=A^k(x^{(0)}).$$ for $k=1,2,\cdots$. Such a sequence is also called the Picard sequence generated by the map.

If the sequence $x^{(k)}$ converges to, say, $x_\infty$, and if $A$ is continuous, then $x_\infty=A(x_\infty)$, and thus $x_\infty$ is a fixed point of $A$ on $\mathcal{X}$. The set of all $x\in\mathcal{X}$ such that $x=A(x)$ is called the fixed point set of $A$ on $\mathcal{X}$, and is written as $\mathcal{F}_\mathcal{X}$.

The literature on fixed point methods is truly gigantic. There are textbooks, conferences, and dedicated journals. A nice and compact treatment, mostly on existence theorems for fixed points, is Smart, [1974]. An excellent modern overview, concentrating on metrical fixed point theory and iterative computation, is Berinde [2007].

The first key result in fixed point theory is the Brouwer Fixed Point Theorem, which says that for compact convex $\mathcal{X}$ and continuous $A$ there is at least one $x\in\mathcal{F}_\mathcal{X}(A)$. The second is the Banach Fixed Point Theorem, which says that if $\mathcal{X}$ is a non-empty complete metric space and $A$ is a contraction, i.e. $d(A(x),A(y))<\kappa\ d(x,y)$ for some $0\leq\kappa<1$, then the Picard sequence $x^{(k)}$ converges from any starting point $x^{(0)}$ to the unique fixed point of $A$ in $\mathcal{X}$.

Much of the fixed point literature is concerned with relaxing the contraction assumption and choosing more general spaces on which the various mappings are defined. I shall discuss some of the generalizations that we will use later in this book.

First, we can generalize to point-to-set maps $A:\mathcal{X}\rightarrow 2^\mathcal{X}$, where $2^\mathcal{X}$ is the power set of $\mathcal{X}$, i.e. the set of all subsets. Point-to-set maps are also called correspondences or multivalued maps. The Picard sequence is now defined by $x^{(k)}\in A(x^{(k-1)})$ and we have a fixed point $x\in\mathcal{F}_\mathcal{X}(A)$ if and only if $x\in A(x)$. The generalization of the Brouwer Fixed Point Theorem is the Kakutani Fixed Point Theorem. It assumes that $\mathcal{X}$ is non-empty, compact and convex and that $A(x)$ is non-empty and convex for each $x\in\mathcal{X}$. In addition, the map $A$ must be closed or upper semi-continuous on $\mathcal{X}$, i.e. whenever $x_n\rightarrow x_\infty$ and $y_n\in A(x_n)$ and $y_n\rightarrow y_\infty$ we have $y_\infty\in A(x_\infty)$. Under these conditions Kakutani's Theorem asserts the existence of a fixed point.

Our discussion of the global convergence of block relaxation algorithms, in a later chapter, will be framed using fixed points of point-to-set maps, assuming the closedness of maps.

In another generalization of iterative algorithms we get rid of the one-step and the stationary assumptions. The iterative sequence is $$x^{(k)}\in A_k(x^{(0)},x^{(1)},\cdots,x^{(k-1)}).$$ Thus the iterations have perfect memory, and the update map can change in each iteration. In an $\ell$-step method, memory is less than perfect, because the update is a function of only the previous $\ell$ elements in the sequence. Formally, for $k\geq\ell$, $$x^{(k)}\in A_k(x^{(k-l)},\cdots,x^{(k-1)}),$$ with some special provisions for $k<\ell$.

Any $\ell$-step method on $\mathcal{X}$ can be rewritten as a one-step method on $$\underbrace{\mathcal{X}\otimes\mathcal{X}\otimes\cdots\otimes\mathcal{X}}_{\ell\ \text{times}}.$$ This makes it possible to limit our discussion to one-step methods. In fact, we will mostly discuss block-relaxation methods which are stationary one-step fixed point methods.

For non-stationary methods it is somewhat more complicated to define fixed points. In that case it is natural to define a set $\mathcal{S}\subseteq\mathcal{X}$ of desirable points or targets, which for stationary algorithms will generally, but not necessarily, coincide with the fixed points of $A$. The questions we will then have to answer are if and under what conditions our algorithms converge to desirable points, and if they converge how fast the convergence will take place.