Calculate explicitly this convex envelope

convex-analysisconvex-hullsenvelopeoptimizationreal-analysis

Define a function $F:[0, \infty) \to [0,\infty)$ by
$$F(s) :=
\begin{cases}
\sqrt 2|\sqrt{s}-1|, & \text{ if }\, s \ge \frac{1}{4} \\
\sqrt{1-2s}, & \text{ if }\, s \le \frac{1}{4}
\end{cases}
$$

$F:[0,\infty) \to [0,\infty)$ is continuous function and satisfying $F(1)=0$; it is strictly increasing on $[1,\infty)$, and strictly decreasing on $[0,1]$.

Let $\hat F(x) = \sup \{ h(x) \mid \text{$h$ is convex on $[0, \infty)$}, h \le F \} \, $ be the convex envelope of $F$. Can we obtain an explicit expression for $\hat F$?

I have tried to plot $F$, but so far I have no idea how to approach the computation.


Motivation:

$F=\sqrt G$, where

$$G(s) :=
\begin{cases}
2(\sqrt{s}-1)^2, & \text{ if }\, s \ge \frac{1}{4} \\
1-2s, & \text{ if }\, s \le \frac{1}{4}
\end{cases}
$$

$G$ is convex, since it is $C^1$ with non-decreasing derivative. The function $G$ arises naturally in the context of this optimization problem.

Best Answer

Note that $\hat F$ is a convex function. It is also clear that $\hat F \ge 0$ since $F\ge 0$ and $\hat F(1) = 0$. First we have $$\tag{1} \hat F(s) = 0, \ \ \ \ \text{ for all } s>1.$$ To show (1), assume that contrary that $\hat F(s_0) >0$ for some $s_0 >1$. Let $\ell(x) = ax+b$ be the linear function passing through $(1,0)$ and $(s_0, \hat F(s_0))$. Since $\hat F$ is convex, $F(s) \le \ell (s)$ for all $s\in (1, s_0)$. By convexity of $\hat F$ again, this implies $$\tag{2} \hat F(s) \ge \ell(s), \ \ \ \ \text{for all } s> s_0.$$ Now since $F(s_0) >0$, the slope of $\ell$ is positive. Also
$$ \lim_{s\to +\infty} \frac{\sqrt 2 |\sqrt s-1|}{\ell(s)} = 0$$ Thus $\ell(s) >F(s)$ when $s$ is large enough. By (2) this is impossible since $\hat F \le F$. Thus we have shown (1).

It remains to find $\hat F(s)$ when $s <1$. Note that \begin{align} F'' \le 0 & \ \ \text{ on } [0,1/4), \\ F'' \ge 0 & \ \ \text{ on } (1/4,1). \end{align} and $$\tag{3} \lim_{s\to 1/4^+} F'(s) = -\sqrt 2 < 2 (\sqrt 2 -2) = \frac{F(1/4) - F(0)}{1/4-0} $$ Let $y=\ell_1(s)$ be the straight line which passing through $(0,1)$ and is tangential to $F$ at some $s\in (1/4, 1)$. If $(\bar s, F(\bar s))$ is the point of contact, then \begin{align} \frac{F(\bar s) - 1}{\bar s-0} &= F'(\bar s)\\ \Rightarrow \sqrt 2 (1-\sqrt {\bar s})-1 &= -\bar s (\sqrt 2\sqrt {\bar s})^{-1} \\ \Rightarrow 2 - 2\sqrt {\bar s} - \sqrt 2&= -\sqrt {\bar s}\\ \Rightarrow \bar s &= (2-\sqrt 2)^2 = 6-4\sqrt 2. \end{align}

Now we claim that

$$ h(s)= \begin{cases} \ell_1 (s) & \text{ if } s\in [0,\bar s], \\ F(s) & \text{ if } s\in (\bar s, 1],\\ 0 & \text{ if } s >1. \end{cases}.$$

Is the convex envelope. First of all, $h(s)$ is convex. Thus by defintion $h\le \hat F \le F$. If $h \neq \hat F$, then $h(s) < \hat F(s)$ for some $s\in (0, \bar s)$. But then $\hat F(s) > \ell_1(s)$, and $\ell_1$ is the line joining $(0,\hat F(0))$ and $\bar s, \hat F(\bar s))$, which contradicts the assumption that $\hat F$ is convex. Thus $h = \hat F$.

Related Question