Timeline for Monge-Kantorovich duality with a $\{0,1\}$ cost function
Current License: CC BY-SA 4.0
22 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 4, 2019 at 18:57 | vote | accept | Tom Solberg | ||
| Apr 4, 2019 at 18:57 | comment | added | Tom Solberg | Ah, so the standard construction for $\varphi$ in Villani's book will automatically result in this fact. So, I just have to read those details more carefully to understand this. Thanks! | |
| Apr 4, 2019 at 18:34 | comment | added | Martin Kell | In the answer I added that phi is integer-valued. This follows from formula (5.17) in Villani’s book and the assumption that c is integer-valued. I don’t claim that a given dual solution is integer-valued. Most likely it is possible to glue together two solutions. One that is constant and another one that has exactly oscillation equal to 1. In a case i could imagine (I don’t have time to construct such an example), there might be a dual solution that has values 0,0.5 and 1. | |
| Apr 4, 2019 at 18:28 | history | edited | Martin Kell | CC BY-SA 4.0 |
added 18 characters in body
|
| Apr 4, 2019 at 18:12 | comment | added | Tom Solberg | The example in my comment shows that we can conclude that $\varphi(x_1)\in [-1,0]$, but I want to prove that in fact $\varphi(x_1)\in \{-1,0\}$, i.e. that $\varphi(x_1)$ must take on one of those two values. As far as I am aware, this is the standard notation for invervals versus discrete sets. | |
| Apr 4, 2019 at 9:53 | comment | added | Martin Kell | I don’t understand the problem as the argument does not claim any sharpness. Maybe it helps to clarify the notation: the constant function equal to 0 has values in $\{0,1\}$. The example given in your comment just verifies that $\varphi$ has values in $\{-1,0\}$. | |
| Apr 3, 2019 at 12:37 | comment | added | Dirk | Well, a supermizer $\varphi$ would like to make the objective as large as possible, so you would always want $\varphi(x_1)$ as large as possible (as long as the constraint stays satisfied). | |
| Apr 3, 2019 at 7:50 | comment | added | Tom Solberg | I am sure that I will smack myself in the forehead once this sinks in, but for the example I gave before with $c(x_2,y_1)=1$ and $c(x_1,y_2) = c(x_1,y_1) = c(x_2,y_2)=0$, these inequalities say that $-1 \leq \varphi(x_1)-\varphi(x_2) \leq 0$. What additional information do I need in order to conclude that one of these inequalities is tight? If I plug in, say, $x_2=x_0$ and $y_2 = y_0$, then I am left with $-1 \leq \varphi(x_1) \leq 0$. | |
| Apr 3, 2019 at 7:42 | comment | added | Martin Kell | Ah, this follows from the construction that the sum and difference of c evaluated at different couples is an integer. Thus phi is integer-values. | |
| Apr 3, 2019 at 7:39 | comment | added | Tom Solberg | That certainly helps, but I'm stuck on the fact that "oscillation of $\varphi$ is AT MOST 1" gives us that the oscillation of $\varphi$ is EQUAL to 1, if at all -- e.g., how does this exclude the possibility that $\varphi(x_1)=0.5$? | |
| Apr 3, 2019 at 7:37 | comment | added | Martin Kell | Was the right hand side. Was just a typo. This is true as c has values 0 or 1 so the difference can have at most the mentioned three values. The inequality then shows that the oscillation of phi is at most 1. Knowing phi at x0 is 0 gives the claims. | |
| Apr 3, 2019 at 7:35 | history | edited | Martin Kell | CC BY-SA 4.0 |
added 1 character in body
|
| Apr 3, 2019 at 7:33 | comment | added | Tom Solberg | I am really sorry that I keep having trouble with this, but I am still unclear on how the two inequalities lead one to conclude that "The left hand side has values in $\{-1,0,1\}$". Am I supposed to plug in $x_0,y_0$ for one of the $x_i,y_i$'s? For example, if $c(x_2,y_1) =1$ and $c(x_1,y_2) = c(x_1,y_1) = c(x_2,y_2)=0$, then the inequalities say that $-1 \leq \varphi(x_1)-\varphi(x_2) \leq 0$, but I don't understand why they have to actually take one of those values. | |
| Apr 2, 2019 at 9:00 | history | edited | Martin Kell | CC BY-SA 4.0 |
added 327 characters in body
|
| Apr 2, 2019 at 8:40 | comment | added | Tom Solberg | Sorry but I am still having trouble with the very last step -- how do the inequalities on $\varphi(x_1)-\varphi(x_2)$ and so forth, combined with the fact that $\varphi(x_0)=0$, lead to the desired conclusion? | |
| Mar 29, 2019 at 8:17 | comment | added | Martin Kell | I changed to a direct argument. | |
| Mar 29, 2019 at 8:05 | history | edited | Martin Kell | CC BY-SA 4.0 |
added 660 characters in body
|
| Mar 28, 2019 at 21:31 | comment | added | Tom Solberg | Could you give a reference that the standard construction shows that $\varphi$ is either identically $0$ or $0$ and somewhere $1$? I do not see how that follows from (5.17) in "Optimal transport old and new". | |
| Mar 28, 2019 at 15:13 | comment | added | Martin Kell | Since the value question was "already" answered in the question itself, I didn't include it. Now there is a short statement. | |
| Mar 28, 2019 at 15:11 | history | edited | Martin Kell | CC BY-SA 4.0 |
added 500 characters in body
|
| Mar 28, 2019 at 14:55 | comment | added | Dirk | How does this answer the question (which asks if there are optimal potentials with taking only specific values )? | |
| Mar 28, 2019 at 14:35 | history | answered | Martin Kell | CC BY-SA 4.0 |