Question regarding norms and convexity

Question

I'm almost done with a proof where I have to show something is a minimizer to the functional

$$||Ax-b||^2 + \lambda ||x||^2$$

I'm practically done, but I have one obstacle remaining. I need to argue that the functional is convex before I can be sure what I've found indeed is the minimizer. I know that norms are convex, but I'm not sure whether you can make an easy argument that a sum of squared norms are convex? I have tried to show convexity by the regular definition, but I find that it ends up being somewhat difficult to show...

Any help or hints would be higly appreciated!

Answer 1

You can just prove it directly.

First notice that $\|\cdot\|^2$ is convex:

\begin{align} \|(1-t)x+ty\|^2 &= (1-t)^2\|x\|^2 + 2t(1-t)\langle x,y\rangle + t^2\|y\|^2\\ &\le (1-t)\|x\|^2 + t\|y\|^2 + ((1-t)^2-(1-t))\|x\|^2 + 2t(1-t)\|x\|\|y\| + (t^2-t)\|y\|^2\\ &= (1-t)\|x\|^2 + t\|y\|^2 - t(1-t)\left(\|x\|^2 -2\|x\|\|y\| + \|y\|^2\right)\\ &= (1-t)\|x\|^2 + t\|y\|^2 - t(1-t)\left(\|x\|^2-\|y\|^2\right)^2\\ &\le (1-t)\|x\|^2 + t\|y\|^2 \end{align}

Now we have

\begin{align} f((1-t)x+ty) &= \|(1-t)Ax + tAy - b\|^2 + \lambda\|(1-t)x+ty\|^2\\ &= \|(1-t)(Ax - b) + t(Ay - b)\|^2 + \lambda\|(1-t)x+ty\|^2\\ &\le (1-t)\|Ax-b\|^2 + t\|Ay-b\|^2 + (1-t)\lambda\|x\|^2 + t\lambda\|y\|^2\\ &= (1-t)(\|Ax-b\|^2+ \lambda\|x\|^2)+ t(\|Ay-b\|^2+\lambda\|y\|^2)\\ &= (1-t)f(x) + tf(y) \end{align}

Answer 2

It is a simple consequence of the fact that the composition of convex with convex and increasing is a convex function. Here the norm is convex and takes non-negative values and the squaring is convex and increasing for non-negative values, then the composition is convex.

The sum of convex functions is convex (assuming $\lambda>0$).

Answer 3

By the definition of convexity, $f:\mathbb{R}^n \to \mathbb{R}$ is convex if and only if for each $x, y\in \mathbb{R}^n$, $y\neq 0$, the function $$ t\mapsto f(x+ty) $$ is convex. If $f$ is twice continuously differentiable, then $$ \frac{d^2}{dt^2}f(x+ty) = y'D^2f(x+ty) y \geq 0 $$ is sufficient and necessary. (Here, $D^2 f$ denotes Hessian matrix of $f$ and $y'$ is the transpose.) That is, $f$ is convex if and only if $D^2 f(x)$ is positive-semidefinite for all $x\in \mathbb{R}^n$.

We may write $$ f(x) = \|Ax-b\|^2 +\lambda\|x\|^2=\langle Ax-b, Ax-b\rangle+\lambda\langle x,x\rangle = x'(A'A+\lambda I) x-x'A'b -b'Ax +b'b. $$ This gives us $$D^2f(x) = 2(A'A +\lambda I). $$ If $\lambda \ge 0$, then $D^2f(x)$ is obviously positive semidefinite, and we are done. If $\lambda <0$, then it is required $\mu + \lambda \ge 0$ where $\mu$ is the least eigenvalue of the matrix $A'A$.