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$
  • $\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$ – Brian Borchers Jun 16 '12 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$ – Cristóvão D. Sousa Jun 16 '12 at 3:21
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$
  • $\begingroup$ Amazing! The LMI had been my ultimate goal :) Thank you very much! $\endgroup$ – Cristóvão D. Sousa Jun 19 '12 at 17:45
  • $\begingroup$ I've found that this is related to Schur complements: en.wikipedia.org/wiki/… $\endgroup$ – Cristóvão D. Sousa Jun 20 '12 at 0:08
  • $\begingroup$ Yes, you are right, I forgot the name. Happy to be of help. $\endgroup$ – BS. Jun 20 '12 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 '12 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$ – Cristóvão D. Sousa Sep 20 '14 at 15:32

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.