# Show Fréchet differentiable convex function satisfies property.

Let $f:\mathbb{R}^n \rightarrow \mathbb{R}$ be convex, i.e., $$f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda)f(y), \ \forall x,y \in \mathbb{R}^n, \ \lambda \in (0,1).$$

Suppose $f(\cdot)$ is also (Fréchet) differentiable. Show that $$f(x) + f_x(x)(y-x) \leq f(y), \ \forall x,y \in \mathbb{R^n}.$$

Here, $f_x(x)$ denotes the Fréchet derivative, so we know that $$\lim_{||y|| \to 0} \frac{|f(x+y)-f(x) - f_x(x) \cdot y|}{||y||} = 0.$$

I tried rearranging things to make the problem nicer, but I have no intuition on how to proceed with this one. If you rewrite the second line as $$f_x(x) \leq \frac{f(y)-f(x)}{y-x}$$ it kind of looks like MVT might come into play, but I could not see where to apply this. Hints please?

• Oh for a second I thought you had it already. I'm writing a solution now. – Chee Han Feb 26 '17 at 23:09

Suppose $f\colon\mathbb{R}^n\longrightarrow\mathbb{R}$ is convex. Then for any $\lambda\in(0,1)$ and $x,y\in\mathbb{R}^n$, we have $$f(\lambda y + (1-\lambda)x)\le \lambda f(y) + (1-\lambda)f(x).$$ Rearranging this yields $$\frac{f(x + \lambda(y-x)) - f(x)}{\lambda} \le f(y) - f(x).$$ Taking the limit as $\lambda\longrightarrow 0$, $$f'(x)(y-x)\le f(y) - f(x).$$ Here, I am using the fact that Frechet differentiable implies Gateuax differentiable, and I am abusing the notation $f'(x)$ here.
• Your notation is confusing me a little... How did you get $f'(x)(y-x)$? – user389056 Feb 26 '17 at 23:26
Since $f:R^{n} \rightarrow R$, the Frechet derivative is simply the gradient. You can find a proof of this first order characterization of convexity of differentiable functions on page 70 of the textbook on Convex Optimization by Boyd and Vandenberghe (with a free download)