Let $f:X \to \mathbb{R}$ be a function such that $\partial f(x)\neq \emptyset$ for all $x \in X$. Show that $f$ is convex.

I would appreciate some help with getting started on this problem. Thanks

  • 1
    $\begingroup$ if $\partial f(x)$ is non empty for all $x\in X$, then $\forall x\in X$ $\exists g\in\mathbb{R}^n$ s.t. $\forall z\in X$, $f(z) \geq f(x) + g^T(z-x)$. Play around with this expression and the definition of a convex function. $\endgroup$ – Thoth Oct 26 '15 at 22:01

Hint: Consider $x_1, x_2\in X$, and $x=\lambda x_1+(1-\lambda)x_2$, for $\lambda\in(0,1)$. What can you say about $f(x_1)-f(x)$?. Or about $f(x_2)-f(x)$?. What does this imply about $\lambda f(x_1)+(1-\lambda)f(x_2)-f(x)$?

  • $\begingroup$ What do you mean by "$x_1 < x_2$" ? Consider $X = \mathcal{H}$, a hilbert space. $\endgroup$ – dohmatob Oct 28 '15 at 8:25
  • $\begingroup$ @dohmatob Indeed, you are correct. I just edited this. $\endgroup$ – Nate River Oct 28 '15 at 10:21

Let $(x_1, x_2, \lambda) \in X^2 \times [0, 1]$, and set $x = \lambda x_1 + (1 - \lambda) x_2$. We wish to show that $\lambda f(x_1) + (1 - \lambda) f(x_2) \ge f(x)$.

The hypothesis implies that $\partial f(x) := \{v \in X \text{ s.t } f(z) \ge f(x) + \langle v, z - x\rangle\text{ }\forall z \in X\} \ne \emptyset$. Now choose any subgradient $v \in \partial f(x)$. One has \begin{equation} f(x_1) \ge f(x) + \langle v, x_1 - x\rangle = f(x) + (1 - \lambda)\langle v, x_1 - x_2\rangle, \end{equation} and \begin{equation} f(x_2) \ge f(x) + \langle v, x_1 - x\rangle = f(x) - \lambda\langle v, x_1 - x_2\rangle. \end{equation} Multiplying the first inequality by $\lambda$ and the second by $(1- \lambda)$ and adding the resulting inequalities then yields $\lambda f(x_1) + (1 - \lambda) f(x_2) \ge f(x) + 0 = f(x)$, which is the required result.


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.