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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
- [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 positive-semi-definite 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 Benson-Ye-Zhang $\endgroup$ Commented Dec 4, 2013 at 18:33