请输入您要查询的百科知识：

　

词条 Polynomial SOS
释义

  1. Square matricial representation (SMR)

      Examples  

  2. Generalizations

      Matrix SOS    Matrix SMR    Noncommutative polynomial SOS  

  3. References

  4. See also

{{about|representing a non-negative polynomial as sum of squares of polynomials|representing polynomial as a sum of squares of rational functions|Hilbert's seventeenth problem|the sum of squares of consecutive integers|square pyramidal number|representing an integer as a sum of squares of integers|Lagrange's four-square theorem}}

In mathematics, a form (i.e. a homogeneous polynomial) h(x) of degree 2m in the real n-dimensional vector x is sum of squares of forms (SOS) if and only if there exist forms of degree m such that

Every form that is SOS is also a positive polynomial, and although the converse is not always true, Hilbert proved that for n = 2, m = 1 or n = 3 and 2m = 4 a form is SOS if and only if it is positive.[1] The same is also valid for the analog problem on positive symmetric forms.[2][3]

Although not every form can be represented as SOS, explicit sufficient conditions for a form to be SOS have been found.[4][5] Moreover, every real nonnegative form can be approximated as closely as desired (in the -norm of its coefficient vector) by a sequence of forms that are SOS.[6]

Square matricial representation (SMR)

To establish whether a form h(x) is SOS amounts to solving a convex optimization problem. Indeed, any h(x) can be written as

where is a vector containing a base for the forms of degree m in x (such as all monomials of degree m in x), the prime ′ denotes the transpose, H is any symmetric matrix satisfying

and is a linear parameterization of the linear space

The dimension of the vector is given by

whereas the dimension of the vector is given by

Then, h(x) is SOS if and only if there exists a vector such that

meaning that the matrix is positive-semidefinite. This is a linear matrix inequality (LMI) feasibility test, which is a convex optimization problem. The expression was introduced in [7] 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.[8]

Examples

  • Consider the form of degree 4 in two variables . We have

Since there exists α such that , namely , it follows that h(x) is SOS.

  • Consider the form of degree 4 in three variables . We have

Since for , it follows that h(x) is SOS.

Generalizations

Matrix SOS

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 of degree m such that

Matrix SMR

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

where is the Kronecker product of matrices, H is any symmetric matrix satisfying

and is a linear parameterization of the linear space

The dimension of the vector is given by

Then, F(x) is SOS if and only if there exists a vector such that the following LMI holds:

The expression was introduced in [9] in order to establish whether a matrix form is SOS via an LMI.

Noncommutative polynomial SOS

Consider the free algebra 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 reverse words formed by X1,...,Xn.

By analogy with the commutative case, the noncommutative symmetric polynomials f are the noncommutative polynomials of the form f=fT. When any real matrix of any dimension r x r is evaluated at a symmetric noncommutative polynomial f results in a positive semi-definite matrix, f is said to be matrix-positive.

A noncommutative polynomial is SOS if there exists noncommutative polynomials such that

Surprisingly, in the noncommutative scenario a noncommutative polynomial is SoS if and only if it is matrix-positive.[10] Moreover, there exist algorithms available to decompose matrix-positive polynomials in sum of squares of noncommutative polynomials.[11]

References

1. ^{{cite journal|last1=Hilbert|first1=David|title=Ueber die Darstellung definiter Formen als Summe von Formenquadraten|journal=Mathematische Annalen|date=September 1888|volume=32|issue=3|pages=342–350|doi=10.1007/bf01443605}}
2. ^{{cite journal|last1=Choi|first1=M. D.|last2=Lam|first2=T. Y.|title=An old question of Hilbert|journal=Queen's Papers in Pure and Applied Mathematics|date=1977|volume=46|pages=385–405}}
3. ^{{cite journal|last1=Goel|first1=Charu|last2=Kuhlmann|first2=Salma|last3=Reznick|first3=Bruce|title=On the Choi–Lam analogue of Hilbert's 1888 theorem for symmetric forms|journal=Linear Algebra and its Applications|date=May 2016|volume=496|pages=114–120|doi=10.1016/j.laa.2016.01.024|arxiv=1505.08145}}
4. ^{{cite journal|last1=Lasserre|first1=Jean B.|title=Sufficient conditions for a real polynomial to be a sum of squares|journal=Archiv der Mathematik|volume=89|issue=5|pages=390–398|doi=10.1007/s00013-007-2251-y|url=http://www.optimization-online.org/DB_HTML/2007/02/1587.html|arxiv=math/0612358|year=2007|citeseerx=10.1.1.240.4438}}
5. ^{{cite journal|last1=Powers|first1=Victoria|last2=Wörmann|first2=Thorsten|title=An algorithm for sums of squares of real polynomials|journal=Journal of Pure and Applied Algebra|date=1998|volume=127|issue=1|pages=99–104|doi=10.1016/S0022-4049(97)83827-3|url=http://www.mathcs.emory.edu/~vicki/pub/sos.pdf}}
6. ^{{cite journal|last1=Lasserre|first1=Jean B.|title=A Sum of Squares Approximation of Nonnegative Polynomials|journal=SIAM Review|date=2007|volume=49|issue=4|pages=651–669|doi=10.1137/070693709|arxiv=math/0412398}}
7. ^{{cite conference |url=http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7099515 |title=On convexification of some minimum distance problems |last1=Chesi |first1=G. |last2=Tesi |first2=A. |last3=Vicino |first3=A. |last4=Genesio |first4=R. |date=1999 |publisher=IEEE |book-title=Proceedings of the 5th European Control Conference |pages=1446–1451 |location=Karlsruhe, Germany}}
8. ^{{cite conference |url= |title=Sums of squares of real polynomials |last1=Choi |first1=M. |last2=Lam |first2=T. |last3=Reznick |first3=B. |date=1995 |book-title=Proceedings of Symposia in Pure Mathematics |pages=103–125 |location=}}
9. ^{{cite conference |url=http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1272307 |title=Robust stability for polytopic systems via polynomially parameter-dependent Lyapunov functions |last1=Chesi |first1=G. |last2=Garulli |first2=A. |last3=Tesi |first3=A. |last4=Vicino |first4=A. |date=2003 |publisher=IEEE |book-title=Proceedings of the 42nd IEEE Conference on Decision and Control |pages=4670–4675 |location=Maui, Hawaii}}
10. ^{{cite journal|last1=Helton|first1=J. William|title="Positive" Noncommutative Polynomials Are Sums of Squares|journal=The Annals of Mathematics|date=September 2002|volume=156|issue=2|pages=675–694|doi=10.2307/3597203|jstor=3597203}}
11. ^{{cite journal|last1=Burgdorf|first1=Sabine|last2=Cafuta|first2=Kristijan|last3=Klep|first3=Igor|last4=Povh|first4=Janez|title=Algorithmic aspects of sums of Hermitian squares of noncommutative polynomials|journal=Computational Optimization and Applications|date=25 October 2012|volume=55|issue=1|pages=137–153|doi=10.1007/s10589-012-9513-8|citeseerx=10.1.1.416.543}}

See also

  • Sum-of-squares optimization
  • Positive polynomial
  • Hilbert's seventeenth problem

2 : Homogeneous polynomials|Real algebraic geometry
随便看

　

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

　

Copyright © 2023 OENC.NET All Rights Reserved
京ICP备2021023879号 更新时间：2024/9/20 8:40:49