## A consequence of convexity

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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?

-

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 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. – xn--qwertyuiop-86a Nov 29 at 17:01

## 3 Answers

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.

-
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)$ ? – xn--qwertyuiop-86a Nov 29 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 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? – xn--qwertyuiop-86a Nov 29 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 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. – xn--qwertyuiop-86a Nov 30 at 9:48
show 1 more comment

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-

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? – xn--qwertyuiop-86a Nov 30 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 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? – xn--qwertyuiop-86a Dec 1 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 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$ . – xn--qwertyuiop-86a Dec 2 at 12:09
show 1 more comment

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 72, "mathjax_display_tex": 9, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9439836144447327, "perplexity_flag": "head"}