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

→ Hauptartikel: Optimierungsproblem

Minimierung der Funktion $f(x)=(x-1)^{2}+2$

Das wohl bekannteste Optimierungsproblem ist das Auffinden eines Minimums oder Maximums einer differenzierbaren eindimensionalen Funktion $f(x)$, was in der Regel durch Berechnung der Nullstellen der ersten Ableitung $f'(x)$ 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 $P$ schreiben als

$$P:\qquad \min _{x}f(x)\quad {\text{u.d.N.}}\quad x\in M,$$

wobei die Zielfunktion $f:V\to \mathbb {R}$ jedem Vektor von Entscheidungsvariablen $x\in V$ aus einem beliebigen Vektorraum $V$ (z. B. $\mathbb {R} ^{n}$) eine reelle Zahl $f(x)$ 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 $x^{\star }$, welcher $f(x)$ minimiert, kommen nur Punkte der zulässigen Menge $M\subseteq V$ infrage, wobei „${\textstyle {\text{u.d.N.}}}$“ bedeutet „unter der Nebenbedingung“. Ist ein Optimalpunkt $x^{\star }$ gefunden, so erhält man den zugehörigen Optimalwert $f(x^{\star })$ durch Einsetzen des Optimalpunkts in die Zielfunktion, welcher im Gegensatz zum Optimalpunkt immer eindeutig bestimmt ist. Die zulässige Menge $M$ lässt sich in der Regel in der Form

$$M=\{x\in V\mid g_{i}(x)\leq 0,\ h_{j}(x)=0,\ i\in I,\ j\in J\}$$

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

Lokale und globale Minima und Maxima der Funktion $f(x)=\cos(3\pi x)/x$ im Bereich $0.1\leq x\leq 1.1$

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 $x^{\star }\in M$ einer Minimierungsaufgabe gilt

$$f(x^{\star })\ \leq \ f(x)\qquad \forall x\in M,$$

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 $x^{\star }\in M$ die anderen zulässigen Punkte nur in einer Umgebung $U(x^{\star })$ dominiert, wenn also gilt

$$f(x^{\star })\ \leq \ f(x)\qquad \forall x\in M\cap U(x^{\star }),$$

so ist $x^{\star }$ 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

→ Hauptartikel: Optimierungsproblem#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

→ Hauptartikel: Nichtlineare 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

Notwendige Optimalitätsbedingungen sind Bedingungen, die in einem Optimalpunkt notwendigerweise erfüllt sein müssen.

In der unrestringierten nichtlinearen Optimierung einer differenzierbaren Funktion $f:\mathbb {R} ^{n}\to \mathbb {R}$ ist beispielsweise bekannt, dass jeder Optimalpunkt $x^{\star }$ notwendigerweise auch ein kritischer Punkt von $f$ ist, das heißt, dass gilt $\nabla f(x^{\star })=0$, die (höherdimensionale) Ableitung von $f$ in $x^{\star }$ also verschwindet. Optimierungsmethoden wie das Newtonverfahren nutzen dies aus und berechnen gezielt kritische Punkte von $f$, in der Hoffnung, dass diese auch optimal sind. In der unrestringierten Optimierung nichtdifferenzierbarer Funktionen lässt sich die Idee auf Subgradientenverfahren verallgemeinern, welche statt mit Gradienten mit dem Subdifferential arbeiten, welches für konvexe Funktionen eindeutig definiert ist und für nichtkonvexe Funktionen in verschiedenen Variationen existiert.

In der restringierten nichtlinearen glatten Optimierung wird das Prinzip der kritischen Punkte auf sogenannte KKT-Punkte erweitert, welches Punkte sind, die die Karush-Kuhn-Tucker-Bedingungen erfüllen. Falls Regularitätsbedingungen (engl. constraint qualifications) wie etwa die Lineare-Unabhängigkeits-Bedingung erfüllt sind, muss jeder Optimalpunkt eines nichtlinearen restringierten Optimierungsproblems notwendigerweise auch ein KKT-Punkt sein, was algorithmisch ausgenutzt werden kann.

Dualität

In der mathematischen Optimierung existiert eine reiche Dualitätstheorie, welche Aussagen über den Zusammenhang zwischen Optimierungsproblemen und ihren dualen Gegenstücken macht. Zu jedem (primalen) Optimierungsproblem $P$ existiert ein duales Optimierungsproblem $D$, das eine enge Beziehung zu $P$ besitzt, die theoretisch und algorithmisch ausgenutzt werden kann. So stimmen etwa die Optimalwerte von $P$ und $D$ laut der Dualitätstheorie für lineare Optimierungsprobleme immer überein, was algorithmisch im primalen und dualen Simplex-Verfahren sowie primal-dualen Innere-Punkte-Verfahren ausgenutzt wird. Diese Aussagen lassen sich auf konvexe kontinuierliche Optimierungsprobleme erweitern, falls eine Regularitätsbedingung wie die Slater-Bedingung erfüllt ist. Für nichtkonvexe kontinuierliche Probleme gibt es ebenfalls verschiedene Ansätze Dualitätstheorien zu entwickeln, die allerdings noch Gegenstand aktueller Forschung sind.

Auszüge aus der Geschichte der mathematischen Optimierung

Vor dem 20. Jahrhundert

Experimenteller Aufbau zur Brachistochrone im Technoseum in Mannheim

Schon die alten Griechen studierten Optimierungsprobleme mit geometrischem Bezug wie etwa das Problem der Dido. Im Jahr 1696 formulierte Johann Bernoulli das Problem der Brachistochrone, was die Entwicklung der Variationsrechnung anstieß, die von Leonhard Euler und Joseph-Louis Lagrange im 18. Jahrhundert fortgeführt wurde. Im Jahr 1805 veröffentlichte Adrien-Marie Legendre einen Artikel zur Methode der kleinsten Quadrate, welche aber wohl schon früher vom jungen Carl Friedrich Gauß entwickelt (aber nicht veröffentlicht) wurde. Eine weitere berühmte Optimierungsmethode, das Gradientenverfahren, wurde 1847 von Augustin-Louis Cauchy publiziert.

Im 20. Jahrhundert

Bedienungskonsole der IBM 701

George Dantzig gilt mit seiner Arbeit im Jahr 1947, in welcher unter anderem der Simplex-Algorithmus eingeführt wurde, als Vater der modernen linearen Optimierung. Allerdings gab es schon davor Wissenschaftler wie etwa Leonid Kantorowitsch, die theoretische Aussagen zur Theorie linearer Optimierungsprobleme erarbeiteten. Die erste Anwendung des Simplex-Algorithmus war eine Berechnung eines optimalen Ernährungsplans mit 21 Restriktionen und 77 Entscheidungsvariablen. Die händische Berechnung nahm 120 Personentage in Anspruch.

In den 50er Jahren wechselte George Dantzig von der US Air Force zur RAND Corporation mit dem Ziel, erste Computerimplementierungen des Simplex-Algorithmus umzusetzen. In den Jahren 1954–1955 wurde eine überarbeitete Version der Methode auf einem IBM 701 implementiert, wo sich immerhin LPs mit 101 Restriktionen modellieren ließen. Im Jahr 1951 veröffentlichten Harold W. Kuhn und Albert W. Tucker ihre Arbeit zu Optimalitätsbedingungen, die jedoch unbekannterweise bereits zuvor im 1939 von William Karush in einer Masterarbeit entwickelt worden waren und heute als Karush-Kuhn-Tucker-Bedingungen bekannt sind. 1961 entwickelten Alisa Land und Alison Doig die Branch-and-Bound-Methode an der London School of Economics im Rahmen einer Zusammenarbeit mit British Petroleum. Im Jahr 1979 zeigte Leonid Chatschijan, dass LPs in polynomialer Zeit gelöst werden können, was ein unerwartetes und bedeutsames theoretisches Resultat war, das jedoch erst im Jahre 1984 mit Narendra Karmarkars Entwicklung der ersten primal-dualen Inneren-Punkte-Methode praktisch umgesetzt werden konnte. Seit Ende der 80er Jahre existieren professionelle Implementierungen von Branch-and-Cut- bzw. Branch-and-Bound-Methoden, die anwendungsunabhängig als Black-Box-Solver für gemischt-ganzzahlige lineare Probleme eingesetzt werden können.

Im 21. Jahrhundert

Im Jahr 2007 wurde ergab eine computergestützte Studie von Robert Bixby, eine Verbesserung kommerzieller Implementierungen von Branch-and-Cut bzw. Branch-and-Bound-Methoden seit ihrer Einführung Ende der 80er Jahre allein aufgrund algorithmischer Verbesserungen um den Faktor 29000. Zeitgleich wurden neue Rekorde in der Berechnung nachweislich optimaler Routen für das Traveling Salesman Problem, welches NP-schwer ist und damit als praktisch unlösbar galt. So wurde von Forschenden rund um William J. Cook im Jahr 2006 eine TSP-Instanz mit 85900 Stationen global optimal gelöst. Der große Erfolg von Methoden des Maschinellen Lernens erforderte in den 2010er Jahren die Entwicklung moderner Optimierungsmethoden für das Training großer neuronaler Netze. Dies führte zur Wiederentdeckung und Weiterentwicklungen des stochastischen Gradientenverfahrens, wie etwa dem Adam-Algorithmus im Jahr 2014.

Weiterführende Informationen

Die gut dokumentierte Geschichte der mathematischen Optimierung wird zum Beispiel im Online-Artikel A Brief History of Optimization and Mathematical Programming zusammengefasst, in welchem die Autoren B. Singh und M. Eisner auch 180 weitere Referenzen angeben.

Literatur (Auswahl)

• Walter Alt: Nichtlineare Optimierung – Eine Einführung in Theorie, Verfahren und Anwendungen. Vieweg, 2002, ISBN 3-528-03193-X.
• S. Boyd, L. Vandenberghe: Convex Optimization. Cambridge University Press, 2004. (online)
• W. Domschke, A. Drexl: Einführung in Operations Research. 7. Auflage. Springer, Berlin 2007, ISBN 978-3-540-70948-0.
• C. Grossmann, J. Terno: Numerik der Optimierung. Teubner Studienbücher, 1997, ISBN 3-519-12090-9. eingeschränkte Vorschau in der Google-Buchsuche
• R. Horst, P. M. Pardalos (Hrsg.): Handbook of Global Optimization. Kluwer, Dordrecht 1995, ISBN 0-7923-3120-6.
• F. Jarre, J. Stoer: Optimierung. Springer, 2004, ISBN 3-540-43575-1. eingeschränkte Vorschau in der Google-Buchsuche
• J. Nocedal, S. J. Wright: Numerical Optimization. Springer, Berlin 1999, ISBN 0-387-98793-2.
• O.Stein: Grundzüge der Nichtlinearen Optimierung. 2. Auflage. Springer Spektrum, Berlin, Heidelberg, 2021, ISBN 978-3-662-62531-6.
• O.Stein: Grundzüge der Globalen Optimierung. 2. Auflage. Springer Spektrum, Berlin, Heidelberg, 2021, ISBN 978-3-662-62533-0.
• N. Sudermann-Merx: Einführung in Optimierungsmodelle. Springer Spektrum, Berlin, Heidelberg, 2023, ISBN 978-3-662-67380-5.
• L. A. Wolsey: Integer Programming. 2. Auflage John Wiley & Sons, Hoboken, New Jersey 2020, ISBN 978-1-119-60653-6.

Weblinks

Commons: Optimization – Sammlung von Bildern, Videos und Audiodateien

• Literatur zur Optimierung im Katalog der Deutschen Nationalbibliothek
• NEOS Optimization Guide (englisch)