0
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ Your notation is confusing me a little... How did you get $f'(x)(y-x)$? $\endgroup$ – user389056 Feb 26 '17 at 23:26
  • $\begingroup$ That's the definition of Gateuax differentiability, or simply, directional derivative. en.wikipedia.org/wiki/G%C3%A2teaux_derivative $\endgroup$ – Chee Han Feb 26 '17 at 23:39
1
$\begingroup$

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)

http://web.stanford.edu/~boyd/cvxbook/

$\endgroup$

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.