Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 sub-gradient of it?

share|improve this question
    
Are you sure you want a sub-gradient and not a super-gradient? In the first case the answer is complicated (and not even well-defined), in the latter I can answer if you want. –  Cristóbal Guzmán Apr 16 at 17:51
    
Thank you for your reply. I would like to see the super gradient. –  dineshdileep Apr 18 at 4:22

1 Answer 1

up vote 1 down vote accepted

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 Hiriart-Urruty & Lemarechal: Fundamentals of Convex analysis, Theorems D.4.2.1 and D.5.1 (for the maximum eigenvalue subdifferential).

share|improve this answer
    
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?? –  dineshdileep Apr 19 at 9:32
    
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 first-order condition reads $0\in\partial f$. –  Cristóbal Guzmán Apr 19 at 14:08
    
If I answered your question you should mark my answer. Thank you –  Cristóbal Guzmán Apr 20 at 16:12
    
Yes of course, I was trying to understand it completely first . Thanks for your help –  dineshdileep Apr 21 at 7:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.