2

I have the following proposition:

Proposition 1.3 (Alternative form of the first-order convexity condition)
The first-order convexity conditions $$ f({\bf y}) \geq f({\bf x}) + ( {\bf y} - {\bf x} ) \cdot \nabla f( {\bf x}) $$ and $$ ( {\bf y} - {\bf x} ) \left( \nabla f( {\bf y}) - \nabla f( {\bf x}) \right) \geq 0 $$ are equivalent, where ${\bf x}, {\bf y} \in D (f)$.

However, it comes without proof. The first implying the second is easy enough. However, I do not see how the second implies the first. I tried many things but I can't get away without assuming too much. I am at the point where I am not sure if they are equivalent.

Question: Is the given equivalence true, and if so, then how does one go about proving the backward direction?

Rodrigo de Azevedo
  • 1
Maths Wizzard
  • 2,259

1 Answers1

4

Questions about convex functions of multiple variables can often be reduced to a question about convex functions of a single variable by considering that function on a line or segment between two points.

The two conditions are indeed equivalent for a differentiable function $f:D \to \Bbb R$ on a convex domain $D \subset \Bbb R^n$.

To prove that the second condition implies the first, fix two points $x, y \in D$ and define $$ l:[0, 1] \to D \, , \, l(t) = x + t (y-x) \, , \\ g:[0, 1] \to \Bbb R\, , \, g(t) = f(l(t)) \, . $$

Note that $$ g'(t) = (y-x) \nabla f(l(t)) \, . $$

For $0 < t < 1$ is $$ g'(t)- g'(0) = (y-x)\bigl(\nabla f(l(t)) - \nabla f(l(0) \bigr) \\ = \frac{1}{t} \bigl(l(t)-l(0)\bigr) \bigl(\nabla f(l(t)) - \nabla f(l(0) \bigr) \ge 0 \, , $$ and the mean-value theorem gives, with some $\xi \in (0, 1)$, $$ f(x) - f(y) = g(1) -g(0) = g'(\xi) \ge g'(0) = (y-x) \nabla f(x) \, . $$

(Actually, $g'$ is increasing so that $g$ is convex.)

Martin R
  • 113,040