3

I know that by definition, the convex envelope of a function $f$ ($f$ not necessarily convex), denoted $\operatorname{conv}f$, is the largest convex function majorized by $f$. That is, it is a convex function $h$ such that $h \leq f$. In fact, I believe that

$$\operatorname{conv}f(x)= \sup\{h(x) \mid h \text{ convex}, h \leq f\}\text{.}$$

My question is how can we directly apply this definition in order to find the convex envelope of $f(x)= \sin x$? Wouldn't it just be all points on and below the line $y= -1$? Not exactly sure why I can't figure this out, but I would really appreciate some helpful input regarding this issue.

Libertron
  • 4,415

1 Answers1

5

The only convex functions majorized by $\sin$ are the functions $h(x) = c$, where $c \le -1$. Hence $(\operatorname{conv} \sin)(x) = -1$.

To see this, suppose $h \le \sin$, $h$ is convex but $h$ is not constant. Then for some $x_1<x_2$, we have $h(x_1) \neq h(x_2)$. Suppose $h(x_1) < h(x_2)$, let $l(x) = \frac{x-x_2}{x_1-x_2}h(x_1) + \frac{x-x_1}{x_2-x_1}h(x_2)$, $l$ is affine and $\lim_{x \to \infty} l(x) = \infty$. Choose $x > x_2$, and write $x_2$ as a convex combination of $x_1,x$. This gives $x_2 = \frac{x_2-x_1}{x-x_1}x+\frac{x-x_2}{x-x_1}x_1$, and hence $h(x_2) \leq \frac{x_2-x_1}{x-x_1}h(x)+\frac{x-x_2}{x-x_1}h(x_1)$. Rearranging gives $l(x) \le h(x)$, which is a contradiction, as $h$ is bounded above by $1$ (since it is majorized by $\sin$). Hence $h$ is constant. Since $h \le \sin$, and $\sin (-\frac{\pi}{2}) = -1$, it follows that the constant is $\le -1$.

The following is a change from my previous answer, thanks to @byk7 (see the comments below) for catching a problem with my previous answer.

Here is another way of seeing this. Given a convex set $C \subset \mathbb{R}^n \times \mathbb{R}$, define $L_C(x) = \inf \{ \mu | (x,\mu) \in C \}$. It is straightforward to see (Theorem 5.3 Rockafellar) that $L_C$ is a convex function.

Now note that $\operatorname{conv} \sin=L_{\operatorname{co} ( \operatorname{epi} \sin)}$.

Since $\operatorname{co} ( \operatorname{epi} \sin) = \mathbb{R} \times [-1,\infty)$, we have $h(x) = \inf \{ \alpha | (\alpha,x) \in \operatorname{co} ( \operatorname{epi} \sin) \} = -1$.

copper.hat
  • 172,524
  • Is it always true that $\operatorname{epi} (\operatorname{conv} f) = \operatorname{co} ( \operatorname{epi} f)$ (for a function $f$ defined on a convex set)? – byk7 Jan 06 '20 at 12:21
  • @byk7: Yes. It ollows more or less directly from the definition. The convex function defined by $\operatorname{co} \operatorname{epi} f $ is majorised by $f$, so that gives $\ge$. If $h$ is a convex function majorised by $f$ then we must have $\operatorname{epi} f \subset \operatorname{epi} h$ and hence this gives $\le$. – copper.hat Jan 06 '20 at 14:59
  • I believe I have a counter example. :) Let $f:[0,\infty)\to\mathbb R,f(0)=1$ and $f(x)=x$ otherwise. Then $\operatorname{epi}(\operatorname{co} f)={[x,y]\in\mathbb R^2; 0\le x\le y}$, but $\operatorname{conv}(\operatorname{epi} f)={[x,y]\in\mathbb R^2; 0\lneq x\le y}\cup{[0,y]\in\mathbb R^2;y\ge 1}$. In particular, $\operatorname{conv}(\operatorname{epi} f)\subsetneqq\operatorname{epi}(\operatorname{co} f).$ – byk7 Jan 07 '20 at 15:32
  • Surely $\operatorname{conv} f = f$ since $f$ is convex? – copper.hat Jan 07 '20 at 16:15
  • My function $f$ (from the previous comment) is not convex on $[0,\infty)$. – byk7 Jan 09 '20 at 17:15
  • @byk7: It is. Why do you say that it is not? You would need something like $f(0) <0$ to make it non convex. – copper.hat Jan 09 '20 at 17:17
  • Ah, of course, my bad. (I thought convex functions are continuous, what i forgot is that that holds only in the (relative) interior.) Ok, one more try... Let $f:\mathbb R\to\mathbb R, f(0)=1$ and $f(x)=|x|$ otherwise. Then $\operatorname{epi}(\operatorname{co} f)\setminus\operatorname{conv}(\operatorname{epi} f)={[0,0]}$. – byk7 Jan 09 '20 at 20:27
  • @byk7: Nice example. I need to do more homework. It seems to work for continuous, but I need to do more leg work. – copper.hat Jan 09 '20 at 20:38
  • @byk7: I know where I got lost. I will clarify in a while. – copper.hat Jan 09 '20 at 20:47
  • 1
    @byk7: I added a clarification, thanks for your persistence. – copper.hat Jan 09 '20 at 21:16