Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
    
hi, i was looking for a alternative solution as my problem is a simple lmi, –  dineshdileep Oct 21 '13 at 4:26
1  
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
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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