# 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" [1] and in the references therein.

See also [2] for already implemented solvers. In particular, if you use MATLAB I recommend using the SeDuMi solver with the YALMIP parser [3], 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