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

Suppose we have a linear matrix inequality (aka LMI aka spectahedron aka linear matrix pencil):

$$A_{0}+x_{1}A_{1}+x_{2}A_{2}+\ldots+x_{m}A_{m} \succeq 0.$$

(The notation $X \succeq Y$ means that $X-Y$ is positive semidefinite).

If the LMI is feasible, then there is some $P \succeq 0$ so that $A_{0}+x_{1}A_{1}+x_{2}A_{2}+\ldots+x_{m}A_{m}=P$.

I would like to know if there is a way to express the $x_{i}$s as functions of $P$ and the $A_{i}$s.

A similar situation in which such a thing is possible is the Lyapunov equation $A^{T}X+XA=H$ for a diagonalizable $A=SDS^{-1}$ where one has: $$ X=(S^{-1})^{T}[L(A)] \circ (S^{T}HS)]S^{-1}, $$

with $L(A)=[(d_{i}+d_{j})^{-1}]$ and $\circ$ denoting the entrywise Schur matrix product. (Cf. pp. 300-301 in the book Topics in Matrix Analysis by Horn and Johnson for the derivation).

share|improve this question
    
The system is $A_0 + x_1A_1 + \ldots + x_mA_m = P$ is just a linear system in the $x_i$. So you could reformat the data to look like $Ax=b$ and then get $x = A^\dagger b$. Is there any reason to expect you could do any better than this? Without any special information about the $A_i$ this looks like a pretty generic linear system. –  Noah Stein Jul 30 '13 at 12:44
    
@NoahStein The reason is that the Lyapunov equation does have a matricial formula which is not at all evident from the scalar formulation. But that's all the evidence I have... (btw, $x=A^{\dagger}b$ does not always hold, you also need to have $x \perp null(A)$, ifirc). –  Felix Goldberg Jul 30 '13 at 12:47
    
But in the Lyapunov case the difficulty is that you're looking for a positive semidefinite solution whereas here the $x_i$ are otherwise unconstrained, right? (And yes, with the pseudoinverse I was assuming that $Ax=b$ has a solution.) –  Noah Stein Jul 30 '13 at 13:33
    
@NoahStein Actually, I do need the $x_{i}$s to be positive, but I was planning to deal with that later... :) –  Felix Goldberg Jul 30 '13 at 15:19
add comment

1 Answer

I would say that the answer is NO, since your problem is basically the general semidefinite program. There are obviously tractable special cases (like, if $A_1$ is psd, then you can set $x_i = \delta_{1i}, P=A_1.$)

share|improve this answer
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.