Polynomial SOS

Polynomial SOS

In mathematics, a homogeneous form "h"("x") of degree 2"m" in the real "n"-dimensional vector "x" is a SOS (sum of squares) of homogeneous forms if and only if it can be written as a sum of squares of homogeneous forms of degree "m":

:h(x)~mbox{is SOS}~iff~exists~mbox{homogeneous forms}~g_1(x),ldots,g_k(x):~h(x)=sum_{i=1}^k g_i(x)^2

SOS of polynomials is a special case of SOS of homogeneous forms since any polynomial is a homogeneous form with an additional variable set to 1.

Square matricial representation

To establish whether a form "h"("x") is a SOS or not amounts to solving a convex optimization problem. Indeed, any "h"("x") can be written according to the square matricial representation (SMR) as

:h(x)=x^{{m}'}left(H+L(alpha) ight)x^{{m

where x^{{m is a vector containing a base for the homogeneous 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

:h(x)=x^{left{m ight}'}Hx^{{m

and L(alpha) is a linear parameterization of the linear space

:mathcal{L}=left{L=L':~x^{{m}'} L x^{{m=0 ight}.

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

:sigma(n,m)=inom{n+m-1}{m}

whereas the dimension of the vector alpha is given by

:omega(n,2m)=frac{1}{2}sigma(n,m)left(1+sigma(n,m) ight)-sigma(n,2m).

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

:H + L(alpha) ge 0,

meaning that the matrix H + L(alpha) is positive-semidefinite. This is a linear matrix inequality (LMI) feasibility test and, hence, a convex optimization problem. The SMR and its use for testing SOS via LMI have been introduced in [1] . The SMR is also known as Gram matrix.

Examples

  • Consider the homogeneous form of degree 4 in two variables, which is given by h(x)=x_1^4-x_1^2x_2^2+x_2^4. We have:m=2,~x^{{m=left(egin{array}{c}x_1^2\x_1x_2\x_2^2end{array} ight),~H+L(alpha)=left(egin{array}{ccc}1&0&-alpha_1\0&-1+2alpha_1&0\-alpha_1&0&1end{array} ight).Since there exists an α such that H+L(alpha)ge 0, namely alpha=1, it follows that "h"("x") is a SOS.
  • h(x)=2x_1^4-2.5x_1^3x_2+x_1^2x_2x_3-2x_1x_3^3+5x_2^4+x_3^4:m=2,~x^{{m=left(egin{array}{c}x_1^2\x_1x_2\x_1x_3\x_2^2\x_2x_3\x_3^2end{array} ight),~H+L(alpha)=left(egin{array}{cccccc}2&-1.25&0&-alpha_1&-alpha_2&-alpha_3\-1.25&2alpha_1&0.5+alpha_2&0&-alpha_4&-alpha_5\0&0.5+alpha_2&2alpha_3&alpha_4&alpha_5&-1\-alpha_1&0&alpha_4&5&0&-alpha_6\-alpha_2&-alpha_4&alpha_5&0&2alpha_6&0\-alpha_3&-alpha_5&-1&-alpha_6&0&1end{array} ight)Since H+L(alpha)ge 0 for α = (1.18, −0.43, 0.73, 1.13, −0.37, 0.57)', it follows that "h"("x") is a SOS

Matrix SOS

A matrix homogeneous form "H"("x") (i.e., a matrix whose entries are homogeneous forms) of dimension "r" and degree "2m" in the real "n"-dimensional vector "x" is a SOS if and only if it can be written as sum of products of matrix homogeneous forms of degree "m" times their transpose:

:H(x)~mbox{is SOS}~iff~exists~mbox{matrix homogeneous forms}~G_1(x),ldots,G_k(x):~H(x)=sum_{i=1}^k G_i(x)'G_i(x)

Matrix SMR

To establish whether a matrix homogeneous form "H"("x") is a SOS or not amounts to solving a convex optimization. Indeed, similarly to the scalar case any "H"("x") can be written according to the matrix SMR as

:h(x)=left(x^{{motimes I_r ight)'left(H+L(alpha) ight)left(x^{{motimes I_r ight)

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

:h(x)=left(x^{{motimes I_r ight)'Hleft(x^{{motimes I_r ight)

and L(alpha) is a linear parameterization of the linear space

:mathcal{L}=left{L=L':~left(x^{{motimes I_r ight)'Lleft(x^{{motimes I_r ight)=0 ight}.

The dimension of the vector alpha is given by

:omega(n,2m,r)=frac{1}{2}rleft(sigma(n,m)left(rsigma(n,m)+1 ight)-(r+1)sigma(n,2m) ight).

Then, "H"("x") is a SOS if and only if the following LMI holds:

:exists alpha:~H+L(alpha) ge 0.

Matrix SOS and matrix SMR have been introduced in [2] .

References

[1] G. Chesi, A. Tesi, A. Vicino, and R. Genesio, "On convexification of some minimum distance problems", 5th European Control Conference, Karlsruhe (Germany), 1999.

[2] G. Chesi, A. Garulli, A. Tesi, and A. Vicino, "Robust stability for polytopic systems via polynomially parameter-dependent Lyapunov functions", in 42nd IEEE Conference on Decision and Control, Maui (Hawaii), 2003.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • SOS (disambiguation) — SOS may stand for:Games* SOS (arcade game), a 1981 arcade game by Nam * SOS (game), a paper and pencil game * SOS (video game), a 1994 Super Nintendo game by Human EntertainmentGovernment and military* Secretary of State * Services of Supply an… …   Wikipedia

  • List of polynomial topics — This is a list of polynomial topics, by Wikipedia page. See also trigonometric polynomial, list of algebraic geometry topics.Basics*Polynomial *Coefficient *Monomial *Polynomial long division *Polynomial factorization *Rational function *Partial… …   Wikipedia

  • List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… …   Wikipedia

  • Linear matrix inequality — In convex optimization, a linear matrix inequality (LMI) is an expression of the form: LMI(y):=A 0+y 1A 1+y 2A 2+cdots+y m A mgeq0,where * y= [y i,, i!=!1dots m] is a real vector, * A 0,, A 1,, A 2,,dots,A m are symmetric matrices in the subspace …   Wikipedia

  • SMR — may mean:* *Safe Memory Reclamation *Saltwood Miniature Railway *Schweitzer Mountain Resort *See Me Running, a musical project of DJ Stanny Tape. *Self Myofascial Release *Sensorimotor rhythm *Shinto Muso ryu, the art of handling the Japanese… …   Wikipedia

  • Sum of squares — is a concept that permeates much of inferential statistics and descriptive statistics. More properly, it is the sum of the squared deviations . Mathematically, it is an unscaled, or unadjusted measure of dispersion (also called variability). When …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Combinatorica — is an international journal of mathematics, publishing papers in the fields of combinatorics and computer science. It started in 1981, with László Babai and László Lovász as the editors in chief with Paul Erdős as honorary editor in chief. The… …   Wikipedia

  • Hilbert's seventeenth problem — is one of the 23 Hilbert problems set out in a celebrated list compiled in 1900 by David Hilbert. It entails expression of definite rational functions as quotients of sums of squares. Original Hilbert s question was:Given a multivariate… …   Wikipedia

  • Palindrome — Palindromes redirects here. For the film, see Palindromes (film). See also: Constrained writing A palindrome is a word, phrase, number, or other sequence of units that can be read the same way in either direction, with general allowances for… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”