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:

  1. 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.".
  2. 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 complex 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.

| cite | improve this answer | |
  • $\begingroup$ Thanks for your answer! While I get the gist of your proof, I am not sure I follow the arguments for the second sentence of your proof: "Then there is a hyperplane M passing through p and disjoint from epi f." Could you please elaborate how you reached the above conclusion from the assumption that p is not in the convex hull of epi f? $\endgroup$ – madnessweasley Dec 14 '17 at 22:09
  • $\begingroup$ Which version of the separating hyperplane theorem do you use? Since the convex hull of epi f is not known to be closed (which is what we are trying to prove) or open, it seems as though the only version that we can use is the first "Hyperplane separation theorem" in the link you provided. However, that version has non-strict inequalities from which we can only deduce that M intersected with the convex hull is contained in the relative boundary of the convex hull; therefore, it is not clear to me how we can conclude that M is disjoint from epi f via this route. $\endgroup$ – madnessweasley Dec 14 '17 at 22:26
  • $\begingroup$ Right, the proof didn't work. Rewritten. $\endgroup$ – user357151 Dec 15 '17 at 1:43
  • $\begingroup$ Thanks, that seems to work. $\endgroup$ – madnessweasley Dec 19 '17 at 23:02
  • $\begingroup$ Are we assuming that $\operatorname{co}(\operatorname{epi} f) = \operatorname{epi} \operatorname{co} f$? I mean, your proof makes sense but it's not straightforward to have the equality between the sets above. $\endgroup$ – Gonzalo Benavides Jun 3 '19 at 7:01

Just thought I'll list out a reference I stumbled upon that answered my own question (although the proof assumes a fair bit of background knowledge). Corollary 3.7 of Rockafellar and Wets' Variational Analysis says (in part) the following:

Let $f:\mathbb{R}^n \to \overline{\mathbb{R}}$ be proper, lower semicontinuous, and coercive. Then con$f$ is proper, lower semicontinuous, and coercive. Furthermore, dom(con$f$) = con(dom$f$).

This readily applies to our setting since the function $f(\cdot) + I_X(\cdot)$, where $I_X$ denotes the indicator function of the set $X$, can be shown to be proper, lower semicontinuous, and coercive.

| cite | improve this answer | |

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.