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
$\begingroup$
$\endgroup$
4
Two iterative algorithms that solve LMI problems is the ellipsoid algorithm and interiorpoint 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.
 [1] The book is freely available to download at http://www.stanford.edu/~boyd/lmibook/
 [2] https://en.wikipedia.org/wiki/Semidefinite_programming#Software
 [3] http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Main.WhatIsYALMIP

$\begingroup$ hi, i was looking for a alternative solution as my problem is a simple lmi, $\endgroup$ Commented Oct 21, 2013 at 4:26

1$\begingroup$ 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. $\endgroup$ Commented Nov 5, 2013 at 14:10

$\begingroup$ ok, Is there any specific instance, where in the solution can be obtained real fast, for instance, say all the matrices are rank one positivesemidefinite matrices or some other instance? $\endgroup$ Commented Nov 13, 2013 at 7:52

1$\begingroup$ Some algorithms can exploit the low rank. One such solver is DSDP by BensonYeZhang $\endgroup$ Commented Dec 4, 2013 at 18:33