Skip to main content
edited tags
Link
Iosif Pinelis
  • 127.8k
  • 8
  • 107
  • 229
added 37 characters in body
Source Link
user128095
user128095

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

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

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

added 37 characters in body
Source Link
user128095
user128095

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

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!

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

deleted 231 characters in body
Source Link
user128095
user128095
Loading
added 17 characters in body
Source Link
user128095
user128095
Loading
Source Link
user128095
user128095
Loading