Consider three $N \times N$ Hermitian matrices $A_0$, $A_1$, $A_2$. Consider the function \begin{align} f(t_1,t_2)=\lambda_{\text{min}}(A_0+t_1A_1+t_2A_2) \end{align} where $\lambda_{\text{min}}$ denotes the minimum eigenvalue. $f(t_1,t_2)$ is clearly a concave function. How do we find the subgradient of it?

$\begingroup$ Are you sure you want a subgradient and not a supergradient? In the first case the answer is complicated (and not even welldefined), in the latter I can answer if you want. $\endgroup$– Cristóbal GuzmánApr 16, 2014 at 17:51

$\begingroup$ Thank you for your reply. I would like to see the super gradient. $\endgroup$– dineshdileepApr 18, 2014 at 4:22
1 Answer
Note that $f(t)=g(A(t))$, where $A(t_1,t_2)=A_0+t_1A_1+t_2A_2$ is affine and $g(B)=\lambda_{min}(B)$ which is concave on $B$. Now, to obtain the supergradient of this function you just need to use the chain rule of convex analysis.
First, it is easy to see that the Jacobian of $A$ is $$ D A(t) = A^{\ast} = [A_1^T;A_2^T]. $$
The maximum eigenvalue $g$ can be described by $$ \lambda_{min}(B) = \min\{u^TBu:\,\, \u\_2=1 \}. $$ So its superdifferential is given by the convex hull of rank one matrices given by eigenvectors associated to the minimum eigenvalue, i.e. $$ \partial \lambda_{min}(B) = \bar{co}\{ uu^T:\,\,u^Tu=1,\,\,Bu=\lambda_{min}(B) u \}.$$
Finally, by the chain rule, $$ \partial f(t) = \langle[A_1^T;A_2^T],\partial \lambda_{min}(At)\rangle := \{ (\langle A_1^T,X\rangle,\langle A_2^T,X\rangle):\,\, X\in \bar{co}\{ uu^T:\,\,u^Tu=1,\,\,A(t)u=\lambda_{min}(A(t)) u \}\}.$$ (the inner product above is the trace inner product) Which is a set of linear operators from $\mathbb{R}^2$ to $\mathbb{R}$, as it should be.
You can derive chain rules for general affine maps: see HiriartUrruty & Lemarechal: Fundamentals of Convex analysis, Theorems D.4.2.1 and D.5.1 (for the maximum eigenvalue subdifferential).

$\begingroup$ is supergradient of a concave function same as the subgradient of a convex function?. I am interested in the question $\max_{t}~f(t)$ where $t=[t_1,t_2]$. Does your derivation mean that the solution will be at the points where supergradient is zero?? $\endgroup$ Apr 19, 2014 at 9:32

$\begingroup$ Yes. If you want to convert your concave function to a convex one just multiply by 1 and then use standard convex analysis (of course, in this case your maximization problem becomes a minimization one). Now, since your objective is nonsmooth, the firstorder condition reads $0\in\partial f$. $\endgroup$ Apr 19, 2014 at 14:08

$\begingroup$ If I answered your question you should mark my answer. Thank you $\endgroup$ Apr 20, 2014 at 16:12

$\begingroup$ Yes of course, I was trying to understand it completely first . Thanks for your help $\endgroup$ Apr 21, 2014 at 7:27