Let $x_1,x_2,y_1,y_2$ be scalar points such that $x_1<x_2$ and $y_1<y_2$. Let $h$ be a convex function from $\mathbb{R}$ to $\mathbb{R}_{+}$. Then,

$$h(x_1-y_1) + h(x_2-y_2) \leq h(x_1-y_2) + h(x_2-y_1)$$

I need this step to caracterise the solution of a 1D Monge Problem. It was thrown in a proof like if it is a trivial fact but I have no idea how to apply the convexity here.


Hint: Represent both $x_1 - y_1$ and $x_2 - y_2$ as convex combinations of the points $x_1 - y_2$ and $x_2 - y_1$.

  • $\begingroup$ I can see that if if have $x:=x_1 - y_2$, $y := x_2 - y_1$ and $\lambda \in (0,1)$ such that $h(x_1-y_1) = h(\lambda x + (1-\lambda )y) \leq \lambda h(x) + (1-\lambda)h(y)$ and $h(x_2-y_2) = h((1-\lambda ) x + \lambda y) \leq (1-\lambda) h(x) + \lambda h(y)$ then summing both terms give the results. But it is not possible to find such a $\lambda$ $\endgroup$ – DimSum Nov 22 '19 at 13:34
  • $\begingroup$ Then you should check your calculations. It should be the same $\lambda$. $\endgroup$ – gerw Nov 22 '19 at 20:51
  • $\begingroup$ Yes, I made a mistake, thanks I have it. $\endgroup$ – DimSum Nov 23 '19 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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