2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Can you give details/references on "the unique minimizer is given by the centroidal Voronoi tessellation"? $\endgroup$ – Iosif Pinelis Aug 23 '19 at 4:27
  • $\begingroup$ @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... $\endgroup$ – Neymar Aug 23 '19 at 4:32
  • $\begingroup$ 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 $\endgroup$ – Neymar Aug 23 '19 at 4:35
  • $\begingroup$ 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. $\endgroup$ – Iosif Pinelis Aug 23 '19 at 4:43
  • $\begingroup$ @IosifPinelis Thank you very much for the consideration. If you don't mind I can email you my draft which might clarify the motivation. $\endgroup$ – Neymar Aug 23 '19 at 4:54
2
$\begingroup$

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.

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

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$.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Neymar Aug 23 '19 at 4:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.