4
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 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
    Commented Jul 30, 2013 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
    Commented Jul 30, 2013 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
    Commented Jul 30, 2013 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
    Commented Jul 30, 2013 at 15:19

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .