2

Note: I can't differentiate 2 times and prove that $f''(x) > 0$

The exercise requires me to prove that the function $f(x) = x^2$ is convex by using the following Theorem:

$f(x) \ge f(x^*) + \nabla f(x^*)^T(x-x^*)$

I tried to replace the $f(x)$ with the actual function and all I got was $(x - x^*)^2 \ge 0$

I was wondering if I could use that to prove by absurd. I know it's bad practice on Stack Exchange groups to post homework assignment, but I'm really stuck and I'd like just a little hint so I can try and figure it out on my own. Thanks in advance.

Marco Aurélio Deleu
  • 313
  • 1
    So you started by a condition that following a sequence of equivalent statements led to a statement of the form $(x-x^{\star})^2 \ge 0$ which is true for all $x$ and $x^{\star}$. What does this tell you for the original statement? – megas Apr 13 '15 at 22:32
  • That the original statement must be held true? – Marco Aurélio Deleu Apr 13 '15 at 22:43
  • Yep. If you have written things down carefully, then starting from the end, i.e. from the fact that $(x-x^{\star})^2 \ge 0$ which is true $\forall x, x^{\star}$, then you would be able to show that $f(x) \ge f(x^{\star}) + \nabla f(x^{\star})^T(x-x^{\star})$ (for the function of interest $f(x)=x^{2}$), which implies the convexity of $f(x)$. – megas Apr 13 '15 at 22:46

1 Answers1

1

Let $x$ and $y$ be real numbers. Then $f(y) + f'(y)(x-y) = y^2 + 2y(x-y) = 2xy -y^2$. Note that $2xy - y^2 - x^2 = -(x-y)^2 \le 0$. Particularly this says that $2xy - y^2 \le x^2$. Translating this into terms involving $f$, we have: $f(y) + f'(y)(x-y)\le f(x)$. Hence $f$ is convex.

I suspect you started with the expression $x^2 \ge y^2 +2y(x-y)$ and wanted to show it was true. This isn't necessarily a bad thing, but it makes it really confusing as to what is going on in terms of proof technique. The way I've presented it is probably the way you should think about it. Don't try to force it to be true. Start with $f(y)+f'(y)(x-y)$ and try to show that this is less than (or equal to) $f(x)$ by doing some sort of manipulation to it.

Cameron Williams
  • 29,432