Mathematische Optimierung

Grundidee und mathematisches Modell

Die mathematische Optimierung ist ein Teilgebiet der angewandten Mathematik. Sie untersucht, wie unbekannte Größen möglichst gut bestimmt werden können. Solche Aufgaben treten unter anderem in Technik, Naturwissenschaften, Informatik, Wirtschaft, Statistik und maschinellem Lernen auf. Da eine analytische Lösung häufig nicht möglich ist, werden meist numerische Verfahren eingesetzt.

Ein Optimierungsproblem besteht aus einer Zielfunktion, Entscheidungsvariablen und gegebenenfalls Nebenbedingungen oder Restriktionen. Die Entscheidungsvariablen beschreiben die veränderbaren Größen. Die Zielfunktion bewertet jede mögliche Wahl dieser Größen durch eine reelle Zahl. Nebenbedingungen legen fest, welche Entscheidungen zulässig sind.

Ein Minimierungsproblem lässt sich schreiben als P: minₓ f(x) unter der Nebenbedingung x ∈ M. Dabei ordnet f: V → ℝ jedem Vektor x aus einem Vektorraum V, beispielsweise ℝⁿ, einen Wert f(x) zu. M ⊆ V ist die zulässige Menge. Sie kann typischerweise durch Gleichungen und Ungleichungen beschrieben werden: M = {x ∈ V | gᵢ(x) ≤ 0, hⱼ(x) = 0, i ∈ I, j ∈ J}. Analog werden Maximierungsprobleme formuliert.

Ein Optimalpunkt x★ ist eine zulässige Wahl der Entscheidungsvariablen, welche die Zielfunktion minimiert oder maximiert. Der zugehörige Optimalwert ist f(x★). Verschiedene Optimalpunkte können denselben Wert besitzen; der Optimalwert ist dagegen eindeutig bestimmt. Ein bekanntes einfaches Beispiel ist die Suche nach dem Minimum oder Maximum einer differenzierbaren eindimensionalen Funktion f(x). Dazu bestimmt man in der Regel die Nullstellen ihrer ersten Ableitung f′(x). Für f(x) = (x − 1)² + 2 liegt das Minimum bei x = 1.

Ein praktischer Sachverhalt lässt sich oft auf mehrere Arten als Optimierungsproblem darstellen. Die Entwicklung einer geeigneten mathematischen Beschreibung heißt mathematische Modellierung; das Ergebnis wird Optimierungsmodell genannt.

Lösungskonzepte und Problemklassen

Ein globaler Optimalpunkt x★ einer Minimierungsaufgabe erfüllt f(x★) ≤ f(x) für alle x ∈ M. Er ist damit mindestens so gut wie jeder andere zulässige Punkt. Bei einer Maximierung spricht man entsprechend von einem globalen Maximum. Ein lokaler Optimalpunkt dominiert dagegen nur die zulässigen Punkte in einer Umgebung U(x★): f(x★) ≤ f(x) für alle x ∈ M ∩ U(x★). Die Suche nach solchen Punkten heißt lokale Optimierung; die Suche nach weltweit besten Punkten heißt globale Optimierung.

Bei konvexen Optimierungsproblemen ist jedes lokale Optimum zugleich global optimal. Bei nichtkonvexen Problemen können mehrere lokale Optima auftreten. Lokale Verfahren der nichtlinearen Optimierung können diese effizient berechnen, liefern aber nicht unbedingt ein globales Optimum. Zur deterministischen globalen Optimierung nichtkonvexer Probleme dienen unter anderem Branch-and-Bound und Branch-and-Cut; ihre Erfolgsaussichten hängen stark von der Problemstruktur ab.

Wichtige Klassen sind die kontinuierliche lineare Optimierung (LP), die ganzzahlige lineare Optimierung (ILP), die kontinuierliche nichtlineare Optimierung, die quadratische und die konvexe Optimierung sowie die Variationsrechnung. Bei mehreren möglicherweise widersprüchlichen Zielfunktionen werden Methoden der Mehrzieloptimierung benötigt. Ganzzahlige Variablen dürfen nur ganzzahlige Werte annehmen; kontinuierliche Variablen können Werte aus einem kontinuierlichen Bereich annehmen.

Wichtige Lösungsverfahren

Optimierungsmethoden sind Algorithmen zur Berechnung von Lösungen eines Optimierungsproblems.

Bei einem kontinuierlichen linearen Optimierungsproblem sind Zielfunktion sowie Gleichungs- und Ungleichungsrestriktionen linear. Ein LP ist konvex, weshalb jedes lokale Optimum global ist. Das primale und das duale Simplex-Verfahren sind Pivotverfahren und lösen LPs nach endlich vielen Iterationen exakt. Obwohl ihre theoretische Worst-Case-Komplexität ungünstig ist, lösen professionelle Implementierungen sehr große praktische Probleme effizient. Innere-Punkte-Verfahren besitzen eine bessere theoretische Komplexität und sind seit den 1990er Jahren konkurrenzfähig. Moderne Pakete wie CPLEX, Gurobi und FICO XPress lassen häufig primalen Simplex, dualen Simplex und ein Innere-Punkte-Verfahren auf verschiedenen Prozessorkernen gegeneinander antreten.

Probleme mit kontinuierlichen und ganzzahligen Variablen werden vor allem mit Branch-and-Bound oder Branch-and-Cut gelöst. Professionelle Implementierungen verwenden zusätzlich Schnittebenen, Presolve-Techniken zur Vereinfachung und Heuristiken. Bei nichtlinearen gemischt-ganzzahligen Problemen ist eine konvexe kontinuierliche Relaxierung hilfreich. Eine Relaxierung ignoriert die Ganzzahligkeitsbedingungen und erleichtert die Berechnung von Schranken für den Optimalwert.

Für lokale Minima kontinuierlicher nichtlinearer Probleme werden im unrestringierten Fall Erweiterungen des Gradienten- und Newtonverfahrens eingesetzt, darunter das Konjugierte-Gradienten-Verfahren, Quasi-Newton-Verfahren, Trust-Region-Methoden und der Levenberg-Marquardt-Algorithmus. Für restringierte nichtlineare Probleme nutzt man häufig Sequential Quadratic Programming (SQP), Innere-Punkte-Methoden und Augmented-Lagrange-Verfahren.

Metaheuristiken suchen ohne genaue Kenntnis der Anwendung nach guten zulässigen Punkten, geben aber normalerweise keine Garantie für globale Optimalität. Dazu zählen evolutionäre Algorithmen, simulierte Abkühlung, Metropolisalgorithmus, Ameisenalgorithmus, Partikelschwarmoptimierung, Bergsteigeralgorithmus und stochastisches Tunneln.

Optimalitätsbedingungen und Dualität

Notwendige Optimalitätsbedingungen müssen an jedem Optimalpunkt erfüllt sein, reichen aber nicht immer aus, um dessen Optimalität zu beweisen. Für eine differenzierbare Funktion f: ℝⁿ → ℝ gilt bei unrestringierter nichtlinearer Optimierung notwendigerweise ∇f(x★) = 0. Der Gradient, also die mehrdimensionale Ableitung, verschwindet dort. Ein solcher Punkt heißt kritischer Punkt. Das Newtonverfahren sucht gezielt kritische Punkte, die jedoch nicht zwangsläufig Optima sind. Bei nichtdifferenzierbaren Funktionen wird diese Idee durch Subgradientenverfahren und das Subdifferential verallgemeinert.

Bei glatten restringierten Problemen treten KKT-Punkte an die Stelle kritischer Punkte. Sie erfüllen die Karush-Kuhn-Tucker-Bedingungen. Falls Regularitätsbedingungen wie die Lineare-Unabhängigkeits-Bedingung gelten, muss jeder Optimalpunkt eines restringierten nichtlinearen Problems ein KKT-Punkt sein.

Die Dualitätstheorie verbindet ein primales Problem P mit einem zugehörigen dualen Problem D. Bei linearen Optimierungsproblemen stimmen die Optimalwerte von P und D immer überein. Dies wird im primalen und dualen Simplex-Verfahren sowie in primal-dualen Innere-Punkte-Verfahren genutzt. Für kontinuierliche konvexe Probleme gilt eine entsprechende Aussage, wenn eine Regularitätsbedingung wie die Slater-Bedingung erfüllt ist. Dualitätstheorien für nichtkonvexe kontinuierliche Probleme sind weiterhin Gegenstand der Forschung.

Typische Anwendungen

Im maschinellen Lernen und in der Statistik werden Modelle durch Minimierung einer Verlustfunktion trainiert. Lineare Regression nach der Methode der kleinsten Quadrate führt zu einem unrestringierten quadratischen Problem, das einem linearen Gleichungssystem entspricht. Support Vector Machines beruhen auf einem restringierten konvexen Problem. Das Training tiefer neuronaler Netze ergibt je nach Verlustfunktion ein unrestringiertes, nichtkonvexes und manchmal nichtdifferenzierbares Problem; eingesetzt werden moderne Varianten des stochastischen Gradientenverfahrens wie Adam. Bei Bayesian Optimization werden teuer auszuwertende Black-Box-Funktionen durch Surrogatmodelle wie Gauß-Prozesse angenähert und anschließend etwa zur Bestimmung optimaler Hyperparameter optimiert.

In den Naturwissenschaften ist die Parameterschätzung für Modelle ein Optimierungsproblem. Das Hamiltonsche Prinzip oder Prinzip der kleinsten Wirkung führt zu Aufgaben der Variationsrechnung. Weitere Beispiele sind das Fermatsche Prinzip der Optik und die Proteinfaltung.

In der Robotik ist die optimale Bahnplanung ein Problem der optimalen Steuerung. Dabei wird in einem unendlichdimensionalen Optimierungsproblem eine optimale Funktion gesucht; Differentialgleichungen bilden die Nebenbedingungen. Weitere Aufgaben sind die Routenplanung mobiler Roboter und die zeitliche Planung von Laborrobotern.

In der Energiewirtschaft bestimmt die Kraftwerkseinsatzoptimierung oder das Unit Commitment Problem den wirtschaftlich optimalen Einsatz von Kraftwerken. Sie wird meist als gemischt-ganzzahliges lineares Problem modelliert. Im Supply Chain Management werden Transporte, Lagerbestände, Produktionsplanung und Marketing optimiert. Historisch wird dieses Gebiet häufig Operations Research genannt; typisch sind kontinuierliche oder gemischt-ganzzahlige lineare Modelle.

Scheduling bezeichnet die Erstellung eines Ablaufplans, der Prozesse optimal auf Ressourcen verteilt, etwa bei Personal, Produktionsmaschinen oder NFL-Spielplänen. Solche Probleme besitzen meist viele ganzzahlige Variablen und komplizierte Abhängigkeiten. Deshalb kann bereits das Finden irgendeiner zulässigen Lösung aufwendig sein.

Historische Entwicklung

Bereits die alten Griechen untersuchten geometrische Optimierungsaufgaben wie das Problem der Dido. Johann Bernoullis Brachistochronenproblem von 1696 gab einen Anstoß zur Variationsrechnung, die Leonhard Euler und Joseph-Louis Lagrange im 18. Jahrhundert weiterentwickelten. Adrien-Marie Legendre veröffentlichte 1805 die Methode der kleinsten Quadrate; vermutlich hatte Carl Friedrich Gauß sie schon früher entwickelt, aber nicht veröffentlicht. Augustin-Louis Cauchy publizierte 1847 das Gradientenverfahren.

George Dantzig führte 1947 den Simplex-Algorithmus ein und gilt als Vater der modernen linearen Optimierung. Bei seiner ersten Anwendung benötigte die händische Berechnung eines Ernährungsplans mit 21 Restriktionen und 77 Entscheidungsvariablen 120 Personentage. Eine 1954–1955 auf einem IBM 701 implementierte Version konnte LPs mit 101 Restriktionen behandeln. Die heute sogenannten Karush-Kuhn-Tucker-Bedingungen wurden 1951 von Harold W. Kuhn und Albert W. Tucker veröffentlicht, waren aber bereits 1939 von William Karush entwickelt worden. Alisa Land und Alison Doig entwickelten 1961 Branch-and-Bound. Leonid Chatschijan bewies 1979, dass LPs in polynomialer Zeit lösbar sind; 1984 folgte Narendra Karmarkars erste praktisch nutzbare primale-duale Innere-Punkte-Methode.

Eine Studie von Robert Bixby ermittelte 2007 für kommerzielle Branch-and-Cut- beziehungsweise Branch-and-Bound-Implementierungen seit Ende der 1980er Jahre allein durch algorithmische Verbesserungen einen Geschwindigkeitsgewinn um den Faktor 29000. Forschende um William J. Cook lösten 2006 eine Instanz des NP-schweren Traveling Salesman Problem mit 85900 Stationen global optimal. Der Erfolg großer neuronaler Netze führte in den 2010er Jahren zur Weiterentwicklung stochastischer Gradientenverfahren; der Adam-Algorithmus entstand 2014.