Let
$$
A:\mathbb R^n\to \mathbb R^{n\times n}
$$
where $A(x)$ is symmetric for any $x=(x_1,..,x_n)$. $$A(x) = A_0+x_1A_1+x_2A_2+…x_nA_n$$ and all $A$ is positive semidefinite.
Consider
$$
\underset{x\in\mathbb R^n}{\rm minimize}~ \lambda_{\rm max}(A(x))
$$
I would like to show that $\lambda_{\rm max}(A(x))$ is Lipschitz continuous but not differentiable.
Attempt:
It is Lipschitz since $\lambda_{\rm max}(A(x))$ is equal to $\|A(x)\|_2$ (is this true?).
Does the non-differentiability also follow from this fact?
Best Answer
We'll show that the $A\mapsto ( \lambda_1, \ldots, \lambda_n)$ from hermitian $n\times n$ matrices to the eigenvalues in decreasing order is Lipschitz. ( One can choose specific norms on both sides but that won't affect the statement).
First, let us show that if $A \preceq B$ ( the semidefinite order, meaning $B- A \succeq 0$ ) then the $k$th eigenvalue of $A$ is $\le $ the $k$-th eigenvalue of $B$, that is $\lambda_k(A) \le \lambda_k(B)$, for all $1 \le k \le n$. Indeed, there exists an $n-k+1$-dimensional subspace $V_1$ of $\mathbb{C}^n$ such that for every vector $x$ in that subspace we have $\langle A x, x \rangle \ge \lambda_k(A) \cdot ||x||^2$, and there exists a $k$-dimensional subspace $V_2$ of $\mathbb{C}^n$ such that for every vector $x$ in that subspace we have $\langle B x, x \rangle \le \lambda_k(B) \cdot ||x||^2$. These two subspaces have a non-zero intersection, let $0 \ne x \in V_1 \cap V_2$. We have $$\lambda_k(A) \cdot ||x||^2 \le \langle A x, x \rangle \le \langle B x, x \rangle \le \lambda_k(B) \cdot ||x||^2$$ and so $\lambda_k(A) \le \lambda_k(B)$.
Now, recall an important ( not hard to prove ) result : if $C$ is an $n\times n$ hermitian matrix so that $c_{ii} > (\ge) \sum_{j, j\ne i} | c_{ij}|$ for all $1 \le i \le n $ ( diagonally dominant) then $C \succ (\succeq) 0$.
Consider the norm $C \mapsto |C| = \max ( |c_{ij}|)$ on hermitian matrices. From the above we conclude that if $|C| \le \frac{\epsilon}{n}$ then $\epsilon \cdot I \pm C \succeq 0$. As a consequence, if $|A-B| \le \frac{\epsilon}{n}$ then $\epsilon \cdot I \pm (A-B) \succeq 0$. From $\epsilon \cdot I + A \succeq B$ we get, using the preceding, $\epsilon + \lambda_k(A) \ge \lambda_k(B)$. Similarly $\epsilon + \lambda_k(B) \ge \lambda_k(A)$. Therefore
$$|\lambda_k(A) - \lambda_k(B)| \le n \cdot |A-B|$$ for all $1 \le k \le n$.
${\bf Added:}$ The constant $n$ is the best possible. Indeed, consider the $n\times n$ matrix $A$ with all entries $1$. $A$ has $n$ as eigenvalue ( eigenvector all entries $1$) and $|A| = |A-0| = 1$.
As for the non-dfferentiability : the matrix$t \left(\matrix{t&0\\0& -t}\right)$ has largest eigenvalue $|t|$.