Let $X \subset \mathbb{R}^n$ be a nonempty compact convex set and $f: X \to \mathbb{R}$ be lower semicontinuous on $X$. How do I prove that the convex envelope of $f$ on $X$, i.e. the largest convex function majorized by $f$ on $X$, is lower semicontinuous on $X$?
Evidence suggesting that the above conclusion holds:
- Page 349 of this paper states without proof: "It is well known and easy to see that" (the above convex envelope) "is l.s.c.".
- Page 253 of this paper states the following more general result without proof: "For any l.s.c. function, the epigraph of its convex envelope over a closed set is a closed convex set" (they replace the assumption that $X$ is compact with the weaker assumption that $X$ is closed).
Thoughts: The convex envelope, being a convex function on $X$, is continuous (and therefore lower semicontinuous) on the relative interior of $X$. Therefore, the only points at which the convex envelope may not be lower semicontinuous are points on the relative boundary of $X$; intuitively, this seems to contradict the fact that the function $f$ is lower semicontinuous on $X$, but I don't seem to be able to complete the argument. Moreover, the above papers seem to suggest that the conclusion follows easily from well-known results.
The frequent appearance of lower semicontinuity to convex analysis is related to the concept of the epigraph of $f$, $$\operatorname{epi}f=\{(x,y)\in\mathbb{R}^{n+1}: x\in \operatorname{dom}f,\ y\ge f(x)\}$$ Namely, the convexity of $f$ is equivalent to the convexity of $\operatorname{epi} f$, and the lower semicontinuity of $f$ (assuming its domain is closed) is equivalent to $\operatorname{epi}f$ being a closed set. Both of these are easy to prove.
The relation $g\le f$ is equivalent to $\operatorname{epi} f\subseteq \operatorname{epi}g$. Hence, we are looking for the smallest convex set containing $\operatorname{epi}f$, i.e., its convex hull $\operatorname{conv}(\operatorname{epi}f)$. The goal is to prove that the convex hull is closed. In general, the convex hull of a closed set is not closed, but here the structure of the set (epigraph of an lsc function on a compact set) helps.
Take any convergent sequence $p_k = (x_k, y_k)$ from $\operatorname{conv}(\operatorname{epi}f)$. Our goal is to prove that its limit $p=(x,y)$ is also in $\operatorname{conv}(\operatorname{epi}f)$. By Carathéodory's theorem, there exist $(n+2)$ sequences $p_{j,k} = (x_{j,k}, y_{j,k})\in \operatorname{epi} f$ with $j\in \{1, \dots, n+2\}$, such that $$p_k = \sum_{j=1}^{n+2} c_{j,k} p_{j,k}$$ for each $k$, where $c_{j,k}\in[0,1]$ and $\sum_{j=1}^{n+2} c_{j,k} = 1$. Using the compactness of $X$ and of $[0,1]$, we can pass to subsequences such that $x_{j,k} \to x_j^* \in X$ and $c_{j,k}\to c_j^* \in [0,1]$ for each $j$. The point $$p^* = \sum_{j=1}^{n+2} c_{j}^* (x_j^*, f(x_j^*))$$ satisfies $$ \sum_{j=1}^{n+2} c_{j}^* x_j^* = \lim_{k\to\infty} x_{k} = x$$ and $$ \sum_{j=1}^{n+2} c_{j}^* f(x_j^*) \le \lim_{k\to\infty} \sum_{j=1}^{n+2} c_{j,k} f(x_{j,k}) \le \lim_{k\to\infty} y_{k} = y $$ Thus, $p^*$ either coincides with $p$ or lies directly below it. Since $p^*\in \operatorname{conv}\operatorname{epi} f$, it follows that $p\in\operatorname{conv}\operatorname{epi} f$ as well.