Special Properties of 1-D convex function

We discuss a few special properties of one-dimensional function convex functions. The first says something about the slope of one-dimensional convex functions.

Lemma 1 Let ${f:[0,1]\rightarrow \mathbb{R}}$ be a (strictly) convex function, then the function ${g(x) = \frac{f(x)-f(0)}{x}, x\in(0,1]}$ is non-decreasing (strictly increasing).

Proof: By the definition of convex function, we have for any ${0<s<t\leq 1}$

$\displaystyle f(s) = f(\frac{s}{t} \times t + 0 \times \frac{t-s}{t}) \leq \frac{s}{t}f(t) +\frac{t-s}{t}f(0).$

Rearrange the above inequality gives

$\displaystyle \frac{f(s) -f(0)}{s}\leq \frac{f(t)-f(0)}{t}.$

The case for strict convexity is simply replacing the above ${\leq}$ by ${<}$ . $\Box$

The second asserts that the slope should always increase.

Lemma 2 If ${f:I\rightarrow \mathbb{R}}$ where ${I}$ is any connected set in ${\mathbb{R}}$ ,i.e., an interval which can be half open half closed or open or closed. The for any ${x<y<z\in I}$ , we have

$\displaystyle \frac{f(x)-f(y)}{x-y}\leq \frac{f(y)-f(z)}{y-z}$

Proof: This is just a twist of algebra.

$\displaystyle \begin{aligned} & \frac{f(x)-f(y)}{x-y}\leq \frac{f(y)-f(z)}{y-z}\\ \iff& \frac{y-z}{x-y}f(x) +f(z)\geq (1+ \frac{y-z}{x-y})f(y)\\ \iff & \frac{y-z}{x-y}f(x) +f(z)\geq \frac{x-z}{x-y}f(y)\\ \iff & \frac{y-z}{x-z}f(x) +\frac{x-y}{x-z}f(z)\geq f(y)\\ \iff & \frac{z-y}{z-x}f(x) +\frac{y-x}{z-x}f(z)\geq f(\frac{z-y}{z-x}x +\frac{y-x}{z-x}z)\\ \end{aligned} \ \ \ \ \ (1)$

where the last one holds due to the definition of convexity. $\Box$

The next lemma shows that convex functions in a real line must always be increasing or always decreasing or first decreasing and then increasing.

Lemma 3 Let ${f:I \rightarrow \mathbb{R}}$ where ${I}$ is an interval in ${\mathbb{R}}$ . The interval ${I}$ can be any one kind of ${[a,b],(a,b),(a,b],[a,b)}$ where ${-\infty \leq a<b\leq \infty}$ . Then ${f}$ is either always increasing or always decreasing or first decreasing and then increasing.

Proof: We may suppose ${f}$ is not always a constant since in this case, the assertion is true. Now suppose that ${f}$ is not always increasing and is also not always decreasing. Then there exists ${x<y <z}$ all in ${I}$ such that

$\displaystyle f(x) > f(y) , f(y)< f(z)$

$\displaystyle f(x) <f(y), f(y) > f(z).$

The latter case is not possible because it implies that

$\displaystyle \frac{f(x)-f(y)}{x-y}> 0 > \frac{f(y) - f(z)}{y-z}$

which contradicts the convexity of ${f}$ . Thus only the first case is possible.

Now if ${x,z}$ are interior point of ${I}$ , Then ${f}$ is continuous on the interior of ${I}$ and so is continuous on ${[x,z]}$ . This means that ${f}$ attains a minimum on ${[x,z]}$ at some ${x_0\in (x,z)}$ as ${f(y)<\min \{f(x),f(z)\}}$ . Now for any ${x_1<x_2<x<x_3<x_4<x_0}$ , by convexity and monotonicity of slope, we have

$\displaystyle \begin{aligned} \frac{f(x_1)-f(x_2)}{x_1-x_2}\leq \frac{f(x_2)-f(x)}{x_2-x_3}\leq \frac{f(x)-f(x_3)}{x-x_3}\leq \frac{f(x_3)-f(x_4)}{x_3-x_4}\leq \frac{f(x_4)-f(x_0)}{x_4-x_0}\leq 0. \end{aligned} \ \ \ \ \ (2)$

which implies ${f(x_1)\geq f(x_2)\geq f(x)\geq f(x_3)\geq f(x_4)}$ . Thus ${f}$ is decreasing on ${I\cap (-\infty,x_0]}$ . Similarly, using monotonicity of slope, we have ${f}$ is increasing on ${I\cap(x_0,\infty)}$ . Now if suppose either ${x}$ or ${z}$ is the end point of ${I}$ . We take the half points ${a_1 = \frac{x+y}{2},b_1 = \frac{y+z}{2}}$ . Then there are only three possible cases

${f(x)\geq f(a_1)\geq f(y)\geq f(b_1)\leq f(z)}$
${f(x)\geq f(a_1)\geq f(y)\leq f(b_1)\leq f(z)}$
${f(x)\geq f(a_1)\leq f(y)\leq f(b_1)\leq f(z)}$

The second case is ideal as ${a_1}$ and ${b_1}$ are interior point and we can proceed our previous argument and show ${f}$ is first decreasing and the then increasing. In the first case, we can take ${b_2 = \frac{b_1+z}{2}}$ and ask the relation between ${f(y),f(b_1),f(b_2)}$ and ${f(z)}$ . The only non-ideal case is that ${f(b_1)\geq f(b_2)\leq f(z)}$ (the other case gives three interior point such that ${f(y)\geq f(b_1)\leq f(b_2)}$ and we can employ our previous argument). We can then further have ${b_3 = \frac{b_2+z}{2}}$ . Again there will be only one non-ideal case that ${f(b_1)\geq f(b_2)\geq f(b_3)}$ .

Continuing this process, we either stop at some point to obtain a pattern ${f(y)\geq f(b_1)\leq f(b_i)}$ or the sequence ${b_n}$ satisfies ${f(b_i)\geq f(b_{i+1})}$ for all ${i}$ and ${\lim_{i\rightarrow \infty} b_i=z}$ . If ${z}$ is an interior point, then continuity of ${f}$ implies that ${\lim_{i\rightarrow \infty}f(b_i) = f(z)}$ . But this is not possible because ${f(z)> f(y)\geq f(b_i)}$ . Thus ${z}$ must be the end point of ${I}$ . Moreover, ${f}$ is actually decreasing on ${I/\{z\}}$ . Indeed, for any ${x_1>x_2, x_i\in I/\{z\}}$ for ${i=1,2}$ , there is a ${b_i}$ such that ${x_2>b_i}$ and so

$\displaystyle \frac{f(x_1)-f(x_2)}{x_1-x_2}\leq \frac{f(x_2)-f(b_i)}{x_2-b_i}\leq \frac{f(b_i)-f(b_{i+1})}{b_i-b_{i+1}}\leq 0.$

But since ${f(z)>f(y)}$ , we see ${f}$ is indeed decreasing on ${I/\{z\}}$ and increase/jump at the point ${z}$ .

The third case is similar, we will either have ${f}$ always increasing and only jump down at the end point ${x}$ or ${f}$ is just first decreases for some interval and then increases for some interval. $\Box$

Utilizing the above lemma, we can say 1) one-dimensional convex function is almost everywhere differentiable and 2) something about the boundary points of ${f}$ on a finite interval.

Lemma 4 Suppose ${f:[a,b] \rightarrow \mathbb{R}}$ is convex for some ${a\in \mathbb{R},b \in \mathbb{R}}$ . Then ${f(a) \geq \lim _{x\downarrow a}f(a) = f(a^+), f(b)\geq \lim_{x\uparrow b}f(x) =f(b^+)}$ .

The above lemma shows that a convex function on a finite open interval is uniformly continuous as it can be extended to the boundary. However, this property does not hold in higher dimension by considering ${f(x,y) = \frac{x^2}{y}}$ on ${x^2 \leq y, 0<y <1}$ and the point ${(0,0)}$ .

Three Squirrels

Little Discoveries of Optimization, Statistics, and Probability

Special Properties of 1-D convex function

Leave a Reply Cancel reply

Share this:

Like this:

Related

Leave a Reply Cancel reply