1
$\begingroup$

Prove that the function $f:\mathbb{R}^n\to \mathbb{R}$ given by $f(x)=x^T \cdot x$ is strictly convex. Use this result to find the absolute minimum by equating the derivative to zero.

I am not sure how to prove that a vector function is convex. Is there a general method to do this? Also, I tried differentiating the function and I got $2x^T$dx as a result for the differential, which would mean that $2x^T$ is the derivative. However, does this give me the absolute minimum? Or did I make a mistake in differentiating? Thanks in advance.

$\endgroup$
  • 1
    $\begingroup$ You probably meant $f:\mathbb{R}^n\longrightarrow\mathbb{R}$. $\endgroup$ – Julien Feb 22 '13 at 21:51
2
$\begingroup$

When the Hessian Matrix of a function $f$ is positiv definit the function $f$ is strict convex. That should help you.

By the way what do you mean with $2x^T \, dx$

Let us first rephrase the definition of strict convexity. $$f(t \cdot x+(1-t)y)< t\cdot f(x) + (1-t)f(y)$$ As this is an easy example we will make it with the definition. $$\sum_{i=1}^n (t\cdot x_i + (1-t)y_i)^2 =\sum_{i=1}^n t^2 x_i^2 + 2 (1-t)(t)(x_i \cdot y_i)+ (1-t)^2 y_i^2 $$ And the right hand side is $$\sum_{i=1} t x_i^2 + (1-t)y_i^2 $$ We can show that it is true for every coordinate (so we don't need the sum) $$t^2 x^2 + 2(1-t)(t)(xy)+(1-t)^2 y^2< tx^2 + (1-t)y^2 $$ This is equivalent to $$0<t(1-t) x^2 + (1-t)(t) y^2 -2t(t-1)xy$$ We have in every term a $t(1-t)$ as $t\in(0,1)$ we can devide through it $$0< x^2 -2 xy +y^2=(x-y)^2 $$ So we see this is true for every summand of the sum, and hence for the sum.

There is a very nice way how to differentiate stuff like that (this one isn't rigorous as I do it). We just use the product rule $$D(x^T x) = (x^T)' x + x^T x'= x^T (x)' + x^T=2 x^T$$ Using the symmetrie of $x^T x$. You could do it with the partial derivates too. The Hessian Matrix is $2\cdot I$ where $I$ is the unit matrix.

$\endgroup$
  • $\begingroup$ Thank you! Well, I thought that that is the differential of this function. I obtained it by working out f(x+dx)-f(x). $\endgroup$ – dreamer Feb 22 '13 at 21:03
  • $\begingroup$ And could you please show me how I can complete the proof of convexity? I am not familiar with the concept 'positiv definit' which you mentioned since I am relatively new to these kinds of excercises. $\endgroup$ – dreamer Feb 22 '13 at 21:05
  • 1
    $\begingroup$ i don't know what the $dx$ should mean over there. ok give me some time $\endgroup$ – Dominic Michaelis Feb 22 '13 at 21:06
  • $\begingroup$ Sorry, that is the way I learned to compute differentials and through that derivatives. How else would you compute the derivative then to do the second part of the question. Thanks for all your help, I really appreciate it. I really want to get better at this but I find it very hard sometimes. $\endgroup$ – dreamer Feb 22 '13 at 21:09
  • 1
    $\begingroup$ I think you meant strictly convex in your first sentence. For otherwise $f(x)=0$ is convex but the Hessian is not definite. $\endgroup$ – Julien Feb 22 '13 at 21:50
3
$\begingroup$

You may prove convexity from first principle. $f(x)$ is said to be strictly convex if and only if $f(px+qy)<pf(x)+qf(y)$ for any $x\not=y$ and for every $0<p<1 \ (q=1-p)$. This can be proved by verifying that $$ pf(x)+qf(y)-f(px+qy)=pq(x-y)^T(x-y)=pq\|x-y\|^2>0, $$ where $\|v\|$ denotes the length (i.e. Euclidean norm) of a vector $v$.

To find the minimum of $f$, note that $f(x)=x^Tx=\|x\|^2\ge0$ and $f(x)=0$ only when $x=0$. Hence the absolute minimum of $f$ occurs at the $x=0$. Calculus is not of much use here, because it can only prove that a certain point is a local minimum, but you are asked to find the absolute minima of $f$. But anyway, since you have $f'(x)=2x^T$, setting $f'(x)=0$ would give you back the critical point $x=0$. To show that $x=0$ is indeed an absolute minimum, you still need to argue that $f(x)\ge f(0)=0$ for every $x$.

Edit: It's worth mentioning (thanks to Dominic Michaelis) that every local minimum of a convex function is a global minimum, but in general, calculus is only helpful for screening out local minima among critical points. Extra work is often required to locate global minima.

$\endgroup$
  • 2
    $\begingroup$ As it is convex we know that a local minimum implies a global $\endgroup$ – Dominic Michaelis Feb 22 '13 at 21:39
  • 2
    $\begingroup$ @DominicMichaelis You are right, but considering what the OP knows, I think this result is even more alien to the oP than positive definiteness is. $\endgroup$ – user1551 Feb 22 '13 at 21:45
  • $\begingroup$ Thank you very much for your help! $\endgroup$ – dreamer Feb 23 '13 at 8:26

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.