# Proof of convexity of linear least squares

It's well known that linear least squares problems are convex optimization problems. Although this fact is stated in many texts explaining linear least squares I could not find any proof of it. That is, a proof showing that the optimization objective in linear least squares is convex. Any idea how can it be proved? Or any pointers that I can look at?

Thanks

• – Avraham Sep 3 '13 at 20:57
• All norms are convex, and the function $\phi(t)= 1_{(-\infty,0)} (t) t^2$ is convex and non-decreasing, hence $x \mapsto \|x\|^2$ is also convex (see Rockafellar's "Convex Analysis" Theorem 5.1) . Finally, a convex function composed with a linear map is convex. – copper.hat Sep 9 '13 at 1:49

Another way to prove that a function is convex is by showing that the second order derivative (if it exists) is positive semi-definite.

$$\phi: \beta \mapsto \Vert y - X \beta \Vert^2 = \Vert y \Vert^2 - 2 y^T X \beta + \Vert X \beta \Vert^2$$ $\phi$ is twice differentiable and the second derivative (i.e. the Hessian) is

$$\dfrac {\partial \phi} {\partial \beta} = - 2y^TX + 2(X\beta)^TX =- 2y^TX + 2\beta^TX^TX$$

$$\dfrac {\partial^2 \phi} {\partial \beta \partial \beta^T} = 2X^TX$$

which is a positive semi-definite matrix. Therefore, $\phi$ is a convex function.

• How were you able to differentiate ϕ twice? – David May 4 '17 at 4:02
• Also, is the second derivative the Hessian? – David May 4 '17 at 6:18
• The first derivative is incorrect. You're adding a row vector to a column vector. – Rodrigo de Azevedo Sep 28 '17 at 9:16
• can anyone explain me how do we reach the first derivative? – Bagus Trihatmaja Jan 12 '18 at 6:30
• @BagusTrihatmaja I corrected the first derivative in my edit. It depends upon the fact that the derivative of $\Vert \mathbf{x}\Vert^2$ with respect to $\mathbf{x}$ is $2\mathbf{x}^T$. Then you can make use of the chain rule. – Christian Sykes Jan 12 '18 at 11:07

You want a proof that the function $$\phi: \beta \mapsto \Vert y - X \beta \Vert^2 = \Vert y \Vert^2 - 2 y^T X \beta + \beta^T X^T X \beta$$ is convex, right? (here $\beta$ and $y$ are vectors and $X$ is a matrix). In other words, you need to prove that $$\phi(t \beta_1 + (1-t) \beta_2) - \left[ t \phi( \beta_1) + (1-t) \phi(\beta_2) \right] \leq 0$$ for all $\beta_1, \beta_2$ and $t \in [0,1]$. After calculation, the left-hand term becomes $$t^2 \beta_1^T X^T X \beta_1 + (1-t)^2 \beta_2^T X^T X \beta_2 + 2 t(1-t) \beta_1^T X^T X \beta_2 - t \beta_1^T X^T X \beta_1 - (1-t) \beta_2^T X^T X \beta_2$$ $$= - t(1-t) \left[ (\beta_1 - \beta_2)^T X^T X (\beta_1 - \beta_2) \right] = - t(1-t) \Vert X (\beta_1 - \beta_2) \Vert^2$$ which is clearly $\leq 0$.

• Can you expand on "after calculation"? – vega Dec 7 '17 at 15:01
• @vega You can use the fact that $\Vert \mathbf{x}\Vert^2 = \mathbf{x}^T\mathbf{x}$. – Christian Sykes Jan 12 '18 at 11:10

Here's an alternative way to see the convexity of $$f(\beta)\triangleq \Vert y-X\beta\Vert^2$$. For $$t\in [0,1]$$, let $$\bar t=1-t$$. Then

$$f(t\alpha + \bar t \beta)=\Vert t(y-X\alpha)+\bar t (y-X\beta)\Vert^2 \le \left(t\Vert y-X\alpha\Vert +\bar t\Vert y-X\beta\Vert\right)^2\le t\Vert y-X\alpha\Vert^2+\bar t \Vert y-X\beta\Vert^2=tf(\alpha)+\bar tf(\beta)$$

where the first inequality is due to triangle inequality of vector norm, and the 2nd inequality follows because the square function ($$x^2$$) is also convex.

• I just noted the copper.hat's comment above. This answer in fact just elaborated his comment. – syeh_106 Nov 26 at 6:55