Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
$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

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.