2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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$ ? $\endgroup$ Nov 29, 2012 at 13:34
  • $\begingroup$ Yes I want an inequality with some $M$ that depends only on the points $x_,y_j$, not necessarely one of those I proposed. $\endgroup$
    – user22980
    Nov 29, 2012 at 17:01

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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)$ ? $\endgroup$
    – user22980
    Nov 29, 2012 at 16:59
  • 1
    $\begingroup$ @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! $\endgroup$ Nov 29, 2012 at 17:25
  • $\begingroup$ 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? $\endgroup$
    – user22980
    Nov 29, 2012 at 17:49
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 29, 2012 at 18:43
  • 1
    $\begingroup$ 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. $\endgroup$
    – user22980
    Nov 30, 2012 at 9:48
3
$\begingroup$

Here is an answer in the case $F$ is convex and decreasing in each variable --- that is the way I understood the original question.

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.

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – user22980
    Nov 30, 2012 at 10:01
  • $\begingroup$ @xn--qwertyuiop-86a, consider function $$f(t)=F(x_0+(x_1-x_0)\cdot t, y_0+(y_1-y_0)\cdot t).$$ $\endgroup$ Nov 30, 2012 at 23:46
  • $\begingroup$ @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? $\endgroup$
    – user22980
    Dec 1, 2012 at 10:26
  • $\begingroup$ 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. $\endgroup$ Dec 1, 2012 at 19:16
  • $\begingroup$ 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$ . $\endgroup$
    – user22980
    Dec 2, 2012 at 12:09
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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