# How to approximate a 3x3 linear inequality constraint

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.

• 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. – 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.