I just finished my optimization class and there is an inequality that I couldn't prove, $$(y-x)^T(\nabla f(y) - \nabla f(x)) \geq 0$$
I can't also understand the intuition of this inequality. Could someone prove this inequality for me, also I would greatly appreciate if some intuition is provided. At last, is there a reference for properties of convex functions? Thanks!
Hop back into one dimension for a moment to see what it says: $$ (y-x)(f'(y)-f'(x)) \geqslant 0. $$ Or, if we let $y=x+h$, $$ h(f'(x+h)-f'(x)) \geqslant 0. $$ If $h>0$, this says the derivative is at least as big at $x+h>x$ as it is at $x$ (replace this with "larger at $x+h>x$ than at $x$" for a more memorable but not quite true statement). If $h<0$, it says the derivative is at most as big at $x+h<x$ as it is at $x$. So in both cases, it says that the derivative is nondecreasing.
To prove this is true if $f$ is convex, we can use the inequality that says that $f$ lies above its tangent plane, $$ f(y) \geqslant f(x) + (y-x)^T \nabla f(x). $$ Swapping $x$ and $y$, $$ f(x) \geqslant f(y) + (x-y)^T \nabla f(y), $$ and then if you add these and rearrange a bit, you find $$ (y-x)^T(\nabla f(y)-\nabla f(x)) \geqslant 0, \tag{1} $$ as required. To go the other way uses the Fundamental Theorem of Calculus, via $$ f(x+y)-f(x) = \int_0^1 \frac{d}{dt}f(x+t(y-x)) \, dt: $$ calculate the derivative on the right-hand side, apply (1), and the "lies above the tangent plane" result follows.