1
$\begingroup$

Let $L:[0,1]\times \mathbb R^m\times \mathbb R^n\to \mathbb R$ be defined by

$$L(\lambda, x,y):=\sum_{1\le i\le m}\alpha_i x_i + \sum_{1\le j\le n}\beta_j y_j -\sum_{1\le i\le m, 1\le j\le n} p_{i,j}\exp\big(x_i+y_j-(i-j)\lambda\big),$$

where $\alpha_i,\beta_j, p_{i,j}> 0$ are given such that

$$\sum_{1\le i\le m}\alpha_i= \sum_{1\le j\le n}\beta_j= \sum_{1\le i\le m, 1\le j\le n} p_{i,j}=1.$$

It is known that for every $\lambda\in [0,1]$, $\mbox{argmax}_{\mathbb R^m\times \mathbb R^n}L(\lambda, \cdot,\cdot)$ exists and is unique (up to a translation, i.e. $L(\lambda, x,y)=L(\lambda, x+c,y-c)$ for any $c\in \mathbb R$). My question is as follows: does there exist a compact set $K\subset \mathbb R^m\times \mathbb R^n$ such that

$$\mbox{argmax}_{\mathbb R^m\times \mathbb R^n}L(\lambda, \cdot,\cdot) \in K,\quad \forall \lambda \in [0,1]?$$

PS : For $x\in \mathbb R^m$ and $c\in \mathbb R$, $x+c:=(x_1+c,\ldots, x_m+c)$. The definition of $y-c$ is similar.

$\endgroup$
4
  • $\begingroup$ Can you provide a reference/link to a proof that "for every $\lambda\in [0,1]$, $\mbox{argmax}_{\mathbb R^m\times \mathbb R^n}L(\lambda, \cdot,\cdot)$ exists"? Also, clearly, you should rather be asking about compactness "up to the translation" (and define it). $\endgroup$ Commented Oct 31, 2023 at 13:42
  • $\begingroup$ @IosifPinelis This is the entropic optimal transport, and can be found in the lecture notes lucanenna.github.io/teaching/optimaltransport/lecture2.pdf (Proposition 1.8 and 1.9) Of course, the maximiser $(x,y)$ is unique if we require $x_1=0$ $\endgroup$
    – Fawen90
    Commented Oct 31, 2023 at 15:18
  • $\begingroup$ The proof of Proposition 1.9 is based on Proposition 1.7, which is left without proof. So, again, can you provide a reference/link to a proof that a maximizer exists? $\endgroup$ Commented Nov 1, 2023 at 20:21
  • $\begingroup$ @IosifPinelis Right. That's why I can not see the explicit dependency of the maximiser on $\lambda$. I'm still seeking for more detailed proofs and will let you know $\endgroup$
    – Fawen90
    Commented Nov 2, 2023 at 21:08

1 Answer 1

1
$\begingroup$

$\newcommand{\R}{\mathbb R}\newcommand{\la}{\lambda}\newcommand{\al}{\alpha}\newcommand{\be}{\beta}\newcommand{\tal}{\tilde\al}\newcommand{\ga}{\gamma}\newcommand{\K}{\mathfrak K}$The answer is yes -- assuming, as done in the comment by the OP, that $x_1=0$ (without this assumption, the answer would clearly be no).

Let \begin{equation*} S(\la):=\sup\{L(\la,x,y)\colon (x,y)\in(\R^n)^2,x_1=0\}. \tag{00}\label{00} \end{equation*} First, note that for all $\la\in[0,1]$ \begin{equation*} S(\la)\ge L(\la,0,0)\ge-p, \tag{10}\label{10} \end{equation*} where \begin{equation*} p:=\min\big\{p_{i,j}e^{-(i-j)}\colon i\in[m],j\in[n]\big\}>0 \end{equation*} and $[m]:=\{1,\dots,m\}$.

Next, \begin{equation*} \sum_{i\in[m]}\al_i x_i + \sum_{j\in[n]}\be_j y_j \le M_x+M_y, \end{equation*} where $M_x:=\max_{1\le i\le m}x_i$ and $M_y:=\max_{1\le j\le n}y_j$, and hence for all $\la\in[0,1]$ \begin{equation*} L(\la,x,y)\le M_x+M_y-pe^{M_x+M_y}. \end{equation*} So, for some real $C>0$, all $\la\in[0,1]$, and all $(x,y)\in(\R^n)^2$ such that $M_x+M_y>C$ we will have $L(\la,x,y)<-p$. So, in view of \eqref{00} and \eqref{10}, for all $\la\in[0,1]$ \begin{equation*} S(\la)>\sup\{L(\la,x,y)\colon(x,y)\notin E_C\}, \end{equation*} where \begin{equation*} E_C:=\{(x,y)\in(\R^n)^2\colon x_1=0, M_x+M_y\le C\}. \end{equation*}

Next, \begin{equation*} L(\la,x,y)<\sum_{i\in[m]}\al_i x_i+ \sum_{j\in[n]}\be_j y_j. \end{equation*} So, using \eqref{10} again, we see that \begin{equation*} S(\la)>\sup\{L(\la,x,y)\colon(x,y)\notin E_{p,C}\}, \tag{20}\label{20} \end{equation*} where \begin{equation*} E_{p,C}:=\Big\{(x,y)\in(\R^n)^2\colon x_1=0, M_x+M_y\le C,\ \\ \sum_{i\in[m]}\al_i x_i+ \sum_{j\in[n]}\be_j y_j\ge-p\Big\}. \end{equation*} Letting $\tal_2:=\al_1+\al_2$ and $\tal_i:=\al_i$ for $i=3,\dots,m$, for any $(x,y)\in E_{p,C}$ we have \begin{equation*} \begin{aligned} \al_1 x_2-p&\le\al_1x_2+\sum_{i\in[m]}\al_i x_i+ \sum_{j\in[n]}\be_j y_j \\ & =\al_1x_2+\sum_{i=2}^m\al_i x_i+ \sum_{j\in[n]}\be_j y_j \\ & =\sum_{i=2}^m\tal_i x_i+ \sum_{j\in[n]}\be_j y_j \\ & \le\sum_{i=2}^m\tal_i M_x+ \sum_{j\in[n]}\be_j M_y \\ & =M_x+M_y\le C, \end{aligned} \end{equation*} whence $x_2\le K:=\frac{p+C}{\al_1}$; since $x_2,\dots,x_m$ are interchangeable, similarly we get $x_j\le K$ for all $j=2,\dots,m$; recalling that $x_1=0$, we get \begin{equation*} 0\le M_x\le K \end{equation*} and then \begin{equation*} M_y\le C-M_x\le C\le K, \end{equation*} for all $(x,y)\in E_{p,C}$.

So, for any $(x,y)\in E_{p,C}$ \begin{equation*} \begin{aligned} -p&\le\sum_{i\in[m]}\al_i x_i+ \sum_{j\in[n]}\be_j y_j \\ &=\be_1 y_1+\sum_{i\in[m]}\al_i x_i+ \sum_{j=2}^n\be_j y_j \\ &\le\be_1 y_1+\sum_{i\in[m]}\al_i K+ \sum_{j=2}^n\be_j K \le \be_1 y_1+2K, \end{aligned} \end{equation*} whence $y_1\ge-\frac{p+2K}{\be_1}$; similarly, $y_j\ge-\frac{p+2K}{\be_j}$ for all $j\in[n]$ and $x_i\ge-\frac{p+2K}{\al_i}$ for all $i\in[m]$; so, \begin{equation*} \min_{i\in[m]}x_i\ge-k,\quad \min_{j\in[n]}y_j\ge-k, \end{equation*} where $k:=\frac{p+2K}\ga$ and $\ga:=\min(\min_{i\in[m]}\al_i,\min_{j\in[n]}\be_j)>0$.

So, \begin{equation*} E_{p,C}\subseteq\K:=[-k,K]^m\times[-k,K]^n. \end{equation*}

For each $\la\in[0,1]$, the function $L(\la,\cdot,\cdot)$ is strictly concave and continuous, and thus, in view of \eqref{00} and \eqref{20}, $L(\la,\cdot,\cdot)$ has a unique maximizer $(x_\la,y_\la)$, and $(x_\la,y_\la)$ is in the compact set $\K$, for all $\la\in[0,1]$. $\quad\Box$

$\endgroup$
1
  • $\begingroup$ I've contacted the author but still not response. I'll let u known once I obtain more details. Thx for the nice answer $\endgroup$
    – Fawen90
    Commented Nov 5, 2023 at 14:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .