Mathematiker und Ingenieure beschäftigen sich oft mit der Suche nach dem Minimum einer bestimmten mathematischen Funktion. Dieses Minimum könnte den optimalen Kompromiss zwischen den beteiligten Kriterien repräsentieren, beispielsweise zwischen der Oberfläche, dem Gewicht und dem Windwiderstand einer Autokarosserie. In der Kontrolltheorie könnte ein Minimum einen stabilen Zustand eines elektromechanischen Systems darstellen, etwa ein Flugzeug im Flug oder einen zweibeinigen Roboter, der versucht, das Gleichgewicht zu halten. Hier wäre ein Ziel eines Kontrollalgorithmus, das System kontinuierlich zurück ins Minimum zu steuern.
Für komplexe Funktionen kann das Finden globaler Minima sehr schwierig sein. Aber es ist viel einfacher, wenn man vorher weiß, ob die Funktion konvex ist, was bedeutet, dass der Graph der Funktion überall zu dem hin Minimum abfällt. Konvexität ist so ein nützliches Werkzeug, dass 1992 im Rahmen einer Konferenz über Optimierung die sieben bedeutendsten ungelösten Probleme in diesem Bereich ausgewählt wurden und eines davon war die Frage, ob die Konvexität einer beliebigen polynomischen Funktion effizient bestimmt werden kann.
Fast 20 Jahre später haben Wissenschaftler am Laboratory for Information and Decision Systems des Massachusetts Institute of Technology (MIT) diese Frage endgültig beantwortet. Unglücklicherweise ist die Antwort Nein. Im May stellten sie ihre Abhandlung auf der Conference on Optimization der Society for Industrial and Applied Mathematics (SIAM) vor. Für eine beliebige polynomische Funktion ist die Bestimmung, ob sie konvex ist NP-schwer. (Anm. d. Red.: siehe auch http://en.wikipedia.org/wiki/NP-hard) In polynomische Funktionen besitzen die Variablen ganzzahlige Exponenten, zum Beispiel 13x4 + 7xy2 +yz.
Auf derselben Konferenz zeigten zwei der vier Autoren der Studie, MIT Professor für Ingenieurswesen und Computerwissenschaften Pablo Parrilo und sein Student Amir Ali Ahmadi, dass eine Eigenschaft, welche effizient bestimmt werden kann, in vielen Fällen ein praktikabler Ersatz für die Konvexität sein kann. Es handelt sich dabei um die Quadratsummen Konvexität. Mehr noch, sie lieferten einen Algorithmus um zu bestimmen, ob eine beliebige Funktion diese Eigenschaft besitzt.
In der ersten Abhandlung wurden Parrilo und Ahmadi von John N. Tsitsiklis, dem Clarence J. LeBel Professor for Electrical Engineering und Alex Olshevsky, einem früheren Studenten von Tsitsiklis und jetzt Postdoktorand an der Princeton University, unterstützt. Laut Etienne de Klerk, einem Professor am Department of Econometrics and Operations Research der Tilburg University in den Niederlanden sei das Ergebnis, dass die Bestimmung der Konvexität NP-schwer ist „nicht nur interessant, sondern recht überraschend.“
„Wenn man irgendein Buch über Optimierung aufschlägt, das wir zum Unterrichten von Studenten verwenden, beginnt es typischerweise mit den Worten ‚Gegeben sei die komplexe Optimierung'“, sagt de Klerk. „All die Funktionen sind konvexe Funkionen.“ Die Arbeit der MIT Wissenschaftler wird „uns dazu bringen, die Welt der Optimierung in einem etwas anderen Licht zu sehen“, ergänzt er.
Um einen Eindruck davon zu bekommen, warum Konvexität so nützlich ist, stelle man sich ein Flugzeug im Flug vor und setzt voraus, dass man eine Funktion hat, welche die Höhe des Flugzeugs und seine Geschwindigkeit mit seinem Treibstoffverbrauch in Zusammenhang bringt – ein Parameter, den man minimieren will. Wenn die Funktion konvex ist, sieht ihr dreidimensionaler Graph wie eine große Schüssel aus und am Boden liegt die Kombination aus Höhe und Geschwindigkeit, die den Treibstoffverbrauch minimiert. Alles was der Kontrollalgorithmus des Flugzeugs tun muss, ist eine neue Höhe und Geschwindigkeit zu finden, die am Gefälle der Schüssel liegen und er weiß, es geht in die richtige Richtung. Aber die Funktion ist nicht konvex, der Graph könnte wie ein Gebirge aussehen. Der minimale Wert könnte zwischen verschiedenen Gipfeln und Tälern liegen und ihn zu lokalisieren könnte zu viel Zeit beanspruchen, um die Berechnungen während des Fluges durchzuführen.
Natürlich sind die Arten der Funktionen, mit denen richtige Kontrollalgorithmen umgehen müssen, weitaus komplexer. Aber das stärkt nur den Vorteil der Konvexität: Es garantiert, dass man eine Entscheidung treffen kann, indem man ausschließlich limitierte lokale Informationen benutzt. „In der Kontrolltheorie gab es in den vergangenen Jahren vermehrt die Tendenz, Optimierungen online zu machen“, erklärt Parrilo. „Jetzt wo wir über so enorme Rechenkapazitäten verfügen, kann man Kontroller entwickeln, die viel kompliziertere Dinge tun. Sie lösen Optimierungsprobleme wie im Flug. „Aber“, sagt Parillo weiter, „wenn man das tun will, braucht man eine Art Garantie dafür, dass die Entscheidung, die man treffen wird optimal oder fast optimal ist und innerhalb einer bestimmten Zeitperiode abgeschlossen ist.“ Konvexität liefert diese Garantie.
Weil sich die Umstände bei der Arbeit mit einem elektromechanischen System ständig ändern, gilt das auch für die Funktionen die den optimalen Zustand des Systems beschreiben. Es wäre schön, wenn man vorher in der Lage wäre zu sagen, ob diese Funktionen konvex sind aber leider haben die MIT Wissenschaftler gezeigt, dass das nicht immer möglich ist.
Aber Parillo und Ahmadi bewiesen auch, dass Konvexität bei polynomischen Funktionen mit wenigen Variablen oder kleinen Exponenten das gleiche ist wie die Quadratsummen Konvexität, die leicht zu überprüfen ist. („Quadratsummen“ bedeutet, dass ein Polynom wie x2 – 2xy + y2 + z2 als Summe von Ausdrücken geschrieben werden kann, die quadriert wurden – in diesem Fall (x – y)2 + z2.)
Um zu beweisen, dass Quadratsummen Konvexität nicht immer das gleiche wie Komplexität ist, mussten Ahmadi und Parrilo einige bizarre Gegenbeispiele anführen, die in den meisten technischen Zusammenhängen wahrscheinlich keine Rolle spielen werden. „Wenn man wenige Variablen hat – sagen wir weniger als fünf oder sechs – dann ist es nicht einfach, Beispiele zu finden, für die es nicht gilt“, sagt Ahmadi. „Deshalb ist es sehr effektiv, zumindest für sinnvolle Probleme.“
Quelle: http://web.mit.edu/newsoffice/2011/convexity-0715.html
(THK)
Antworten