Polynôme somme de carrés
En mathématiques, un polynôme homogène à coefficients réels de degré , en les n variables est somme de carrés (en anglais SOS pour sum of squares) si et seulement s'il existe des polynômes homogènes de degré tels que
Exemple et propriétés
[modifier | modifier le code]Le polynôme homogène de degré 4 en deux variables s'écrit sous la forme
- .
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 ou pour , un polynôme homogène est somme de carrés si et seulement s'il est positif[1]. Il en est de même pour le problème analogique des polynômes homogènes symétriques positifs [2],[3].
Des conditions suffisantes pour qu'un polynôme homogène soit somme de carrés ont été données[4],[5]. De plus, un polynôme homogène réel positif peut être approchée arbitrairement près (pour la norme de son vecteur de coefficients) par une suite de polynômes homogènes qui sont sommes de carrés[6].
Représentation matricielle carrée (SMR)
[modifier | modifier le code]On peut voir le problème d'établir qu'un polynôme homogène est somme de carrés comme la résolution d'un problème d'optimisation convexe. En effet, peut s'écrire sous la forme
où est un vecteur contenant une base des polynômes homogènes de degré en (comme par exemple les monômes de degré degré en ), le symbole ′ désigne la transposée, où est la matrice symétrique vérifiant
et où est une paramétrisation linéaire de l'espace linéaire
La dimension du vecteur est égale à
et la dimension du vecteur est :
Avec ces notation, le polynôme est une somme de carrés si et seulement s'il existe un vecteur tel que
- ,
ce qui signifie que la matrice 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
a été introduite dans[7] 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[8].
Exemples
[modifier | modifier le code]- On considère le polynôme homogène de degré 4 en deux variables . On a
- Pour la valeur on a ; il s'ensuit que est somme de carrés.
- On considère le polynôme homogène de degré 4 en trois variables . On a
- Comme pour , il s'ensuit que est somme de carrés.
Somme de carrés de polynômes non commutatifs
[modifier | modifier le code]On considère l'algèbre libre engendrée par symboles non commutants , muni de l'involution ~, qui fixe et les et qui retourne les mots sur . 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 tel que
Lorsqu'une matrice réelle de dimension est évaluée en un polynôme non commutatif symétrique , et qu'on obtient une matrice semi-définie positive, 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[9]. 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[10].
Notes et références
[modifier | modifier le code]- (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).
- David Hilbert, « Ueber die Darstellung definiter Formen als Summe von Formenquadraten », Mathematische Annalen, vol. 32, no 3, , p. 342–350 (DOI 10.1007/bf01443605, lire en ligne).
- M. D. Choi et T. Y. Lam, « An old question of Hilbert », Queen's Papers in Pure and Applied Mathematics, vol. 46, , p. 385–405.
- Charu Goel, Salma Kuhlmann et Bruce Reznick, « On the Choi–Lam analogue of Hilbert's 1888 theorem for symmetric forms », Linear Algebra and Its Applications, vol. 496, , p. 114–120 (DOI 10.1016/j.laa.2016.01.024, arXiv 1505.08145).
- Jean B. Lasserre, « Sufficient conditions for a real polynomial to be a sum of squares », Archiv der Mathematik, vol. 89, no 5, , p. 390–398 (DOI 10.1007/s00013-007-2251-y, arXiv math/0612358, lire en ligne)
- Victoria Powers et Thorsten Wörmann, « An algorithm for sums of squares of real polynomials », Journal of Pure and Applied Algebra, vol. 127, no 1, , p. 99–104 (DOI 10.1016/S0022-4049(97)83827-3, lire en ligne
).
- Jean B. Lasserre, « A Sum of Squares Approximation of Nonnegative Polynomials », SIAM Review, vol. 49, no 4, , p. 651–669 (DOI 10.1137/070693709, arXiv math/0412398).
- G. Chesi, A. Tesi, A. Vicino et R. Genesio « On convexification of some minimum distance problems » () (lire en ligne)
— « (ibid.) », dans Proceedings of the 5th European Control Conference, Karlsruhe, Germany, IEEE, p. 1446–1451. - M. Choi, T. Lam et B. Reznick « Sums of squares of real polynomials » () (lire en ligne)
— « (ibid.) », dans Proceedings of Symposia in Pure Mathematics, p. 103–125. - J. William Helton, « "Positive" Noncommutative Polynomials Are Sums of Squares », The Annals of Mathematics, vol. 156, no 2, , p. 675–694 (DOI 10.2307/3597203, JSTOR 3597203)
- Sabine Burgdorf, Kristijan Cafuta, Igor Klep et Janez Povh, « Algorithmic aspects of sums of Hermitian squares of noncommutative polynomials », Computational Optimization and Applications, vol. 55, no 1, , p. 137–153 (DOI 10.1007/s10589-012-9513-8)