Skip to main content
5 of 6
added 37 characters in body
user avatar
user avatar

Reference request on Min-Max theorem

Consider the following min-max problem

$$\inf_{x\in M} \sup_{y\in N} F(x,y),$$

where $F: M\times N\to\mathbb R$ is Lipschitz and $y\mapsto F(x,y)$ is concave for all $x\in M$. Could we derive $\inf_{x\in M} \sup_{y\in N} F(x,y)=\sup_{y\in N} \inf_{x\in M}F(x,y)$ if $M\subset \mathbb R^m$ and $N\subset\mathbb R^n$ are both compact?

PS: To the best of my knowledge, the reference on Min-Max theorem is from M. Sion : https://msp.org/pjm/1958/8-1/pjm-v8-n1-p14-p.pdf However, the convexity of $x\mapsto F(x,y)$ is missing in my case. Any comments or references are highly appreciated!

PS2: Thank Nik Weaver for the counterexample and Iosif Pinelis for providing a helpful condition. The function above is defined as

$$F(x,y)~:=~\sum_{k=1}^n\int_{V_k(x,y)}\left\{|z-x_k|^2-y_k\right\}\rho(z)dx+\sum_{k=1}^n p_ky_k,$$

where $x=(x_1,\ldots, x_n)\in\Omega^n$, $y=(y_1,\ldots, y_n)\in\mathbb R^n$ and

$$V_k(x,y)~:=~\big\{z\in\Omega:~ |z-x_k|^2-y_k\le |z-x_{i}|^2-y_{i},~ \forall 1\le i\le n\big\}.$$

Here $\Omega\subset\mathbb R^d$ is compact, $\rho$ is a density function on $\Omega$ and $p_1,\ldots, p_n\in (0,1)$ are given weights satisfying

$$\int_{\Omega}\rho(z)dz ~=~ 1 ~=~ \sum_{k=1}^n p_k.$$

According to Iosif Pinelis, to show $\inf_{x\in\Omega^n}\sup_{y\in\mathbb R^n}F(x,y)=\sup_{y\in\mathbb R^n}\inf_{x\in\Omega^n}F(x,y)$, it suffices to show, for each $y\in\mathbb R^n$, there exists a unique $x_y\in\Omega^n$ s.t. $\inf_{x\in\Omega^n}F(x,y)=F(x_y,y)$.

It is known that $(V_k)_{1\le k\le n}$ is the weighted Voronoi tessellation (if $y=(0,\ldots, 0)$ it becomes the Voronoi tessellation, and the unique minimizer is given by the centroidal Voronoi tessellation).

user128095