# Convexity of a specific semialgebraic set

I have an engineering problem which maybe resolved with semi-definite programming optimization. I have a set which I would like to know if is convex:

Being $m \in \mathbb{R}^+$ a positive real scalar, $l \in \mathbb{R}^3$ a size 3 real vector, and $L \succ 0$ a size 3x3 real positive-definite matrix, does the expression

$L - m\ S\left(\frac{l}{m}\right)^T S\left(\frac{l}{m}\right) \succ 0$

where $S(\dot{})$ means the skew-symmetric matrix operator, and $\succ 0$ means positive-definite, defines a convex set?

I.e.:

Being

$$m \in \mathbb{R}$$

$$l \equiv \left[l_x\ l_y\ l_z\right]^T$$

$$L \equiv \left[\begin{matrix} L_{xx} & L_{xy} & L_{xz} \\ L_{xy} & L_{yy} & L_{yz} \\ L_{xz} & L_{yz} & L_{zz} \\ \end{matrix}\right]$$

The variables $m,l_x,l_y,l_z,L_{xx},L_{xy},L_{xz},L_{yy},L_{yz},L_{zz}$ define a $\mathbb{R}^{10}$ space.

The constraints

$$\left\{ \begin{matrix} m &> 0 \\ L &\succ 0\\ L - m\ S\left(\frac{l}{m}\right)^T S\left(\frac{l}{m}\right) &\succ 0 \end{matrix} \right.$$

which, since $m>0$, are equivalent to

$$\left\{ \begin{matrix} m &> 0 \\ L &\succ 0\\ m L - S\left(l\right)^T S\left(l\right) &\succ 0 \end{matrix} \right.$$

define a semialgebraic set on the $\mathbb{R}^{10}$ variables space.

Here, $\succ 0$ means that the left argument is a positive-definite matrix, and,

$$S(x) = \left[\begin{smallmatrix} 0 & -x_3 & x_2 \\ x_3 & 0 & -x_1 \\ -x_2 & x_1 & 0 \end{smallmatrix}\right]\quad\text{with}\quad x = \left[x_1\ x_2\ x_3\right]^T$$

I did some, manipulation and rewrote the last constraint as a polynomial inequalities system:

being

$$mI = m L - S\left(l\right)^T S\left(l\right) = \left[\begin{smallmatrix} L_{1xx} m_{1} - l_{1y}^{2} - l_{1z}^{2} & L_{1xy} m_{1} + l_{1x} l_{1y} & L_{1xz} m_{1} + l_{1x} l_{1z} \\ L_{1xy} m_{1} + l_{1x} l_{1y} & L_{1yy} m_{1} - l_{1x}^{2} - l_{1z}^{2} & L_{1yz} m_{1} + l_{1y} l_{1z} \\ L_{1xz} m_{1} + l_{1x} l_{1z} & L_{1yz} m_{1} + l_{1y} l_{1z} & L_{1zz} m_{1} - l_{1x}^{2} - l_{1y}^{2} \end{smallmatrix}\right]$$

then, through Sylvester's criterion,

$$mI \succ 0 \Leftrightarrow \left\{ \begin{matrix} \det\left(mI_{1,1}\right) = L_{1xx} m_{1} - l_{1y}^{2} - l_{1z}^{2} &> 0\\ \det\left(mI_{1:2,1:2}\right) &> 0\\ \det\left(mI\right) &>0 \end{matrix} \right.$$

It would be sufficient that the polynomials were concave to guarantee set convexity, however they are not concave. Although not being concave, it does not imply that set is not convex; for example, the first polynomial $L_{1xx} m_{1} - l_{1y}^{2} - l_{1z}^{2}$ is not concave itself but defines a convex set if constraint $m>0$ is taken into account. (This representation also gave me some suspicions that maybe the $L \succ 0$ constraint is implicit on the other.)

I also tried to write the set as a linear matrix inequality (LMI), but I couldn't (my knowledge in this area is really short).

Update:

I was able to check that this set is close under positive scalar multiplication, since $$(\gamma\ m) (\gamma\ L) - S\left(\gamma\ l\right)^T S\left(\gamma\ l\right) = \gamma^2 \ \left( m L - S\left(l\right)^T S\left(l\right)\right) \succ 0 \quad \text{for} \quad \gamma > 0$$ then it is a cone. If one can prove the set is close under addition then it will be proven to be a convex cone.

Now, the questions are:

Which methods can I use to check if the defined set is convex?

If so, is it possible to represent it as an LMI?

-
$S$ is a linear operator, so you can take the factors of $1/m$ out of $S(l/m)$ and rewrite your constraint as $L-\frac{1}{m} S(l)^{T}S(l) \succ 0$ –  Brian Borchers Jun 16 '12 at 2:44
It is true Brian, that's why I said the constraint is equivalent to $m L − S(l)^T S(l) \succ 0$ which is representable by polynomial inequalities. –  CDSousa Jun 16 '12 at 3:21

Your set is indeed a convex cone.

Since it is a cone, it suffices to show that the $m=1$ section is convex.

But this is equivalent to show that the (symmetric matrix valued) "function" $u\mapsto P(u)=S(u)^*S(u)$ is "convex", i.e. $P((u+v)/2)\prec (P(u)+P(v))/2$, because the set is basically the "epigraph" $(u,L)$ : $L\succ P(u)$.

Now it is easily checked that the quadratic function $P$ satisties the parallelogram identity $P((u+v)/2)+P((u-v)/2)=(P(u)+P(v))/2$, which does the job since $P$ is positive.

EDIT : in fact any set of $(x,y)$ defined by an inequality $S(y)-A(x)^*A(x) \succ 0$, with $S(y)$ $n\times n$ symmetric and linear in $y$, and $A(x)$ $n\times d$ and linear in $x$, is convex and moreover defined by a Linear Matrix Inequality.

Indeed this is equivalent to

$$\left(\begin{matrix} S(y) & A(x)^* \\\ A(x) & I \end{matrix}\right) \succ 0$$

as easily seen by row and column operations. In fact substituting $I$ by $\lambda I$, you can "re-homogenize" the problem.

-
Amazing! The LMI had been my ultimate goal :) Thank you very much! –  CDSousa Jun 19 '12 at 17:45
I've found that this is related to Schur complements: en.wikipedia.org/wiki/… –  CDSousa Jun 20 '12 at 0:08
Yes, you are right, I forgot the name. Happy to be of help. –  BS. Jun 20 '12 at 9:09
By the way, after a little digging, I found a SIAM review on "semidefinite programming" that might interest you at this address stanford.edu/~boyd/papers/sdp.html –  BS. Jun 20 '12 at 17:38
I would like to formally thank you in the acknowledgments section of my PhD thesis, do you mind? I would like to use your real name. If you don't mind, please contact me at crisjss@gmail.com. Thanks. –  CDSousa Sep 20 at 15:32