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!


2 Answers 2


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.

  • $\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
    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
    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
    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
    Aug 28, 2019 at 14:47

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.