I.6.2: Definition

Formalizing augmentation is straightforward. Suppose $f$ is a real valued function, defined for all $x\in\mathcal{X}$, where $\mathcal{X}\subseteq\mathbb{R}^n.$ Suppose there exists another real valued function $g,$ defined on $\mathcal{X}\otimes\mathcal{Y},$ where $\mathcal{Y}\subseteq\mathbb{R}^m,$ such that $$f(x)=\min_{y\in\mathcal{Y}}g(x,y).$$ We also suppose that minimizing $f$ over $\mathcal{X}$ is hard while minimizing $g$ over $\mathcal{X}$ is easy for all $y\in\mathcal{Y}$. And we suppose that minimizing $g$ over $y\in\mathcal{Y}$ is also easy for all $x\in\mathcal{X}.$ This last assumption is not too far-fatched, because we already know what the value at the minimum is.

I am not going to define hard and easy. What may be easy for you, may be hard for me.

Anyway, by augmenting the function we are in the block-relaxation situation again, and we can apply our general results on global convergence and linear convergence. The results can be adapted to the augmentation situation.

Note: augmentation duality.

$$h(y)=\min_{x\in\mathcal{X}}g(x,y)$$ then $$\min_{x\in\mathcal{X}}f(x)=\min_{x\in\mathcal{X}}\min_{y\in\mathcal{Y}}g(x,y)=\min_{y\in\mathcal{Y}}\min_{x\in\mathcal{X}}g(x,y)=\min_{y\in\mathcal{Y}}h(y).$$