Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given $f(a,b)=\sum_{k=1}^n(ax_k+b-y_k)^2$ where $x_k$ and $y_k$ are arbitrary real numbers such that $\exists i,k:x_i \ne x_j$.

Show that $f(a,b)$ gets minimized at exactly one point.

I've managed to show that the partial derivatives vanish at exactly one point $(a_0,b_0)$.

I then took the set $K=f^{-1}([f(a_0,b_0),f(a_0,b_0+\varepsilon)]$, and I'm trying to show that $K$ is compact which will finish the proof.

It's clear that $K$ is closed, to show that it is bound I tried to use the fact that $(a,b)\in K\implies |f(a,b)-f(a_0,b_0)| <\varepsilon$ to somehow bound $a-a_0$ and $b-b_0$, but to no avail...

Does anyone know how to bound this set, or maybe have some better idea?

share|improve this question

2 Answers 2

up vote 1 down vote accepted

Well, I found a better solution.

I won't go into to many details as this didn't get a lot of attention, but taking increasingly large cocentric spheres closed around $(a_0,b_0)$ compactness reveals that each sphere either attains a minimum in $(a_0,b_0)$ or on the boundary.

Assume BWoC all minima are attained on the respective boundaries, and choose a minimal point for each sphere, then this sequence is positive decreasing and thus converges.

It is easy to prove on the other hand that for any unbound sequence $x_n$ the sequence $f(x_n)$ is also unbound (a direct result of the existence of $i$ and $j$ s.t. $x_i\ne x_j$) and reach a contradiction, getting that one of said spheres attains a minimum at $(a_0,b_0)$ as needed.

share|improve this answer

It might better to compute the Jacobian, i.e. the two by two matrix of second partials of $f(a,b)$ w.r.t. the variables $a,b$. In this case it is independent of $a,b$ and comes out $$ \sum_{k=1}^n x_k^2 - \sum_{k=1}^n x_k \cdot \sum_{k=1}^n x_k$$ which is $n^2$ times the variance of the $x_k$. This is known to be positive, so that your only critical point is a relative minimum, and all you need now is to make sure it is also the absolute minimum.

ADDED NOTE: The function $f(a,b)$ being minimized is the sum of squared errors for the linear regression of the $y_k$ as function of the $x_k$. So you could also look up "linear regression" and find various proofs that this is indeed the absoloute minimum. The values $a,b$ are slope and intercept of best fit line.

share|improve this answer
    
Don't you mean Hessian? –  Shai Deshe Dec 10 '12 at 1:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.