How to realize $\lambda_{max}(X)$ is convex?

Question

How to realize is convex (f is convex)

X is symmetric. (S.Boyd's book p.82, Example 3.10)

It is easy to undertand like f = x^2 is convex; however, it is a bit hard for me to understand this function.

Thanks

Answer 1

Example 3.10 of Boyd is already presenting you with a proof!

Ok, let us revisit: what is eigenvalue of $X$? Given a vector $y$, if $$Xy = \lambda y \ldots (1)$$ then $\lambda$ is called the eigenvalue of X. Multiplying (1) by $y^{\top}$ we get, $$y^{\top}Xy = \lambda y^{\top}y = \lambda \|y\|^2$$ So, if we restrict ourselves to all $y$'s of norm $1$, then we see that, $$y^{\top}Xy = \lambda $$ That is, if $y$ is an eigenvector of $X$ of unit length, $y^{\top}Xy$ gives the eigenvalue. Now, here I will leave you to prove the following: $$\lambda_{max}(X) = \sup_{y:\|y\| = 1} y^{\top}Xy$$ For this, you will need to know some properties of symmetric matrices, particular that of decomposition [1].

Now, $$g(X) = y^{\top}Xy$$ is linear (which also means it is convex) in $X$ for a fixed $y$.

Therefore, $$f(X) = \lambda_{max}(X) = \sup_{y:\|y\| = 1} g(X)$$

So, finding maximum eigenvalue is equivalent to taking pointwise supremum over several linear (thereby convex) functions, which implies $f(X)$ is convex (section 3.2.3 page 80).

Alternatively, we can also show $f(X)$ is convex via the epigraph technique, but maybe I will leave it for you to think about.

[1] http://en.wikipedia.org/wiki/Symmetric_matrix#Decomposition