# Fast algorithm for maximizing smallest eigenvalue of linear combination of hermitian matrices

I have an engineering back ground. Due to work, I came across this problem \begin{align} &\max_{\lambda,y_i\in \mathbb{R}}~\lambda \\\ s.t.~&\left(\mathbf{A}_0+\sum_{i=1}^{K}y_i\mathbf{A}_i\right)-\lambda\mathbf{I}\geq 0 \end{align} where $\mathbf{A}_i$ are all hermitian matrices. We are seeking $\lambda$ and $y_i$. I know that this is called a Linear Matrix Inequality problem and can be solved by a general convex package (for eg, CVX). To me, it seems like we are looking for a matrix formed from the linear combination of given hermitian matrices whose smallest eigenvalue is as maximum as possible among all such combinations. I was wondering if they are iterative algorithms to solve this problem which are simple to implement. Please point me to relevant references.

## 1 Answer

Two iterative algorithms that solve LMI problems is the ellipsoid algorithm and interior-point methods. Both are described in sections 2.3 and 2.4 of Stephen Boyd's book "Linear Matrix Inequalities in System and Control Theory"  and in the references therein.

See also  for already implemented solvers. In particular, if you use MATLAB I recommend using the SeDuMi solver with the YALMIP parser , since this one allows one to input the LMI programs to the solver in a more intuitive way.

• hi, i was looking for a alternative solution as my problem is a simple lmi, – dineshdileep Oct 21 '13 at 4:26
• Your problem definition is essentially as general as an LMIs can get, so you will not be able to solve this faster than any other LMI problem. – Johan Löfberg Nov 5 '13 at 14:10
• ok, Is there any specific instance, where in the solution can be obtained real fast, for instance, say all the matrices are rank one positive-semi-definite matrices or some other instance? – dineshdileep Nov 13 '13 at 7:52
• Some algorithms can exploit the low rank. One such solver is DSDP by Benson-Ye-Zhang – Johan Löfberg Dec 4 '13 at 18:33