Le problème mathématique classique se manifeste dans le monde réel

Il y a cent ans, le grand mathématicien David Hilbert a posé une question de recherche dans le domaine des mathématiques pures. Les récents développements de la théorie de l'optimisation font entrer le travail de Hilbert dans le monde des robots

Bien avant que les robots puissent fonctionner et que les voitures puissent se conduire, les mathématiciens ont considéré une simple question mathématique. Enfin, ils l'ont trié et mis de côté - ne pouvant pas savoir que l'objet de leur curiosité mathématique se manifesterait dans des machines d'un avenir lointain.

L'avenir est venu. À la suite des nouveaux travaux d' Amir Ali Ahmadi et d' Aniruda Majumara de l'Université de Princeton, le problème classique des mathématiques pures est prêt à fournir une preuve irréfutable que les drones et les robots motorisés ne tomberont pas dans les arbres ou ne rouleront pas dans la voie venant en sens inverse.

"Il y a une garantie complète et 100% démontrable que votre système" peut éviter les collisions, a déclaré Georgina Hall , une étudiante diplômée de Princeton qui a collaboré avec Ahmadi sur ce travail.

Amir Ali Ahmadi, professeur à Princeton

La garantie est prise dans un endroit inattendu - dans un problème mathématique connu sous le nom de " somme des carrés ". Il a été mis en 1900 par le grand mathématicien David Hilbert. Il a demandé si certaines équations pouvaient toujours être exprimées comme la somme de deux termes distincts, chacun étant au carré.

Les mathématiciens ont répondu à la question de Hilbert quelques décennies plus tard. Puis, près de 90 ans plus tard, les informaticiens et ingénieurs ont découvert que cette propriété mathématique - l'expressibilité d'une équation en termes de somme des carrés - aide à résoudre de nombreux problèmes réels qu'ils aimeraient résoudre.

"Beaucoup de mathématiques classiques du 19ème siècle sont utilisées dans ce que je fais, avec des mathématiques informatiques très modernes", a déclaré Ahmadi.

Cependant, dès que les chercheurs ont réalisé que la somme des carrés pouvait aider à répondre à de nombreux types de questions, ils ont rencontré des problèmes en appliquant cette approche. Le nouveau travail élimine l'un des plus grands problèmes de ce type, forçant la vieille question mathématique à résoudre certains des problèmes technologiques les plus importants de notre époque.

Garantie positive

Qu'est-ce que cela signifie qu'une certaine quantité est la somme des carrés? Prenez le nombre 13. Il s'agit de la somme de deux carrés - 2 ² et 3 ² . Le nombre 34 est la somme de 3 ² et 5 ² .

Au lieu de chiffres, la question de Hilbert - le 17e sur 23 problèmes qu'il a proposé à l'aube du 20e siècle - porte sur des polynômes tels que 5x ² + 16x + 13. De tels polynômes peuvent parfois également être représentés comme des sommes de carrés. Par exemple, 5x ² + 16x + 13 peuvent être réécrits comme (x + 2) ² + (2x + 3) ² .

Lorsqu'une expression est la somme des carrés, vous savez qu'elle est toujours positive (tous les nombres [réels] au carré donnent un nombre positif ou zéro, et la somme des nombres positifs est positive). Hilbert a voulu savoir si cela fonctionnait dans l'autre sens: tous les polynômes non négatifs peuvent-ils être exprimés comme la somme des carrés des fonctions rationnelles. En 1927, le mathématicien Emil Artin a prouvé que l'hypothèse de Hilbert était vraie.

Cette relation est très utile. Si l'on vous donne un polynôme complexe, avec des dizaines de variables élevées au plus haut degré, il est assez difficile de déterminer immédiatement s'il est toujours non négatif. «Certains polynômes ne sont évidemment pas négatifs, d'autres non. Il est difficile de les tester pour la non-négativité », a déclaré Ahmadi.

Mais dès que vous montrez que ce polynôme peut être exprimé en termes de somme de carrés, la non-négativité n'en sera que la conséquence. "La somme des carrés vous donne un beau certificat de positivité", a déclaré Pablo Parrilo , un informaticien et ingénieur au Massachusetts Institute of Technology qui a été impliqué dans le transfert de la question de la somme des carrés dans le monde des applications.

Savoir qu'un polynôme particulier est toujours non négatif peut sembler banal mathématique. Mais cent ans après que Hilbert ait posé sa question, la non-négativité des polynômes s'est avérée être la réponse aux problèmes appliqués qui nous affectent tous.

Meilleur moyen

La somme des carrés rencontre le monde réel dans le domaine de l'optimisation. La théorie de l'optimisation se préoccupe de trouver la meilleure façon de faire quelque chose tout en respectant les contraintes - par exemple, trouver la meilleure route pour se rendre au travail, compte tenu de l'état de la route et de l'arrêt nécessaire que vous devez faire en cours de route. De tels scénarios peuvent souvent être réduits à des polynômes. Dans de tels cas, il est possible de résoudre ou «d'optimiser» le scénario en trouvant la valeur minimale que prend le polynôme.

Trouver le minimum d'un polynôme avec de nombreuses variables est une tâche difficile. Il n'y a pas d'algorithme simple du manuel pour calculer la valeur minimale des polynômes complexes; de plus, ils sont difficiles à construire sur un graphique.

Salle Georgina

Comme la valeur minimale d'un polynôme est difficile à calculer directement, les chercheurs font des hypothèses sur cette valeur par d'autres méthodes. C'est là que la non-négativité entre en jeu, et la question de savoir si un polynôme est la somme des carrés. «Garantir la non-négativité est l'essence de tous les problèmes d'optimisation», a déclaré Reha Thomas, mathématicien à l'Université de Washington.

Une façon de trouver la valeur minimale est de poser la question: quelle valeur maximale peut-on soustraire d'un polynôme non négatif pour qu'il ne devienne pas négatif à un moment donné? Pour répondre à la question, il faut vérifier différentes valeurs - est-il possible de soustraire 3 pour qu'il ne devienne pas négatif? Et 4? Et 5? En répétant la procédure, à chaque étape, vous devez savoir si le polynôme reste non négatif. Ceci est vérifié par la possibilité de son expression comme la somme des carrés.

"La question qui doit être posée est" le polynôme est-il non négatif? "Le problème est qu'avec un grand nombre de variables, cette question est difficile à répondre, a expliqué Ahmadi. "Par conséquent, nous utilisons la somme des carrés en remplacement de la non-négativité."

Dès que les chercheurs prennent conscience du minimum - la valeur optimale du polynôme - ils peuvent utiliser d'autres méthodes pour déterminer les paramètres d'entrée qui conduisent à cette valeur. Cependant, pour que la non-négativité aide à résoudre les problèmes d'optimisation, vous devez trouver un moyen de calculer rapidement si un polynôme est exprimé en termes de somme des carrés. Et pour que les chercheurs puissent le faire, il a fallu 100 ans à partir du moment où Hilbert a posé la question.

Briser le problème

Le 17e problème de Hilbert est passé du monde des mathématiques pures au plan appliqué vers l'an 2000. C'est alors que plusieurs chercheurs ont trouvé un algorithme pour vérifier si un polynôme peut être représenté en termes de somme des carrés. Ils sont arrivés à ce point en résolvant le problème du carré grâce à une «programmation semi-définie », grâce à laquelle les ordinateurs sont capables de faire face à une telle tâche. Cela a permis aux chercheurs de domaines tels que l'informatique et l'ingénierie d'utiliser les possibilités de non-négativité pour orienter leurs recherches vers des moyens optimaux de résoudre les problèmes.

Aniruda Majumdar

Mais la programmation semi-définie a une grande limitation: elle travaille lentement sur de grandes tâches et est incapable de traiter certains des polynômes les plus complexes qui intéressent particulièrement les chercheurs. La programmation semi-définie peut être utilisée pour décomposer en la somme de carrés de tels polynômes qui ne consistent pas en plus d'une douzaine de variables élevées à une puissance ne dépassant pas 6. Les polynômes décrivant des problèmes d'ingénierie complexes - par exemple, garantissant que le robot restera debout - peut entrez 50 variables, voire plus que cela. Un programme peut mâcher un tel polynôme jusqu'à la fin des temps et ne pas encore donner la somme des carrés.

Dans un article publié en ligne en juin dernier, Ahmadi et Majumdar expliquent comment contourner le lent travail de la programmation semi-définie. Au lieu d'essayer de trouver la décomposition dans la somme des carrés avec un seul programme lent, ils montrent comment vous pouvez le faire avec une solution
des séquences de tâches plus simples, qui seront beaucoup plus rapides à calculer.

Les tâches de ce type sont appelées «linéaires» et ont été développées dans les années 40 pour résoudre les problèmes d'optimisation liés aux problèmes militaires. Les programmes en ligne sont désormais bien compris et résolus rapidement. Dans un nouvel article, Ahmadi et Majumdar montrent que l'on peut résoudre de nombreux programmes linéaires connectés (ou, dans certains cas, un type de problème différent, un programme de cône de second ordre), et combiner les résultats pour obtenir quelque chose de presque aussi bon que la réponse , ce qui pourrait donner un programme pour une programmation semi-définie. En conséquence, les ingénieurs disposent d'un nouvel outil pratique qu'ils peuvent utiliser pour vérifier la non-négativité et trouver rapidement la décomposition dans la somme des carrés.

«Nous avons étudié plusieurs problèmes de robotique et de théorie du contrôle, et avons montré que la qualité des solutions résultantes est utile pour une utilisation pratique et qu'elles sont beaucoup plus rapides à calculer», a déclaré Majumdar.

Preuve de sécurité

La vitesse de décision est tout si vous êtes dans un robot. Dans une telle situation, le polynôme peut agir comme une barrière mathématique érigée autour d'obstacles dans lesquels vous ne voulez pas vous écraser - s'il peut être calculé assez rapidement.

Imaginez un exemple simple: une voiture robotisée dans un parking géant. Il n'y a rien dans le parking sauf une cabine de sécurité au fond. Votre tâche consiste à programmer la machine afin qu'elle ne se bloque jamais dans cette cabine.

Dans ce cas, vous pouvez tirer la grille dans le parking. Faites ensuite un polynôme qui prend des points sur la grille en entrée. Assurez-vous que les valeurs du polynôme à l'emplacement de la machine sont négatives et que la valeur à l'emplacement de la cabine du gardien est positive.

Sur un certain nombre de points entre votre voiture et la cabine, le polynôme passera de moins à plus. Puisque votre voiture ne peut être localisée que là où le polynôme est négatif, ces points joueront le rôle d'un mur.

«Si vous partez d'un certain endroit, le robot ne franchira pas la ligne derrière laquelle se trouve l'obstacle. Cela vous donne des preuves formelles d'éviter les collisions », a déclaré Ahmadi.

Bien sûr, ce sera gênant si ce mur est au milieu du chemin entre la machine et la cabine. Il est nécessaire de construire un polynôme afin que le mur entoure l'obstacle aussi étroitement que possible. Cette option protégera la cabine et donnera à la voiture beaucoup d'espace pour se déplacer.

En pratique, il est nécessaire de minimiser la valeur - la distance entre le mur et la boîte - vous devez donc déplacer le graphique du polynôme et voir jusqu'où il peut être déplacé jusqu'à ce qu'il passe de moins à plus. Ceci est réalisé en vérifiant si le polynôme reste la somme des carrés.

Un parking presque vide est une chose. Mais dans des scénarios réalistes de contrôle d'une machine, ses capteurs détectent constamment de nouveaux obstacles en mouvement - voitures, vélos, enfants. Chaque fois qu'un nouvel obstacle apparaît ou qu'un obstacle connu se déplace, la machine doit construire de nouveaux polynômes complexes qui entourent ces obstacles. C'est beaucoup de contrôles sur la quantité de carrés qui doivent être exécutés à la volée.

Il y a sept ans, une autre paire de chercheurs imaginait déjà que de telles techniques pour travailler avec des polynômes pourraient être utilisées pour séparer les robots et les endroits où ils ne devraient pas tomber. Mais à cette époque, la puissance des ordinateurs faisait de cette idée un rêve.

La nouvelle approche d'Ahmadi et de Majumdar ouvre une nouvelle façon de mener une telle informatique instantanée. Donc, si et quand les robots motorisés peuvent se déplacer en toute sécurité dans le monde, nous pouvons remercier Google et Tesla - ainsi que Hilbert pour cela.