Let $M$ be a $3\times3$ symmetric matrix (6 independent variables). The following constraint:

$$M \succeq 0$$

is a convex linear matrix inequality (LMI), meaning that M is positive semidefinite.

I'm looking for ways to approximate this constraints with standard linear inequalities. It is possible to assume that I have some sort of reference point for the approximation. I think the usual way to compute such approximations is to express the original LMI inequality constraint as a list of standard inequality constraints:

$$f_1(x) \leq 0$$ $$f_2(x) \leq 0$$ $$\dots$$

Then use a first order approximation for $f_i$ around the reference point. However, here, I'm not sure what $f_i$ functions I should choose.

One possible way is to try to express the smallest eigenvalue of M analytically and this would lead to $\lambda > 0$. Then approximate $\lambda$ linearly. But the expression for $\lambda$ involves solving cubic polynomials and it would be quite involved.

Another less direct way would be to look for alternative (nonlinear) conditions that characterize the positive definiteness of $M$. For example, that the determinant of all upper left sub-matrices are positive. This would lead to 3 inequalities. A linear one, a quadratic one, and another cubic one. I can then approximate the second and third ones linearly. But it is not clear to me what is the difference between different choices of the functions $f_i$. Is there a best choice? Are there other natural alternatives beside the two possibilities I described above?

I think what's missing here is some geometric interpretation of the feasible set but since the domain is in $\mathbb{R}^6$ it's not trivial.

  • $\begingroup$ To make this worthwhile, your homebrew solver is going to have to be better than an off-the-shelf LMI solver which had already had extensive development and testing. $\endgroup$ – Mark L. Stone Sep 19 '18 at 11:28

Since you were seeking an alternative approximate way, let me point out one. Note that $$M\succ 0$$ is equivalent to $$x^T Mx \geq 0 ~~\forall x \in \mathbb{R}^3 $$ Note that this is a linear constraint in terms of entries of $M$ though there are infinite constraints. But you can sample a large number of vectors from $\mathbb{R}^3$ and this should hold in an approximate sense.


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.