Convexity of a specific semialgebraic set - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T00:01:47Z http://mathoverflow.net/feeds/question/99758 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/99758/convexity-of-a-specific-semialgebraic-set Convexity of a specific semialgebraic set CDSousa 2012-06-15T23:44:31Z 2012-06-19T17:20:27Z <p>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:</p> <p>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</p> <p>$L - m\ S\left(\frac{l}{m}\right)^T S\left(\frac{l}{m}\right) \succ 0$</p> <p>where $S(\dot{})$ means the skew-symmetric matrix operator, and $\succ 0$ means positive-definite, defines a convex set?</p> <hr> <p>I.e.:</p> <p>Being</p> <p>$$m \in \mathbb{R}$$</p> <p>$$l \equiv \left[l_x\ l_y\ l_z\right]^T$$</p> <p> $$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]$$ </p> <p>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.</p> <p>The constraints</p> <p> $$\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.$$ </p> <p>which, since $m>0$, are equivalent to</p> <p> $$\left\{ \begin{matrix} m &> 0 \\ L &\succ 0\\ m L - S\left(l\right)^T S\left(l\right) &\succ 0 \end{matrix} \right.$$ </p> <p>define a semialgebraic set on the $\mathbb{R}^{10}$ variables space.</p> <p>Here, $\succ 0$ means that the left argument is a positive-definite matrix, and,</p> <p> $$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$$ </p> <hr> <p>I did some, manipulation and rewrote the last constraint as a polynomial inequalities system:</p> <p>being</p> <p> $$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]$$ </p> <p>then, through Sylvester's criterion,</p> <p> $$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.$$ </p> <p>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.)</p> <p>I also tried to write the set as a <a href="http://www.math.uni-konstanz.de/~schweigh/presentations/dcssblmi.pdf" rel="nofollow">linear matrix inequality (LMI)</a>, but I couldn't (my knowledge in this area is really short). </p> <hr> <p><strong>Update</strong>:</p> <p>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.</p> <hr> <blockquote> <p>Now, the <strong>questions</strong> are:</p> <p>Which methods can I use to check if the defined set is convex?</p> <p>If so, is it possible to represent it as an LMI?</p> </blockquote> http://mathoverflow.net/questions/99758/convexity-of-a-specific-semialgebraic-set/100018#100018 Answer by BS for Convexity of a specific semialgebraic set BS 2012-06-19T15:55:33Z 2012-06-19T17:20:27Z <p>Your set is indeed a convex cone.</p> <p>Since it is a cone, it suffices to show that the $m=1$ section is convex. </p> <p>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)$.</p> <p>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.</p> <p>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 <em>defined by a Linear Matrix Inequality</em>.</p> <p>Indeed this is equivalent to </p> <p>$$\left(\begin{matrix} S(y) &amp; A(x)^* \\ A(x) &amp; I \end{matrix}\right) \succ 0$$</p> <p>as easily seen by row and column operations. In fact substituting $I$ by $\lambda I$, you can "re-homogenize" the problem.</p>