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).

  • 1
    $\begingroup$ 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. $\endgroup$ – Noah Stein Jul 30 '13 at 12:44
  • $\begingroup$ @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). $\endgroup$ – Felix Goldberg Jul 30 '13 at 12:47
  • $\begingroup$ 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.) $\endgroup$ – Noah Stein Jul 30 '13 at 13:33
  • $\begingroup$ @NoahStein Actually, I do need the $x_{i}$s to be positive, but I was planning to deal with that later... :) $\endgroup$ – Felix Goldberg Jul 30 '13 at 15:19

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.$)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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