Reference request on computational schemes for $\inf_{x\in\Omega^n}\sup_{y\in\mathbb R^n}F(x,y)$

Let $$\Omega\subset \mathbb R^d$$ be compact, $$\rho$$ be a density function on $$\Omega$$ and $$p_1,\ldots, p_n\in (0,1)$$ be weights satisfying $$\int_{\Omega}\rho(z)dz=1=\sum_{k=1}^n p_k$$. We consider the optimization problem $$\inf_{x\in\Omega^n}\sup_{y\in\mathbb R^n}F(x,y)$$, where $$F$$ is defined by

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

with $$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\}.$$

My question is whether there exists any known computational scheme for solving numerically $$\inf_{x\in\Omega^n}\sup_{y\in\mathbb R^n}F(x,y)$$?

Some thoughts: This question appears in Reference request on Min-Max theorem where I asked $$\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)$$. To the best of my knowledge (under suitable conditions):

(1) the first order partial derivatives $$\partial_x F$$ and $$\partial_y F$$ have explicit expression;

(2) the second order partial derivatives $$\partial_{xx} F$$ and $$\partial_{yy} F$$ have explicit expression;

(3) For fixed $$x\in\Omega^n$$, $$\sup_{y\in\mathbb R^n}F(x,y)$$ can be numerically computed (related to optimal transport);

(4) For fixed $$y\in\mathbb R^n$$, $$\inf_{x\in\Omega^n}F(x,y)$$ can be numerically computed (related to Lloyd's algorithm).

Any comments or references are highly appreciated!

Assuming I understood correctly that the function is smooth in $$x$$ and $$y$$ you can use Nemirovski's Mirror Prox from this paper

Nemirovski, Arkadi. "Prox-method with rate of convergence O (1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems." SIAM Journal on Optimization 15.1 (2004): 229-251.

which achieves the provably optimal convergence rate for this kind of problem.

• Thanks a lot for the reply. Yes, $\nabla_x F$, $\nabla^2_{xx} F$, $\nabla_y F$ and $\nabla^2_{yy} F$ can be explicitly calculated (not sure for $\nabla^2_{xy} F$ at this stage but I believe it is also explicit).
– user128095
Aug 27, 2019 at 20:54
• Oh, I just realized that I forgot to make sure that your function is concave in $y$ and convex in $x$. I just assumed so because you posted under the tag "convex optimization"... Can you confirm that this is indeed the case?
– xel
Aug 27, 2019 at 22:13
• The concavity of $y\mapsto F(x,y)$ follows by definition. However, $x\mapsto F(x,y)$ is not always convex. For example, taking $n=d=2$, $\Omega=[0,1]\times [0,1]$, $\rho(z)=\mathbf{1}_{\Omega}(z)$ and $y_1=y_2=0$, one may find $x\mapsto F(x,0)$ is not convex.
– user128095
Aug 28, 2019 at 11:12
• in this case my answer is useless and you should probably remove the convex optimization tag
– xel
Aug 28, 2019 at 14:47

This problem is called semi-discrete optimal transportation, you can find an algorithm in, e.g.,