Polynôme somme de carrés

En mathématiques, un polynôme homogène à coefficients réels $h(x)$ de degré $2m$, en les n variables $x=(x_{1},\ldots ,x_{n})$ est somme de carrés (en anglais SOS pour sum of squares) si et seulement s'il existe des polynômes homogènes $g_{1}(x),\ldots ,g_{k}(x)$ de degré $m$ tels que

$h(x)=\sum _{i=1}^{k}g_{i}(x)^{2}.$

Exemple et propriétés

Le polynôme homogène de degré 4 en deux variables $h(x)=x_{1}^{4}-x_{1}^{2}x_{2}^{2}+x_{2}^{4}$ s'écrit sous la forme

$h(x)=x_{1}^{4}-x_{1}^{2}x_{2}^{2}+x_{2}^{4}=(x_{1}^{2}-x_{2}^{2})^{2}+(x_{1}x_{2})^{2}$.

Il est donc la somme de deux carrés.

Tout polynôme homogène qui est somme de carrés est un polynôme positif (un polynôme qui ne prend que des valeurs positives) ; la réciproque n'est pas vraie et Hilbert a prouvé que, pour $n=2,m=1$ ou pour $n=3,m=2$, un polynôme homogène est somme de carrés si et seulement s'il est positif. Il en est de même pour le problème analogique des polynômes homogènes symétriques positifs .

Des conditions suffisantes pour qu'un polynôme homogène soit somme de carrés ont été données. De plus, un polynôme homogène réel positif peut être approchée arbitrairement près (pour la norme $l_{1}$ de son vecteur de coefficients) par une suite de polynômes homogènes qui sont sommes de carrés.

Représentation matricielle carrée (SMR)

On peut voir le problème d'établir qu'un polynôme homogène $h(x)$ est somme de carrés comme la résolution d'un problème d'optimisation convexe. En effet, $h(x)$ peut s'écrire sous la forme

$h(x)=x^{\{m\}'}(H+L(\alpha ))x^{\{m\}}$

où $x^{\{m\}}$ est un vecteur contenant une base des polynômes homogènes de degré $m$ en $x$ (comme par exemple les monômes de degré degré $m$ en $x$), le symbole ′ désigne la transposée, où $H$ est la matrice symétrique vérifiant

$h(x)=x^{\left\{m\right\}'}Hx^{\{m\}}$

et où $L(\alpha )$ est une paramétrisation linéaire de l'espace linéaire

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

La dimension du vecteur $x^{\{m\}}$ est égale à

$\sigma (n,m)={\binom {n+m-1}{m}},$

et la dimension du vecteur $\alpha$ est :

$\omega (n,2m)={\frac {1}{2}}\sigma (n,m)\left(1+\sigma (n,m)\right)-\sigma (n,2m).$

Avec ces notation, le polynôme $h(x)$ est une somme de carrés si et seulement s'il existe un vecteur $\alpha$ tel que

$H+L(\alpha )\geq 0$,

ce qui signifie que la matrice $H+L(\alpha )$ est semi-définie positive. On se ramène ainsi à la vérification d'une inégalité matricielle linéaire qui est un problème d'optimisation convexe. L'expression

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

a été introduite dans sous le nom de représentation matricielle carrée (square matrix representation abrégé en SMR) afin d'établir si un polynôme homogène est somme de carrés à travers une inégalité matricielle linéaire. Cette représentation est également connue sous le nom de matrice de Gram.

Exemples

• On considère le polynôme homogène de degré 4 en deux variables $h(x)=x_{1}^{4}-x_{1}^{2}x_{2}^{2}+x_{2}^{4}$ . On a

$m=2,~x^{\{m\}}=\left({\begin{array}{c}x_{1}^{2}\\x_{1}x_{2}\\x_{2}^{2}\end{array}}\right)\!,~H+L(\alpha )=\left({\begin{array}{ccc}1&0&-\alpha _{1}\\0&-1+2\alpha _{1}&0\\-\alpha _{1}&0&1\end{array}}\right)\!.$

Pour la valeur $\alpha =1$ on a $H+L(\alpha )\geq 0$ ; il s'ensuit que $h(x)$ est somme de carrés.

• On considère le polynôme homogène de degré 4 en trois variables $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}$ . On a

$m=2,~x^{\{m\}}=\left({\begin{array}{c}x_{1}^{2}\\x_{1}x_{2}\\x_{1}x_{3}\\x_{2}^{2}\\x_{2}x_{3}\\x_{3}^{2}\end{array}}\right)\!,~H+L(\alpha )=\left({\begin{array}{cccccc}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{array}}\right)\!.$

Comme $H+L(\alpha )\geq 0$ pour $\alpha =(1.18,-0.43,0.73,1.13,-0.37,0.57)$, il s'ensuit que $h(x)$ est somme de carrés.

Somme de carrés de polynômes non commutatifs

On considère l'algèbre libre $R\langle X\rangle$ engendrée par $n$ symboles non commutants $X=\{x_{1},\ldots ,x_{n}\}$, muni de l'involution ~, qui fixe $R$ et les $x_{i}$ et qui retourne les mots sur $X$ . Par analogie au cas commutatif, les polynômes symétriques non commutatifs sont les polynômes non commutatifs invariants par l'involution ~.

Un polynôme non commutatif est somme de carrés s'il existe des polynômes non commutatifs $h_{1},\ldots ,h_{k}$ tel que

$f(X)=\sum _{i=1}^{k}h_{i}(X)^{\sim }h_{i}(X).$

Lorsqu'une matrice réelle de dimension $r\times r$ est évaluée en un polynôme non commutatif symétrique $f$ , et qu'on obtient une matrice semi-définie positive, $f$ est dite matrice-positif. Dans le cadre non commutatif, un polynôme non commutatif est somme de carrés si et seulement s'il est matrice-positif. De plus, il existe des algorithmes pour décomposer les polynômes matrice-positifs en une somme des carrés de polynômes non commutatifs.

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Polynomial SOS » (voir la liste des auteurs).

Voir également

• Dix-septième problème de Hilbert
• Sommes de carrés