imported>Boehm: typog

2025-12-17T06:43:27Z

typog

Neue Seite

Die '''mathematische Optimierung''' ist ein Teilgebiet der [[Angewandte Mathematik|angewandten Mathematik]], welches sich mit dem Lösen von [[Optimierungsproblem]]en beschäftigt. Sie hat zahlreiche Anwendungen, beispielsweise in den Bereichen [[Automatisierungstechnik]], [[Automobilindustrie]], [[Energiewirtschaft]], [[Ernährungswissenschaft]], [[Finanzen]], [[Gesundheitssystem|Gesundheitswesen]], [[Luft- und Raumfahrttechnik]], [[Marketing]], [[Produktionsplanung und -steuerung|Produktionsplanung]], [[Maschinelles Lernen|Machine Learning]], [[Robotik]] und [[Supply-Chain-Management]].<ref name=":0">{{Literatur |Autor=H. P. Williams |Titel=Model Building in Linear and Integer Programming |Auflage=5. |Verlag=Wiley |Ort=New Jersey |Datum=2013 |ISBN=978-1-118-44333-0}}</ref><ref>{{Internetquelle |autor=Gurobi |url=https://www.gurobi.com/industry/ |titel=Industries that use Mathematical Optimization |sprache=en-US |abruf=2023-12-08}}</ref><ref>{{Literatur |Autor=Leena Suhl, Taïb Mellouli |Titel=Optimierungssysteme: Modelle, Verfahren, Software, Anwendungen |Auflage=3., korrigierte und aktualisierte |Verlag=Springer Gabler |Ort=Berlin / Heidelberg |Datum=2013 |ISBN=978-3-642-38936-8}}</ref> 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 [[Wirtschaftswissenschaft]]en. Häufig ist eine analytische Lösung von Optimierungsproblemen nicht möglich und es müssen [[Numerische Mathematik|numerische Verfahren]] eingesetzt werden.

== Optimierungsprobleme ==
{{Hauptartikel|Optimierungsproblem}}
[[Datei:Optimalpunkt Optimalwert.jpg|mini|350x350px|Minimierung der Funktion <math>f(x) = (x-1)^2+2</math>]]
Das wohl bekannteste Optimierungsproblem ist das Auffinden eines [[Extremwert|Minimums]] oder [[Extremwert|Maximums]] einer [[Differenzierbarkeit|differenzierbaren]] eindimensionalen [[Funktion (Mathematik)|Funktion]] <math>f(x)</math>, was in der Regel durch Berechnung der [[Nullstelle]]n der ersten [[Differentialrechnung|Ableitung]] <math>f'(x)</math> gelingt. Ein einfaches Beispiel ist in nebenstehendem Bild aufgezeigt.

Jedes Optimierungsproblem besteht aus einer zu optimierenden [[Zielfunktion]] und [[Entscheidungsvariable]]n, welchen manchmal [[Optimierungsproblem|Nebenbedingungen]] (auch ''Restriktionen'' genannt) auferlegt werden, die die [[zulässige Menge]] definieren.

Mathematisch formuliert lässt sich das Optimierungsproblem <math>P</math> schreiben als

: <math display="block">P:\quad\min_x f(x)\quad\mathrm{u.\,d.\,N.}\quad x\in M,</math>

wobei die ''Zielfunktion'' <math>f\colon V\to\mathbb R </math> jedem Vektor von ''Entscheidungsvariablen'' <math>x\in V</math> aus einem beliebigen [[Vektorraum]] <math>V</math> (z. B. <math>\mathbb{R}^n</math>) eine reelle Zahl <math>f(x)</math> zuordnet, die es zu minimieren gilt. Analog zu einem solchen [[Minimierungsproblem]] können natürlich auch [[Maximierungsproblem]]e betrachtet werden. Bei der Suche nach einem [[Optimalpunkt]] <math>x^\star</math>, welcher <math>f(x)</math> minimiert, kommen nur Punkte der ''zulässigen Menge'' <math>M\subseteq V</math> infrage, wobei „<math display="inline">\mathrm{u.\,d.\,N.}</math>“ bedeutet „unter der Nebenbedingung“. Ist ein Optimalpunkt <math>x^\star</math> gefunden, so erhält man den zugehörigen [[Optimalwert]] <math>f(x^\star)</math> durch Einsetzen des Optimalpunkts in die Zielfunktion, welcher im Gegensatz zum Optimalpunkt immer eindeutig bestimmt ist. Die zulässige Menge <math>M</math> lässt sich in der Regel in der Form

<math display="block">M = \{x\in V\mid g_i(x)\le 0,\ h_j(x)=0,\ i\in I,\ j\in J\}</math>

darstellen, d. h. sie ist durch Gleichungen und Ungleichungen funktional beschrieben, die als [[Gleichungsrestriktion]]en und [[Ungleichungsrestriktion]]en 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 [[Optimierungsmodell]]en.<ref name=":0" /><ref name=":1">{{Literatur |Autor=Nathan Sudermann-Merx |Titel=Einführung in Optimierungsmodelle |Verlag=Springer Berlin Heidelberg |Ort=Berlin / Heidelberg |Datum=2023 |ISBN=978-3-662-67380-5 |DOI=10.1007/978-3-662-67381-2}}</ref><ref>{{Literatur |Autor=Josef Kallrath |Titel=Gemischt-ganzzahlige Optimierung: Modellierung in der Praxis |Datum=2002 |DOI=10.1007/978-3-322-80219-4}}</ref>

== Ausgewählte Anwendungen ==
=== Maschinelles Lernen, Statistik ===
Das Training von Modellen in den Bereichen [[Maschinelles Lernen]] und [[Statistik]] findet durch die Minimierung einer [[Verlustfunktion (Statistik)|Verlustfunktion]] (engl. ''loss function'') statt, was ein Optimierungsproblem ist. Je nach Modellklasse und gewählter Verlustfunktion ergeben sich unterschiedliche Optimierungsprobleme und zugehörige [[#Optimierungsmethoden|Optimierungsmethoden]], die zur Lösung der Optimierungsmodelle eingesetzt werden. Im Falle der [[Lineare Regression|linearen Regression]] mit der [[Methode der kleinsten Quadrate]] ergibt sich etwa ein unrestringiertes [[Quadratische Optimierung|quadratisches Optimierungsproblem]], welches äquivalent zu einem [[Lineares Gleichungssystem|linearen Gleichungssystem]] ist. [[Support Vector Machine]]s werden durch das Lösen eines restringierten [[Konvexe Optimierung|konvexen Optimierungsproblems]] gelöst und das Training eines tiefen [[Künstliches neuronales Netz|neuronalen Netzes]] ergibt je nach Wahl der loss function ein unrestringiertes nichtkonvexes (manchmal auch nichtdifferenzierbares) Optimierungsproblem, welches durch moderne Varianten des [[Stochastisches Gradientenverfahren|stochastischen Gradientenverfahrens]] wie etwa Adam gelöst wird.<ref>{{Literatur |Autor=Trevor Hastie, Robert Tibshirani, Jerome Friedman |Titel=The Elements of Statistical Learning |Verlag=Springer New York |Ort=New York |Datum=2009 |ISBN=978-0-387-84857-0}}</ref><ref name=":4">{{Literatur |Autor=Diederik P. Kingma, Jimmy Ba |Titel=Adam: A Method for Stochastic Optimization |Auflage=revidiert |Datum=2017 |arXiv=1412.6980}}</ref> Weitere Anwendungen der mathematischen Optimierung finden sich in der [[Bayes’sche Optimierung|Bayesian Optimization]], in welcher teuer zu evaluierende Black-Box-Funktionen durch Surrogatmodelle (z. B. [[Gauß-Prozess]]e) approximiert und anschließend optimiert werden, um etwa optimalen [[Hyperparameteroptimierung|Hyperparameter]] zu bestimmen.

=== Naturwissenschaften ===
Die Parameterschätzung naturwissenschaftlicher Modelle ist ein Optimierungsproblem. Darüber hinaus folgen physikalische Systeme dem [[Hamiltonsches Prinzip|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 [[Fermatsches Prinzip|Fermatschen Prinzip]] der Optik und der [[Proteinfaltung]].

=== Robotik ===
Die optimale Bahnplanung eines Industrieroboters ist ein Problem der [[Optimale Steuerung|optimalen Steuerung]], also ein unendlichdimensionales Optimierungsproblem, in welchem eine optimale Funktion gesucht wird, deren Nebenbedingungen durch [[Differentialgleichung]]en 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-ganzzahlige Optimierung#Gemischt-ganzzahlige lineare Optimierungsprobleme|gemischt-ganzzahliges lineares Optimierungsproblem]] modelliert.<ref>{{Literatur |Autor=Kenneth Van den Bergh, Kenneth Bruninx, Erik Delarue, William D‘haeseleer |Titel=LUSYM: a unit commitment model formulated as a mixed-integer linear program |Verlag=KU Leuven, TME Branch Working Paper 7 |Datum=2014 |Online=https://mech.kuleuven.be/en/tme/research/energy_environment/Pdf/wpen2014-07-2.pdf |Format=PDF |KBytes=}}</ref>

=== Supply Chain Management ===
Viele Probleme des [[Transportproblem|Transports]], der optimalen Lagerbestände<ref>{{Literatur |Autor=Edward A. Silver, David F. Pyke, Douglas J. Thomas |Titel=Inventory and production management in supply chains |Auflage=4. |Verlag=CRC Press, Taylor & Francis Group |Ort=Boca Raton / FL London New York / NY |Datum=2021 |ISBN=978-1-03-217932-2}}</ref>, der [[Produktionsplanung und -steuerung|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 [[Lineare Optimierung|kontinuierliche lineare Optimierungsprobleme]] oder gemischt-ganzzahlige lineare Optimierungsprobleme.<ref>{{Literatur |Autor=Leena Suhl, Taïb Mellouli |Titel=Optimierungssysteme: Modelle, Verfahren, Software, Anwendungen |Reihe=Springer-Lehrbuch |Auflage=3., korrigierte und aktualisierte Aufl |Verlag=Springer Gabler |Ort=Berlin / Heidelberg |Datum=2013 |ISBN=978-3-642-38936-8 |DOI=10.1007/978-3-642-38937-5}}</ref>

=== 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 [[National Football League|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.<ref>{{Internetquelle |url=https://www.gurobi.com/case_studies/national-football-league-scheduling/ |titel=National Football League Scheduling |werk=Gurobi Optimization |sprache=en-US |abruf=2023-12-09}}</ref><ref>{{Literatur |Autor=Michael Pinedo |Titel=Scheduling: theory, algorithms, and systems |Auflage=5. |Verlag=Springer |Ort=Cham / Heidelberg / New York / Dordrecht / London |Datum=2018 |ISBN=978-3-319-79973-5}}</ref>

== {{Anker|Globale Optimierung}} Lösungskonzepte, lokale und globale Optimierung ==
[[Datei:Extrema example de.svg|mini|300x300px|Lokale und globale Minima und Maxima der Funktion <math>f(x)=\cos(3\pi x)/x</math> im Bereich <math>0{,}1 \le x \le 1{,}1</math>]]
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 <math>x^\star\in M</math> einer Minimierungsaufgabe gilt

<math display="block">f(x^\star)\ \le\ f(x)\qquad \forall x\in M,</math>

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 <math>x^\star\in M</math> die anderen zulässigen Punkte nur in einer [[Umgebung (Mathematik)|Umgebung]] <math>U(x^\star)</math> dominiert, wenn also gilt

<math display="block">f(x^\star)\ \le\ f(x)\qquad \forall x\in M\cap U(x^\star),</math>

so ist <math>x^\star</math> 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 Optimierung|konvexe Optimierungsprobleme]] sind alle lokale Optimalpunkte immer auch global optimal.<ref>{{Literatur |Autor=Stephen Boyd, Lieven Vandenberghe |Titel=Convex Optimization |Verlag=Cambridge University Press |Datum=2004 |ISBN=0-521-83378-7 |Online=https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf |Format=PDF |KBytes= |Abruf=2023-12-08}}</ref> Für nichtkonvexe Probleme werden in der lokalen Optimierung Lösungsmethoden der [[Nichtlineare Optimierung|nichtlinearen Optimierung]] zur effizienten Berechnung lokaler Optima eingesetzt.<ref>{{Literatur |Autor=Carl Geiger, Christian Kanzow |Titel=Theorie und Numerik restringierter Optimierungsaufgaben |Datum=2002 |DOI=10.1007/978-3-642-56004-0}}</ref> 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 Optimierung|gemischt-ganzzahlige Optimierungsprobleme]] eingesetzt werden.<ref>{{Literatur |Autor=Oliver Stein |Titel=Grundzüge der Globalen Optimierung |Datum=2021 |DOI=10.1007/978-3-662-62534-7}}</ref><ref name=":1" />

== Klassifikation von Optimierungsproblemen ==
{{Hauptartikel|Optimierungsproblem#Klassifikation von Optimierungsproblemen}}
Als bekannte Unterklassen der mathematischen Optimierung seien hier die [[Lineare Optimierung|(kontinuierliche) lineare Optimierung (LP)]], die [[ganzzahlige lineare Optimierung]] (ILP), die [[Nichtlineare Optimierung|(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|Optimierungsproblem (Klassifikation von Optimierungsproblemen]]).

== Optimierungsmethoden ==
Optimierungsmethoden sind [[Algorithmus|Algorithmen]], die zur Berechnung der Lösung von Optimierungsproblemen eingesetzt werden.

=== Methoden der kontinuierlichen linearen Optimierung ===
Bei einem [[Lineare Optimierung|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.<ref name=":2">{{Literatur |Autor=Robert E. Bixby |Titel=A brief history of linear and mixed-integer programming computation |Sammelwerk=Optimization Stories |Verlag=EMS Press |Datum=2012 |ISBN=978-3-936609-58-5 |Seiten=107–121 |Online=https://www.math.uni-bielefeld.de/documenta/vol-ismp/25_bixby-robert.pdf |Format=PDF |KBytes= |Abruf=2023-12-09}}</ref> 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.<ref>{{Internetquelle |url=https://www.gurobi.com/documentation/current/refman/method.html |titel=Method |werk=Gurobi Optimization |sprache=en |abruf=2023-12-09}}</ref>

=== 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 [[Schnittebenenverfahren|Schnittebenen]] (eng. ''cutting planes''), Presolve-Techniken<ref>{{Literatur |Autor=Tobias Achterberg, Robert E. Bixby, Zonghao Gu, Edward Rothberg, Dieter Weninger |Titel=Presolve Reductions in Mixed Integer Programming |Sammelwerk=INFORMS Journal on Computing |Band=32 |Nummer=2 |Datum=2020-04 |ISSN=1091-9856 |Seiten=473–506 |Online=https://opus4.kobv.de/opus4-zib/files/6037/Presolve.pdf |Format=PDF |KBytes= |Abruf=2023-12-09}}</ref> und Heuristiken in den letzten Jahrzehnten enorme Geschwindigkeitszuwächse verzeichnen konnten.<ref name=":2" /><ref>{{Internetquelle |url=https://www.youtube.com/watch?v=q8nQTNvCrjE |titel=William Cook: "Information, Computation, Optimization..." |sprache=de-DE |abruf=2023-12-09}}</ref> 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.

=== {{Anker|Algorithmen}} 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 [[Gradientenverfahren]]s und des [[Newtonverfahren]]s aufgreifen und erweitern. Die populärsten Methoden sind vermutlich das [[CG-Verfahren|Konjugierte-Gradienten-Verfahren]] sowie [[Quasi-Newton-Verfahren]], [[Trust-Region-Verfahren|Trust-Region-Methoden]] und der [[Levenberg-Marquardt-Algorithmus]]. Für restringierte nichtlineare Probleme kommen häufig [[SQP-Verfahren|SQP-Verfahren (Sequential-Quadratic-Programming-Verfahren)]], [[Innere-Punkte-Verfahren|Innere-Punkte-Methoden]] und Augmented-Lagrange-Verfahren zum Einsatz.<ref>{{Literatur |Autor=Jorge Nocedal, Stephen J. Wright |Titel=Numerical optimization |Reihe=Springer series in operation research and financial engineering |Auflage=2. |Verlag=Springer |Ort=New York |Datum=2006 |ISBN=0-387-30303-0}}</ref>

=== 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ä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 Konzepte ==
=== Notwendige Optimalitätsbedingungen ===

Notwendige [[Optimalitätskriterium|Optimalitätsbedingungen]] sind Bedingungen, die in einem Optimalpunkt [[Notwendige Bedingung|notwendigerweise]] erfüllt sein müssen.

In der unrestringierten nichtlinearen Optimierung einer [[Differenzierbarkeit|differenzierbaren]] Funktion <math>f\colon \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 Punkte 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 |ISBN=978-3-662-62531-6}}</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 |Reihe=Princeton Landmarks in mathematics and physics |Auflage=10. |Verlag=Princeton Univ. Press |Ort=Princeton, NJ |Datum=1997 |ISBN=0-691-08069-0}}</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 |Reihe=Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen |Auflage=3. |Verlag=Springer |Ort=Berlin / Heidelberg |Datum=2009 |ISBN=978-3-540-62772-2}}</ref><ref>{{Literatur |Titel=Nonsmooth analysis and control theory |Reihe=Graduate texts in mathematics |Verlag=Springer |Ort=New York / Heidelberg |Datum=1998 |ISBN=0-387-98336-8}}</ref>

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=3-540-42790-2}}</ref>

=== 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 |Seiten=268–285 |DOI=10.1137/0312021}}</ref>

== Auszüge aus der Geschichte der mathematischen Optimierung ==

=== Vor dem 20. Jahrhundert ===
[[Datei:Brachistochronerutschbahn.jpg|mini|Experimenteller Aufbau zur Brachistochrone im [[Technoseum]] in Mannheim]]
Schon die alten Griechen studierten Optimierungsprobleme mit geometrischem Bezug wie etwa [[Isoperimetrische Ungleichung#Das Problem der Dido|das Problem der Dido]]. Im Jahr 1696 formulierte [[Johann I Bernoulli|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 ===
[[Datei:IBM 701console.jpg|mini|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 Witaljewitsch Kantorowitsch|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.<ref>{{Literatur |Autor=George Dantzig |Titel=Linear Programming and Extensions |Datum=1963 |DOI= |Online= |Abruf=}}</ref>

In den 50er Jahren wechselte George Dantzig von der [[United States Air Force|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.<ref name=":2" /> 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 [[Ailsa Land|Alisa Land]] und [[Alison Harcourt|Alison Doig]] die Branch-and-Bound-Methode an der [[London School of Economics and Political Science|London School of Economics]] im Rahmen einer Zusammenarbeit mit [[BP|British Petroleum]]. Im Jahr 1979 zeigte [[Leonid Gendrichowitsch Chatschijan|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 Karmarkar]]s 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.<ref name=":2" /> Zeitgleich wurden neue Rekorde in der Berechnung nachweislich optimaler Routen für das [[Problem des Handlungsreisenden|Traveling Salesman Problem]], welches [[NP-Schwere|NP-schwer]] ist und damit als praktisch unlösbar galt. So wurde von Forschenden rund um [[William Cook (Mathematiker)|William J. Cook]] im Jahr 2006 eine TSP-Instanz mit 85900 Stationen global optimal gelöst.<ref>{{Literatur |Autor=David L. Applegate, Robert E. Bixby, Vasek Chvátal, William J. Cook |Titel=The traveling salesman problem: a computational study |Verlag=Princeton university press |Ort=Princeton (N.J.) |Datum=2006 |Reihe=Princeton series in applied mathematics |ISBN=978-0-691-12993-8 |Abruf=}}</ref> Der große Erfolg von Methoden des [[Maschinelles Lernen|Maschinellen Lernens]] erforderte in den 2010er Jahren die Entwicklung moderner Optimierungsmethoden für das Training großer [[Künstliches neuronales Netz|neuronaler Netze]]. Dies führte zur Wiederentdeckung und Weiterentwicklungen des stochastischen Gradientenverfahrens, wie etwa dem Adam-Algorithmus im Jahr 2014.<ref name=":4" />

=== 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.<ref>{{Internetquelle |autor=INFORMS |url=https://www.informs.org/Explore/History-of-O.R.-Excellence/O.R.-Methodologies/Optimization-Mathematical-Programming |titel=Optimization/Mathematical Programming |sprache=en-US |abruf=2023-12-11}}</ref>

== 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. [https://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.
* C. Grossmann, J. Terno: ''Numerik der Optimierung''. Teubner Studienbücher, 1997, ISBN 3-519-12090-9. {{Google Buch |BuchID=tBU8KIoB7KoC}}
* 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}}
* 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.

== Einzelnachweise ==
<references />

== Weblinks ==
{{Commonscat|Optimization}}
* {{DNB-Portal|4043664-0|TEXT=Literatur zur|NAME=Optimierung}}
* [https://www.neos-guide.org/Optimization-Guide NEOS Optimization Guide] (englisch)

{{Normdaten|TYP=s|GND=4043664-0|LCCN=|NDL=|VIAF=}}

[[Kategorie:Optimierung| ]]
[[Kategorie:Teilgebiet der Mathematik]]

Mathematische Optimierung - Versionsgeschichte

imported>Boehm: typog