Mathematische Optimierung

Die mathematische Optimierung ist ein Teilgebiet der angewandten Mathematik, welches sich mit dem Lösen von Optimierungsproblemen beschäftigt. Sie hat zahlreiche Anwendungen, beispielsweise in den Bereichen Automatisierungstechnik, Automobilindustrie, Energiewirtschaft, Ernährungswissenschaft, Finanzen, Gesundheitswesen, Luft- und Raumfahrttechnik, Marketing, Produktionsplanung, Machine Learning, Robotik und Supply-Chain-Management. Generell ist sie in allen Disziplinen von Interesse, in denen mit unbekannten Variablen gearbeitet wird, die optimal bestimmt werden sollen wie beispielsweise in der Chemie, der Informatik, der Physik oder den Wirtschaftswissenschaften. Häufig ist eine analytische Lösung von Optimierungsproblemen nicht möglich und es müssen numerische Verfahren eingesetzt werden.

Optimierungsprobleme

mini|350x350px|Minimierung der Funktion Das wohl bekannteste Optimierungsproblem ist das Auffinden eines Minimums oder Maximums einer differenzierbaren eindimensionalen Funktion , was in der Regel durch Berechnung der Nullstellen der ersten Ableitung gelingt. Ein einfaches Beispiel ist in nebenstehendem Bild aufgezeigt.

Jedes Optimierungsproblem besteht aus einer zu optimierenden Zielfunktion und Entscheidungsvariablen, welchen manchmal Nebenbedingungen (auch Restriktionen genannt) auferlegt werden, die die zulässige Menge definieren.

Mathematisch formuliert lässt sich das Optimierungsproblem schreiben als

wobei die Zielfunktion jedem Vektor von Entscheidungsvariablen aus einem beliebigen Vektorraum (z. B. ) eine reelle Zahl zuordnet, die es zu minimieren gilt. Analog zu einem solchen Minimierungsproblem können natürlich auch Maximierungsprobleme betrachtet werden. Bei der Suche nach einem Optimalpunkt , welcher minimiert, kommen nur Punkte der zulässigen Menge infrage, wobei „“ bedeutet „unter der Nebenbedingung“. Ist ein Optimalpunkt gefunden, so erhält man den zugehörigen Optimalwert durch Einsetzen des Optimalpunkts in die Zielfunktion, welcher im Gegensatz zum Optimalpunkt immer eindeutig bestimmt ist. Die zulässige Menge lässt sich in der Regel in der Form

darstellen, d. h. sie ist durch Gleichungen und Ungleichungen funktional beschrieben, die als Gleichungsrestriktionen und Ungleichungsrestriktionen bezeichnet werden. Eine solche Darstellung ist in der Regel nicht eindeutig. Generell gibt es für die meisten Anwendungen verschiedene Möglichkeiten, diese als Optimierungsproblem zu formulieren, die sich teilweise jeweils auch nicht klar dominieren. Sobald der Schwerpunkt auf einer möglichst vorteilhaften mathematischen Beschreibung des zu optimierenden Sachverhalts liegt, befindet man sich im Bereich der mathematischen Modellierung und spricht entsprechend auch von Optimierungsmodellen.

Ausgewählte Anwendungen Maschinelles Lernen, Statistik Das Training von Modellen in den Bereichen Maschinelles Lernen und Statistik findet durch die Minimierung einer Verlustfunktion (engl. loss function) statt, was ein Optimierungsproblem ist. Je nach Modellklasse und gewählter Verlustfunktion ergeben sich unterschiedliche Optimierungsprobleme und zugehörige Optimierungsmethoden, die zur Lösung der Optimierungsmodelle eingesetzt werden. Im Falle der linearen Regression mit der Methode der kleinsten Quadrate ergibt sich etwa ein unrestringiertes quadratisches Optimierungsproblem, welches äquivalent zu einem linearen Gleichungssystem ist. Support Vector Machines werden durch das Lösen eines restringierten konvexen Optimierungsproblems gelöst und das Training eines tiefen neuronalen Netzes ergibt je nach Wahl der loss function ein unrestringiertes nichtkonvexes (manchmal auch nichtdifferenzierbares) Optimierungsproblem, welches durch moderne Varianten des stochastischen Gradientenverfahrens wie etwa Adam gelöst wird. Weitere Anwendungen der mathematischen Optimierung finden sich in der Bayesian Optimization, in welcher teuer zu evaluierende Black-Box-Funktionen durch Surrogatmodelle (z. B. Gauß-Prozesse) approximiert und anschließend optimiert werden, um etwa optimalen Hyperparameter zu bestimmen.

Naturwissenschaften Die Parameterschätzung naturwissenschaftlicher Modelle ist ein Optimierungsproblem. Darüber hinaus folgen physikalische Systeme dem Hamiltonschen Prinzip, welches auch das Prinzip der kleinsten Wirkung genannt wird und beispielsweise in Optimierungsproblemen der Variationsrechnung mündet. Weitere Anwendungen der mathematischen Optimierung finden sich etwa im Fermatschen Prinzip der Optik und der Proteinfaltung.

Robotik Die optimale Bahnplanung eines Industrieroboters ist ein Problem der optimalen Steuerung, also ein unendlichdimensionales Optimierungsproblem, in welchem eine optimale Funktion gesucht wird, deren Nebenbedingungen durch Differentialgleichungen definiert sind. Darüber hinaus gibt es noch zahlreiche weitere Optimierungsfragestellungen in der Robotik, wie beispielsweise die optimale Routenplanung mobiler Roboter oder das Scheduling der Aufgaben von Labor-Robotern.

Energiewirtschaft Die Kraftwerkseinsatzoptimierung (engl. Unit Commitment Problem) ist ein Modell der mathematischen Optimierung, welches von Energieversorgern eingesetzt, um Kraftwerke wirtschaftlich optimal einzusetzen. Mathematisch wird dies meistens als gemischt-ganzzahliges lineares Optimierungsproblem modelliert.

Supply Chain Management Viele Probleme des Transports, der optimalen Lagerbestände, der Produktionsplanung und des Marketings können mit Methoden der mathematischen Optimierung modelliert und gelöst werden. Historisch bedingt spricht man in diesen Bereichen statt von mathematischer Optimierung eher von Operations Research. Hierbei entstehen in der Regel kontinuierliche lineare Optimierungsprobleme oder gemischt-ganzzahlige lineare Optimierungsprobleme.

Scheduling Unter Scheduling versteht man die Erstellung eines Ablaufplanes, der Prozesse auf Ressourcen optimal verteilt. Dies kann die Personaleinsatzplanung innerhalb eines Unternehmens, die Maschinenbelegungsplanung in der Produktion oder die Erstellung des Spielplans der NFL sein. Optimierungsprobleme, die aus Scheduling-Anwendungen entstehen, besitzen in der Regel viele ganzzahlige Variablen und eine komplizierte Struktur der Nebenbedingungen, da viele Abhängigkeiten existieren und sich somit oft selbst das Finden einer zulässigen Lösung als aufwändig gestaltet.

Lösungskonzepte, lokale und globale Optimierung mini|300x300px|Lokale und globale Minima und Maxima der Funktion im Bereich Neben der Unterscheidung in Optimalpunkt- und wert wird in Literatur und Praxis oft einfach nur von der Lösung, dem Optimum oder dem Minimum/Maximum eines Optimierungsproblems gesprochen. Da für den Optimalpunkt einer Minimierungsaufgabe gilt

er also alle anderen zulässigen Punkte global dominiert, wird er auch als globaler Optimalpunkt (auch globales Optimum oder globales Minimum) bezeichnet. Entsprechend spricht man bei einer Maximierung von einem globalen Maximum. Falls ein Punkt die anderen zulässigen Punkte nur in einer Umgebung dominiert, wenn also gilt

so ist ein lokaler Optimalpunkt (auch lokales Optimum oder lokales Minimum) bzw. im Maximierungsfall ein lokales Maximum. Ist man interessiert an der Berechnung lokaler Optima, so spricht man von lokaler Optimierung und analog bei für globale Minima oder Maxima von globaler Optimierung. Für konvexe Optimierungsprobleme sind alle lokale Optimalpunkte immer auch global optimal. Für nichtkonvexe Probleme werden in der lokalen Optimierung Lösungsmethoden der nichtlinearen Optimierung zur effizienten Berechnung lokaler Optima eingesetzt. Die deterministische globale Optimierung nichtkonvexer Optimierungsprobleme erfolgt mit Branch-and-Bound bzw. Branch-and-Cut Methoden, deren Erfolgsaussichten stark von der Struktur des Optimierungsproblems abhängen und die beispielsweise erfolgreich zur Lösung (nichtlinearer) gemischt-ganzzahlige Optimierungsprobleme eingesetzt werden.

Klassifikation von Optimierungsproblemen

Als bekannte Unterklassen der mathematischen Optimierung seien hier die (kontinuierliche) lineare Optimierung (LP), die ganzzahlige lineare Optimierung (ILP), die (kontinuierliche) nichtlineare Optimierung, die quadratische Optimierung, die konvexe Optimierung und die Variationsrechnung erwähnt. Falls nicht nur eine, sondern mehrere sich ggf. widersprechende Zielfunktionen vorliegen, so benötigt man Methoden der Mehrzieloptimierung. Für eine ausführlichere Klassifikation von Optimierungsproblemen hinsichtlich ihrer mathematischen Struktur siehe Optimierungsproblem (Klassifikation von Optimierungsproblemen).

Optimierungsmethoden Optimierungsmethoden sind Algorithmen, die zur Berechnung der Lösung von Optimierungsproblemen eingesetzt werden.

Methoden der kontinuierlichen linearen Optimierung Bei einem kontinuierlichen linearen Optimierungsproblem (LP) ist die Zielfunktion linear, und die Nebenbedingungen sind durch ein System linearer Gleichungen und Ungleichungen beschrieben. Da ein LP ein konvexes Optimierungsproblem ist, ist jedes lokale Optimum auch automatisch ein globales Optimum. Pivotverfahren wie das duale sowie das primale Simplex-Verfahren lösen LPs exakt nach einer endlichen Anzahl an Iterationen. Trotz ihrer schlechten theoretischen Worst-Case-Komplexität existieren professionelle Implementierungen der Simplex-Methode, welche sehr große praxisrelevante LPs effizient lösen. Im Gegensatz dazu sind Innere-Punkte-Verfahren, deren theoretische Komplexität besser ist, erst seit den 1990er Jahren konkurrenzfähig zum Simplex-Verfahren. In modernen Optimierungspaketen wie CPLEX, Gurobi und FICO XPress findet in der Regel auf verschiedenen Kernen ein Wettlauf zwischen dem primalen und dualen Simplex-Verfahren sowie einem Innere-Punkte-Verfahren statt.

Methoden der gemischt-ganzzahligen Optimierung Bei der Lösung von Optimierungsproblemen, in denen sowohl kontinuierliche als auch ganzzahlige Entscheidungsvariablen auftreten, kommen Branch-and-Bound sowie Branch-and-Cut Methoden zum Einsatz. Für diese Algorithmen existieren seit den 1980er Jahren professionelle Implementierungen, die durch den effizienten Einsatz von zusätzlichen Schnittebenen (eng. cutting planes), Presolve-Techniken und Heuristiken in den letzten Jahrzehnten enorme Geschwindigkeitszuwächse verzeichnen konnten. Bei nichtlinearen gemischt-ganzzahligen Problemen ist es in der Regel hilfreich, wenn die kontinuierliche Relaxierung des Problems, d. h. die Formulierung unter Ignorierung der Ganzzahligkeitsbedingungen, konvex ist, da dadurch einfacher Schranken an den Optimalwert des Optimierungsproblems berechnet werden können.

Methoden der kontinuierlichen lokalen nichtlinearen Optimierung

Für die Berechnung lokaler Minima kontinuierlicher linearer Optimierungsprobleme werden im unrestringierten Fall Optimierungsverfahren eingesetzt, die Grundideen des Gradientenverfahrens und des Newtonverfahrens aufgreifen und erweitern. Die populärsten Methoden sind vermutlich das Konjugierte-Gradienten-Verfahren sowie Quasi-Newton-Verfahren, Trust-Region-Methoden und der Levenberg-Marquardt-Algorithmus. Für restringierte nichtlineare Probleme kommen häufig SQP-Verfahren (Sequential-Quadratic-Programming-Verfahren), Innere-Punkte-Methoden und Augmented-Lagrange-Verfahren zum Einsatz.

Metaheuristiken Im Gegensatz zu anwendungsspezifischen Heuristiken wie der Nearest-Neighbor-Heuristik versuchen Metaheuristiken ohne Kenntnis der genauen Anwendung gute zulässige Punkte zu finden. Aussagen über die globale Optimalität dieser Punkte werden in der Regel nicht getroffen. Zu den bekanntesten Metaheuristiken zählen evolutionäre Algorithmen, naturanaloge Optimierungsverfahren (zum Beispiel Sintflutalgorithmus, Simulierte Abkühlung, Metropolisalgorithmus, Schwellenakzeptanz, Ameisenalgorithmus, Partikelschwarmoptimierung …) und sonstige Verfahren wie der Bergsteigeralgorithmus und Stochastisches Tunneln.

Theoretische Konzepte Notwendige Optimalitätsbedingungen