0

$(\nabla f(x) - \nabla f(y))^T (x-y) \geq 0$

$f$ be twice differentiable, with $\mathrm{dom}(f)$ convex.

I can derive the convexity of $f$ from the above inequality through first order condition, but is that also the sufficiency for convexity of $f$?

good2know
  • 665
  • 1
    If $f$ is continuously differentiable over a convex domain then it is convex if and only if the following condition holds: $ f(x) \ge f(y) + \langle x-y,\nabla f(y)\rangle $ for every pair $(x,y)$ in the domain. Assume $f$ is convex then, just by replicating the previous inequality for $(x,y)$ then for $(y,x)$: combining these two yield your inequality. For the other way, you can try starting by contradiction: if $f$ is non-convex then there exists $x$ such that $f(x)<f(y)+\langle x-y,\nabla f(y)\rangle$ and go on from there – tibL Sep 08 '16 at 11:35
  • @tibL The contradiction method seems to be fine, however there exist $x,y$ such that $f(x) < f(y) + <x-y, \nabla f(y)>$ does not also suggest $f(y) < f(x) + <y-x, \nabla f(x)>$ – good2know Sep 08 '16 at 22:04
  • sorry I don't get your comment, if you can indeed find a $x$ such that the strict inequality holds, then the function is non-convex. The contradiction would go: there is no such $x$ for any $y$, hence the contradiction is false, thus the function is convex. (by the way, I have not tried this, I am actually not sure the condition is sufficient for convexity) – tibL Sep 09 '16 at 08:33

1 Answers1

3

This is something that can be found in textbooks, like the Nesterov book Introductory lectures on convex optimization. You can fix $x$ and $y$ in $\mathbb{R}^n$ and define $h(t) = f(x+t(y-x))$ for $t \in \mathbb{R}$. Then $h(1) = h(0) + \int_0^1h'(t)dt$ and so \begin{align} \underbrace{f(y)}_{h(1)} &= \underbrace{f(x)}_{h(0)} + \int_0^1 \underbrace{\nabla f(x+t(y-x))^T(y-x)}_{h'(t)}dt\\ &= f(x) + \nabla f(x)^T (y-x) + \int_0^1 [\nabla f(x+t(y-x)) -\nabla f(x)]^T(y-x)dt\\ &=f(x) + \nabla f(x)^T (y-x) + \int_0^1 \frac{1}{t}\underbrace{[\nabla f(x+t(y-x)) -\nabla f(x)]^T(t(y-x))}_{\geq 0}dt\\ \end{align}

Michael
  • 23,905