Polynomial SOS

<h2 id="square-matricial-representation-smr">Square matricial representation (SMR)</h2>
To establish whether a form h(x) is SOS amounts to solving a <a href="/facts/Convex_optimization/7D6U4MTN">convex optimization</a> problem. Indeed, any h(x) can be written as

h
        (
        x
        )
        =
        
          x
          
            {
            m
            
              }
              ′
            
          
        
        
          (
          
            H
            +
            L
            (
            α
            )
          
          )
        
        
          x
          
            {
            m
            }
          
        
      
    
    {\displaystyle h(x)=x^{\{m\}'}\left(H+L(\alpha )\right)x^{\{m\}}}

where 
 
 
 
 
 x
 
 {
 m
 }
 
 
 
 
 {\displaystyle x^{\{m\}}}
 
 is a vector containing a base for the forms of degree m in x (such as all <a href="/facts/Monomial/6VAPCYXJ">monomials</a> of degree m in x), the prime ′ denotes the <a href="/facts/Transpose/8wmsagGS">transpose</a>, H is any <a href="/facts/Symmetric_matrix/08CGwjNl">symmetric matrix</a> satisfying

h
        (
        x
        )
        =
        
          x
          
            
              
                {
                m
                }
              
              ′
            
          
        
        H
        
          x
          
            {
            m
            }
          
        
      
    
    {\displaystyle h(x)=x^{\left\{m\right\}'}Hx^{\{m\}}}

and 
 
 
 
 L
 (
 α
 )
 
 
 {\displaystyle L(\alpha )}
 
 is a linear parameterization of the <a href="/facts/Vector_space/M1pxMLx2">linear space</a>

L
          
        
        =
        
          {
          
            L
            =
            
              L
              ′
            
            :
             
            
              x
              
                {
                m
                
                  }
                  ′
                
              
            
            L
            
              x
              
                {
                m
                }
              
            
            =
            0
          
          }
        
        .
      
    
    {\displaystyle {\mathcal {L}}=\left\{L=L':~x^{\{m\}'}Lx^{\{m\}}=0\right\}.}

The dimension of the vector 
 
 
 
 
 x
 
 {
 m
 }
 
 
 
 
 {\displaystyle x^{\{m\}}}
 
 is given by

σ
        (
        n
        ,
        m
        )
        =
        
          
            
              (
            
            
              
                n
                +
                m
                −
                1
              
              m
            
            
              )
            
          
        
        ,
      
    
    {\displaystyle \sigma (n,m)={\binom {n+m-1}{m}},}

whereas the dimension of the vector 
  
    
      
        α
      
    
    {\displaystyle \alpha }
  
 is given by

ω
        (
        n
        ,
        2
        m
        )
        =
        
          
            1
            2
          
        
        σ
        (
        n
        ,
        m
        )
        
          (
          
            1
            +
            σ
            (
            n
            ,
            m
            )
          
          )
        
        −
        σ
        (
        n
        ,
        2
        m
        )
        .
      
    
    {\displaystyle \omega (n,2m)={\frac {1}{2}}\sigma (n,m)\left(1+\sigma (n,m)\right)-\sigma (n,2m).}

Then, h(x) is SOS if and only if there exists a vector 
 
 
 
 α
 
 
 {\displaystyle \alpha }
 
 such that

H
        +
        L
        (
        α
        )
        ≥
        0
        ,
      
    
    {\displaystyle H+L(\alpha )\geq 0,}

meaning that the <a href="/facts/Matrix_(mathematics)/qa8FI4ko">matrix</a> 
 
 
 
 H
 +
 L
 (
 α
 )
 
 
 {\displaystyle H+L(\alpha )}
 
 is <a href="/facts/Positive-semidefinite_matrix/Hbr6AuPS">positive-semidefinite</a>. This is a <a href="/facts/Linear_matrix_inequality/D8CDTIdc">linear matrix inequality</a> (LMI) feasibility test, which is a convex optimization problem. The expression 
 
 
 
 h
 (
 x
 )
 =
 
 x
 
 {
 m
 
 }
 ′
 
 
 
 
 (
 
 H
 +
 L
 (
 α
 )
 
 )
 
 
 x
 
 {
 m
 }
 
 
 
 
 {\displaystyle h(x)=x^{\{m\}'}\left(H+L(\alpha )\right)x^{\{m\}}}
 
 was introduced in <a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> with the name square matricial representation (SMR) in order to establish whether a form is SOS via an LMI. This representation is also known as Gram matrix.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>

<h3>Examples</h3>
<ul><li>Consider the form of degree 4 in two variables 
 
 
 
 h
 (
 x
 )
 =
 
 x
 
 1
 
 
 4
 
 
 −
 
 x
 
 1
 
 
 2
 
 
 
 x
 
 2
 
 
 2
 
 
 +
 
 x
 
 2
 
 
 4
 
 
 
 
 {\displaystyle h(x)=x_{1}^{4}-x_{1}^{2}x_{2}^{2}+x_{2}^{4}}
 
. We have 
 
 
 
 m
 =
 2
 ,
  
 
 x
 
 {
 m
 }
 
 
 =
 
 
 (
 
 
 
 
 x
 
 1
 
 
 2
 
 
 
 
 
 
 
 x
 
 1
 
 
 
 x
 
 2
 
 
 
 
 
 
 
 x
 
 2
 
 
 2
 
 
 
 
 
 )
 
 
 
 ,
  
 H
 +
 L
 (
 α
 )
 =
 
 
 (
 
 
 
 1
 
 
 0
 
 
 −
 
 α
 
 1
 
 
 
 
 
 
 0
 
 
 −
 1
 +
 2
 
 α
 
 1
 
 
 
 
 0
 
 
 
 
 −
 
 α
 
 1
 
 
 
 
 0
 
 
 1
 
 
 
 )
 
 
 
 .
 
 
 {\displaystyle m=2,~x^{\{m\}}={\begin{pmatrix}x_{1}^{2}\\x_{1}x_{2}\\x_{2}^{2}\end{pmatrix}}\!,~H+L(\alpha )={\begin{pmatrix}1&0&-\alpha _{1}\\0&-1+2\alpha _{1}&0\\-\alpha _{1}&0&1\end{pmatrix}}\!.}
 
 Since there exists α such that 
 
 
 
 H
 +
 L
 (
 α
 )
 ≥
 0
 
 
 {\displaystyle H+L(\alpha )\geq 0}
 
, namely 
 
 
 
 α
 =
 1
 
 
 {\displaystyle \alpha =1}
 
, it follows that h(x) is SOS.</li>
<li>Consider the form of degree 4 in three variables 
 
 
 
 h
 (
 x
 )
 =
 2
 
 x
 
 1
 
 
 4
 
 
 −
 2.5
 
 x
 
 1
 
 
 3
 
 
 
 x
 
 2
 
 
 +
 
 x
 
 1
 
 
 2
 
 
 
 x
 
 2
 
 
 
 x
 
 3
 
 
 −
 2
 
 x
 
 1
 
 
 
 x
 
 3
 
 
 3
 
 
 +
 5
 
 x
 
 2
 
 
 4
 
 
 +
 
 x
 
 3
 
 
 4
 
 
 
 
 {\displaystyle h(x)=2x_{1}^{4}-2.5x_{1}^{3}x_{2}+x_{1}^{2}x_{2}x_{3}-2x_{1}x_{3}^{3}+5x_{2}^{4}+x_{3}^{4}}
 
. We have 
 
 
 
 m
 =
 2
 ,
  
 
 x
 
 {
 m
 }
 
 
 =
 
 
 (
 
 
 
 
 x
 
 1
 
 
 2
 
 
 
 
 
 
 
 x
 
 1
 
 
 
 x
 
 2
 
 
 
 
 
 
 
 x
 
 1
 
 
 
 x
 
 3
 
 
 
 
 
 
 
 x
 
 2
 
 
 2
 
 
 
 
 
 
 
 x
 
 2
 
 
 
 x
 
 3
 
 
 
 
 
 
 
 x
 
 3
 
 
 2
 
 
 
 
 
 )
 
 
 ,
  
 H
 +
 L
 (
 α
 )
 =
 
 
 (
 
 
 
 2
 
 
 −
 1.25
 
 
 0
 
 
 −
 
 α
 
 1
 
 
 
 
 −
 
 α
 
 2
 
 
 
 
 −
 
 α
 
 3
 
 
 
 
 
 
 −
 1.25
 
 
 2
 
 α
 
 1
 
 
 
 
 0.5
 +
 
 α
 
 2
 
 
 
 
 0
 
 
 −
 
 α
 
 4
 
 
 
 
 −
 
 α
 
 5
 
 
 
 
 
 
 0
 
 
 0.5
 +
 
 α
 
 2
 
 
 
 
 2
 
 α
 
 3
 
 
 
 
 
 α
 
 4
 
 
 
 
 
 α
 
 5
 
 
 
 
 −
 1
 
 
 
 
 −
 
 α
 
 1
 
 
 
 
 0
 
 
 
 α
 
 4
 
 
 
 
 5
 
 
 0
 
 
 −
 
 α
 
 6
 
 
 
 
 
 
 −
 
 α
 
 2
 
 
 
 
 −
 
 α
 
 4
 
 
 
 
 
 α
 
 5
 
 
 
 
 0
 
 
 2
 
 α
 
 6
 
 
 
 
 0
 
 
 
 
 −
 
 α
 
 3
 
 
 
 
 −
 
 α
 
 5
 
 
 
 
 −
 1
 
 
 −
 
 α
 
 6
 
 
 
 
 0
 
 
 1
 
 
 
 )
 
 
 .
 
 
 {\displaystyle m=2,~x^{\{m\}}={\begin{pmatrix}x_{1}^{2}\\x_{1}x_{2}\\x_{1}x_{3}\\x_{2}^{2}\\x_{2}x_{3}\\x_{3}^{2}\end{pmatrix}},~H+L(\alpha )={\begin{pmatrix}2&-1.25&0&-\alpha _{1}&-\alpha _{2}&-\alpha _{3}\\-1.25&2\alpha _{1}&0.5+\alpha _{2}&0&-\alpha _{4}&-\alpha _{5}\\0&0.5+\alpha _{2}&2\alpha _{3}&\alpha _{4}&\alpha _{5}&-1\\-\alpha _{1}&0&\alpha _{4}&5&0&-\alpha _{6}\\-\alpha _{2}&-\alpha _{4}&\alpha _{5}&0&2\alpha _{6}&0\\-\alpha _{3}&-\alpha _{5}&-1&-\alpha _{6}&0&1\end{pmatrix}}.}
 
 Since 
 
 
 
 H
 +
 L
 (
 α
 )
 ≥
 0
 
 
 {\displaystyle H+L(\alpha )\geq 0}
 
 for 
 
 
 
 α
 =
 (
 1.18
 ,
 −
 0.43
 ,
 0.73
 ,
 1.13
 ,
 −
 0.37
 ,
 0.57
 )
 
 
 {\displaystyle \alpha =(1.18,-0.43,0.73,1.13,-0.37,0.57)}
 
, it follows that h(x) is SOS.</li></ul>
<h2 id="generalizations">Generalizations</h2>
<h3>Matrix SOS</h3>
A matrix form F(x) (i.e., a matrix whose entries are forms) of dimension r and degree 2m in the real n-dimensional vector x is SOS if and only if there exist matrix forms 
 
 
 
 
 G
 
 1
 
 
 (
 x
 )
 ,
 …
 ,
 
 G
 
 k
 
 
 (
 x
 )
 
 
 {\displaystyle G_{1}(x),\ldots ,G_{k}(x)}
 
 of degree m such that

F
        (
        x
        )
        =
        
          ∑
          
            i
            =
            1
          
          
            k
          
        
        
          G
          
            i
          
        
        (
        x
        
          )
          ′
        
        
          G
          
            i
          
        
        (
        x
        )
        .
      
    
    {\displaystyle F(x)=\sum _{i=1}^{k}G_{i}(x)'G_{i}(x).}

<h4>Matrix SMR</h4>
To establish whether a matrix form F(x) is SOS amounts to solving a convex optimization problem. Indeed, similarly to the scalar case any F(x) can be written according to the SMR as

F
        (
        x
        )
        =
        
          
            (
            
              
                x
                
                  {
                  m
                  }
                
              
              ⊗
              
                I
                
                  r
                
              
            
            )
          
          ′
        
        
          (
          
            H
            +
            L
            (
            α
            )
          
          )
        
        
          (
          
            
              x
              
                {
                m
                }
              
            
            ⊗
            
              I
              
                r
              
            
          
          )
        
      
    
    {\displaystyle F(x)=\left(x^{\{m\}}\otimes I_{r}\right)'\left(H+L(\alpha )\right)\left(x^{\{m\}}\otimes I_{r}\right)}

where 
 
 
 
 ⊗
 
 
 {\displaystyle \otimes }
 
 is the <a href="/facts/Kronecker_product/gABGx6I6">Kronecker product</a> of matrices, H is any symmetric matrix satisfying

F
        (
        x
        )
        =
        
          
            (
            
              
                x
                
                  {
                  m
                  }
                
              
              ⊗
              
                I
                
                  r
                
              
            
            )
          
          ′
        
        H
        
          (
          
            
              x
              
                {
                m
                }
              
            
            ⊗
            
              I
              
                r
              
            
          
          )
        
      
    
    {\displaystyle F(x)=\left(x^{\{m\}}\otimes I_{r}\right)'H\left(x^{\{m\}}\otimes I_{r}\right)}

and 
  
    
      
        L
        (
        α
        )
      
    
    {\displaystyle L(\alpha )}
  
 is a linear parameterization of the linear space

L
          
        
        =
        
          {
          
            L
            =
            
              L
              ′
            
            :
             
            
              
                (
                
                  
                    x
                    
                      {
                      m
                      }
                    
                  
                  ⊗
                  
                    I
                    
                      r
                    
                  
                
                )
              
              ′
            
            L
            
              (
              
                
                  x
                  
                    {
                    m
                    }
                  
                
                ⊗
                
                  I
                  
                    r
                  
                
              
              )
            
            =
            0
          
          }
        
        .
      
    
    {\displaystyle {\mathcal {L}}=\left\{L=L':~\left(x^{\{m\}}\otimes I_{r}\right)'L\left(x^{\{m\}}\otimes I_{r}\right)=0\right\}.}

The dimension of the vector 
 
 
 
 α
 
 
 {\displaystyle \alpha }
 
 is given by

ω
        (
        n
        ,
        2
        m
        ,
        r
        )
        =
        
          
            1
            2
          
        
        r
        
          (
          
            σ
            (
            n
            ,
            m
            )
            
              (
              
                r
                σ
                (
                n
                ,
                m
                )
                +
                1
              
              )
            
            −
            (
            r
            +
            1
            )
            σ
            (
            n
            ,
            2
            m
            )
          
          )
        
        .
      
    
    {\displaystyle \omega (n,2m,r)={\frac {1}{2}}r\left(\sigma (n,m)\left(r\sigma (n,m)+1\right)-(r+1)\sigma (n,2m)\right).}

Then, F(x) is SOS if and only if there exists a vector 
 
 
 
 α
 
 
 {\displaystyle \alpha }
 
 such that the following LMI holds:

H
        +
        L
        (
        α
        )
        ≥
        0.
      
    
    {\displaystyle H+L(\alpha )\geq 0.}

The expression 
 
 
 
 F
 (
 x
 )
 =
 
 
 (
 
 
 x
 
 {
 m
 }
 
 
 ⊗
 
 I
 
 r
 
 
 
 )
 
 ′
 
 
 (
 
 H
 +
 L
 (
 α
 )
 
 )
 
 
 (
 
 
 x
 
 {
 m
 }
 
 
 ⊗
 
 I
 
 r
 
 
 
 )
 
 
 
 {\displaystyle F(x)=\left(x^{\{m\}}\otimes I_{r}\right)'\left(H+L(\alpha )\right)\left(x^{\{m\}}\otimes I_{r}\right)}
 
 was introduced in <a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> in order to establish whether a matrix form is SOS via an LMI.

<h3>Noncommutative polynomial SOS</h3>
Consider the <a href="/facts/Free_algebra/xMrT0WbT">free algebra</a> R⟨X⟩ generated by the n noncommuting letters X = (X1, ..., Xn) and equipped with the involution T, such that T fixes R and X1, ..., Xn and reverses words formed by X1, ..., Xn.
By analogy with the commutative case, the noncommutative <a href="/facts/Symmetric_polynomial/GNhguVcn">symmetric polynomials</a> f are the noncommutative polynomials of the form f = fT. When any real matrix of any dimension r × r is evaluated at a symmetric noncommutative polynomial f results in a <a href="/facts/Positive_semi-definite_matrix/Hbr6AuPS">positive semi-definite matrix</a>, f is said to be matrix-positive.
A noncommutative polynomial is SOS if there exists noncommutative polynomials 
 
 
 
 
 h
 
 1
 
 
 ,
 …
 ,
 
 h
 
 k
 
 
 
 
 {\displaystyle h_{1},\ldots ,h_{k}}
 
 such that

f
        (
        X
        )
        =
        
          ∑
          
            i
            =
            1
          
          
            k
          
        
        
          h
          
            i
          
        
        (
        X
        
          )
          
            T
          
        
        
          h
          
            i
          
        
        (
        X
        )
        .
      
    
    {\displaystyle f(X)=\sum _{i=1}^{k}h_{i}(X)^{T}h_{i}(X).}

Surprisingly, in the noncommutative scenario a noncommutative polynomial is SOS if and only if it is matrix-positive.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> Moreover, there exist algorithms available to decompose matrix-positive polynomials in sum of squares of noncommutative polynomials.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Sum-of-squares_optimization/wz5NPbeB">Sum-of-squares optimization</a></li>
<li><a href="/facts/Positive_polynomial/WIl2Mv9s">Positive polynomial</a></li>
<li><a href="/facts/Hilbert%2527s_seventeenth_problem/G5USMzdt">Hilbert's seventeenth problem</a></li>
<li><a href="/facts/SOS-convexity/BUDlkY06">SOS-convexity</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Hilbert, David (September 1888). "Ueber die Darstellung definiter Formen als Summe von Formenquadraten". Mathematische Annalen. 32 (3): 342–350. doi:10.1007/bf01443605. S2CID 177804714. <a href="https://zenodo.org/record/1428214" target="_blank">https://zenodo.org/record/1428214</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Choi, M. D.; Lam, T. Y. (1977). "An old question of Hilbert". Queen's Papers in Pure and Applied Mathematics. 46: 385–405. <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Goel, Charu; Kuhlmann, Salma; Reznick, Bruce (May 2016). "On the Choi–Lam analogue of Hilbert's 1888 theorem for symmetric forms". Linear Algebra and Its Applications. 496: 114–120. arXiv:1505.08145. doi:10.1016/j.laa.2016.01.024. S2CID 17579200. <a href="/wiki/Bruce_Reznick" target="_blank">/wiki/Bruce_Reznick</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Lasserre, Jean B. (2007). "Sufficient conditions for a real polynomial to be a sum of squares". Archiv der Mathematik. 89 (5): 390–398. arXiv:math/0612358. CiteSeerX 10.1.1.240.4438. doi:10.1007/s00013-007-2251-y. S2CID 9319455. <a href="https://www.optimization-online.org/DB_HTML/2007/02/1587.html" target="_blank">https://www.optimization-online.org/DB_HTML/2007/02/1587.html</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Powers, Victoria; Wörmann, Thorsten (1998). "An algorithm for sums of squares of real polynomials" (PDF). Journal of Pure and Applied Algebra. 127 (1): 99–104. doi:10.1016/S0022-4049(97)83827-3. <a href="/wiki/Victoria_Powers" target="_blank">/wiki/Victoria_Powers</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Lasserre, Jean B. (2007). "A Sum of Squares Approximation of Nonnegative Polynomials". SIAM Review. 49 (4): 651–669. arXiv:math/0412398. Bibcode:2007SIAMR..49..651L. doi:10.1137/070693709. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Chesi, G.; Tesi, A.; Vicino, A.; Genesio, R. (1999). "On convexification of some minimum distance problems". Proceedings of the 5th European Control Conference. Karlsruhe, Germany: IEEE. pp. 1446–1451. <a href="https://ieeexplore.ieee.org/document/7099515" target="_blank">https://ieeexplore.ieee.org/document/7099515</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Choi, M.; Lam, T.; Reznick, B. (1995). "Sums of squares of real polynomials". Proceedings of Symposia in Pure Mathematics. pp. 103–125. <a href="https://www.researchgate.net/publication/240268385" target="_blank">https://www.researchgate.net/publication/240268385</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Chesi, G.; Garulli, A.; Tesi, A.; Vicino, A. (2003). "Robust stability for polytopic systems via polynomially parameter-dependent Lyapunov functions". Proceedings of the 42nd IEEE Conference on Decision and Control. Maui, Hawaii: IEEE. pp. 4670–4675. doi:10.1109/CDC.2003.1272307. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Helton, J. William (September 2002). ""Positive" Noncommutative Polynomials Are Sums of Squares". The Annals of Mathematics. 156 (2): 675–694. doi:10.2307/3597203. JSTOR 3597203. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Burgdorf, Sabine; Cafuta, Kristijan; Klep, Igor; Povh, Janez (25 October 2012). "Algorithmic aspects of sums of Hermitian squares of noncommutative polynomials". Computational Optimization and Applications. 55 (1): 137–153. CiteSeerX 10.1.1.416.543. doi:10.1007/s10589-012-9513-8. S2CID 254416733. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
</ol>

Polynomial SOS open-in-new

Polynomial SOS