1
$\begingroup$

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?

$\endgroup$
2
  • $\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$ Apr 16, 2014 at 17:51
  • $\begingroup$ Thank you for your reply. I would like to see the super gradient. $\endgroup$ Apr 18, 2014 at 4:22

1 Answer 1

1
$\begingroup$

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

$\endgroup$
4
  • $\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 first-order 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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