# 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).

• Can you give details/references on "the unique minimizer is given by the centroidal Voronoi tessellation"? – Iosif Pinelis Aug 23 '19 at 4:27
• @IosifPinelis Actually this is what I wish to know. I've just learnt this aspect recently (as it's related to my current research), and as I saw your answer to mathoverflow.net/questions/337261/… So I suppose you know better than I... – Neymar Aug 23 '19 at 4:32
• The only reference that I have now is alice.loria.fr/publications/papers/2009/onCVT/onCVT.pdf Now I don't know any result concerning the uniqueness of minimizer, but I will let you know as soon as I find any related reference – Neymar Aug 23 '19 at 4:35
• I'll try to think about the uniqueness. Actually, some weaker versions of the uniqueness would be enough, as is now detailed a bit in my answer. – Iosif Pinelis Aug 23 '19 at 4:43
• @IosifPinelis Thank you very much for the consideration. If you don't mind I can email you my draft which might clarify the motivation. – Neymar Aug 23 '19 at 4:54

It's false. Take $$M = [0,1]$$ and $$N = \mathbb{R}$$ and define $$F(x,y) = 1 - |x-y|$$. Taking $$y_x = x$$ satisfies condition (2). Here $$\inf_M \sup_N F(x,y) = 1$$ and $$\sup_N \inf_M F(x,y) = 1/2$$, achieved when $$y = 1/2$$.

Edit: this answers the original question. The new version of the question, with $$N$$ compact, is falsified by taking $$N=[0,1]$$ in the above example.

• Thanks for the quick reply. Could the two operator be exchanged if $N$ is also assumed to be compact (see what I've edited)? – Neymar Aug 23 '19 at 0:01
• Just take $N = [0,1]$ in my example. – Nik Weaver Aug 23 '19 at 0:42

As pointed out by Nik Weaver, the minimax duality will not hold in general without assuming that $$F(x,y)$$ is convex in $$x$$.

However, if, for instance, for each $$y$$ the minimum of $$F(x,y)$$ in $$x$$ is attained at only one point, then under natural regularity conditions we have the minimax duality. See e.g. Theorem 1.1 or Theorem 1 or Theorem 1.

Remark 1: In Nik Weaver's counterexample, with $$M=N=[0,1]$$, the condition that the minimum of $$F(x,y)$$ in $$x$$ be attained at only one point was violated only for one value of $$y$$, namely $$y=1/2$$, and that was enough to bring the minimax duality down! On the other hand, as seen from the above citations, it is not necessary to require a unique minimizer in $$x$$ for each $$y$$ -- it is enough to require it just for one special $$y$$. In Nik Weaver's counterexample, $$1/2$$ would be precisely that special $$y$$ -- for which the uniqueness condition fails, though.

Remark 2: A necessary and sufficient condition for the minimax duality for generalized concave-convex functions $$F$$ is given here. This condition consists in the upper semi-continuity at $$0$$ of a certain functional constructed based on $$F$$.

• Thank you very kindly for the detailed comments (I did not know about Thereom 1.1 or Theorem 1 before). I have now added more details about function $F$ in PS2 (see above). After taking a look at your previous answers, I believe that you are familiar with optimal transport and Voronoi tessellation. Now to check the condition ensuring the minmax duality, it suffices to check the uniqueness of $argmin_{x\in M}F(x,y)$. For the function $F$ defined above, do you have any idea whether this condition is satisfied? Thanks a lot! – Neymar Aug 23 '19 at 4:19