Das klassische mathematische Problem manifestiert sich in der realen Welt

Vor hundert Jahren stellte der große Mathematiker David Hilbert eine Forschungsfrage aus dem Bereich der reinen Mathematik. Jüngste Entwicklungen in der Optimierungstheorie bringen Hilberts Arbeit in die Welt der Robomobile

Lange bevor Roboter rennen und Autos selbst fahren konnten, betrachteten Mathematiker eine einfache mathematische Frage. Schließlich sortierten sie es aus und legten es beiseite - ohne zu wissen, dass sich das Objekt ihrer mathematischen Neugier in Maschinen der fernen Zukunft manifestieren würde.

Die Zukunft ist gekommen. Als Ergebnis der neuen Arbeit von Amir Ali Ahmadi und Aniruda Majumara von der Princeton University ist das klassische Problem der reinen Mathematik bereit, eisernen Beweis dafür zu liefern, dass automatische Drohnen und Robomobile nicht gegen Bäume stoßen oder auf die Gegenfahrbahn rollen.

"Es gibt eine 100% ige nachweisbare Garantie dafür, dass Ihr System Kollisionen vermeiden kann", sagte Georgina Hall , eine Doktorandin aus Princeton, die bei dieser Arbeit mit Ahmadi zusammengearbeitet hat.

Amir Ali Ahmadi, Professor aus Princeton

Die Garantie wird an einem unerwarteten Ort übernommen - bei einem mathematischen Problem, das als " Summe der Quadrate " bekannt ist. Es wurde 1900 von dem großen Mathematiker David Hilbert gestellt. Er fragte, ob bestimmte Gleichungen immer als die Summe zweier getrennter Terme ausgedrückt werden können, von denen jeder quadratisch ist.

Einige Jahrzehnte später beantworteten Mathematiker Hilberts Frage. Dann, fast 90 Jahre später, entdeckten Informatiker und Ingenieure, dass diese mathematische Eigenschaft - die Ausdruckbarkeit einer Gleichung in Form der Quadratsumme - zur Lösung vieler realer Probleme beiträgt, die sie lösen möchten.

"In meiner Arbeit wird viel klassische Mathematik des 19. Jahrhunderts verwendet, zusammen mit sehr moderner Computermathematik", sagte Ahmadi.

Sobald die Forscher jedoch erkannten, dass die Summe der Quadrate bei der Beantwortung vieler Arten von Fragen hilfreich sein könnte, stießen sie bei der Anwendung dieses Ansatzes auf Probleme. Die neue Arbeit beseitigt eines der größten derartigen Probleme und zwingt die alte mathematische Frage, einige der wichtigsten technologischen Probleme unserer Zeit zu lösen.

Positiv garantiert

Was bedeutet es, dass eine bestimmte Menge die Summe der Quadrate ist? Nehmen Sie die Zahl 13. Dies ist die Summe zweier Quadrate - 2 ² und 3 ² . Die Zahl 34 ist die Summe von 3 ² und 5 ² .

Anstelle von Zahlen befasst sich Hilberts Frage - das 17. von 23 Problemen , die er zu Beginn des 20. Jahrhunderts vorschlug - mit Polynomen wie 5x ² + 16x + 13. Solche Polynome können manchmal auch als Quadratsummen dargestellt werden. Zum Beispiel kann 5x ² + 16x + 13 als (x + 2) ² + (2x + 3) ² umgeschrieben werden.

Wenn ein Ausdruck die Summe der Quadrate ist, wissen Sie, dass er immer positiv ist (alle [reellen] quadratischen Zahlen ergeben eine positive Zahl oder Null, und die Summe der positiven Zahlen ist positiv). Hilbert wollte wissen, ob dies anders funktioniert: Können alle nicht negativen Polynome als Summe der Quadrate rationaler Funktionen ausgedrückt werden? Der Mathematiker Emil Artin bewies 1927, dass Hilberts Hypothese wahr war.

Diese Beziehung ist sehr nützlich. Wenn Sie ein komplexes Polynom erhalten, bei dem Dutzende von Variablen in höchstem Maße angehoben sind, ist es ziemlich schwierig, sofort festzustellen, ob es immer nicht negativ ist. „Einige Polynome sind offensichtlich nicht negativ, andere nicht. Es ist schwer, sie auf Nicht-Negativität zu testen “, sagte Ahmadi.

Sobald Sie jedoch zeigen, dass dieses Polynom als Quadratsumme ausgedrückt werden kann, ist die Nicht-Negativität einfach eine Folge davon. "Die Summe der Quadrate gibt Ihnen ein schönes Zertifikat für Positivität", sagte Pablo Parrilo , ein IT-Spezialist und Ingenieur am Massachusetts Institute of Technology, der daran beteiligt war, das Problem der Summe der Quadrate in die Anwendungswelt zu bringen.

Zu wissen, dass ein bestimmtes Polynom immer nicht negativ ist, mag wie mathematische Trivialität erscheinen. Aber hundert Jahre nachdem Hilbert seine Frage gestellt hatte, stellte sich heraus, dass die Nicht-Negativität der Polynome die Antwort auf die angewandten Probleme war, die uns alle betreffen.

Bester Weg

Die Summe der Quadrate trifft im Bereich der Optimierung auf die reale Welt. Die Optimierungstheorie befasst sich damit, den besten Weg zu finden, um etwas zu tun, während man sich innerhalb der Einschränkungen befindet - zum Beispiel den besten Weg zu finden, um zur Arbeit zu gelangen, angesichts des Straßenzustands und des notwendigen Stopps, den Sie auf dem Weg machen müssen. Solche Szenarien können oft auf Polynome reduziert werden. In solchen Fällen ist es möglich, das Szenario zu lösen oder zu „optimieren“, indem der Mindestwert ermittelt wird, den das Polynom annimmt.

Das Minimum eines Polynoms mit vielen Variablen zu finden, ist eine schwierige Aufgabe. Es gibt keinen einfachen Algorithmus aus dem Lehrbuch zur Berechnung des Minimalwerts komplexer Polynome, außerdem sind sie in einem Graphen schwer zu konstruieren.

Georgina Hall

Da es schwierig ist, den Mindestwert eines Polynoms direkt zu berechnen, treffen die Forscher mit anderen Methoden Annahmen über diesen Wert. Hier kommt die Nicht-Negativität ins Spiel und die Frage, ob ein Polynom die Summe der Quadrate ist. "Die Sicherstellung der Nicht-Negativität ist die Essenz aller Optimierungsprobleme", sagte Reha Thomas, Mathematikerin an der University of Washington.

Eine Möglichkeit, den Minimalwert zu finden, besteht darin, die Frage zu stellen: Welcher Maximalwert kann von einem nicht negativen Polynom subtrahiert werden, damit er irgendwann nicht negativ wird? Um die Frage zu beantworten, müssen verschiedene Werte überprüft werden. Ist es möglich, 3 zu subtrahieren, damit es nicht negativ wird? Und 4? Und 5? Wenn Sie den Vorgang wiederholen, müssen Sie bei jedem Schritt wissen, ob das Polynom nicht negativ bleibt. Dies wird durch die Möglichkeit seines Ausdrucks als Summe der Quadrate verifiziert.

"Die Frage, die gestellt werden muss, lautet:" Ist das Polynom nicht negativ? "Das Problem ist, dass diese Frage bei einer großen Anzahl von Variablen schwer zu beantworten ist, sagte Ahmadi. "Deshalb verwenden wir die Summe der Quadrate als Ersatz für Nicht-Negativität."

Sobald sich die Forscher des Minimums - des optimalen Werts des Polynoms - bewusst werden, können sie mit anderen Methoden die Eingabeparameter bestimmen, die zu diesem Wert führen. Damit Nicht-Negativität zur Lösung von Optimierungsproblemen beiträgt, müssen Sie jedoch eine Möglichkeit finden, schnell zu berechnen, ob ein Polynom als Quadratsumme ausgedrückt wird. Und damit die Forscher dazu in der Lage waren, dauerte es 100 Jahre, bis Hilbert die Frage stellte.

Das Problem lösen

Hilberts 17. Problem verlagerte sich um das Jahr 2000 von der Welt der reinen Mathematik auf die angewandte Ebene. Zu diesem Zeitpunkt entwickelten mehrere Forscher einen Algorithmus, mit dem überprüft werden konnte, ob ein Polynom in Form der Quadratsumme dargestellt werden kann. Sie kamen an diesen Punkt, indem sie das quadratische Problem durch „ semi-definierte Programmierung “ lösten, dank derer Computer eine solche Aufgabe bewältigen können. Dies ermöglichte es Forschern aus Bereichen wie Informatik und Ingenieurwesen, die Möglichkeiten der Nicht-Negativität zu nutzen, um ihre Suche auf optimale Wege zur Problemlösung auszurichten.

Aniruda Majumdar

Die semi-definierte Programmierung hat jedoch eine große Einschränkung: Sie arbeitet langsam bei großen Aufgaben und kann einige der komplexesten Polynome, an denen Forscher besonders interessiert sind, nicht verarbeiten. Semi-definierte Programmierung kann verwendet werden, um solche Polynome, die aus nicht mehr als einem Dutzend Variablen bestehen, die auf eine Potenz von nicht mehr als 6 angehoben werden, in die Summe der Quadrate zu zerlegen. Polynome, die komplexe technische Probleme beschreiben - zum Beispiel um sicherzustellen, dass der Roboter auf den Beinen bleibt - können Geben Sie 50 Variablen oder sogar mehr ein. Ein Programm kann ein solches Polynom bis zum Ende der Zeit kauen und trotzdem nicht die Summe der Quadrate ausgeben.

In einem im letzten Juni online veröffentlichten Artikel erklären Ahmadi und Majumdar, wie man die langsame Arbeit der semi-definierten Programmierung umgeht. Anstatt zu versuchen, die Zerlegung in der Summe der Quadrate mit einem einzigen langsamen Programm zu finden, zeigen sie, wie Sie dies mit einer Lösung tun können
Sequenzen einfacherer Aufgaben, die viel schneller zu berechnen sind.

Aufgaben dieser Art werden als "linear" bezeichnet und wurden in den 1940er Jahren entwickelt, um Optimierungsprobleme im Zusammenhang mit militärischen Problemen zu lösen. Linienprogramme sind jetzt gut verstanden und schnell gelöst. In einem neuen Artikel zeigen Ahmadi und Majumdar, dass man viele verbundene lineare Programme (oder in einigen Fällen eine andere Art von Problem, ein Kegelprogramm zweiter Ordnung) lösen und die Ergebnisse kombinieren kann, um etwas zu erhalten, das fast so gut ist wie die Antwort , die ein Programm für die semi-definierte Programmierung geben könnte. Als Ergebnis haben Ingenieure ein neues, praktisches Werkzeug, mit dem sie auf Nicht-Negativität prüfen und die Zerlegung in der Summe der Quadrate schnell finden können.

"Wir haben verschiedene Probleme der Robotik und der Steuerungstheorie untersucht und gezeigt, dass die Qualität der resultierenden Lösungen für den praktischen Gebrauch nützlich ist und dass sie viel schneller zu berechnen sind", sagte Majumdar.

Sicherheitsnachweis

Die Geschwindigkeit der Entscheidung ist alles, wenn Sie in einem Robomobil sitzen. In einer solchen Situation kann das Polynom als mathematische Barriere um Hindernisse fungieren, gegen die Sie nicht stoßen möchten - wenn es schnell genug berechnet werden kann.

Stellen Sie sich ein einfaches Beispiel vor: ein Roboterauto auf einem riesigen Parkplatz. Auf dem Parkplatz gibt es nichts außer einer Sicherheitskabine am anderen Ende. Ihre Aufgabe ist es, die Maschine so zu programmieren, dass sie niemals in diese Kabine stürzt.

In diesem Fall können Sie das Gitter auf den Parkplatz ziehen. Erstellen Sie dann ein Polynom, das Punkte auf dem Gitter als Eingabe verwendet. Stellen Sie sicher, dass die Werte des Polynoms am Ort der Maschine negativ und der Wert am Ort der Wachkabine positiv sind.

An einigen Punkten zwischen Ihrem Auto und der Kabine wechselt das Polynom von minus nach plus. Da sich Ihr Auto nur dort befinden kann, wo das Polynom negativ ist, spielen diese Punkte die Rolle einer Wand.

„Wenn Sie an einem bestimmten Ort starten, überschreitet der Roboter nicht die Linie, hinter der sich das Hindernis befindet. Dies gibt Ihnen formelle Beweise für die Vermeidung von Kollisionen “, sagte Ahmadi.

Natürlich ist es unpraktisch, wenn sich diese Wand in der Mitte des Weges zwischen Maschine und Kabine befindet. Es ist notwendig, ein Polynom zu bauen, damit die Wand das Hindernis so eng wie möglich umgibt. Diese Option schützt die Kabine und gibt dem Auto viel Bewegungsfreiheit.

In der Praxis ist es notwendig, den Wert - den Abstand zwischen der Wand und der Box - zu minimieren, damit Sie den Graphen des Polynoms verschieben und sehen können, wie weit es verschoben werden kann, bis es von minus nach plus geht. Dies wird erreicht, indem geprüft wird, ob das Polynom die Summe der Quadrate bleibt.

Fast leere Parkplätze sind eine Sache. In realistischen Szenarien der Steuerung einer Maschine erkennen ihre Sensoren jedoch ständig neue Hindernisse - Autos, Fahrräder, Kinder. Jedes Mal, wenn ein neues Hindernis auftritt oder sich ein bekanntes bewegt, muss die Maschine neue komplexe Polynome erstellen, die diese Hindernisse einschließen. Dies ist eine Menge Überprüfungen der Anzahl der Quadrate, die im laufenden Betrieb ausgeführt werden müssen.

Vor sieben Jahren stellte sich bereits ein anderes Forscherpaar vor, dass solche Techniken zur Arbeit mit Polynomen verwendet werden könnten, um Robomobile von Orten zu trennen, an denen sie nicht fallen sollten. Aber zu dieser Zeit machte die Macht der Computer diese Idee zu einem Traum.

Der neue Ansatz von Ahmadi und Majumdar eröffnet eine neue Möglichkeit, ein solches Sofort-Computing durchzuführen. Wenn sich Robomobile sicher auf der ganzen Welt bewegen können, können wir uns bei Google und Tesla sowie bei Hilbert dafür bedanken.