Mathematische Optimierung: Theorie
Überblick
Optimierungsprobleme \( \min f(x), x \in D\) zu formulieren und zu lösen erfordert den Einsatz verschiedener Felder der angewandten Mathematik und ist ein vielseitiges Unterfangen.
Echtweltprobleme in mathematischer Sprache zu modellieren ist eine kreative Aufgabe, die zurückgreift auft Wahrscheinlichkeitsrechnung und lineare Algebra. Die in Folge entstehenden Optimierungsprobleme können hinsichtlich ihrer strukturellen Eigenschaften untersucht werden; je nach Zielfunktion \(f\) und Nebenbedingungen \(D\) können theoretisch beweisbare Garantien über Lösbarkeit und Komplexität des Problemes abgeleitet werden. Die letztendliche Lösung des Optimierungsproblemes fällt in die Domäne der Numerik, in der sich Mathematik, Informatik, und Programmiertechnische Herausforderungen verbinden.
Modellierung
Echtweltphänomene zeichnen sich durch Komplexität, nichtlineare Zusammenhänge, und Unsicherheiten aus. Ihre korrekte Repräsentation erfordert eine detaillierte Untersuchung der das Phänomen beschreibenden Variablen und etwaiger kausaler Zusammenhänge.
Diese können simpel sein (Zshg. Produktionskosten und Profit), komplex (Zshg. Beschleunigung und Position) oder stochastisch (Zshg. Investitionsdauer und Rendite). Oft erfordert die Modellierung die Auswertung von Daten, um die Interaktionen der verschiedenen Variablen zu quantifizieren. Dies injiziert eine weitere Quelle der Unsicherheit in den Modellierungsvorgang. Deren Quantifizierung und Beschränkung muss mittels stochastischer Methoden gewährleistet werden.
Die Überführung in ein abstraktes mathematisches Modell wird noch dadurch erschwert, dass nur eine restriktive Klasse von Modellen im Rahmen der mathematischen Optimierung überhaupt zuverlässig gelöst werden kann. Daher sind für die zentralen Zusammenhänge irrelevante Details zwecks späterer Nutzung so weit wie möglich zu reduzieren — ein Zielkonflikt zu dem ursprünglichen Anspruch wahrheitsgetreuer mathematischer Repräsentation eines Echtweltphänomenes. Zyklen von Modellformulierung, ‑analyse, und ‑evaluation sind der Standard [1, p. 13]. Kurzum: Modelle sind einfach, Modellierung ist schwierig.
Analyse
Ob und wie ein Optimierungsproblem \( \min f(x), x \in D\) lösbar ist, hängt von den Eigenschaften der Zielfunktion \(f\) und der Nebenbedingungen \(D\) ab. Für manche Kombinationen können Lösungsgarantien ausgesprochen werden, während andere sich jeglichem Optimierungsversuch entziehen.
Entscheidend ist dabei eine Eigenschaft namens Konvexität. Ist ein Optimierungsproblem konvex, dann hat \(f\) nur ein einziges lokales Optimum und jede Verbindungslinie zwischen zwei Punkten \(x_1, x_2 \in D\) liegt komplett in \(D\) [2, p. 138]. Als Konsequenz reduziert sich die Suche nach einem globalen Optimum auf die Suche nach dem einzigen lokalen Optimum. Der Einsatz gradientenbasierter Verfahren ist ausreichend, um eine Folge von sukzessig besseren Punkten zu generieren, die gegen das globale Optimum konvergiert.
Konvexe Optimierungsprobleme verfügen ausserdem über eine systematisch konstruierbare untere Schranke für Ihre Optimalwerte \( \min f(x), x \in D\). Diese Schranken sind ihrerseits Lösungen eines Optimierungsproblemes, dem sogenannten dualen Problem [2, p. 216]. Diese Sekundärprobleme verraten viel über das ursprüngliche Optimierungsproblme und erlauben z.B. Diagnose über die Sensitivität des Optimalwertes gegenüber Veränderungen der Nebenbedingungen oder die Aussprache von Lösbarkeitsgarantien.
Lösung
ist das Optimierungsproblem konvex, dann ist es prinzipiell lösbar. Mit Hilfe von Vektoren und Matrizen werden lokale Steigungen und Krümmungen quantifiziert. Diese werden benutzt, um in einem iterativen Verfahren eine Folge von sich hinsichtlich ihres Funktionswertes verbessernder Punkte zu generieren, die gegen das globale Optimum konvergiert.
Dabei müssen mathematische Belange vorsichtig abgewägt werden gegen Speicherplatzbedarf, Rechenintensität, und Interpretierbarkeit des Verfahrens. All dies lässt die Lösung eines allgemeinen konvexen Optimierungsproblemes zu einer komplizierten Angelegenheit werden. Sind jedoch Zielfunktion und Nebenbedinungen linear, so existieren leistungsfähige Algorithmen. Das gilt auch, wenn quadratische Terme und Kegelbedingungen auftreten. In diese Fällen ist dank der Verfügbarkeit von open source solvern wenig schwierige Arbeit zu leisten und das Optimierungsproblem kann nach automatisierten Regeln gelöst werden [3, pp. 155–210].
Ausblick
Auf den untergeordneten Seiten finden sich Informationen zu Konvexität, Dualtitätstheorie sowie der Modellierung von Unsicherheit. Einige Grundzüge der numerischen Lösung konvexer Probleme werden beschrieben.
Quellen
[1] Meyer, W. J. (2012). Concepts of Mathematical Modeling. New York: Courier Corporation.
[2] Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge: Cambridge University Press.
[3] Liberti, L., & Maculan, N. (2006). Global Optimization: From Theory to Implementation. Berlin Heidelberg: Springer Science & Business Media.
