„Mathematische Optimierung“ – Versionsunterschied

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Versionsgeschichte interaktiv durchsuchen
[gesichtete Version][ungesichtete Version]
← Zum vorherigen VersionsunterschiedZum nächsten Versionsunterschied →
Inhalt gelöscht Inhalt hinzugefügt
VisuellWikitext
K form
→‎Theoretische Aussagen: Konvexität muss hier nicht erklärt werden, da das bereits an anderen Stellen passiert und nicht zentral für math. Opt. ist; Notwendige Optimalitätsbedingungen und Dualität in versch. Variationen eingeführt und belegt, bisheriges Material entfernt, da zu speziell (beispielsweise nur auf Probleme mit Gleichungen) oder zu kurz/informell präsentiert; Vier Elemente aus Literaturliste entfernt, da entweder zu alt oder nicht thematisch exakt passend
Zeile 70: Zeile 70:
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ärer Algorithmus|evolutionäre Algorithmen]], [[naturanaloge Optimierungsverfahren]] (zum Beispiel [[Sintflutalgorithmus]], [[Simulierte Abkühlung]], [[Metropolisalgorithmus]], [[Schwellenakzeptanz]], [[Ameisenalgorithmus]], [[Partikelschwarmoptimierung]] …) und sonstige Verfahren wie der [[Bergsteigeralgorithmus]] und [[Stochastisches Tunneln]].
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ärer Algorithmus|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 Aussagen ==
== Theoretische Konzepte ==
=== Notwendige Optimalitätsbedingungen ===
Bei der Optimierung einer (differenzierbaren) Funktion <math>f(x)</math> ohne Nebenbedingungen ist bekannt, dass Minima/Maxima nur an Stellen mit <math>\nabla f(x) = 0</math> sein können. Diese Bedingung wird bei der Konstruktion vieler Lösungsverfahren ausgenutzt. In dem Fall der Optimierung mit Nebenbedingungen gibt es analoge theoretische Aussagen: [[Dualität (Mathematik)|Dualität]] und [[Lagrange-Multiplikator]]en.


Notwendige [[Optimalitätskriterium|Optimalitätsbedingungen]] sind Bedingungen, die in einem Optimalpunkt [[Notwendige Bedingung|notwendigerweise]] erfüllt sein müssen.
=== Konvexe Probleme ===
{{Hauptartikel|Konvexe Optimierung}}
Bei konvexen Problemen ist das abzusuchende Gebiet und die Zielfunktion konvex. Bei einem konvexen Gebiet liegen alle Punkte auf der Verbindungslinie zweier beliebiger Punkte im Gebiet ebenfalls vollständig im Gebiet. Mathematisch:
:<math>\lambda \in [0,1] \Rightarrow x + \lambda (y-x) \in X \quad \forall x,y \in X</math>
Beispiele für konvexe Gebiete sind Kreise, Ellipsen, Dreiecke und Quadrate.


In der unrestringierten nichtlinearen Optimierung einer [[Differenzierbarkeit|differenzierbaren]] Funktion <math>f:\mathbb{R}^n\to\R</math> ist beispielsweise bekannt, dass jeder Optimalpunkt <math>x^\star</math> notwendigerweise auch ein [[Kritischer Punkt (Mathematik)|kritischer Punkt]] von <math>f</math> ist, das heißt, dass gilt <math>\nabla f(x^\star)=0</math>, die (höherdimensionale) Ableitung von <math>f</math> in <math>x^\star</math> also verschwindet. Optimierungsmethoden wie das Newtonverfahren nutzen dies aus und berechnen gezielt kritische Punkt von <math>f</math>, in der Hoffnung, dass diese auch optimal sind.<ref>{{Literatur |Autor=Oliver Stein |Titel=Grundzüge der Nichtlinearen Optimierung |Auflage=2. Auflage |Verlag=Springer Spektrum |Ort=Berlin |Datum=2021 |Reihe= |ISBN=978-3-662-62531-6 |Abruf=}}</ref> 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<ref>{{Literatur |Autor=Ralph Tyrrell Rockafellar |Titel=Convex analysis |Auflage=10 |Verlag=Princeton Univ. Press |Ort=Princeton, NJ |Datum=1997 |Reihe=Princeton Landmarks in mathematics and physics |ISBN=978-0-691-08069-7 |Abruf=}}</ref> und für nichtkonvexe Funktionen in verschiedenen Variationen existiert.<ref>{{Literatur |Autor=Ralph Tyrrell Rockafellar, Roger J.-B. Wets, Maria Wets |Titel=Variational analysis |Nummer= |Auflage=3 |Verlag=Springer |Ort=Berlin / Heidelberg |Datum=2009 |Reihe=Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen |ISBN=978-3-540-62772-2 |Abruf=}}</ref><ref>{{Literatur |Titel=Nonsmooth analysis and control theory |Nummer= |Verlag=Springer |Ort=New York / Heidelberg |Datum=1998 |Reihe=Graduate texts in mathematics |ISBN=978-0-387-98336-3 |Abruf=}}</ref>
Die Zielfunktion ist konvex, wenn alle Werte der Zielfunktion von Punkten auf der Geraden, die zwei Punkte im Gebiet verbinden, unter dieser Geraden liegen. Mathematisch:
:<math>\lambda \in [0,1] \Rightarrow f(x + \lambda (y-x)) \le f(x) + \lambda (f(y)-f(x)) \quad \forall x,y \in X</math>.
Die zu Beginn dieses Artikels gezeigte parabelförmige Optimierungsaufgabe hat eine konvexe Zielfunktion.


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 [[Karush-Kuhn-Tucker-Bedingungen#Regularitätsvoraussetzungen|Regularitätsbedingungen]] (engl. ''constraint qualifications'') wie etwa die [[Linear independence constraint qualification|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.<ref name=":3">{{Literatur |Autor=Carl Geiger, Christian Kanzow |Titel=Theorie und Numerik restringierter Optimierungsaufgaben: mit 140 Übungsaufgaben |Verlag=Springer |Ort=Berlin / Heidelberg |Datum=2002 |ISBN=978-3-540-42790-2 |Abruf=}}</ref>
Bei konvexen Problemen ist jedes lokale Minimum auch globales Minimum. Sind die Punkte <math>x_i\,,\; i=1,\dotsc,n</math> optimal, dann sind alle Punkte „zwischen“ diesen Punkten optimal. Mathematisch:
:<math>
\alpha_1, \alpha_2,\dotsc,\alpha_n \in [0,1]\; \wedge\; \sum_{i=1}^n \alpha_i = 1
\quad\Rightarrow\quad
f\left(\sum_{i=1}^n \alpha_i x_i\right)=f_\text{opt}
</math>.


=== Dualität ===
=== 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 <math>P</math> existiert ein duales Optimierungsproblem <math>D</math>, das eine enge Beziehung zu <math>P</math> besitzt, die theoretisch und algorithmisch ausgenutzt werden kann. So stimmen etwa die Optimalwerte von <math>P</math> und <math>D</math> laut der [[Lineare Optimierung#Dualität|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.<ref name=":3" /> Für nichtkonvexe kontinuierliche Probleme gibt es ebenfalls verschiedene Ansätze Dualitätstheorien zu entwickeln, die allerdings noch Gegenstand aktueller Forschung sind.<ref>{{Literatur |Autor=R. Tyrrell Rockafellar |Titel=Augmented Lagrange Multiplier Functions and Duality in Nonconvex Programming |Sammelwerk=SIAM Journal on Control |Band=12 |Nummer=2 |Datum=1974-05 |ISSN=0036-1402 |DOI=10.1137/0312021 |Seiten=268–285 |Online= |Abruf=}}</ref>
Das einem Optimierungsproblem <math>\min \; f(x): \; g(x) = 0</math> zugeordnete [[Lagrange-Dualität|(Lagrange-)''duale Problem'']] ist
:<math>\max_\lambda \min_x \mathcal{L}(x, \lambda)</math>
wobei <math>\mathcal{L}(x,\lambda) = f(x) + \lambda^Tg(x)</math> die zugehörige Lagrange-Funktion ist. Die <math>\lambda</math> heißen hierbei [[Lagrange-Multiplikator]]en, oder auch ''duale Variablen'' oder ''[[Opportunitätskosten|Schattenpreise]]''. Anschaulich erlaubt man eine Verletzung der Nebenbedingungen, bestraft sie aber in der Zielfunktion durch Zusatzkosten <math>\lambda</math> pro verletzter Einheit. Eine Lösung <math>\lambda</math>, für die es sich nicht lohnt, die Nebenbedingungen zu verletzen, löst das duale Problem. Für konvexe (insbesondere lineare) Probleme ist der Wert des dualen Problems gleich dem Wert des Ursprungsproblems. Für lineare und konvexe quadratische Probleme lässt sich die innere Minimierung geschlossen lösen und das duale Problem ist wieder ein lineares oder konvexes quadratisches Problem.

=== Lagrange-Multiplikatoren ===
Der Lagrange-Multiplikatorsatz besagt, dass Lösungen des eingeschränkten Optimierungsproblems <math>\min_x \, f(x): \, g(x)=0</math> nur an Stellen <math>x</math> zu finden sind, an denen es ''[[Lagrange-Multiplikator]]en'' <math>\lambda_i</math> gibt, die die Bedingung
:<math>\nabla_x \mathcal{L}(x,\lambda) = \nabla f(x) + \sum_i \lambda_i \nabla g_i(x) = 0</math>
erfüllen. Diese Bedingung ist die direkte Verallgemeinerung der obigen Ableitungsbedingung. Wie diese gibt der Lagrange-Multiplikatorensatz eine [[notwendige Bedingung]] für ein Minimum bzw. Maximum. Eine [[hinreichende Bedingung]] kann durch Betrachtung der zweiten Ableitungen gewonnen werden.

Der Lagrange-Multiplikatorensatz gilt nur für den Fall, dass die Nebenbedingungen durch Gleichungen gegeben sind. Die Verallgemeinerung auf Ungleichungen
<math>\min_x \{f(x): g(x)\le 0\}</math> gibt der [[Konvexe Optimierung#Karush-Kuhn-Tucker-Bedingungen|Satz von Karush-Kuhn-Tucker]].

=== Straffunktionen ===
Im Grenzwert der gegen unendlich gehenden Strafparameter geht die mit Straffunktionen gefundene Lösung in die mit den Lagrange-Multiplikatoren gefundene Lösung über.

=== Erweiterte Lagrange-Methode ===
Im Grenzwert unendlich vieler Iterationen strebt die mit der erweiterten Lagrange-Methode gefundene Lösung auch gegen die mit den Lagrange-Multiplikatoren gefundene Lösung.


== Literatur (Auswahl) ==
== Literatur (Auswahl) ==
* Walter Alt: ''Nichtlineare Optimierung – Eine Einführung in Theorie, Verfahren und Anwendungen''. Vieweg, 2002, ISBN 3-528-03193-X.
* Walter Alt: ''Nichtlineare Optimierung – Eine Einführung in Theorie, Verfahren und Anwendungen''. Vieweg, 2002, ISBN 3-528-03193-X.
* Yonathan Bard: ''Nonlinear Parameter Estimation''. Academic Press, New York 1974, ISBN 0-12-078250-2.
* Hans Benker: ''Mathematische Optimierung mit Computeralgebrasystemen.'' Springer-Verlag, Berlin/ Heidelberg/ New York 2003.
* S. Boyd, L. Vandenberghe: ''Convex Optimization''. Cambridge University Press, 2004. [http://www.stanford.edu/~boyd/cvxbook/ (online)]
* S. Boyd, L. Vandenberghe: ''Convex Optimization''. Cambridge University Press, 2004. [http://www.stanford.edu/~boyd/cvxbook/ (online)]
* W. Domschke, A. Drexl: ''Einführung in Operations Research.'' 7. Auflage. Springer, Berlin 2007, ISBN 978-3-540-70948-0.
* W. Domschke, A. Drexl: ''Einführung in Operations Research.'' 7. Auflage. Springer, Berlin 2007, ISBN 978-3-540-70948-0.
* R. Fletcher: ''Practical Methods of Optimization''. Wiley, 1987, ISBN 0-471-91547-5.
* U. Hoffmann, H. Hofmann: ''Einführung in die Optimierung: mit Anwendungsbeispielen aus dem Chemie-Ingenieur-Wesen''. Verlag Chemie, Weinheim 1971, ISBN 3-527-25340-8.
* R. Horst, P. M. Pardalos (Hrsg.): ''Handbook of Global Optimization''. Kluwer, Dordrecht 1995, ISBN 0-7923-3120-6.
* 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. {{Google Buch |BuchID=DyHc3WU0QOcC}}
* F. Jarre, J. Stoer: ''Optimierung''. Springer, 2004, ISBN 3-540-43575-1. {{Google Buch |BuchID=DyHc3WU0QOcC}}

Version vom 11. Dezember 2023, 00:08 Uhr

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.[1][2][3] 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

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. Bei der Suche nach dem Optimalpunkt , welcher minimiert, kommen nur Punkte der zulässigen Menge infrage. 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. 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.[1][4][5]

Ausgewählte Anwendungen der Mathematischen Optimierung

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.[6][7] 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 Routenplanung eines Roboters ist ein Problem der optimalen Steuerung, also ein unendlichdimensionales Optimierungsproblem, in welchem eine optimale Funktion gesucht wird, deren Nebenbedingungen durch Differentialgleichungen definiert sind.

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.[8]

Supply Chain Management

Viele Probleme des Transports, der optimalen Lagerbestände[9], 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.[10]

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.[11][12]

Lösungskonzepte, lokale und globale Optimierung

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.[13] Für nichtkonvexe Probleme werden in der lokalen Optimierung Lösungsmethoden der nichtlinearen Optimierung zur effizienten Berechnung lokaler Optima eingesetzt.[14] Die deterministische globale Optimierung nichtkonvexer Optimierungsprobleme erfolgt mit Branch-and-Bound bzw. Branch-and-Cut Methoden, deren Effizienz stark von der Struktur des Optimierungsproblems abhängt und die beispielsweise erfolgreich zur Lösung (nichtlinearer) gemischt-ganzzahlige Optimierungsprobleme eingesetzt werden.[15][4]

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. 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.[16] 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.[17]

Methoden der gemischt-ganzzahligen linearen und nichtlinearen 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[18] und Heuristiken in den letzten Jahrzehnten enorme Geschwindigkeitszuwächse verzeichnen konnten.[16][19] 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.[20]

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 ist beispielsweise bekannt, dass jeder Optimalpunkt notwendigerweise auch ein kritischer Punkt von ist, das heißt, dass gilt , die (höherdimensionale) Ableitung von in also verschwindet. Optimierungsmethoden wie das Newtonverfahren nutzen dies aus und berechnen gezielt kritische Punkt von , in der Hoffnung, dass diese auch optimal sind.[21] 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[22] und für nichtkonvexe Funktionen in verschiedenen Variationen existiert.[23][24]

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.[25]

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 existiert ein duales Optimierungsproblem , das eine enge Beziehung zu besitzt, die theoretisch und algorithmisch ausgenutzt werden kann. So stimmen etwa die Optimalwerte von und 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.[25] Für nichtkonvexe kontinuierliche Probleme gibt es ebenfalls verschiedene Ansätze Dualitätstheorien zu entwickeln, die allerdings noch Gegenstand aktueller Forschung sind.[26]

Literatur (Auswahl)

Einzelnachweise

  1. ↑ a b H. P. Williams: Model Building in Linear and Integer Programming. 5. Auflage. Wiley, New Jersey 2013, ISBN 978-1-118-44333-0.
  2. ↑ Gurobi: Industries that use Mathematical Optimization. Abgerufen am 8. Dezember 2023 (amerikanisches Englisch).
  3. ↑ Leena Suhl, Taïb Mellouli: Optimierungssysteme: Modelle, Verfahren, Software, Anwendungen. 3., korrigierte und aktualisierte Auflage. Springer Gabler, Berlin / Heidelberg 2013, ISBN 978-3-642-38936-8.
  4. ↑ a b Nathan Sudermann-Merx: Einführung in Optimierungsmodelle. Springer Berlin Heidelberg, Berlin / Heidelberg 2023, ISBN 978-3-662-67380-5, doi:10.1007/978-3-662-67381-2.
  5. ↑ Josef Kallrath: Gemischt-ganzzahlige Optimierung: Modellierung in der Praxis. 2002, doi:10.1007/978-3-322-80219-4.
  6. ↑ Trevor Hastie, Robert Tibshirani, Jerome Friedman: The Elements of Statistical Learning. Springer New York, New York 2009, ISBN 978-0-387-84857-0.
  7. ↑ Diederik P. Kingma, Jimmy Ba: Adam: A Method for Stochastic Optimization. revidiert Auflage. 2017, arxiv:1412.6980.
  8. ↑ Kenneth Van den Bergh, Kenneth Bruninx, Erik Delarue, William D‘haeseleer: LUSYM: a unit commitment model formulated as a mixed-integer linear program. KU Leuven, TME Branch Working Paper 7, 2014 (kuleuven.be [PDF]).
  9. ↑ Edward A. Silver, David F. Pyke, Douglas J. Thomas: Inventory and production management in supply chains. 4. Auflage. CRC Press, Taylor & Francis Group, Boca Raton / FL London New York / NY 2021, ISBN 978-1-03-217932-2.
  10. ↑ Leena Suhl, Taïb Mellouli: Optimierungssysteme: Modelle, Verfahren, Software, Anwendungen (= Springer-Lehrbuch). 3., korrigierte und aktualisierte Auflage. Springer Gabler, Berlin / Heidelberg 2013, ISBN 978-3-642-38936-8 (springer.com).
  11. ↑ National Football League Scheduling. In: Gurobi Optimization. Abgerufen am 9. Dezember 2023 (amerikanisches Englisch).
  12. ↑ Michael Pinedo: Scheduling: theory, algorithms, and systems. 5. Auflage. Springer, Cham / Heidelberg / New York / Dordrecht / London 2018, ISBN 978-3-319-79973-5.
  13. ↑ Stephen Boyd, Lieven Vandenberghe: Convex Optimization. Cambridge University Press, 2004, ISBN 0-521-83378-7 (stanford.edu [PDF; abgerufen am 8. Dezember 2023]).
  14. ↑ Carl Geiger, Christian Kanzow: Theorie und Numerik restringierter Optimierungsaufgaben. 2002, doi:10.1007/978-3-642-56004-0.
  15. ↑ Oliver Stein: Grundzüge der Globalen Optimierung. 2021, doi:10.1007/978-3-662-62534-7.
  16. ↑ a b Robert E. Bixby: A brief history of linear and mixed-integer programming computation. In: Optimization Stories. EMS Press, 2012, ISBN 978-3-936609-58-5, S. 107–121 (uni-bielefeld.de [PDF; abgerufen am 9. Dezember 2023]).
  17. ↑ Method. In: Gurobi Optimization. Abgerufen am 9. Dezember 2023 (englisch).
  18. ↑ Tobias Achterberg, Robert E. Bixby, Zonghao Gu, Edward Rothberg, Dieter Weninger: Presolve Reductions in Mixed Integer Programming. In: INFORMS Journal on Computing. Band 32, Nr. 2, April 2020, ISSN 1091-9856, S. 473–506 (kobv.de [PDF; abgerufen am 9. Dezember 2023]).
  19. ↑ William Cook: "Information, Computation, Optimization..." Abgerufen am 9. Dezember 2023 (deutsch).
  20. ↑ Jorge Nocedal, Stephen J. Wright: Numerical optimization (= Springer series in operation research and financial engineering). 2. Auflage. Springer, New York 2006, ISBN 978-0-387-30303-1.
  21. ↑ Oliver Stein: Grundzüge der Nichtlinearen Optimierung. 2. Auflage. Springer Spektrum, Berlin 2021, ISBN 978-3-662-62531-6.
  22. ↑ Ralph Tyrrell Rockafellar: Convex analysis (= Princeton Landmarks in mathematics and physics). 10. Auflage. Princeton Univ. Press, Princeton, NJ 1997, ISBN 978-0-691-08069-7.
  23. ↑ Ralph Tyrrell Rockafellar, Roger J.-B. Wets, Maria Wets: Variational analysis (= Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen). 3. Auflage. Springer, Berlin / Heidelberg 2009, ISBN 978-3-540-62772-2.
  24. ↑ Nonsmooth analysis and control theory (= Graduate texts in mathematics). Springer, New York / Heidelberg 1998, ISBN 978-0-387-98336-3.
  25. ↑ a b Carl Geiger, Christian Kanzow: Theorie und Numerik restringierter Optimierungsaufgaben: mit 140 Übungsaufgaben. Springer, Berlin / Heidelberg 2002, ISBN 978-3-540-42790-2.
  26. ↑ R. Tyrrell Rockafellar: Augmented Lagrange Multiplier Functions and Duality in Nonconvex Programming. In: SIAM Journal on Control. Band 12, Nr. 2, Mai 1974, ISSN 0036-1402, S. 268–285, doi:10.1137/0312021.

Weblinks

Commons: Optimization – Sammlung von Bildern, Videos und Audiodateien
Abgerufen von „https://de.wikipedia.org/w/index.php?title=Mathematische_Optimierung&oldid=240072656“