I.3.4: Generalized Block Relaxation

In some cases, even the supposedly simple minimizations within blocks may not have very simple solutions. In that case, we often use generalized block relaxation, which is defined by $p$ maps $\mathcal{A}_s$ mapping $\mathcal{X}$ into (subsets of) $\mathcal{X}$. We have $$\mathcal{A}_s(x)\in\{x_1\}\otimes\cdots\otimes\{x_{s-1}\}\otimes\mathcal{F}_s(x)\otimes\{x_{s+1}\}\otimes\cdots\otimes\{x_p\},$$ where $z\in\mathcal{F}_s(x)$ implies $$f(x_1,\cdots,x_{s-1},z,x_{s+1},\cdots,x_p)\leq f(x_1,\cdots,x_{s-1},x_s,x_{s+1},\cdots,x_p).$$

In ordinary block relaxation $$\mathcal{F}_s(x)=\mathop{\mathbf{argmin}}\limits_{z\in\mathcal{X}_s} f(x_1,\cdots,x_{s-1},z,x_{s+1},\cdots,x_p),$$ but in generalized block relaxation we could update $x_s$ by taking one or more steps of a stable and convergent iterative algorithm for minimizing $f(x_1,\cdots,x_{s-1},z,x_{s+1},\cdots,x_p)$ over $z\in\mathcal{X}_s$.