4
$\begingroup$

Let $A_1,\dots,A_L$ be $N\times N$ hermitian matrices. Define the simplex \begin{align} \mathcal{S}=\left\{[x_1,\dots,x_L]\mid x_i\geq 0,~\sum_{i=1}^{L}x_i=1 \right\} \end{align} and consider the function over the simplex \begin{align} f(x_1,\dots,x_L)=\lambda_{min}\left(\sum_{i=1}^{L}x_iA_i\right) \end{align} where $\lambda_{min}(.)$ denotes the minimum eigenvalue. What are the properties of this function?

$\endgroup$
5
$\begingroup$

Yes, this function is well-studied. It can be maximized by semidefinite programming (and is in fact one of the standard examples of a non-trivial function that can be maximized by SDP).

The paper "M. Huhtanen and O. Seiskari. Computational geometry of positive definiteness, Linear Algebra and its Applications, 437:1562-1578, 2012" is devoted entirely to maximizing this function, and based on your previous posts about the joint numerical range, I expect that this is what you want to do?

$\endgroup$
1
$\begingroup$

This is a concave function (the infimum of the affine functions $ \sum_{i} x_i \langle v, A_i v \rangle$ for $v$ in the unit sphere).

$\endgroup$
1
$\begingroup$

Functions of eigenvalues have been well studied in convex analysis and optimization. The whole field of Semidefinite Programming is based on the polynomial-time solvability of linear optimization problems over domains that generalize what you described.

If you are interested on finding inequalities for the function you described there are fomulae for its subgradient (when you take max instead of min), see my answer here Subgradient of Minimum Eigenvalue

I also advise you to have a look at the chapter on semidefinite programming in the lecture notes by Ben-Tal and Nemirovski http://www2.isye.gatech.edu/~nemirovs/Lect_ModConvOpt.pdf

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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