I.3.2: Definition

Block relaxation methods are fixed point methods. A brief general introduction to fixed point methods, with some of the terminology we will use, is in the fixed point section of the background chapter [background/fixed].

Let us thus consider the following general situation. We minimize a real-valued function $f$ defined on the product-set $\mathcal{X}=\mathcal{X}_1\otimes\mathcal{X}_2\otimes\cdots\otimes\mathcal{X}_p,$ where $\mathcal{X}_s\subseteq\mathbb{R}^{n_s}.$

In order to minimize $f$ over $\mathcal{X}$ we use the following iterative algorithm.

$$\begin{matrix} \text{Starter:}&\text{Start with } x^{(0)}\in\mathcal{X}.\\ \hline \text{Step k.1:}&x^{(k+1)}_1\in\mathbf{Arg}\mathop{\mathbf{min}}\limits_{x_1\in\mathcal{X}_1} f(x_1,x^{(k)}_2,\cdots,x^{(k)}_p). \\ \text{Step k.2:}&x^{(k+1)}_2\in\mathbf{Arg}\mathop{\mathbf{min}}\limits_{x_2\in\mathcal{X}_2} f(x^{(k+1)}_1,x_2,x^{(k)}_3,\cdots, x^{(k)}_p). \\ \cdots&\cdots\\ \text{Step k.p:}&x^{(k+1)}_p\in\mathbf{Arg}\mathop{\mathbf{min}}\limits_{x_p\in\mathcal{X}_p} f(x^{(k+1)}_1,\cdots,x^{(k+1)}_{p-1}, x_p).\\ \hline \text{Motor:}&k\leftarrow k+1 \text{ and go to } k.1 \\ \hline \end{matrix}$$

Observe that we assume that the minima in the substeps exist, but they need not be unique. The $\mathbf{Argmin}'s$ are point-to-set maps, although in many cases they map to singletons. In actual computations we will always have to use a selection from the $\mathbf{Argmin}$.

We set $$x^{(k)}\mathop{=}\limits^{\Delta}(x^{(k)}_1,\cdots,x^{(k)}_p),$$ and $f^{(k)}\mathop{=}\limits^{\Delta}f(x^{(k)}).$ The map $\mathcal{A}$ that is the composition of the $p$ substeps on an iteration satisfies $x^{(k+1)}\in\mathcal{A}(x^{(k)})$. We call it the iteration map (or the algorithmic map or update map). If $\mathcal{A}(x)$ is a singleton for all $x\in\mathcal{X}$, then we can write $x^{(k+1)}=\mathcal{A}(x^{(k)})$ without danger of confusion, and call $\mathcal{A}$ the iteration function.

If $\mathcal{A}$ is differentiable on $\mathcal{X}$ then we introduce some extra terminology and notation. The matrix $\mathcal{M}(x)\mathop{=}\limits^{\Delta}\mathcal{DA}(x)$ of partial derivatives is called the Iteration Jacobian and its spectral radius $\rho(x)\mathop{=}\limits^{\Delta}\rho(\mathcal{DA}(x))$, the eigenvalue of maximum modulus, is called the Iteration Spectral Radius or simply the Iteration Rate. Note that for a linear iteration $x^{(k+1)}=Ax^{(k)}+b$ we have $\mathcal{M}(x)=A$ and $\rho(x)=\rho(A)$.

The file blockrelax.R has a reasonable general R function for unrestricted block relation in which each $\mathcal{X}_s$ is all of $\mathbb{R}^{n_s}$. The arguments are the function to be minimized, the initial estimate, and the block structure. Both the initial estimate and the block structure are of length $n=\sum n_s$, and block structure is indicated by two elements having the same integer value if and only if they are in the same block. Each of the subproblems is solved by a call to the optim() function in R.