I.3.6.3: Block Optimization Methods

The resuilts in the previous two sections were for general bock modification methods. We now specialize to block relaxation methods for unconstrained differentiable optimization problems. The rate of convergence of block relaxation algorithms depends on the block structure, and on the matrix of second derivatives of the function $f$ we are minimizing.

The functions $F_s$ that update block $s$ are defined implicitly by $$\mathcal{D}_sf(x_1,x_2,\cdots,x_p)=0.$$ From the implicit function theorem $$\mathcal{D}_tF_s(x)=-[\mathcal{D}_{ss}f(x)]^{-1}\mathcal{D}_{st}f(x).$$ If we use this in the LU-form $\mathcal{M}=(I-B_L)^{-1}B_U$ we find $$\mathcal{M}(x)=- \begin{bmatrix} \mathcal{D}_{11}f(x)&0&\cdots&0\\ \mathcal{D}_{21}f(x)&\mathcal{D}_{22}f(x)&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ \mathcal{D}_{p1}f(x)&\mathcal{D}_{p2}f(x)&\cdots&\mathcal{D}_{pp}f(x)\\ \end{bmatrix}^{-1} \begin{bmatrix} 0&\mathcal{D}_{12}f(x)&\cdots&\mathcal{D}_{1p}f(x)\\ 0&0&\cdots&\mathcal{D}_{2p}f(x)\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&0\\ \end{bmatrix},$$

If there are only two blocks the result simplifies to

$$\begin{multline*} \mathcal{M}(x)=- \begin{bmatrix} [\mathcal{D}_{11}f(x)]^{-1}&0\\ -[\mathcal{D}_{22}f(x)]^{-1}\mathcal{D}_{21}f(x)^{}[\mathcal{D}_{11}f(x)]^{-1}& [\mathcal{D}_{22}f(x)]^{-1} \end{bmatrix} \begin{bmatrix} 0&\mathcal{D}_{12}f(x)\\ 0&0 \end{bmatrix}=\\ \begin{bmatrix} 0&-[\mathcal{D}_{11}f(x)]^{-1}\mathcal{D}_{12}f(x)^{}\\ 0&[\mathcal{D}_{22}f(x)]^{-1}\mathcal{D}_{21}f^{}(x)[\mathcal{D}_{11}f(x)]^{-1}\mathcal{D}_{12}f(x)^{} \end{bmatrix} \end{multline*}$$ Thus, in a local minimum, where the matrix of second derivatives is non-negative definite, we find that the largest eigenvalue of $\mathcal{M}(x)$ is like the largest squared canonical correlation $\rho$ of two sets of variables, and is consequently less than or equal to one.

We also see that a sufficient condition for local convergence to a stationary point of the algorithm is that $\rho<1.$ This is always true for an isolated local minimum, because there the matrix of second derivatives is positive definite. If $\mathcal{D}^2f(x)$ is singular at the solution $x$, we find a canonical correlation equal to $+1,$ and we do not have guaranteed linear convergence.

For the product form we find that $$\mathcal{DA}_s(x)=I-E_s[\mathcal{D}_{ss}f(x)]^{-1}E_s'\mathcal{D}^2f(x),$$ where $E_s$ has blocks of zeroes, except for block $s$, which is the identity. Thus $$\mathcal{M}(x)=\{I-E_s[\mathcal{D}_{ss}f(x)]^{-1}E_s'\mathcal{D}^2f(x)\}\times\cdots\times \{I-E_1[\mathcal{D}_{11}f(x)]^{-1}E_1'\mathcal{D}^2f(x)\}.$$ It follows that $\mathcal{M}(x)z=z$ for all $z$ such that $\mathcal{D}^2f(x)z=0$. Thus $\rho(\mathcal{M}(z))=1$ whenever $\mathcal{D}^2f(x)$ is singular.

For two blocks $$\mathcal{M}(x)=\begin{bmatrix} I&0\\-[\mathcal{D}_{22}f(x)]^{-1}\mathcal{D}_{21}f(x)&0 \end{bmatrix}\begin{bmatrix} 0&-[\mathcal{D}_{11}f(x)]^{-1}\mathcal{D}_{12}f(x)\\0&I, \end{bmatrix}$$ which gives the same result as obtained from the LU-form.

The code in blockRate.R computes $\mathcal{M}(x)$ in one of four ways. We can use the analytical form of the Hessian or compute it numerically, and we can use the LU-form or the product form. If we compute the Hessian numerically we give the function we are minimizing as an argument, if we use the Hessian analytically we pass a function for evaluating it at $x$.