Show that if a proper function has a subgradient everywhere in its convex domain, then it's convex.

Question

Let $f:\mathbb{R}^n\rightarrow (-\infty,\infty]$ be proper. If $\operatorname{dom} f$ is convex and $\operatorname{dom} \partial f=\operatorname{dom} f$, show that $f$ is convex. I wonder what is the angle to prove such a statement?

Answer 1

The idea is straightforward; if we can write $f(x) = \sup_{h \in H} h(x)$ where each $h \in H$ is convex, then $f$ is convex.

Let $H = \{ y \mapsto f(x)+g^T(y-x) | x \in \operatorname{dom}f, g \in \partial f(x) \}$.

Answer 2

Let $H$ be a family of linear functions using the following definition, $$ H=\{x\rightarrow f(z)+g^T(x-z)|z\in \operatorname{dom} f, g\in\partial f(z)\} $$ From the definition of subgradients, we know that $\forall h\in H$, $$ f(x)\ge h(x) $$ so that $$ f(x) \ge \underset{h\in H}\sup h(x) $$ On the other hand, we can always let $z=x$, then any $h\in H$ will satisfy $$ h(x)=f(x)\ge f(x) $$ so that $$ \underset{h\in H}\sup h(x) \ge f(x) $$ Hence $f(x)=\underset{h\in H}\sup h(x)$ is convex as the supremum of a family of linear functions.