Optimierung (Mathematik)

|Beispiel einer lokalen Optimierungsaufgabe|Beispiel einer globalen Optimierungsaufgabe

Das Gebiet der Optimierung in der angewandten Mathematik beschäftigt sich damit, optimale Parameter eines - meist komplexen - Systems zu finden. "Optimal" bedeutet, dass eine Zielfunktion minimiert oder maximiert wird. Optimierungsprobleme stellen sich in der Wirtschaftsmathematik, Statistik, Operations Research, in allen Wissenschaftsgebieten, in denen mit unbekannten Parametern gearbeitet wird, insbesondere Physik, Chemie, Metereologie usw.

Siehe auch: Allgemein Optimierung, Operations Research und Optimierung in der Informatik.

Inhaltsverzeichnis

1 Beispiel eines einfachen Optimierungsproblems

2 Beispiele für Optimierungsprobleme

3 Abgrenzung

4 Begriffe: Zielfunktion, Fittopologie, lokale und globale Optimierung

5 Lineare Optimierung

6 Methoden der lokalen nichtlinearen Optimierung

7 Methoden der globalen nichtlinearen Optimierung

8 Quellen

9 Links

Beispiel eines einfachen Optimierungsproblems

Das einfachste Optimierungsproblem ist das Auffinden eines Minimums oder Maximums einer analytischen eindimensionalen Funktion f(x), was in der Regel durch Auffinden der Nullstellen der ersten Ableitung gelingt.

Beispiele für Optimierungsprobleme

Wirtschaftsmathematik: Die Zielfunktion stellt hier meist der Gewinn oder der Umsatz einer Firma dar, Parameter sind Rohstoffe, Personal-, Maschineneinsatz, Preise usw.. Die Zielfunktion soll maximiert werden. Im Grunde genommen handelt es sich um eine vereinfachte Formalisierung eines grundlegenden Managementproblems. Seine systematische Fundierung erhält es in der Operations Research.
Statistik, Data Mining: Statistische Modelle enthalten offene Parameter, die geschätzt werden. Ein Parametersatz ist optimal, wenn dann das Modell die Datenbeziehungen (welche Werte y1,y2,... treten auf, wenn x1,x2,... auftreten?) optimal darstellt, d.h. die Abweichungen der modellierten Daten ym1,ym2,... von den empirischen Daten y1,y2,... optimal gering ist. Die Zielfunktion kann hier unterschiedlich gewählt werden, z.B. als Least Square oder als Likelihood-Funktion.
Klimaforschung: Klimamodelle stellen vereinfachte numerische Systeme der eigentlichen hydrodynamischen Prozesse in der Atmosphäre dar. Innerhalb der Gitterzellen müssen die Wechselwirkungen durch Gleichungen approximiert werden. Die Gleichungen können dabei entweder aus grundlegenden hydrodynamischen Gesetzen abgeleitet werden oder es werden empirische Gleichungen verwendet, also im Grunde statistische Modelle, deren Parameter so optimiert werden müssen, dass die Klimamodelle die tatsächlichen Prozesse möglichst gut darstellen.
Spieltheorie: Erreicht eine Spielerpopulation in einem Superspiel ein Populationsoptimum? Oder wenigstens ein Pareto-Optimum? Ist dieses Gleichgewicht stabil?

Abgrenzung

Verwandt zur Optimierung ist das Gebiet der Approximation in der Numerik. Man kann umgekehrt sagen: Ein Approximationsproblem ist das Problem, den Abstand (die Metrik) zweier Funktionen zu minimieren.

Begriffe: Zielfunktion, Fittopologie, lokale und globale Optimierung

Es sei im Folgenden eine Miniminierungsaufgabe angenommen. Das, was minimiert werden soll, z.B. ein Abstand, nennt man Zielfunktion. Das, was variert wird, sind die Parameter der Zielfunktion. Gibt es zwei unabhängige Parameter, ist die Zielfunktion zweidimensional. Stellt man sich die Zielfunktion räumlich vor, indem die Parameter die Längen- und Tiefenachse aufspannen, dann ist die Höhe der Zielfunktionswert, also z.B. der jeweilige Abstand zum Parameterpaar. Das sieht i.a. aus wie ein "Gebirge" mit Bergen und Tälern. Falls es sich bei der Optimierungsaufgabe tatsächlich um ein Approximationsproblem handelt, dann spricht man bei dem "Gebirge" mitunter auch von der Fittopologie.

Da die Zielfunktion ein "Gebirge" darstellt, ist das Optimierungsproblem damit gleichzusetzen, in diesem Gebirge das tiefste Tal (Minimierung) oder den höchsten Gipfel (Maximum) zu finden. Der Aufwand zur Lösung der Aufgabe hängt entscheidend von der Form des "Gebirges" ab. Extrembeispiel für eine Minimierungsaufgabe wäre die Form eine Billiardtisches, also einer absolut flachen Ebene, aus dem an zufälligen Punkten einzelne nadelförmige Spitzen herausragen. In diesem Fall hilft keinerlei Suchalgorithmus, man kann nur zufällig suchen (Monte Carlo-Methode) oder systematisch die gesamte Fläche abrastern. Der einfachste Fall einer zweidimensionalen Optimierierungsaufgabe wäre es, wenn das Gebirge die Form eines einzigen Kegels hätte, dessen Spitze man finden müsste.

Besteht die Optimierungsaufgabe darin, von einem gegebenen Punkt im Gebirge aus das nächste relative Minimum oder Maximum in der Nachbarschaft zu finden, dann spricht man von lokaler Optimierung. Besteht die Aufgabe darin, das absolute Minimum oder Maximum im gesamten Gebirge zu finden, dann spricht man von globaler Optimierung. Beide Aufgaben sind ungleich schwierig: Für die lokale Optimierung gibt es zahlreiche Methoden, die alle mehr oder weniger schnell, in allen nicht allzuschwierigen Fällen mit grosser Sicherheit zum Ziel führen. Bei der globalen Optimierung hängt die Lösbarkeit der Aufgabe im Rahmen eines gegebenen oder realisierbaren Rechenbudgets sehr stark von der Zielfunktionstopologie ab.

Lineare Optimierung

Bei der linearen Optimierung handelt es sich um einen Sonderfall: Die Zielfunktion ist durch ein lineares Gleichungssystem darstellbar. Es gibt Methoden, das globale Optimum ohne Iteration zu erhalten, das bekannteste ist das Simplex-Verfahren. (Nicht zu verwechseln mit dem Downhill-Simplex-Verfahren) weiter unten. Neuerdings gibt es allerdings auch effiziente Innere-Punkte-Verfahren, die es mit dem Simplex-Verfahren aufnehmen können.

Schwieriger ist der Fall der nichtlinearen Optimierung:

Methoden der lokalen nichtlinearen Optimierung

Bei der lokalen Optimierung hängt die Wahl der Methode von der genauen Problemstellung ab: Handelt es sich um eine beliebig exakt bestimmte Zielfunktion? (Das ist bei stochastischen Zielfunktionen oft nicht der Fall) Ist die Zielfunktion in der Umgebung streng monoton, nur monoton oder könnte es "unterwegs" sogar kleine relative Extrema geben? Wie hoch sind die Kosten, einen Gradienten zu bestimmen?

Beispiele für Methoden:

Ableitungsfreie Methoden

Intervallhalbierungsverfahren, goldener Schnitt und andere Verfahren der Liniensuche.
Sekantenverfahren
Downhill-Simplex-Verfahren

Diese Methoden kosten viele Iterationen, sind aber (teilweise) relativ robust gegenüber Problemen in der Zielfunktion, z.B. kleine relative Extrema und sie verlangen nicht die Berechnung eines Gradienten. Letzteres kann sehr kostspielig sein, wenn lediglich ein relativ ungenaues Ergebnis angestrebt wird.

Verfahren, für die die 1. Ableitung benötigt wird

Gradientenverfahren und konjugiertes Gradientenverfahren.

Diese Methoden sind schneller als die ableitungsfreien Methoden, sofern ein Gradient schnell berechnet werden kann und sie sind ähnlich robust wie die ableitungsfreien Methoden.

Verfahren, für die die 2. Ableitung benötigt wird

Newton-Verfahren, bzw. Newton-Rephson-Verfahren.

Gemeinhin ist das Newton-Verfahren als Verfahren zur Bestimmung einer Nullstelle bekannt und benötigt die erste Ableitung. Dementsprechend lässt es sich auch auf die Ableitung einer Zielfunktion anwenden, da die Optimierungsaufgabe auf die Bestimmung der Nullstellen der 1. Ableitung hinausläuft. Das Newton-Verfahren ist sehr schnell, aber sehr wenig robust. Wenn man sich der "Gutartigkeit" seines Optimierungsproblems nicht sicher ist, sollte man es nicht anwenden.

Methoden der globalen nichtlinearen Optimierung

Im Gegensatz zur lokalen Optimierung ist die globale Optimierung ein quasi ungelöstes Problem der Mathematik: Es gibt praktisch keinerlei Methoden, bei deren Anwendung man in den meisten Fällen als Ergebnis einen Punkt erhält, der mit Sicherheit oder auch nur grosser Wahrscheinlichkeit das absolute Extremum darstellt.

Allen Methoden zur globalen Optimierung gemein ist, dass sie wiederholt nach einem bestimmten System lokale Minima/Maxima aufsuchen.

Am häufigsten werden hier genetische Algorithmen angewandt. Diese liefern dann ein gutes Ergebnis, wenn die Anordnung der relativen Minima und Maxima eine gewisse Gesetzmässigkeit aufweisen, deren Kenntnis vererbt werden kann. Gibt es keine Regelmässigkeiten in der Anordnung der Minima und Maxima, hilft auch die Genetik nichts. Eine ganz gute Methode kann auch sein, die Ausgangspunkte für die Suche nach lokalen Minima/Maxima zufällig zu wählen, um dann mittels statistischer Methoden die Suchergebnisse nach Regelmässigkeiten zu untersuchen.

Oft wird allerdings in der Praxis das eigentliche Suchkriterium nicht genügend reflektiert. So ist es oft viel wichtiger, nicht das globale Optimum zu finden, sondern ein Parametergebiet, innerhalb dem sich möglichst viele relative Minima befinden. Hier eignen sich dann Methoden der Clusteranalyse oder neuronale Netze.

Weitere Methoden der nichtlinearen globalen Optimierung:

Bergsteigeralgorithmus (hill climbing)
Metropolisalgorithmus
simulierte Abkühlung (simulated annealing)
Schwellenakzeptanz (threshold accepting)

Quellen

W.H. Press et al.: Numerical Recipes. Cambridge: University Press.
R. Horst and P.M. Pardalos (eds.), Handbook of Global Optimization, Kluwer, Dordrecht 1995