2
$\begingroup$

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!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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). $\endgroup$
    – user128095
    Commented Aug 27, 2019 at 20:54
  • $\begingroup$ 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? $\endgroup$
    – xel
    Commented Aug 27, 2019 at 22:13
  • $\begingroup$ 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. $\endgroup$
    – user128095
    Commented Aug 28, 2019 at 11:12
  • $\begingroup$ in this case my answer is useless and you should probably remove the convex optimization tag $\endgroup$
    – xel
    Commented Aug 28, 2019 at 14:47
0
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.