14
$\begingroup$

Let a convex $ U \subset_{op} \mathbb{R^n} , n \geq 2$, with the usual inner product. A function $F: U \rightarrow \mathbb{R^n} $ is monotone if $ \langle F(x) - F(y), x-y \rangle \geq 0, \forall x,y \in \mathbb{R^n}.$

Let $f:U \rightarrow \mathbb{R}$ differentiable. Show that $f$ is convex $\iff \nabla f:U \rightarrow \mathbb{R^n}$ is monotone.

My attempt on the right implication: I already proved that if $f$ is convex and 2-differentiable then $f''(x) \geq 0$. But this exercise only says f is 1-differentiable. Then I tried the following: $f$ is convex $\iff \forall x,y \in U $ the function $\varphi:[0,1] \rightarrow \mathbb{R}$, defined by $ \varphi(t) = f((1-t)x+ty)$ is convex. Then $\varphi'$ is non-decreasing, then $\nabla \varphi(x) \geq 0$... but I'm stucked here.

My attempt on the left implication:

$ |\nabla \varphi (x) - \nabla \varphi (y)|| x-y| \geq | \langle \nabla \varphi (x) - \nabla \varphi (y), x-y \rangle | \geq 0$

And so $ |\nabla \varphi (x) - \nabla \varphi (y)| \geq 0 $ then $\nabla \varphi $ is non-increasing and then (By an already proved Theorem) it is convex.

Can someone please verify what I did and give me a hint?

Thanks.

$\endgroup$
5
  • $\begingroup$ If you define $F$ only on $U$, then it is difficult to verify $\langle F(x) - F(y), x-y \rangle\ge 0$ for every $x,y\in\mathbb R^n$. $\endgroup$
    – user251257
    Mar 28, 2016 at 19:34
  • $\begingroup$ Did you mean isn't difficult? $\endgroup$
    – user286485
    Mar 28, 2016 at 20:19
  • $\begingroup$ no. How do you compute $F(x)$ for $x\notin U$? $\endgroup$
    – user251257
    Mar 28, 2016 at 20:20
  • 2
    $\begingroup$ As much as I love the humor in the error, the term is monotone or monotonic, not monotonous :-) Convex functions are anything but monotonous! math.stackexchange.com/q/365717/52878 $\endgroup$ Jun 15, 2018 at 13:22
  • 6
    $\begingroup$ Does this answer your question? Equivalent definitions of convexity for $f\in\mathcal C^1(\mathbb R^n)$ $\endgroup$ Jan 23, 2021 at 11:56

2 Answers 2

4
$\begingroup$

1) If $f$ is convex, then $$ f(y)\geq f(x) + \nabla f(x)\cdot (y-x) $$

and $$ f(x)\geq f(y) + \nabla f(y)\cdot (x-y) $$

so that by adding $$ (y-x)\cdot( \nabla f(x) - \nabla f(y)) \leq 0 $$

2) Assume that $\nabla f$ is monotone : Define $A =\{ x| f(x)\leq a\}$. If $A$ is not convex, then there are $x,\ y\in \partial A$ s.t. $$ \nabla f(x)\cdot (y-x),\ \nabla f(y)\cdot (x-y) >0 $$ Hence $$ (\nabla f(x) -\nabla f(y))\cdot (y-x) >0 $$

It is a contradiction.

$\endgroup$
1
  • 5
    $\begingroup$ I think this is not correct. You showed that $A$ has to be convex because of contradiction. But even all of the sublevel sets are convex doesn't imply the function $f$ is convex. $\endgroup$
    – Pew
    Oct 13, 2021 at 1:42
2
$\begingroup$

Argument for why gradient monotonicity gives convexity:

Suppose the gradient is monotone and fix any $x$, $y$. We can reparametrize $F$ to $$ G(t) = F(x + t(y-x)). $$ Then $G(0) =x, G(1)=y$. Moreover: $$ G'(t) = \nabla F(x + t(y-x)) \cdot(y-x). $$ Now, notice: $$ [G'(t)-G'(0)]t = [\nabla F(x + t(y-x)) - \nabla F(x) ]\cdot[(x-t(y-x)) - x], $$ and so monotonicity tells you that $G'(t)\geq G'(0)$.

Then we can write the following: $$ G(1) = G(0)+ \int_0^1 G'(t)dt \geq G(0)+\int_0^1 G'(0) dt = G(0)+\nabla F(x) \cdot(y-x). $$ This gives: $$ F(y) = F(x) + \nabla F(x) \cdot(y-x). $$ Since this holds for every $y$, $\nabla F(x)$ is a subgradient of $F$ at $x$. Since this argument also holds for every $x$, $F$ has a subgradient everywhere and so must be convex.

$\endgroup$

You must log in to answer this question.