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$ 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
    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$ 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
    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
    Nov 5, 2023 at 14:52

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.