Globale Optimierung - Global optimization

Globale Optimierung ist ein Zweig der angewandten Mathematik und numerischen Analysis , der versucht, die globalen Minima oder Maxima einer Funktion oder einer Menge von Funktionen auf einer gegebenen Menge zu finden. Es wird normalerweise als Minimierungsproblem bezeichnet, da die Maximierung der reellwertigen Funktion der Minimierung der Funktion entspricht . ${\displaystyle g(x)}$${\displaystyle f(x):=(-1)\cdot g(x)}$

Gegeben eine möglicherweise nichtlineare und nichtkonvexe stetige Funktion mit den globalen Minima und der Menge aller globalen Minimierer in , kann das Standard-Minimierungsproblem gegeben werden als ${\displaystyle f:\Omega\subset\mathbb{R}^{n}\to\mathbb{R}}$${\displaystyle f^{*}}$${\displaystyle X^{*}}$${\displaystyle \Omega}$

${\displaystyle \min_{x\in\Omega}f(x),}$

das heißt, das Finden und einen globalen Minimierer in ; wobei eine (nicht unbedingt konvexe) kompakte Menge durch Ungleichungen definiert ist . ${\displaystyle f^{*}}$${\displaystyle X^{*}}$${\displaystyle \Omega}$${\displaystyle g_{i}(x)\geqslant 0,i=1,\ldots,r}$

Die globale Optimierung unterscheidet sich von der lokalen Optimierung dadurch, dass sie sich darauf konzentriert, das Minimum oder Maximum über die gegebene Menge zu finden, im Gegensatz zum Finden lokaler Minima oder Maxima. Das Auffinden eines beliebigen lokalen Minimums ist mit klassischen lokalen Optimierungsmethoden relativ einfach . Das Auffinden des globalen Minimums einer Funktion ist weitaus schwieriger: Analytische Methoden sind häufig nicht anwendbar und der Einsatz numerischer Lösungsstrategien führt oft zu sehr harten Herausforderungen.

Allgemeine Theorie

Ein neuer Ansatz für das globale Optimierungsproblem ist die Minimaverteilung . In dieser Arbeit wurde eine Beziehung zwischen jeder stetigen Funktion auf einer kompakten Menge und ihren globalen Minima streng hergestellt. Als typischer Fall folgt, dass ${\displaystyle f}$${\displaystyle \Omega\subset\mathbb{R}^{n}}$${\displaystyle f^{*}}$

${\displaystyle \lim_{k\to\infty}\int_{\Omega}f(x)m^{(k)}(x)\,\mathrm {d} x=f^{*},~ ~{\textrm {wo}}~~m^{(k)}(x)={\frac {e^{-kf(x)}}{\int _{\Omega}e^{-kf(x )}\,\mathrm{d}x}};}$

in der Zwischenzeit,

${\displaystyle \lim_{k\to\infty}m^{(k)}(x)=\left\{{\begin{array}{cl}{\frac {1}{\mu(X^{ *})}},&x\in X^{*},\\0,&x\in \Omega -X^{*},\end{array}}\right.}$

wo ist das -dimensionale Lebesgue-Maß der Menge der Minimierer . Und wenn keine Konstante auf ist , ist die monotone Beziehung ${\displaystyle \mu(X^{*})}$${\displaystyle n}$${\displaystyle X^{*}\in \Omega}$${\displaystyle f}$${\displaystyle \Omega}$

${\displaystyle \int _{\Omega}f(x)m^{(k)}(x)\,\mathrm {d}x>\int _{\Omega}f(x)m^{(k+\ Delta k)}(x)\,\mathrm{d}x>f^{*}}$

gilt für alle und , was eine Reihe von monotonen Eindämmungsbeziehungen impliziert, und eine davon ist zum Beispiel ${\displaystyle k\in\mathbb{R}}$${\displaystyle \Delta k>0}$

${\displaystyle \Omega \supset D_{f}^{(k)}\supset D_{f}^{(k+\Upset k)}\supset X^{*},{\text{ where }}D_{f }^{(k)}=\links\{x\in\Omega :f(x)\leqslant \int _{\Omega}f(t)m^{(k)}(t)\,\mathrm { d} t\rechts\}.}$

Und wir definieren eine Minimaverteilung als schwache Grenze, so dass die Identität ${\displaystyle m_{f,\Omega}}$

${\displaystyle \int _{\Omega}m_{f,\Omega}(x)\varphi(x)\,\mathrm {d} x=\lim_{k\to\infty}\int _{\Omega }m^{(k)}(x)\varphi(x)\,\mathrm {d}x}$

hält für jede reibungslose Funktion mit kompakter Unterstützung in . Hier sind zwei unmittelbare Eigenschaften von : ${\displaystyle\varphi}$${\displaystyle \Omega}$${\displaystyle m_{f,\Omega}}$

(1) erfüllt die Identität .${\displaystyle m_{f,\Omega}}$${\displaystyle \int_{\Omega}m_{f,\Omega}(x)\,\mathrm {d} x=1}$

(2) Wenn kontinuierlich an ist , dann .${\displaystyle f}$${\displaystyle \Omega}$${\displaystyle f^{*}=\int_{\Omega}f(x)m_{f,\Omega}(x)\,\mathrm {d}x}$

Zum Vergleich: Die bekannte Beziehung zwischen jeder differenzierbaren konvexen Funktion und ihren Minima wird streng durch den Gradienten hergestellt. Wenn auf einer konvexen Menge differenzierbar ist , dann ist genau dann konvex, wenn ${\displaystyle f}$${\displaystyle D}$${\displaystyle f}$

${\displaystyle f(y)\geqslant f(x)+\nabla f(x)(yx),~~\forall x,y\in D;}$

impliziert also, dass für alle gilt , dh ein globaler Minimierer von on ist . ${\displaystyle \nabla f(x^{*})=0}$${\displaystyle f(y)\geqslant f(x^{*})}$${\displaystyle y\in D}$${\displaystyle x^{*}}$${\displaystyle f}$${\displaystyle D}$

Anwendungen

Typische Beispiele für globale Optimierungsanwendungen sind:

• Proteinstrukturvorhersage (Minimierung der Energie-/Freie-Energie-Funktion)
• Computergestützte Phylogenetik (z. B. Minimierung der Anzahl der Zeichentransformationen im Baum)
• Traveling-Salesman-Problem und elektrischer Schaltungsentwurf (Minimierung der Weglänge)
• Chemieingenieurwesen (z. B. Analyse der Gibbs-Energie )
• Sicherheitsnachweis, Sicherheitstechnik (z. B. von mechanischen Konstruktionen, Gebäuden)
• Worst-Case-Analyse
• Mathematische Probleme (z. B. die Kepler-Vermutung )
• Probleme beim Packen von Objekten (Konfigurationsdesign)
• Ausgangspunkt mehrerer Molekulardynamiksimulationen ist eine anfängliche Optimierung der Energie des zu simulierenden Systems.
• Gläser drehen
• Kalibrierung von Funkausbreitungsmodellen und vielen anderen Modellen in Naturwissenschaften und Technik
• Kurvenanpassung wie die nichtlineare Analyse der kleinsten Quadrate und andere Verallgemeinerungen, die zur Anpassung von Modellparametern an experimentelle Daten in Chemie, Physik, Biologie, Wirtschaft, Finanzen, Medizin, Astronomie und Ingenieurwesen verwendet werden.
• Planung der IMRT- Strahlentherapie

Deterministische Methoden

Die erfolgreichsten allgemeinen exakten Strategien sind:

Innere und äußere Näherung

Bei beiden Strategien wird die Menge, über die eine Funktion optimiert werden soll, durch Polyeder approximiert. In innerer Näherung sind die Polyeder in der Menge enthalten, während in äußerer Näherung die Polyeder die Menge enthalten.

Schnittebenenverfahren

Das Schnittebenenverfahren ist ein Überbegriff für Optimierungsverfahren, die eine zulässige Menge oder Zielfunktion mittels linearer Ungleichungen, sogenannten Schnitten, iterativ verfeinern . Solche Verfahren werden allgemein verwendet, um ganzzahlige Lösungen für Probleme der gemischt ganzzahligen linearen Programmierung (MILP) zu finden, sowie um allgemeine, nicht unbedingt differenzierbare konvexe Optimierungsprobleme zu lösen. Die Verwendung von Schnittebenen zur Lösung von MILP wurde von Ralph E. Gomory und Václav Chvátal eingeführt .

Verzweigungs- und gebundene Methoden

Branch and Bound ( BB oder B&B ) ist ein Algorithmusentwurfsparadigma für diskrete und kombinatorische Optimierungsprobleme . A Branch-and-Bound Algorithmus besteht aus einer systematischen Aufzählung der Kandidatenlösungen mittels Zustandsraum - Suche : Die Menge der Kandidatenlösungen gedacht wird , einen der als Formungs verwurzelten Baumes mit dem vollen Satz an der Wurzel. Der Algorithmus untersucht Zweige dieses Baums, die Teilmengen der Lösungsmenge darstellen. Vor dem Aufzählen der Kandidatenlösungen einer Verzweigung wird die Verzweigung gegen obere und untere geschätzte Schranken der optimalen Lösung geprüft und verworfen, wenn sie keine bessere Lösung als die bisher vom Algorithmus gefundene beste erzeugen kann.

Intervallmethoden

Intervallarithmetik , Intervallmathematik , Intervallanalyse oder Intervallberechnung ist eine seit den 1950er und 1960er Jahren von Mathematikern entwickelte Methode, um Rundungs- und Messfehler im mathematischen Rechnen einzugrenzen und so numerische Verfahren zu entwickeln , die zuverlässige Ergebnisse liefern. Intervallarithmetik hilft, zuverlässige und garantierte Lösungen für Gleichungen und Optimierungsprobleme zu finden.

Methoden basierend auf reeller algebraischer Geometrie

Die reelle Algebra ist der Teil der Algebra, der für die reelle algebraische (und semialgebraische) Geometrie relevant ist. Es befasst sich hauptsächlich mit dem Studium geordneter Körper und geordneter Ringe (insbesondere reeller geschlossener Körper ) und ihrer Anwendung auf das Studium positiver Polynome und Quadratsummen von Polynomen . Es kann in der konvexen Optimierung verwendet werden

Stochastische Methoden

Es gibt mehrere genaue oder ungenaue Monte-Carlo-basierte Algorithmen:

Direkte Monte-Carlo-Probenahme

Bei dieser Methode werden Zufallssimulationen verwendet, um eine Näherungslösung zu finden.

Beispiel: Das Handelsvertreterproblem ist ein sogenanntes konventionelles Optimierungsproblem. Das heißt, alle Fakten (Entfernungen zwischen jedem Zielpunkt), die zur Bestimmung des optimalen zu verfolgenden Pfads erforderlich sind, sind mit Sicherheit bekannt und das Ziel besteht darin, die möglichen Reiseoptionen durchzugehen, um die mit der geringsten Gesamtentfernung zu ermitteln. Nehmen wir jedoch an, dass wir, anstatt die zurückgelegte Gesamtentfernung zu jedem gewünschten Ziel zu minimieren, die Gesamtzeit minimieren wollten, die zum Erreichen jedes Ziels benötigt wird. Dies geht über die konventionelle Optimierung hinaus, da die Reisezeit von Natur aus ungewiss ist (Stau, Tageszeit usw.). Um unseren optimalen Weg zu bestimmen, möchten wir daher Simulation - Optimierung verwenden, um zuerst den Bereich der möglichen Zeiten zu verstehen, die es dauern könnte, um von einem Punkt zum anderen zu gelangen (in diesem Fall durch eine Wahrscheinlichkeitsverteilung und nicht durch eine bestimmte Entfernung dargestellt). und optimieren dann unsere Reiseentscheidungen, um den besten Weg zu ermitteln, der dieser Unsicherheit Rechnung trägt.

Stochastischer Tunnelbau

Stochastisches Tunneln (STUN) ist ein Ansatz zur globalen Optimierung basierend auf der Monte-Carlo-Methode – Abtasten der objektiv zu minimierenden Funktion, wobei die Funktion nichtlinear transformiert wird, um ein einfacheres Tunneln zwischen Regionen mit Funktionsminima zu ermöglichen. Ein einfacheres Tunneln ermöglicht eine schnellere Untersuchung des Probenraums und eine schnellere Konvergenz zu einer guten Lösung.

Paralleles Temperieren

Das parallele Tempern , auch bekannt als Replika-Austausch-MCMC-Sampling , ist ein Simulationsverfahren , das darauf abzielt, die dynamischen Eigenschaften von Monte-Carlo-Methodensimulationen von physikalischen Systemen und von Markov-Chain-Monte-Carlo- (MCMC)-Samplingmethoden im Allgemeinen zu verbessern . Die Replik Austauschverfahren ursprünglich von Swendsen, dann erweitert durch Geyer und später entwickelte unter anderem durch erdacht wurde Giorgio Parisi ., Sugita und Okamoto formuliert , um eine Molekulardynamik - Version parallel Anlassen: dies ist in der Regel als Replik-Austausch Molekulardynamik oder REMD bekannt .

Im Wesentlichen lässt man N Kopien des Systems, zufällig initialisiert, bei unterschiedlichen Temperaturen laufen . Dann tauscht man basierend auf dem Metropolis-Kriterium Konfigurationen bei unterschiedlichen Temperaturen aus. Die Idee dieser Methode ist, Konfigurationen bei hohen Temperaturen den Simulationen bei niedrigen Temperaturen zur Verfügung zu stellen und umgekehrt. Dies führt zu einem sehr robusten Ensemble, das sowohl nieder- als auch hochenergetische Konfigurationen abtasten kann. Auf diese Weise können thermodynamische Eigenschaften wie die spezifische Wärme, die im kanonischen Ensemble im Allgemeinen nicht gut berechnet wird, mit hoher Genauigkeit berechnet werden.

Heuristiken und Metaheuristiken

Hauptseite: Metaheuristik

Andere Ansätze umfassen heuristische Strategien, um den Suchraum auf mehr oder weniger intelligente Weise zu durchsuchen, einschließlich:

• Optimierung der Ameisenkolonie (ACO)
• Simuliertes Tempern , eine generische probabilistische Metaheuristik
• Tabu-Suche , eine Erweiterung der lokalen Suche , die lokale Minima umgehen kann
• Evolutionäre Algorithmen (z. B. genetische Algorithmen und Evolutionsstrategien )
• Differentielle Evolution , eine Methode, die ein Problem optimiert , indem iterativ versucht wird, eine Kandidatenlösung in Bezug auf ein gegebenes Qualitätsmaß zu verbessern
• Schwarmbasierte Optimierungsalgorithmen (z. B. Partikelschwarmoptimierung , sozialkognitive Optimierung , Multischwarmoptimierung und Ameisenkolonieoptimierung )
• Memetische Algorithmen , die globale und lokale Suchstrategien kombinieren
• Reaktive Suchoptimierung (dh Integration subsymbolischer maschineller Lerntechniken in Suchheuristiken)
• Abgestufte Optimierung , eine Technik, die versucht, ein schwieriges Optimierungsproblem zu lösen, indem zunächst ein stark vereinfachtes Problem gelöst und dieses Problem (während der Optimierung) schrittweise transformiert wird, bis es dem schwierigen Optimierungsproblem entspricht.

Response-Surface-Methodik-basierte Ansätze

• IOSO Indirekte Optimierung basierend auf Selbstorganisation
• Bayes'sche Optimierung , eine sequentielle Entwurfsstrategie zur globalen Optimierung von Black-Box-Funktionen mit Bayes'scher Statistik

Siehe auch

• Deterministische globale Optimierung
• Multidisziplinäre Designoptimierung
• Mehrzieloptimierung
• Optimierung (Mathematik)

Fußnoten

Verweise

Externe Links

• A. Neumaiers Seite zur globalen Optimierung
• Einführung in die globale Optimierung von L. Liberti
• Kostenloses E-Book von Thomas Weise