1

Say I have a function $f(x,y)$. When is $$\min_{x,y}f(x,y)=\min_x\min_y f(x,y)=\min_y\min_x f(x,y)$$ and what happens when there are constraints?

Undertherainbow
  • 760
  • 1
    If the function f is convex, then the above are always equivalent. As long as the constrains are linear constraints or linear inequality constraints, then the problem is convex and, again, the problems are equivalent. – NicNic8 Dec 27 '20 at 14:14

1 Answers1

1

The below equation is always true, $$ \min_{x,y}f(x,y)=\min_x\min_y f(x,y)=\min_y\min_x f(x,y) $$

Let's take any point $x_0, y_0$. The following is always true by definition of $\min$, $$ f(x_0, y_0) \geq \ \min_y f(x_0, y) \geq \ \min_x\min_y f(x, y) $$ Note that the above holds for any point $x_0, y_0$. What if $x_0, y_0 = \arg\min_{x, y} f(x, y)$?

$$ \implies \min_{x, y} f(x, y) \geq \ \min_x\min_y f(x, y) $$

Let's prove the reverse direction for any point $x_0, y_0$,

$$ \min_{x, y} f(x, y) \leq f(x_0, y_0) $$

The above holds for any $y_0$, What if $y_0 = \arg\min_{y} f(x_0, y)$?

$$ \min_{x, y} f(x, y) \leq \min_{y} f(x_0, y) $$

The above holds for any $x_0$, What if $x_0 = \arg\min_{x} \arg\min_{y}f(x, y)$?

$$ \min_{x, y} f(x, y) \leq \min_x \min_{y} f(x, y) $$

Combining both eqns. We get the required result.

Shiv Tavker
  • 1,612
  • 7
  • 19
  • So for this proof to work, you would need to assume that $f$ is convex in $x$, convex in $y$, and jointly convex in $x$ and $y$ right? – Undertherainbow Dec 28 '20 at 14:34
  • 1
    @Undertherainbow No we do not need any such assumptions. The statement is true for all families of functions. One can even replace the $\min$ by $\inf$ to make it even more robust. – Shiv Tavker Dec 28 '20 at 17:45
  • Ah ok. This may not be generally applicable when there are constraints involving both variables right? – Undertherainbow Dec 28 '20 at 19:32
  • 1
    Actually it is applicable even with constraints. Let $X$ be the feasible space for $x$ and $Y$ be the feasible region for $y$. We can change all the equations to incorporate $x \in X$ and $y \in Y$. For e.g. $\min_{x\in X, y\in Y}$ – Shiv Tavker Dec 28 '20 at 19:37
  • But what about when the constraints are not separable, e.g. $xy\ge1$? – Undertherainbow Dec 28 '20 at 20:19
  • 1
    Well, its still applicable but may not be useful. Say you have a constraint $\phi(x, y) \leq 0$, $\min_{y} f (x_0, y)$ becomes $\min_{y \ | \ \phi(x_0, y) \leq 0} f(x_0, y)$ – Shiv Tavker Dec 29 '20 at 11:44
  • 1
    To make it more clear. The result is valid on each and every part of domain. Hence, even when $\phi(x, y) \leq 0$ and $\phi$ is an implicit function of $x, y$, constraint region is still part of the domain and the result is valid. – Shiv Tavker Dec 29 '20 at 11:52
  • Doesn't this result imply that when we don't need joint convexity in x and y to find a global optimum? We just need element-wise convexity? – Undertherainbow Jul 26 '23 at 14:27
  • Also you assume a unique minimum in each optimization right? – Undertherainbow Jul 26 '23 at 19:30