⚡ electrical engineering

Disjunctive Sum of Squares

Cet article introduit le concept de somme disjonctive de carrés, une méthode pour certifier la non-négativité des polynômes au moyen de multiples identités algébriques parallèles permettant la construction de hiérarchies d'optimisation convergentes avec des contraintes de type semi-défini de taille fixe et des alternatives sans optimisation, tout en démontrant des applications pratiques dans les domaines de l'optimisation polynomiale, copositive et combinatoire.

Auteurs originaux : Amir Ali Ahmadi, Sanjeeb Dash, Yixuan Hua, Bartolomeo Stellato

Publié 2026-05-28

📖 4 min de lecture☕ Lecture pause café

CC BY 4.0

Auteurs originaux : Amir Ali Ahmadi, Sanjeeb Dash, Yixuan Hua, Bartolomeo Stellato

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous soyez un détective tentant de prouver qu'une machine mystérieuse et complexe (un polynôme mathématique) ne produit jamais de nombre négatif. Dans le monde des mathématiques, cela s'appelle prouver la « non-négativité ».

Pendant des décennies, la méthode standard pour résoudre ce mystère consistait à trouver une seule et unique équation algébrique parfaite qui agit comme une clé magique. Si vous pouviez écrire la sortie de la machine comme une somme de carrés (comme $A^2 + B^2 + C^2$ ), vous saviez avec certitude qu'elle ne pouvait jamais être négative, car les carrés sont toujours positifs.

Cependant, cette approche de la « clé unique » présente un défaut majeur : parfois, pour faire fonctionner cette unique équation, vous devez utiliser des nombres incroyablement complexes et de haut degré. C'est comme essayer d'ouvrir une porte simple avec une clé squelette géante de 15 mètres de long. Cela fonctionne, mais c'est lourd, coûteux à fabriquer et computationnellement impossible à utiliser dans de nombreux scénarios réels.

La Nouvelle Idée : Une Équipe de Petites Clés

Ce papier introduit une nouvelle stratégie appelée Somme Disjonctive de Carrés. Au lieu de chercher une unique clé géante et complexe, les auteurs proposent d'utiliser une équipe de clés plus petites et plus simples.

Voici le concept de base :

Diviser le Monde : Imaginez l'univers des entrées possibles comme une grande pièce. Au lieu d'essayer de prouver que la machine est sûre pour toute la pièce d'un coup, nous divisons la pièce en zones plus petites et gérables (comme couper une pizza en parts).
Preuve Locale : Dans chaque zone, nous devons seulement prouver que la machine est sûre en utilisant une équation simple et de bas degré.
La Logique « OU » : Nous n'avons pas besoin d'une équation pour tout couvrir. Nous devons simplement prouver : « Si vous êtes dans la Zone A, la machine est sûre OU si vous êtes dans la Zone B, la machine est sûre OU si vous êtes dans la Zone C... » Tant que chaque point possible de la pièce tombe dans au moins une de ces zones sûres, toute la machine est prouvée sûre.

Pourquoi est-ce un changement de donne ?

Simplicité : Les « clés » (identités algébriques) utilisées dans chaque zone sont beaucoup plus simples et plus petites que la clé géante requise par l'ancienne méthode.
Traitement Parallèle : Parce que chaque zone est indépendante, vous pouvez les vérifier toutes en même temps. C'est comme avoir une équipe de détectives vérifiant différentes pièces simultanément, plutôt qu'un seul détective essayant de vérifier tout le bâtiment seul.
Efficacité : Les auteurs prouvent mathématiquement que vous pouvez toujours trouver ces preuves simples et de bas degré, quelle que soit la complexité de la machine. Vous n'avez pas besoin de rendre les équations plus compliquées ; vous devez simplement ajouter plus de zones.

Applications Réelles Mentionnées dans le Papier

Les auteurs ont testé cette approche de « l'équipe de clés » sur plusieurs problèmes difficiles :

L'Énigme « Motzkin » : Ils ont utilisé cette méthode pour prouver la sûreté d'une célèbre énigme mathématique (le polynôme de Motzkin) avec laquelle l'ancienne méthode peinait. Ils ont trouvé des preuves utilisant des équations simples que l'ancienne méthode ne pouvait pas trouver sans devenir impossibly complexe.
Coposivité des Matrices : Il s'agit d'un type spécifique de problème impliquant des grilles de nombres (matrices). Les auteurs ont montré comment décomposer le problème en formes géométriques plus petites (triangles et cônes) pour prouver que ces matrices sont sûres, ce qui est utile en optimisation et en économie.
Trouver la « Clique » : En théorie des graphes (réseaux de points et de lignes), une « clique » est un groupe de points où chacun est connecté à tous les autres. Trouver la plus grande clique est un problème notoirement difficile. Les auteurs ont utilisé leur méthode pour résoudre ce problème en le décomposant en plus petites pièces, trouvant avec succès la taille exacte du plus grand groupe dans plusieurs réseaux aléatoires.

Le Fond du Problème

Le papier soutient que nous n'avons pas besoin de forcer une solution unique, massive et compliquée pour prouver une vérité mathématique. Au lieu de cela, en divisant le problème en plus petites pièces qui se chevauchent et en résolvant chaque pièce avec un outil simple, nous pouvons prouver que l'ensemble est vrai beaucoup plus rapidement et plus efficacement. C'est la différence entre essayer de soulever un rocher avec un seul levier géant et utiliser une équipe de personnes avec de petits leviers simples travaillant ensemble.

Résumé Technique : Somme Disjonctive de Carrés

Énoncé du Problème

L'article aborde le problème fondamental de la certification de la non-négativité des polynômes. Bien qu'un polynôme $p$ soit non-négatif si $p(x) \geq 0$ pour tout $x \in \mathbb{R}^n$ , la détermination de cette propriété est généralement NP-difficile. L'approche standard, la méthode de la Somme de Carrés (SOS), certifie la non-négativité en exprimant $p$ comme une seule identité algébrique $p(x) = \sum q_i^2(x)$ . Cependant, tous les polynômes non-négatifs ne sont pas SOS (un fait établi par Hilbert), et prouver la non-négativité pour ceux qui ne le sont pas nécessite généralement de multiplier $p$ par un polynôme SOS de haut degré (par exemple, via la solution d'Artin au 17e problème de Hilbert). Cela se traduit par des identités algébriques dont les degrés sont nettement supérieurs à celui du polynôme original, conduisant à des Programmes Semidéfinis (SDP) dont la taille croît de manière exponentielle et deviennent computationnellement ingérables.

La question centrale motivant cette recherche est : La complexité d'une preuve de non-négativité polynomiale basée sur SOS peut-elle être réduite en construisant plusieurs identités algébriques au lieu d'une seule ?

Méthodologie

Les auteurs introduisent le concept de Somme Disjonctive de Carrés (Disjunctive SOS). Au lieu d'une identité globale unique, la non-négativité est certifiée par une collection d'identités algébriques, chacune valable sur une sous-région spécifique du domaine. Ces sous-régions forment une partition (ou un recouvrement) de l'espace, définie par une disjonction algébrique.

Définitions Fondamentales

Disjonction Algébrique : Une collection de polynômes $\mathcal{D} = \{\{q_{k,j}\}\}$ telle que l'union des régions $\Omega_k = \{x \mid q_{k,j}(x) \geq 0, \forall j\}$ recouvre $\mathbb{R}^n$ .
Preuve Disjonctive SOS : Un polynôme $p$ est une somme disjonctive de carrés par rapport à $\mathcal{D}$ si, pour chaque région $\Omega_k$ , il existe des polynômes SOS $s_{k,j}$ tels que :
$p(x) = s_{k,0}(x) + \sum_{j=1}^{n_k} s_{k,j}(x)q_{k,j}(x) \quad \text{pour tout } x \in \Omega_k.$
Crucialement, le degré des polynômes SOS $s_{k,j}$ peut être maintenu bas (spécifiquement, borné par le degré de $p$ ), contrairement aux preuves SOS globales où le degré doit souvent augmenter.

Cadre Théorique

L'article établit deux résultats théoriques principaux, qualifiés de Positivstellensatz Disjonctifs :

Positivstellensatz Disjonctif basé sur les SDP (Théorème 1) :
Pour toute forme définie positive $p$ de degré $d$ , il existe une famille explicite de disjonctions algébriques (construites via des calottes sphériques) telle que $p$ admette une preuve disjonctive SOS où le degré des multiplicateurs SOS est au plus $d$ . Cela permet une hiérarchie convergente de bornes inférieures pour la minimisation polynomiale sur la sphère unité, utilisant des SDP de taille fixe (indépendante du niveau de la hiérarchie).
Positivstellensatz Disjonctif sans Optimisation (Théorème 8) :
Un résultat plus fort montrant que pour toute forme définie positive, il existe une famille de disjonctions simpliciales (cônes polyédraux) telle que $p$ puisse être certifié non-négatif simplement en vérifiant que ses coefficients sont non-négatifs après un changement de coordonnées linéaire à l'intérieur de chaque cône. Cette approche ne nécessite aucun solveur d'optimisation (seulement de la programmation linéaire ou des vérifications directes de coefficients) mais peut nécessiter un plus grand nombre de régions par rapport à l'approche SDP.

Cadre Algorithmique

Les auteurs proposent un cadre de Recherche Spatiale par Séparation et Évaluation (Spatial Branch-and-Bound - SBB) pour rechercher adaptivement ces preuves disjonctives. Plutôt que de partitionner uniformément l'espace (comme dans les preuves théoriques), l'algorithme :

Maintient un arbre de sous-régions (cônes simpliciaux).
Calcule des bornes inférieures via des SDP (ou des vérifications linéaires) sur chaque sous-région.
Calcule des bornes supérieures via la descente de gradient projetée.
Effectue une séparation en bisectant l'arête la plus longue de la sous-région ayant la plus petite borne inférieure.
Cette approche adaptative vise à trouver des certificats avec moins de sous-régions que les constructions uniformes.

Contributions et Résultats Clés

1. Garanties Théoriques

Degré Fixe : L'article prouve que des preuves disjonctives SOS de bas degré existent toujours. Le degré des polynômes SOS dans la preuve n'a pas besoin de croître avec le niveau de la hiérarchie ; il peut être fixé au degré du polynôme original.
Convergence : Les auteurs construisent une hiérarchie de SDP avec des contraintes de taille fixe qui converge vers le minimum global d'un polynôme homogène sur la sphère unité. Ils établissent un taux de convergence de $O(1/m)$ , où $m$ est lié à la résolution de la partition spatiale.
Certificats sans Optimisation : Le second Positivstellensatz fournit une méthode pour certifier la non-négativité sans résoudre de SDP, reposant plutôt sur des transformations linéaires et des vérifications de non-négativité des coefficients.

2. Application à l'Optimisation Contrainte

Optimisation Polynomiale : En combinant l'approche disjonctive avec une technique de réduction issue de [2], les auteurs construisent une hiérarchie convergente de bornes inférieures pour les problèmes d'optimisation polynomiale générale (POPs) sur des ensembles semi-algébriques compacts de base.
Programmation Copositive : La méthode est spécialisée pour certifier la copositive des matrices (vérifiant $x^T Q x \geq 0$ pour $x \geq 0$ ). Les auteurs définissent une condition « Disjonctive P+N » où une matrice est certifiée copositive si, sur chaque sous-région simpliciale du quadrant non-négatif, elle peut être décomposée en une matrice semi-définie positive et une matrice non-négative. Cela produit une hiérarchie complète où la taille de la contrainte SDP reste fixe ( $n \times n$ ), contrairement aux hiérarchies existantes où la taille des contraintes croît polynomialement avec le niveau.

3. Expériences Numériques

Les auteurs présentent des expériences numériques sur :

Polynômes non-SOS : Les algorithmes ont certifié avec succès la non-négativité de polynômes classiques non-SOS (par exemple, Motzkin, Robinson, Choi-Lam, Delzell) en utilisant un petit nombre de sous-régions (souvent moins de 20) via le cadre SBB.
Programmes Copositifs : L'algorithme a résolu des programmes quadratiques non convexes et calculé le nombre de cliques de graphes (via le théorème de Motzkin-Straus) sur des instances aléatoires.
Performance : Les résultats indiquent que l'approche disjonctive peut certifier la non-négativité et résoudre des problèmes d'optimisation avec nettement moins de sous-régions que le partitionnement uniforme, et que les contraintes SDP restent de taille gérable.

Importance et Revendications

L'article revendique que l'approche de la somme disjonctive de carrés offre une alternative viable aux hiérarchies SOS traditionnelles en découplant la complexité de la preuve (le degré des polynômes SOS) du nombre d'identités algébriques utilisées.

Efficacité Computationnelle : En maintenant le degré des polynômes SOS bas et fixe, la taille des SDP sous-jacents reste constante tout au long de la hiérarchie, évitant ainsi le « fléau de la dimensionnalité » associé à l'augmentation des degrés polynomiaux dans les méthodes SOS standard.
Flexibilité : Le cadre prend en charge à la fois les recherches basées sur les SDP (pour des bornes plus serrées avec moins de régions) et les recherches sans optimisation (pour des certificats plus rapides, bien que potentiellement plus grossiers).
Complétude : Les auteurs prouvent que cette approche est complète ; pour tout polynôme strictement positif (ou toute matrice strictement copositive), un certificat existe dans leur cadre.

L'article conclut en notant que, bien que les constructions théoriques utilisent des partitions uniformes, l'algorithme SBB pratique affine l'espace de manière adaptative, suggérant que des disjonctions spécifiques à l'instance pourraient réduire davantage le nombre de régions requises. Ce travail ouvre des pistes pour combiner la somme disjonctive de carrés avec l'exploitation de la parcimonie et de la symétrie, et pour explorer le côté dual des moments du cadre.