Equivalence of full and sequential minimization

Question

I would like to show that two problems are equivalent, so that by solving one of them I get the optimal solution to the second. Formally, I'm trying to prove that: $$ \min_{\mathbf{x,y}\in\mathbf{X\times Y}}\; f(\mathbf{x,y})\; =\; \min_{\mathbf{x}\in\mathbf{X}}\; \min_{\mathbf{y}\in\mathbf{Y}} f(\mathbf{x,y}) $$ where $f$ is a closed, proper, convex function and $\mathbf{X,Y}$ are closed convex sets. Is this generally possible? So far I have the "easy" direction: $$ \min_{\mathbf{x}\in\mathbf{X}}\; \min_{\mathbf{y}\in\mathbf{Y}} f(\mathbf{x,y})=\min_{\mathbf{x}\in\mathbf{X}}\; \min_{\mathbf{x,y}\in\mathbb{R}^n\times\mathbf{Y}} f(\mathbf{x,y})\leq \min_{\mathbf{x}\in\mathbf{X}}\; \min_{\mathbf{x,y}\in\mathbf{X\times Y}} f(\mathbf{x,y}) = \min_{\mathbf{x,y}\in\mathbf{X\times Y}} f(\mathbf{x,y}) $$ where the first inequality is due to the fact that $\big(\mathbf{X\times Y}\big)\subseteq\mathbb{R}^n\times\mathbf{Y}$ and the second equality is since we already minimized w.r.t. $\mathbf{x}$, hence the inner minimization produced a solution which is already optimal in $\mathbf{x}$.

However I'm not sure how to get the opposite direction. Does anyone have any ideas? Maybe a different technique should be used?

Answer 1

Since you have minimums, they are reached at optimal points $\mathbb x^*$ and $\mathbb y^*$ ; and the value of the $\min$s is the value of $f$ at these points.

Note that if your sets and functions aren't convex and instead of minimums you have infimums (which aren't necessarily reached), this results still holds ; but instead of using points $\mathbb x^*, \mathbb y^*$ you have to use sequences that converge towards the right value, and be careful when taking the limit of limits...

Answer 2

To show the other direction, we consider the optimal vector $(\mathbf{x}^*,\mathbf{y}^*)\in\text{argmin}_{\mathbf{x,y}}f(\mathbf{x,y})$. Then we have the relation: $$ \min_{\mathbf{x,y}}f(\mathbf{x},\mathbf{y})\leq f(\mathbf{x}^*,\mathbf{y}^*)=\min_{\mathbf{x}}\min_{\mathbf{y}}f(\mathbf{x}^*,\mathbf{y}^*)\leq\min_{\mathbf{x}}\min_{\mathbf{y}}f(\mathbf{x},\mathbf{y}) $$ Coupled with the direction in the question, this proves that $\min_{\mathbf{x,y}}f(\mathbf{x},\mathbf{y})=\min_{\mathbf{x}}\min_{\mathbf{y}}f(\mathbf{x},\mathbf{y})$.