Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
Do I understand correctly that you want your inequality for $f$ to hold with SOME $M$ that depends only on $x_j,y_j$ but not of $f$ ? Or you only want one of the two expressions you proposed for $M$ ? –  Alexandre Eremenko Nov 29 '12 at 13:34
    
Yes I want an inequality with some $M$ that depends only on the points $x_,y_j$, not necessarely one of those I proposed. –  user22980 Nov 29 '12 at 17:01

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
    
Thank you Brian. I think the statement after the triangular inequality should be "Repalcing $F(x_1,y_0)$ with $F(x_1,y_1)$". Please could you explain how do you use convexity to prove that $F(x_2,y_0)-F(x_2,y_1)\leq F(x_0,y_0)-F(x_0,y_1)$ ? –  user22980 Nov 29 '12 at 16:59
1  
@xn I can't explain it because it's not true! I had a false picture in my head. I was essentially claiming (in the smooth case) that having positive `unmixed' second partial derivatives implies that the mixed partial derivative is positive, which is not true. I apologize! –  Brian Rushton Nov 29 '12 at 17:25
    
Thank you as well, maybe I can extend my assumptions. If I assume all the second partial derivatives (mixed and pures) of F are $\geq0$, all should work right? –  user22980 Nov 29 '12 at 17:49
1  
As long as the derivatives exist, it should work. If the derivatives do not exist, then you would have to assume that $F(x,y)-F(x,y+\Delta Y)$ is a decreasing function of $x$ (you could also interchange $x$ and $y$ and have this work). This is analagous to regular convexity where $F(x)-F(x+\Delta x)$ is a decreasing function of $x$, and it probably has a name. But yes, it should work if all second derivatives are positive and $F$ is decreasing in each variable separately. –  Brian Rushton Nov 29 '12 at 18:43
1  
To improve the bound one may use: 1) triangular inequality; 2) convexity in $x$ and $y$; 3) $\frac{\partial F}{\partial x\partial y}\geq0$. And to sum up one obtains the bound $M=\max(\frac{x_2-x_0}{x_1-x_0},\ \frac{y_2-y_0}{y_1-y_0})$. In this way there's no $2$, so that $M$ does not depend on the dimension of the space. –  user22980 Nov 30 '12 at 9:48

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}$.

share|improve this answer

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.

share|improve this answer
    
Thank you Anton. Please could you explain how you use the one dimensional case to get the inequality? I found the same bound but adding the hypothesis $\frac{\partial F}{\partial x\partial y}\geq0$ (see the last comment to Brian's answer). Instead you don't use this hypothesis, right? –  user22980 Nov 30 '12 at 10:01
    
@xn--qwertyuiop-86a, consider function $$f(t)=F(x_0+(x_1-x_0)\cdot t, y_0+(y_1-y_0)\cdot t).$$ –  Anton Petrunin Nov 30 '12 at 23:46
    
@Anton Petrunin, let me see if I've understood. The inequality [F(x_0,y_0)-F(x_2',y_2)\leq M\cdot(F(x_0,y_0)-F(x_1,y_1))] is equivalent to [f(0)-f(\frac{y_2-y_0}{y_1-y_0}\leq M\cdot(f(0)-f(1)))] and this is true if $f$ is convex. But to have $f$ convex one need also $\frac{\partial^2F}{\partial x\partial y}\geq0$: it isn't enough to assume $F$ convex w.r.t. each variable separately. Correct? –  user22980 Dec 1 '12 at 10:26
    
I understood the question as "convex" and "decreasing with respect to each variable". Convex usually means convex on any line. It seems that you wanted to say "restriction to any line t↦(x,t) and t↦(t,y) is convex". Let me know if this is the case. –  Anton Petrunin Dec 1 '12 at 19:16
    
Yes, I wanted to say $F$ restricted to any line parallel to the $x$-axis or to the $y$-axis is convex. In other words (assuming $F$ regular enough) my hypotesis is that $\frac{\partial^2 F}{\partial x^2}\geq0$ and $\frac{\partial^2 F}{\partial y^2}\geq0$ . –  user22980 Dec 2 '12 at 12:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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