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$

3 Answers 3

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 agree to our terms of service and acknowledge you have read our privacy policy.

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