II.1.4.5: Majorization Duality

Because $g(x,y)\geq g(x,x)=f(x)$ for all $x,y\in\mathcal{X}$ we have seen that $$f(x)=\min_{y\in\mathcal{X}}g(x,y)$$ for all $x\in\mathcal{X}$. Thus $$\min_{x\in\mathcal{X}}f(x)=\min_{x\in\mathcal{X}}\min_{y\in\mathcal{X}}g(x,y)=\min_{y\in\mathcal{X}}h(y).$$ where $$h:y\rightarrow \min_{x\in\mathcal{X}}g(x,y).$$

Suppose, for example, that our majorization on $\mathcal{X}$ is of the form $$g(x,y)=f(y)+(x-y)'\mathcal{D}f(y)+\frac12(x-y)'A(y)(x-y),$$ with $A(y)$ positive definite for all $y$. This can be rewritten as $$\begin{align*} g(x,y)&=f(y)-\frac12(\mathcal{D}f(y))'A^{-1}(y)\mathcal{D}f(y)+\\ &+(x-z(y))'A(y)(x-z(y)), \end{align*}$$ with $z(y)\mathop{=}\limits^{\Delta}y-A^{-1}(y)\mathcal{D}f(y)$, and thus $$\begin{align*} h(y)=\min_{x\in\mathcal{X}}g(x,y)&=f(y)-\frac12(\mathcal{D}f(y))'(A(y))^+\mathcal{D}f(y)+\\&+\min_{x\in\mathcal{X}}(x-z(y))'A(y)(x-z(y)). \end{align*}$$