A consequence of convexity - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T12:27:27Z http://mathoverflow.net/feeds/question/114881 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/114881/a-consequence-of-convexity A consequence of convexity xn--qwertyuiop-86a 2012-11-29T13:10:10Z 2012-12-02T23:28:05Z <p>Let $f:\mathbb{R}\to\mathbb{R}$ a <em>convex decreasing</em> function. Let $x_0 &lt; x_1 &lt; 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$.</p> <p>Now take $F:\mathbb{R}^2\to\mathbb{R}$ <em>convex</em> and <em>decreasing</em> with respect to each variable. Let $x_0 &lt; x_1 &lt; x_2$ and $y_0 &lt; y_1 &lt; 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}$.</p> <p><em>Edit after Brian's answer</em>: 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.</p> <p><em>Edit</em>: 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 <em>without the additional assumption</em> on the mixed derivatives?</p> http://mathoverflow.net/questions/114881/a-consequence-of-convexity/114883#114883 Answer by Brian Rushton for A consequence of convexity Brian Rushton 2012-11-29T13:32:51Z 2012-11-29T23:13:32Z <p>You can use the triangle inequality to solve this by looking at each coordinate separately.</p> <p>$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.</p> <p><strong>Edit:</strong> This argument doesn't work without additional assumptions; see the comments.</p> http://mathoverflow.net/questions/114881/a-consequence-of-convexity/114885#114885 Answer by Daniel Spector for A consequence of convexity Daniel Spector 2012-11-29T14:02:00Z 2012-11-29T14:02:00Z <p>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:</p> <p>$|f(x)-f(y)| \leq \frac{N}{r} (\sup_{B_{2r}} f - \inf_{B_{2r}} f) |x-y|$</p> <p>for all $x,y \in B_{r}$.</p> http://mathoverflow.net/questions/114881/a-consequence-of-convexity/114924#114924 Answer by Anton Petrunin for A consequence of convexity Anton Petrunin 2012-11-29T20:12:59Z 2012-12-02T23:28:05Z <p>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.</p> <p>It seems to be the optimal bound.</p> <p><strong>P.S.</strong> 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. </p> <p>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.</p>