A consequence of convexity - MathOverflow

A consequence of convexity

2012-11-29T13:10:10Z

Let $f:\mathbb{R}\to\mathbb{R}$ a convex decreasing function. Let $x_0 < x_1 < x_2$. Studying the behaviour of the difference quotient, it is clear that $$f(x_0)-f(x_2) \leq M (f(x_0)-f(x_1))$$ with $M=\frac{x_2-x_0}{x_1-x_0}>0$.

Now take $F:\mathbb{R}^2\to\mathbb{R}$ convex and decreasing with respect to each variable. Let $x_0 < x_1 < x_2$ and $y_0 < y_1 < y_2$. I ask if a similar condition holds, say for example $$F(x_0,y_0)-F(x_2,y_2) \leq M (F(x_0,y_0)-F(x_1,y_1))$$ with $M=\max ( \frac{x_2-x_0}{x_1-x_0}, \frac{y_2-y_0}{y_1-y_0} )$ or $M=\frac{x_2-x_0}{x_1-x_0}+\frac{y_2-y_0}{y_1-y_0}$.

Edit after Brian's answer: you may add the hypothesis that $F$ is $C^2$ and also the mixed derivative $\frac{\partial^2F}{\partial x\partial y}$ is non-negative.

Edit: under the additional assumption the answer is yes with $M=\max(\frac{x_2-x_0}{x_1-x_0},\ \frac{x_2-x_0}{x_1-x_0})$. But is it possible to reach the same conclusion without the additional assumption on the mixed derivatives?

Answer by Brian Rushton for A consequence of convexity

2012-11-29T13:32:51Z

You can use the triangle inequality to solve this by looking at each coordinate separately.

$F(x_0,y_0)-F(x_2,y_2)=F(x_0,y_0)-F(x_2,y_0)+F(x_2,y_0)-F(x_2,y_2)$ $\leq M_1(F(x_0,y_0)-F(x_1,y_0))+M_2(F(x_2,y_0)-F(x_2,y_1))$. Replacing $F(x_1,y_0)$ with $F(x_1,y_1)$ only increases the right side, and replacing both $x_2$'s on the far right side with $x_0$ only makes the right hand side larger by convexity. Finally, replace the last $x_0$ that we just added with $x_1$ without ncreasing the right hand side. This gives us $F(x_0,y_0)-F(x_2,y_2)\leq M(F(x_0,y_0)-F(x_1,y_1))$, where $M$ is $2\max(\frac{x_2-x_0}{x_1-x_0},\frac{y_2-y_0}{y_1-y_0})$. $M$ can also be the sum instead of the max, in which case we can drop the 2.

Edit: This argument doesn't work without additional assumptions; see the comments.

Answer by Daniel Spector for A consequence of convexity

2012-11-29T14:02:00Z

In general, whenever you have a (separately) convex function $f :\mathbb{R}^N \to \mathbb{R}$, which means it is convex in each variable, this implies the function is locally Lipschitz. The fact that it is decreasing allows you to make some explicit calculations of the constant, as Brian Rushton does, but in general the inequality looks like this:

$|f(x)-f(y)| \leq \frac{N}{r} (\sup_{B_{2r}} f - \inf_{B_{2r}} f) |x-y|$

for all $x,y \in B_{r}$.

Answer by Anton Petrunin for A consequence of convexity

2012-11-29T20:12:59Z

Without loss of generality, we can assume that $$\frac{y_2-y_0}{y_1-y_0}\ge\frac{x_2-x_0}{x_1-x_0}.$$ Let $x_2'$ be the real number number such that $$\frac{y_2-y_0}{y_1-y_0}=\frac{x'_2-x_0}{x_1-x_0}.$$ Clearly $x_2'\ge x_2$; therefore $$F(x_2',y_2)\le F(x_2,y_2).$$ From the one-dimensional case, you get $$F(x_0,y_0)-F(x_2',y_2) \leq M\cdot (F(x_0,y_0)-F(x_1,y_1))$$ with $$M=\frac{y_2-y_0}{y_1-y_0}=\max\left\{\frac{y_2-y_0}{y_1-y_0},\frac{x_2-x_0}{x_1-x_0}\right\}.$$ Hence the result follows.

It seems to be the optimal bound.

P.S. It turned out that the term "convex" was used in a nonstandard way; namely, xm wants to consider $F$ such that the restriction to any line parallel to the $x$-axis or to the $y$-axis is convex.

In particular $F(x,y)= -x\cdot y$ is "xm"-convex in positive quadrant. Note that in this example $F(t,t)=- t^{2}$, so $M$ has to be much bigger; maybe $$M=\left(\max\left\{\frac{y_2-y_0}{y_1-y_0},\frac{x_2-x_0}{x_1-x_0}\right\}\right)^2$$ will do.