5
$\begingroup$

I have an engineering problem that may be solved using semidefinite programming. I would like to know whether a given set is convex.

Let $m \in \mathbb{R}^+$ be a positive real scalar, $l \in \mathbb{R}^3$ be a real vector, and $L \succ 0$ be a size $3 \times 3$ real positive definite matrix. Does the following inequality

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

where $S(\cdot)$ denotes the skew-symmetric matrix operator and $\succ 0$ denotes positive definiteness, define 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?

$\endgroup$
2
  • $\begingroup$ $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$ $\endgroup$ Jun 16, 2012 at 2:44
  • $\begingroup$ 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. $\endgroup$ Jun 16, 2012 at 3:21

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Amazing! The LMI had been my ultimate goal :) Thank you very much! $\endgroup$ Jun 19, 2012 at 17:45
  • $\begingroup$ I've found that this is related to Schur complements: en.wikipedia.org/wiki/… $\endgroup$ Jun 20, 2012 at 0:08
  • $\begingroup$ Yes, you are right, I forgot the name. Happy to be of help. $\endgroup$
    – BS.
    Jun 20, 2012 at 9:09
  • $\begingroup$ 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 $\endgroup$
    – BS.
    Jun 20, 2012 at 17:38
  • $\begingroup$ 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. $\endgroup$ Sep 20, 2014 at 15:32

Your Answer

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