Ableitungsfreie Optimierung

Um vorhandene Produkte oder Verfahren zu verbessern, muss man in deren Design die Variablen, die die Qualität des Produkts oder Verfahrens beeinflussen, optimal wählen. Zur Wahl dieser Entscheidungsvariablen gehört auch sicherzustellen, dass notwendige Einschränkungen erfüllt werden. Einige Variablen können z.B. alle Werte zwischen einem niedrigsten und einem höchsten Wert annehmen; andere Variablen nur wenige oder sogar nur zwei Werte (z.B. Ein und Aus). Oft muss die Summe einiger Werte unter oder über einem Schwellenwert liegen, usw. Bei vielen Anwendungen in Wissenschaft und Technik beruht die quantitative Bewertung ihrer Qualität auf teuren Messungen oder komplexen Simulationen. Da keine mathematische Formel dafür vorhanden ist, verhält sich die Suche nach der besten Entscheidung wie die Suche nach dem tiefsten Punkt in einem dunklen See, wo die einzigen Informationen, die gesammelt werden können, lokale Tiefenmessungen durch ein Boot auf der Oberfläche sind. Man kann diee Messungen nutzen, um die Form des Seebodens gut genug zu bestimmen, dass man das Boot in die Nähe der tiefsten Stelle führen kann. Gute Optimierungsmethoden halten die Anzahl der Messungen klein, die erforderlich sind, um die tiefsten Stelle zu erreichen. Analog dazu werden allgemeine Optimierungsprobleme gelöst. Statt des Tiefenmessers gibt eine aufwendige Blackbox, z.B. eine Mess- oder Simulationssoftware, nach Eingabe der Entscheidungsvariablen (der Position des Boots) einen Wert (die Tiefenmessung) zurück, der die Nähe zum Ziel beschreibt. Aus den bisherigen Outputs der Blackbox berechnet ein Blackbox-Solver neue Werte der Entscheidungsvariablen als Input für die Blackbox, und zwar so, dass man letztlich die optimale Entscheidung findet (Boot über der tiefsten Stelle). Unsere Gruppe verfügt über langfristige Erfahrung mit dem Design vonOptimierungsalgorithmen. Unsere neuesten Blackbox-Solver berücksichtigen den Stand der Forschung im wichtigsten Fall, wo die Entscheidungsvariablen keine Einschränkungen erfüllen müssen. In unserem Projekt wollen wir unsere Solver so erweitern, dass beliebige Einschränkungen berücksichtigt werden können. Wir streben eine robuste (selten versagende) und effiziente (mit wenigen Aufrufen der Blackbox auskommende) Software an, die mit einer grossen Zahl von Entscheidungsvariablen und mit aufwendig berechneten, oft ungenauen Werten für das Qualitätsmass zurechtkommt. Ein letzter, wichtiger Teil des Projekts ist die Abgleichung unserer zu entwickelnden Blackbox Software und der Vergleich mit schon vorhandenen Optimierungspaketen. Abgleichung ist der Prozess, die Parameter eines Solver-Designs (die die Details des Solver- Verhaltens festlegen) so zu wählen, dass seine Leistung optimiert wird. Dies ist selbst ein Blackbox Optimierungsproblem. Um die Abgleichung vorzunehmen, werden wir daher unseren Blackbox-Solver in Münchhausen-ähnlicher Weise auf sich selbst anwenden.

Dieses zweijährige Projekt resultierte in einer Software-Suite für die effiziente Lösung von Optimierungsproblemen, bei denen die Zielfunktion, die das zu optimierende Ziel quantifiziert, nur über eine Black Box zugänglich ist, die für jedes vorgegebene Szenario eine numerische Bewertung liefert. Optimierung ist die Grundlage dafür, in der Praxis vorhandene Produkte oder Verfahren zu verbessern, um in deren Design die Variablen, die die Qualität des Produkts oder Verfahrens beeinflussen, optimal wählen zu können. Zur Wahl dieser Entscheidungsvariablen gehört auch, sicherzustellen, dass notwendige Einschränkungen erfüllt werden. Bei vielen Anwendungen in Wissenschaft und Technik beruht die quantitative Bewertung ihrer Qualität auf teuren Messungen oder komplexen Simulationen. Da keine mathematische Formel dafür vorhanden ist, verhält sich die Suche nach der besten Entscheidung wie die Suche nach dem tiefsten Punkt in einem dunklen See, wo die einzigen Informationen, die gesammelt werden können, lokale Tiefenmessungen durch ein Boot auf der Oberfläche sind. Man muss die Messungen also nutzen, um die Form des Seebodens so gut zu bestimmen, dass man das Boot in die Nähe der tiefsten Stelle führen kann. Gute Optimierungsmethoden halten die Anzahl der Messungen klein, die erforderlich sind, um die tiefste Stelle zu erreichen. Analog dazu werden allgemeine Optimierungsprobleme gelöst. Statt des Tiefenmessers gibt eine aufwendige Blackbox, z.B. eine Mess- oder Simulationssoftware, nach Eingabe eines Szenarios mit den Entscheidungsvariablen (im Beispiel der Position des Boots) einen Wert (die Tiefenmessung) zurück, der die Qualität des Szenarios beschreibt. Aus den bisherigen Outputs der Blackbox berechnet ein Blackbox-Solver neue Werte der Entscheidungsvariablen als Input für die Blackbox, und zwar so, dass man letztlich die optimale Entscheidung findet (Boot über der tiefsten Stelle). Unsere Gruppe verfügt über langfristige Erfahrung mit dem Design solcher Optimierungsalgorithmen. Die neu entwickelte Software-Suite ermöglicht es, optimale Entscheidungen zu finden, die auch Einschränkungen berücksichtigen: Untere und obere Schranken für die Variablen, Ganzzahligkeitsbedingungen und lineare Gleichungen und Ungleichungen können vom Benutzer spezifiziert werden. Ebenso wird berücksichtigt, dass die Bewertung in der Praxis oft mit (unbekannten) Unsicherheiten behaftet ist. Unsere Algorithmen stechen im Vergleich mit andern State-of-the-Art Algorithmen besonders in hohen Dimensionen und bei grossen Unsicherheiten hervor. U.A. geschieht dies dadurch, dass wir unsere Suche auf die wiederholte Lösung von vielversprechenden, adaptiv konstruierten Hilfsproblemen mit wenigen Variablen zurückführen. Um unsere Algorithmen zu testen und mit den besten bekannten Algorithmen zu vergleichen, entwickelten wir eine Testumgebung für Optimierungsprobleme mit Einschränkungen. Unser Software-Release enthält diese Testumgebung und die neue Software-Suite. Die zugehörigen Publikationen zeigen die theoretische Effizienz und die praktische state-of-the-art Performance im Vergeleich mit anderer Optimierungssoftware. Wir implementierten auch eine vorläufige (noch nicht freigegebene) Umgebung für das automatische optimale Einstellen der Parameter, die das Verhalten eines Algorithmus beeinflussen.