What is the relation between $\nabla f(\mathbf x), \mathbf y - \mathbf x, \text{ and } f(\mathbf y) - f(\mathbf x)$? The Problem:
Let $f(\mathbf x)$ be a convex function on $\mathbb R^n$. Given two points $\mathbf x$ and $\mathbf y$, what is the relation between $\nabla f(\mathbf x), \mathbf y - \mathbf x, \text{ and } f(\mathbf y) - f(\mathbf x)$?
Where I Am:
I guess I don't really know what this question is asking. I wrote down the definition of a convex function, as applied to this context, i.e.
$$ f(t\mathbf x+(1-t)\mathbf y) \le tf(\mathbf x) - (1-t)f(\mathbf y) \quad \forall t \in [0,1] $$
then did some algebra to isolate things on one side of the inequality, and whatnot. Nothing really popped out to me. I imagine that I'm supposed to come to the conclusion that one thing is less-than-or-equal to another thing, or something, but I'm not seeing it. If anybody has an idea, I'd appreciate a little guidance here. Thanks.
 A: What you're looking for is this, a standard definition of the secant inequality for convexity for differentiable functions:
$$f(y) \geq f(x) + \nabla f(x) ^T ( y - x )$$
and when you subtract $f(x)$ from both sides you get this:
$$f(y) - f(x) \geq \nabla f(x)^T(y-x)$$
Surprisingly, the Wikipedia article for convex functions doesn't come right out and offer this. It has the one-dimensional version of this relationship, and it has the version that defines strong convexity:
$$f(y) \geq f(x) + \nabla f(x)^T(y-x)+\tfrac{1}{2}m\|y-x\|_2^2$$
from which you can recover the standard case with $m=0$.
A: Consider first the one dimensional case. Let us make a comparison between:
$(A) \qquad$ the gradient $\nabla f(x)$ and
$(B) \qquad$ the quotient $\frac {f(y)-f(x)} {y-x}$
Expression $A$ denotes the first derivative of $f$ in a very small interval around the point $x$. Expression $B$ can be regarded as the average value of the first derivative of $f$ over the interval $(x,y)$. Now it is given that the function $f$ is convex, which means that the first derivative increases monotonically. From this we can conclude: 
if $y > x$ then $(B) > (A)$.
if $y < x$ then $(B) < (A)$.
In the limit of $y$ towards $x$, we see that $(B)$ should converge to $(A)$. And this is of course the correct result, in view of the definition of $\nabla f(x)$. Furthermore it follows that if we multiply both $(A)$ and $(B)$ by $y-x$ we get:
$$f(y) - f(x) \ge (y - x) * \nabla f(x) $$
where the equality sign holds only in case $y = x$. 
This equation can be extended to the $n$-dimensional case. Assume that $y-x$ (which is now a vector) is parallel to one of the Cartesian unit vectors. For the gradient we should then take the projection onto the same Cartesian unit vector. Generalizing for arbitrary directions [for example by considering the effect of rotating our Cartesian coordinate system], we see that the one-dimensional result still holds. Only the multiplication $"*"$ between two scalar quantities on the RHS is replaced by the inner product $"."$ of two vectorial quantities. 
