0

How to realize enter image description here 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

daw
  • 49,113
  • 2
  • 38
  • 76
sleeve chen
  • 8,281
  • According to the def: For each y in A, f(x,y) is convex in x, then g(x,y) = sup f(x,y) is convex in x. However, in this example it says f(X) is convex, so why is it convex? – sleeve chen Mar 28 '14 at 21:51

1 Answers1

2

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

TenaliRaman
  • 3,846