We know that all the gradient of convex functions $f: X \to \mathbb{R}, X$ convex, are monotone maps, that is,

$f$ convex, continuously differentiable $\implies (\nabla f(x) - \nabla f(x^\prime)^T(x-x^\prime) \geq 0$

[Boyd Page 115 https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf]

We can make this statement stronger,

$f$ strictly convex, cont. diff. $\implies (\nabla f(x) - \nabla f(x^\prime)^T(x-x^\prime) > 0, \forall x$ such that $x \neq x^\prime$

$f$ strongly convex, cont. diff.$\implies (\nabla f(x) - \nabla f(x^\prime)^T(x-x^\prime) \geq c\| x-x^\prime\|, c>0, \forall x, x^\prime$

What about?

$f$ ??? continuously diff.$\implies (\nabla f(x) - \nabla f(x^\prime)^T(x-x^\prime) \geq -c\| x-x^\prime\|, c>0, \forall x, x^\prime$

What condition must $f$ satisfy? Is this the case when $f$ is strongly concave?

  • $\begingroup$ You are missing squares on the norms. $\endgroup$ – gerw May 10 '19 at 11:28

The statement on the right-hand side in the last box (with $||x-x'||^2$) is equivalent to $f + \frac c2 \,\|\cdot\|^2$ being convex.

  • $\begingroup$ What could be an example of such function? $\endgroup$ – Roy Ayers May 10 '19 at 20:30
  • $\begingroup$ $f \equiv 0$ or $f = c \, \|\cdot\|^2$ or (more generally) any smooth function whose Hessian is bounded from below (i.e., the smallest eigenvalue is bounded from below). $\endgroup$ – gerw May 11 '19 at 11:04

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.