I.6.6: Decomposition Methods

The following theorem is so simple it's almost embarassing. Nevertheless it seems to have some important applications to algorithm construction.

Theorem: Suppose $G: X\otimes Y\Rightarrow Z$ and $f$ is an extended real-valued function. Then $$\inf_{z\in\overline{Z}} f(z)=\inf_{x\in X}\inf_{y\in Y} f(G(x,y)),$$ where $\overline{Z}=G(X,Y)$. Moreover if the infimum on the right is attained in $(\hat x,\hat y)$, then the infimum on the left is attained in $\hat z=G(\hat x,\hat y)$.

Proof: In the eating (see below).QED

Here are some quick examples. First take $G(x,y)=x-y$. Then $$\begin{align*} \inf_{z}f(z)&=\inf_{x\geq 0}\inf_{y\geq 0}f(x-y)=\\ &=\inf_{x}\inf_{y}f(x-y). \end{align*}$$

Now take $G(x,\lambda)=\lambda x$, with $\lambda$ a scalar and $x$ a vector, $$\begin{align*} \inf_{z}f(z)&=\inf_{\lambda\geq 0}\inf_{x'x=1}f(\lambda x)=\\ &=\inf_{\lambda}\inf_{x'x=1}f(\lambda x)=\\ &=\inf_{\lambda}\inf_{x}f(\lambda x). \end{align*}$$ If $G(x,\lambda)=\frac{x}{\lambda}$, with $\lambda\not= 0$ and $x'x=1$, then $\overline Z$ is the set of all vectors $z\not= 0$. Thus $$\inf_{z\not= 0}f(z)=\inf_{\lambda\not= 0}\inf_{x'x=1}f(\frac{x}{\lambda}).$$ Somewhat less trivially, for a symmetric matrix argument $A$, $$\inf_{A}f(A)=\inf_{\mathbf{dg}(\Lambda)=\Lambda}\quad\inf_{K'K=I}\ f(K\Lambda K').$$ Observe we can always interchange the two infimum operations, because $\inf_{x\in X}\inf_{y\in Y}=\inf_{y\in Y}\inf_{x\in X}$. Because $f$ is extended real valued, the infimum always exists, although it may be $-\infty$.