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?

  • $\begingroup$ 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. $\endgroup$ – Cristóbal Guzmán Apr 16 '14 at 17:51
  • $\begingroup$ Thank you for your reply. I would like to see the super gradient. $\endgroup$ – dineshdileep Apr 18 '14 at 4:22

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).

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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