Eine Softwareumgebung für globale Optimierung

Das beantragte Projekt zielt darauf ab, das Gebiet der globalen Optimierung sowohl in theoretischer als auch in praktischer Hinsicht durch die Integration von Zugängen verschiedener mathematischer Disziplinen zu bereichern. Das frei erhältliche Softwarepaket zur globalen Optimierung, das COCONUT Environment, das während des EU- Projektes COCONUT entwickelt wurde und nun an der Universität Wien gewartet wird, soll durch neuentwickelte und verbesserte Strategien erweitert werden, was die Anwendung an viele verschiedene im wirklichen Leben vorkommender Probleme ermöglicht. Darüber hinaus ist geplant, die Steigerung der Geschwindigkeit und Effizienz des COCONUT Environment zu erhöhen, durch Implementierung einer automatischer Strategie-Auswahl. Globale Optimierung ist die Aufgabe, die absolut beste Möglichkeit(en) zu finden, ein Ziel unter gegebenen Nebenbedingungen zu erreichen, unter der Annahme, dass alles in mathematischen Ausdrücken modelliert ist. Ein Spezialfall davon ist das Zulässigkeits Problem, das darauf abzielt, eine oder alle Lösungen zu finden, die einem vorgegebenen Satz von Nebenbedingungen entsprechen. Beide Probleme sind viel schwieriger als konvexe Optimierung, die Auffindung lokaler Minima nichtlinearer Optimierungsprobleme oder die Lösung eines algebraischen Gleichungssystems, wenn gute Startpunkte bekannt sind. Viele wissenschaftliche und industrielle Anwendungen (z.B. Form-Optimierung in der Strukturmechanik, Design und Analyse von Robotern, Analyse von Phasengleichgewichten, Proteinfaltung, Logistik) führen zu schwierigen globalen Optimierungsproblemen in Dimensionen von weniger als zehn bis zu mehreren tausend Variablen. Im letzten Jahrzehnt hat sich das Interesse an globaler Optimierung substantiell gesteigert, zum Teil, weil immer mehr Anwendungen entstanden sind, aber auch, weil die algorithmische Entwicklung den Punkt erreicht hat, ab dem viele kleinere Probleme, die aber bereits Industrie-relevante Größenordnungen erreicht haben, zuverlässig gelöst werden können. Um den Herausforderungen realer Anwendungen zu begegnen, ist es oft nötig, neue theoretische Methoden zu erforschen und sie einzusetzen, die die speziellen Eigenschaften der Anwendung besonders ausnützen. Wie in vielen Bereichen, die sich mit schwierigen Rechner-intensieven-Problemen beschäftigen, kommt der Erfolg viel häufiger über theoretische Fortschritte als durch die Erhöhung der reinen Rechenstärke im Hardware-Bereich oder durch geschikte Nutzung bereits vorhandener Software-Pakete. Es gibt eine Reihe unterschiedlicher Zugänge zur Lösung globaler Optimierungsprobleme. Diese traditionellen Herangehensweisen wachsen langsam zueinander in Richtung eines Ganzen, was wiederum die Lösung globaler Optimierungsprobleme in Dimensionen realisierbar macht, die für die Lösung realer Probleme relevant sind. Leider wird dieser Prozess behindert durch die Tatsache, dass die verschiedenen Zugänge substantiell verschieden sind und ihre Stärken aus unterschiedlichen mathematischen Traditionen ziehen welche nur geringe Gemeinsamkeiten aufweisen: numerische Mathematik, konvexe Analysis, Optimierung, Kombinatorik, Logik und algebraische Geometrie. Daher sind auch Synergieeffekte zu erzielen, hauptsächlich aufgrund der Einarbeitungszeit, die benötigt wird, um sich mit den tieferen Aspekten der benachbarten Disziplinen vertraut zu machen. Bis heute werden globale Optimierungsalgorithmen daher nur auf einem der verschiedenen Zugänge aufgebaut. Ein wichtiger Schritt in Richtung einer Integration mehrerer Traditionen wurde im EU-Projekt COCONUT gelegt, an dem sechs akademische Institutionen und die Firma ILOG teilgenomment haben, und das das COCONUT- Environment hervorgebracht hat. Im vorgeschlagenen Projekt hoffen wir, die Integration weiter zu treiben, mehr mathematische Theorie zu entwickeln und neue Algorithmen in das COCONUT-Framework einzubauen, das zum größten Teil an der Univ. Wien entwickelt wurde.

Das beantragte Projekt zielt darauf ab, das Gebiet der globalen Optimierung sowohl in theoretischer als auch in praktischer Hinsicht durch die Integration von Zugängen verschiedener mathematischer Disziplinen zu bereichern. Das frei erhältliche Softwarepaket zur globalen Optimierung, das COCONUT Environment, das während des EU- Projektes COCONUT entwickelt wurde und nun an der Universität Wien gewartet wird, soll durch neuentwickelte und verbesserte Strategien erweitert werden, was die Anwendung an viele verschiedene im wirklichen Leben vorkommender Probleme ermöglicht. Darüber hinaus ist geplant, die Steigerung der Geschwindigkeit und Effizienz des COCONUT Environment zu erhöhen, durch Implementierung einer automatischer Strategie-Auswahl. Globale Optimierung ist die Aufgabe, die absolut beste Möglichkeit(en) zu finden, ein Ziel unter gegebenen Nebenbedingungen zu erreichen, unter der Annahme, dass alles in mathematischen Ausdrücken modelliert ist. Ein Spezialfall davon ist das Zulässigkeits Problem, das darauf abzielt, eine oder alle Lösungen zu finden, die einem vorgegebenen Satz von Nebenbedingungen entsprechen. Beide Probleme sind viel schwieriger als konvexe Optimierung, die Auffindung lokaler Minima nichtlinearer Optimierungsprobleme oder die Lösung eines algebraischen Gleichungssystems, wenn gute Startpunkte bekannt sind. Viele wissenschaftliche und industrielle Anwendungen (z.B. Form-Optimierung in der Strukturmechanik, Design und Analyse von Robotern, Analyse von Phasengleichgewichten, Proteinfaltung, Logistik) führen zu schwierigen globalen Optimierungsproblemen in Dimensionen von weniger als zehn bis zu mehreren tausend Variablen. Im letzten Jahrzehnt hat sich das Interesse an globaler Optimierung substantiell gesteigert, zum Teil, weil immer mehr Anwendungen entstanden sind, aber auch, weil die algorithmische Entwicklung den Punkt erreicht hat, ab dem viele kleinere Probleme, die aber bereits Industrie-relevante Größenordnungen erreicht haben, zuverlässig gelöst werden können. Um den Herausforderungen realer Anwendungen zu begegnen, ist es oft nötig, neue theoretische Methoden zu erforschen und sie einzusetzen, die die speziellen Eigenschaften der Anwendung besonders ausnützen. Wie in vielen Bereichen, die sich mit schwierigen Rechner-intensieven-Problemen beschäftigen, kommt der Erfolg viel häufiger über theoretische Fortschritte als durch die Erhöhung der reinen Rechenstärke im Hardware-Bereich oder durch geschikte Nutzung bereits vorhandener Software-Pakete. Es gibt eine Reihe unterschiedlicher Zugänge zur Lösung globaler Optimierungsprobleme. Diese traditionellen Herangehensweisen wachsen langsam zueinander in Richtung eines Ganzen, was wiederum die Lösung globaler Optimierungsprobleme in Dimensionen realisierbar macht, die für die Lösung realer Probleme relevant sind. Leider wird dieser Prozess behindert durch die Tatsache, dass die verschiedenen Zugänge substantiell verschieden sind und ihre Stärken aus unterschiedlichen mathematischen Traditionen ziehen welche nur geringe Gemeinsamkeiten aufweisen: numerische Mathematik, konvexe Analysis, Optimierung, Kombinatorik, Logik und algebraische Geometrie. Daher sind auch Synergieeffekte zu erzielen, hauptsächlich aufgrund der Einarbeitungszeit, die benötigt wird, um sich mit den tieferen Aspekten der benachbarten Disziplinen vertraut zu machen. Bis heute werden globale Optimierungsalgorithmen daher nur auf einem der verschiedenen Zugänge aufgebaut. Ein wichtiger Schritt in Richtung einer Integration mehrerer Traditionen wurde im EU-Projekt COCONUT gelegt, an dem sechs akademische Institutionen und die Firma ILOG teilgenomment haben, und das das COCONUT-Environment hervorgebracht hat. Im vorgeschlagenen Projekt hoffen wir, die Integration weiter zu treiben, mehr mathematische Theorie zu entwickeln und neue Algorithmen in das COCONUT-Framework einzubauen, das zum größten Teil an der Univ. Wien entwickelt wurde.