2

Consider the following max-min problem: $$\sup_{x\in D_{X}}\inf_{y\in D_Y} f(x, y),$$ where $f:D_{X}\times D_{Y}\to \mathbb{R}$. Assume that $D_{Y}$ can be partitioned into $k$ disjoint union of sets $D_{Y, 1}, D_{Y, 2}, \dots, D_{Y, k}$, i.e., $D_{Y}=\cup_{i=1}^k D_{Y, i}$. Let $f^*_i=\sup_{x\in D_{X}}\inf_{y\in D_{Y, i}} f(x, y)$. Intuitively, it seems to me that the following is correct: $$\inf_{i}f^*_i=\inf_{i}\sup_{x\in D_{X}}\inf_{y\in D_{Y, i}} f(x, y)=\sup_{x\in D_{X}}\inf_{y\in D_Y} f(x, y).$$ If this is true, how to prove that the second equality holds? If not, what is the problem? Thanks.

Chasel Weng
  • 186

1 Answers1

1

I may have made some progress with this but couldn't finish. Since $D_{Y,i}\subset D_{Y}$, we have $$\inf_{y\in D_{Y,i}} f(x,y)\geq \inf_{y\in D_Y} f(x,y),\forall i,\forall x$$ Moreover, since there is only finitely many of $D_{Y,i}$'s, for any $x$ the infimum should happen in one of the partition members; i.e. $\exists i^*(x)\in\{1,\dots,k\}$ such that

$$\inf_{y\in D_{Y,i^*(x)}} f(x,y)= \min_{i\in\{1,\dots,k\}} \inf_{y\in D_{Y,i}} f(x,y) = \inf_{y\in D_Y} f(x,y)$$

Take the $\sup$ over $x$ to get $$\sup_{x\in D_X}\min_{i\in\{1,\dots,k\}} \inf_{y\in D_{Y,i}} f(x,y) = \sup_{x\in D_X}\inf_{y\in D_Y} f(x,y)$$

So the answer to your question depends on whether we can switch the order of sup and min in the expression above. This might be true but I am not sure. Maybe von-Neuman min-max theorem can be applied since at least we have a min instead of an inf?

Hassan A
  • 29
  • Hi, thanks for your reply. Using your first fact, I can show $\inf_i\sup_{x\in D_X}\inf_{y\in D_{Y, i}}f(x, y)\ge \sup_{x\in D_x}\inf_{y\in D_y}f(x, y)$. The reverse direction as you said, may require von-Neuman min-max theorem. However, I have a question about this. Let $h(x, i)\triangleq \inf_{y\in D_{Y, i}}f(x, y)$. We want to exchange the $\inf$ and $\sup$ in this expression $\inf_{i}\sup_{x\in D_X} h(x, i)$. von-Neuman's theorem says that if $h(x, i)$ is concave in $x$ and convex in $i$, then we can exchange the order. Here, I am not sure how to verify the convexity of $h(x, i)$ in $i$. – Chasel Weng Sep 15 '19 at 14:14