2
$\begingroup$

Let $F:[0,\infty) \to [0,\infty)$ be a $C^1$ strictly convex function.

Let $\lambda_n \in [0,1],a_n\le c<b_n \in [0,\infty)$ satisfy $$ \lambda_n a_n +(1-\lambda_n)b_n=c_n \tag{1}$$ and assume that $c_n \to ֿ\infty$. (which implies $b_n \to ֿ\infty$). $c>0$ is just some constant, to make $a_n$ bounded.

Set $D_n=\lambda_nF(a_n)+(1-\lambda_n)F(b_n)-F\big(c_n\big) $, and assume that $\lim_{n \to \infty}D_n=0$

Question: Does $\lambda_n \to 0$?

My intuition is that even if $F$ becomes "less convex" (closer to being affine) when $x \to \infty$, then we cannot put to much weight on the $a_n$-since otherwise we get hit by the "convexity gap" between $a_n$ and $b_n$ by a non-negligible amount, which should make $D_n$ large.

Edit:

This is an attempt to understand Ron P's answer:

We have $D(a_n,c_n,b_n)=\lambda_n F(a_n)+(1-\lambda_n)F( b_n)-F(c_n)$, where $ \lambda_n a_n +(1-\lambda_n) b_n=c_n$.

Similarly, $D(a,c_n,b_n)=\tilde \lambda_n F(a)+(1-\tilde \lambda_n)F( b_n)-F(c_n)$, where $ \tilde\lambda_n a +(1-\tilde \lambda_n) b_n=\tilde c_n$.

Suppose that $a_n \to a$. (This implies $\lambda_n-\tilde \lambda_n \to 0$). We have

$$D(a_n,c_n,b_n)-D(a,c_n,b_n)=\lambda_n F(a_n)-\tilde \lambda_n F(a)+(\tilde \lambda_n-\lambda_n)F(b_n). \tag{2}$$ The first term tends to zero, since $F(a_n) \to F(a)$ and $\lambda_n-\tilde \lambda_n \to 0$.

Why does the second term tend to zero? we don't have control over $F(b_n)$, right?

$\endgroup$
7
  • 1
    $\begingroup$ It should be easy to make a strictly convex function with $F(2n)/2+F(0)/2 -F(n)=1/n$, as envelope of a family of lines. (that is a counterexample with $a_n=0, c_n=n, b_n=2n, \lambda_n=1/2$) $\endgroup$ Aug 18, 2020 at 6:39
  • $\begingroup$ One can also just do it for powers of 2, b_n=2^n $\endgroup$ Aug 18, 2020 at 7:21
  • $\begingroup$ Dear Pietro, it seems that your suggestion cannot work. You may see Iosif Pinelis's answer below which proves that the answer is in fact positive. $\endgroup$ Aug 18, 2020 at 18:31
  • $\begingroup$ Yes! I realized it with the tentative counterexample in the answer then deleted. The fact it does not work may be turned into a positive proof $\endgroup$ Aug 19, 2020 at 6:27
  • $\begingroup$ Is assumed that $F$ is increasing? $\endgroup$
    – Ron P
    Aug 20, 2020 at 11:32

2 Answers 2

4
$\begingroup$

The answer is yes.

Indeed, by rescaling, without loss of generality (wlog) $c=1$. To simplify the notations, let $f:=F$, $a:=a_n$, $b:=b_n$, $c:=c_n$, $t:=\lambda_n$, $D:=D_n$. Passing to a subsequence, wlog $a\to a_*\in[0,1]$ and $t\to t_*\in(0,1]$. Also, wlog $a+2\le c$, since $a\le1$ and $c\to\infty$. Also, wlog $b>c$, since wlog $t>0$ and $c>a$.

By the convexity of $f$ and inequalities $a+1\le a+2\le c$, \begin{equation*} f(a+1)\ge f(c)+\frac{a+1-c}{b-c}\,(f(b)-f(c)).\tag{1} \end{equation*} Using now the convexity of $f$ again together with the inequality $a+2\le c$ and (1), we have \begin{align*} 0\le d&:=\frac{f(a)+f(a+2)}2-f(a+1) \\ &\le \frac{f(a)}2+\frac12\,\frac{(c-a-2)f(a)+2f(c)}{c-a}-f(a+1) \\ &=\tilde d:=\frac{(c-a-1)f(a)+f(c)}{c-a}-f(a+1) \\ &\le\frac{(c-a-1)f(a)+f(c)+D}{c-a} \\ &\ \ -\Big(f(c)+\frac{a+1-c}{b-c}\,(f(b)-f(c))\Big) \\ &=\tilde D:=\frac{b-a-1}{b-a}\frac Dt\sim\frac D{t_*}\to0, \end{align*} so that \begin{equation*} d\to0. \tag{2} \end{equation*} On the other hand, \begin{equation*} d\to\frac{f(a_*)+f(a_*+2)}2-f(a_*+1)>0 \end{equation*} by the strict convexity of $f$. This contradicts (2). $\Box$

Remark: As seen from the above, condition $c\to\infty$ can be relaxed to $\liminf(c-a)>0$.


The above solution might look somewhat mysterious. In fact, the idea is a rather simple geometric one. For any real $A,B,C$ such as $A\le B\le C$, let the "gain" $g(A,B;C)$ denote the distance between the point on the graph of the convex function $f$ with abscissa $C$ and the point with the same abscissa on the chord connecting the points on the graph of $f$ with abscissas $A$ and $B$.

So (see the picture below), $D=g(a,b;c)$ and $\tilde d=g(a,c;a+1)$, where $\tilde d$ is as defined in the above multi-line display. In that display, it was shown that $\tilde d\le\tilde D$, which is clear from the picture. Also, if $t$ is bounded away from $0$ -- that is, if $c/b$ is bounded away from $1$, then, as it is clear from the picture by looking at the similar triangles, we have $\tilde D\asymp D\to0$; cf. the last line of the above multi-line display. This and the inequality $\tilde d\le\tilde D$ imply $\tilde d\to0$.

By the convexity of $f$, for any fixed real $A,C$ such as $A\le C$, the gain $g(A,B;C)$ is nondecreasing in $B\in[C,\infty)$ (here you may want to draw another picture). Therefore and because $a+2\le c$, we have $d=g(a,a+2;a+1)\le g(a,c;a+1)=\tilde d$, so that $d\le\tilde d$, which was shown in the first three lines of the above multi-line display.

This is the geometric explanation of (1) and the above multi-line display.

enter image description here

$\endgroup$
1
  • $\begingroup$ wow! This is an amazing answer, really. I liked a lot your geometric explanation and picture-very clear. (and indeed it was a bit mysterious before you added them). Just to be sure- in your third (last) inequality you have added the non-negative term $\frac{D}{c-a}$? I am also not sure how did you deduce that this was the "right thing" to add in order to get $\tilde D$. Did you also use the visual intuition from the picture here, or did you just take the difference and then wrote it "backwards"? $\endgroup$ Aug 19, 2020 at 12:10
2
$\begingroup$

First let's reformulate the question. For $0\leq a\leq c\leq b$, let $\lambda=\lambda(a,c,b)\in[0,1]$ be the number such that $c=\lambda a + (1-\lambda)b$, and for $f\colon \mathbb R_+\to\mathbb R$ define $$ D_f(a,c,b)= \lambda f(a)+(1-\lambda)f(b)-f(c). $$

Lemma 1. Let $f\colon \mathbb R_+\to\mathbb R$ be strictly convex and continuously differentiable. Let $0\leq a_n\leq c_n\leq b_n$ be sequences such that $a_n$ is bounded, $c_n-a_n$ is bounded away from 0, and $\limsup \lambda(a_n,c_n,b_n)>0$. Then, $\limsup D_f(a_n,c_n,b_n)>0$.

We first apply a sequence of reduction steps that allow us to assume wlog that $a_n=0$, $c_n\geq 1$, , for all $n$, and $\liminf\lambda(a_n,c_n,b_n)>0$. If you trust that that is possible, you may skip directly to Lemma 5 below.

By taking a sub-sequence $n'$ on which $\liminf \lambda(a_{n'},c_{n'},b_{n'})>0$, Lemma 1 follows from Lemma 2.

Lemma 2. Let $f\colon \mathbb R_+\to\mathbb R$ be strictly convex and continuously differentiable. Let $0\leq a_n\leq c_n\leq b_n$ be sequences such that $a_n$ is bounded, $c_n-a_n$ is bounded away from 0, and $\liminf \lambda(a_n,c_n,b_n)>0$. Then, $\limsup D_f(a_n,c_n,b_n)>0$.

By further taking a sub-sequence $n'$ on which both $a_{n'}$ converges, Lemma 2 follows from Lemma 3.

Lemma 3. Let $f\colon \mathbb R_+\to\mathbb R$ be strictly convex and continuously differentiable. Let $0\leq a_n\leq c_n\leq b_n$ be sequences such that $a_n\to a$, $c_n-a_n$ is bounded away from 0, and $\liminf \lambda(a_n,c_n,b_n)>0$. Then, $\limsup D_f(a_n,c_n,b_n)>0$.

For any fixed $\epsilon>0$, the functions $\lambda(a,c,b)$ is continuous in $a$ uniformly in $c$ and $b$ over the domain $\epsilon\leq a +\epsilon\leq c\leq b$; therefore, under the assumptions of Lemma 3, $0<\liminf\lambda(a_n,c_n,b_n)=\liminf\lambda(\lim a_n,c_n,b_n)$. Furthermore, for $\lim a_n <a<\liminf c_n$ small enough, we have $\liminf\lambda(a,c_n,b_n)>0$. Since $D_f(a,c,b)$ is decreasing in $a$, $\limsup D_f(a_n,c_n,b_n)\geq\limsup D_f(a,c_n,b_n)$. Therefore, Lemma 3 follows from Lemma 4.

Lemma 4. Let $f\colon \mathbb R_+\to\mathbb R$ be strictly convex and continuously differentiable. Let $0\leq a\leq c_n\leq b_n$ be sequences such that $c_n-a$ is bounded away from 0, and $\liminf \lambda(a,c_n,b_n)>0$. Then, $\limsup D_f(a,c_n,b_n)>0$.

Let $T\colon \mathbb R\to\mathbb R$ be the affine transformation that maps $a$ to $0$ and $\inf c_n$ to $1$. Replacing $f$ by $F=f\circ T^{-1}$, and $a,c_n,b_n$ by $T(a),T(c_n),T(b_n)$ respectively, Lemma 4 follows from Lemma 5.

Lemma 5. Let $F\colon \mathbb R_+\to\mathbb R$ be strictly convex and continuously differentiable. Let $1\leq c_n\leq b_n$ be sequences such that $\liminf \lambda(0,c_n,b_n)>0$. Then, $\limsup D_F(0,c_n,b_n)>0$.

Proof of Lemma 5. We assume wlog that $F(0)=0$ and denote $\lambda_n=\lambda(0,c_n,b_n)$ and $D_n=D_F(0,c_n,b_n)$.

Define a function $G\colon [1,\infty)\times (1,\infty)\to \mathbb R$ by $$ G(x,y)=\tfrac 1 y F(xy)-F(x). $$

Claim 6. $G$ is positive and increasing in both $x$ and $y$.

Proof of Claim 6. Since $F$ is strictly convex, $F(0)=0$, and $x = 1/y(xy)+(1-1/y)0$, $G(xy)>0$. Since $F'$ is increasing, we have $\frac {d}{dx}G(xy)=F'(xy)-F'(x)>0$, so $G$ increases in $x$. Since $F'$ is increasing and $G(x,y)=1/y\int_0^yF'(xt)x\,dt - F(x)$, $G$ increases in $y$, completing the proof of Claim 6.

Suppose there is $\lambda_0>0$ such that $\lambda_n\geq \lambda_0$ for all $n$. Then, $$ D_n = G(c_n,1/(1-\lambda_n))\geq G(1,1/(1-\lambda_0)>0, \quad\text{for all $n$.} $$ QED

$\endgroup$
5
  • $\begingroup$ @AsafShachar you're right. I should elaborate about this point. I will do it soon. The idea is to replace $a_n$ with its limit in the expression of $D_n$. By continuity, such a modification does not change whether it converges to zero or not. $\endgroup$
    – Ron P
    Aug 21, 2020 at 7:09
  • $\begingroup$ @AsafShachar I've elaborated on "re-scaling." Note that the answer does not assume neither that $F$ is non-negative, nor that $c_n\to\infty$, rather just that it is bounded away from $a_n$. $\endgroup$
    – Ron P
    Aug 21, 2020 at 12:39
  • $\begingroup$ Thanks for the elaboration. I am still somewhat troubled tough. It seems to me that the most crucial non-trivial step is in passing from Lemma 3 to Lemma 4 (from $a_n$ to $\lim a_n$). I understand why $\liminf\lambda(a_n,c_n,b_n)=\liminf\lambda(\lim a_n,c_n,b_n)$ (because the difference between the 'lambdas' tend to zero.) However, I don't see why $\limsup D_f(a_n,c_n,b_n)= \limsup D_f(\lim a_n,c_n,b_n)$. I think it reduces to $\lim_{n \to \infty }( \lambda(a_n,c_n,b_n)-\lambda(\lim a_n,c_n,b_n))F(b_n)=0, $ but I don't see why this limit should be zero. $\endgroup$ Aug 24, 2020 at 11:39
  • $\begingroup$ I have edited the question to make my misunderstanding clear. Thanks. $\endgroup$ Aug 24, 2020 at 11:39
  • $\begingroup$ @AsafShachar, you're right. I've corrected the reduction from Lemma 3 to Lemma 4. Instead of using the continuity of $D_f$ in $a$, I now use monotonicity. $\endgroup$
    – Ron P
    Aug 25, 2020 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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