Mathematische Optimierung

Mathematische Optimierung (Alternativ geschrieben Optimierung) oder Mathematische Programmierung ist die Auswahl eines besten Elements in Bezug auf ein Kriterium aus einigen verfügbaren Alternativen.^[1] Eine Art Optimierungsprobleme entstehen in allen quantitativen Disziplinen aus Informatik und Ingenieurwesen^[2] zu Unternehmensforschung und Wirtschaftund die Entwicklung von Lösungsmethoden war von Interesse an Mathematik seit Jahrhunderten.^[3]

Im einfachsten Fall eine Optimierungsproblem besteht aus Maximierung oder Minimierung a echte Funktion durch systematische Wahl Eingang Werte von innerhalb eines zulässigen Satzes und Berechnung der Wert der Funktion. Die Verallgemeinerung der Optimierungstheorie und -techniken auf andere Formulierungen bildet einen großen Bereich von angewandte Mathematik. Im Allgemeinen umfasst die Optimierung die Suche nach "besten verfügbaren" Werten einer Zielfunktion, die eine definierte Domain (oder Eingabe), einschließlich einer Vielzahl verschiedener Arten von objektiven Funktionen und verschiedenen Arten von Domänen.

Optimierungsprobleme

Ein Optimierungsproblem kann auf folgende Weise dargestellt werden:

Gegeben: a Funktion f: A → ℝ von einigen einstellen A zum reale Nummern

Gesucht: ein Element x₀ ∈ A so dass f(x₀) ≤ f(x) für alle x ∈ A ("Minimierung") oder so, dass f(x₀) ≥ f(x) für alle x ∈ A ("Maximierung").

Eine solche Formulierung wird als eine bezeichnet Optimierungsproblem oder ein Mathematisches Programmierungsproblem (Ein Begriff, der nicht direkt mit dem Zusammenhang mit Computerprogrammierung, aber immer noch in Gebrauch zum Beispiel in Lineares Programmieren - sehen Geschichte unter). Viele reale und theoretische Probleme können in diesem allgemeinen Rahmen modelliert werden.

Da das Folgende gültig ist

$oder ),}$

Es reicht aus, nur Minimierungsprobleme zu lösen. Die gegenteilige Perspektive der Berücksichtigung von nur Maximierungsproblemen wäre jedoch ebenfalls gültig.

Probleme, die mit dieser Technik in den Feldern von formuliert wurden Physik kann die Technik als beziehen Energie Minimierung, Apropos Wert der Funktion f als Darstellung der Energie der System Sein modelliert. Im maschinelles LernenEs ist immer notwendig, die Qualität eines Datenmodells kontinuierlich mit a zu bewerten Kostenfunktion Wenn ein Minimum einen Satz möglicherweise optimaler Parameter mit einem optimalen (niedrigsten) Fehler impliziert.

Typischerweise, A ist einige Teilmenge des Euklidischer Raum ℝⁿ, oft angegeben durch einen Satz von Einschränkungen, Gleichheiten oder Ungleichheiten, von denen die Mitglieder von A müssen befriedigen. Das Domain A von f wird genannt Suchraum oder der Auswahlset, während die Elemente von A werden genannt Kandidatenlösungen oder realisierbare Lösungen.

Die Funktion f wird unterschiedlich genannt, eine Zielfunktion, a verlustfunktion oder Kostenfunktion (Minimierung),^[4] a Nützlichkeitsfunktion oder Fitnessfunktion (Maximierung) oder, in bestimmten Bereichen, an Energiefunktion oder Energie funktional. Eine praktikable Lösung, die minimiert (oder maximiert, falls dies das Ziel ist) die objektive Funktion wird als als ein optimale Lösung.

In der Mathematik werden herkömmliche Optimierungsprobleme in der Regel in Bezug auf die Minimierung angegeben.

A Lokales Minimum x* ist definiert als ein Element, für das es einige gibt δ > 0 so dass

${\ displaystyle \ forall \ mathbf {x} \ in a \; {\ text {wobei}} \; \ links \ vert \ mathbf {x} -\ mathbf {x} ^{\ ast} \ rechts \ vert \ leqff {x} ^{\ ast} \ rechts \ vert \ leq \ Delta, \,}$

der Ausdruck f(x*) ≤ f(x) hält;

Das heißt, in einer Region herum x* Alle Funktionswerte sind größer oder gleich dem Wert bei diesem Element. Lokale Maxima sind ähnlich definiert.

Während ein lokales Minimum mindestens so gut ist wie alle Elemente in der Nähe, ist a globales Minimum ist mindestens so gut wie jedes realisierbare Element. Im Allgemeinen, es sei denn, die objektive Funktion ist konvex Bei einem Minimierungsproblem kann es mehrere lokale Minima geben. In einem Konvexes ProblemWenn es ein lokales Minimum gibt, das innen ist (nicht am Rande des Satzes realisierbarer Elemente), ist es auch das globale Minimum, aber ein nicht konvexes Problem kann mehr als ein lokales Minimum haben, das nicht alle global sein müssen.

Eine große Anzahl von Algorithmen zur Lösung der nicht konvexen Probleme - einschließlich der Mehrheit der im Handel erhältlichen Solver - kann nicht in der Lage sein, zwischen lokal optimalen Lösungen und global optimalen Lösungen zu unterscheiden und erstere als tatsächliche Lösungen für das ursprüngliche Problem zu behandeln. Globale Optimierung ist der Zweig von angewandte Mathematik und numerische Analyse Dies befasst sich mit der Entwicklung deterministischer Algorithmen, die in der Lage sind, die Konvergenz in der endlichen Zeit auf die tatsächliche optimale Lösung eines nicht konvexen Problems zu gewährleisten.

Notation

Optimierungsprobleme werden häufig mit besonderer Notation ausgedrückt. Hier sind einige Beispiele:

Mindest- und Maximalwert einer Funktion

Betrachten Sie die folgende Notation:

${\ displaystyle \ min _ {x \ in \ mathbb {r} \ \; \ links (x^{2} +1 \ rechts)}}$

Dies bezeichnet das Minimum Wert der Zielfunktion x² + 1, bei der Wahl x aus dem Satz von reale Nummern ℝ. Der Mindestwert in diesem Fall beträgt 1, der bei auftritt x = 0.

Ebenso die Notation

${\ displaystyle \ max _ {x \ in \ mathbb {r}} \; 2x}$

fragt nach dem Maximalwert der Zielfunktion 2x, wo x kann jede reelle Zahl sein. In diesem Fall gibt es kein solches Maximum, wie die objektive Funktion unbegrenzt ist, daher lautet die Antwort. "Unendlichkeit"oder" undefiniert ".

Optimale Eingabargumente

Betrachten Sie die folgende Notation:

$oder$

oder gleichwertig

$oder , -1].}$

Dies repräsentiert den Wert (oder die Werte) der Streit x in dem Intervall (−∞, −1] Das minimiert (oder minimiert) die objektive Funktion x² + 1 (Der tatsächliche Mindestwert dieser Funktion ist nicht das, wonach das Problem fragt). In diesem Fall lautet die Antwort x = –1, seit x = 0 ist nicht realisierbar, das heißt, es gehört nicht dem realisierbares Set.

Ähnlich,

$oder$

oder gleichwertig

$oder , 5], \; y \ in \ mathbb {r},},}$

repräsentiert die {x, y} Paar (oder Paare), die den Wert der objektiven Funktion maximieren (oder maximieren) x cos ymit der zusätzlichen Einschränkung, die x in der Pause liegen [–5,5] (Auch hier spielt der tatsächliche Maximalwert des Ausdrucks keine Rolle). In diesem Fall sind die Lösungen die Paare der Form {5, 2kπ} und {–5, (2)k + 1)π}, wo k reicht über alle Ganzzahlen.

Betreiber arg min und Arg Max werden manchmal auch geschrieben als Argmin und Argmax, und stehen für Argument des Minimums und Argument des Maximums.

Geschichte

Fermat und Lagrange Found Calculus-basierte Formeln zur Identifizierung von Optima während Newton und Gauß Vorgeschlagene iterative Methoden zur Bewegung zu einem Optimum.

Der Begriff "Lineares Programmieren"Für bestimmte Optimierungsfälle war es auf George B. Dantzig, obwohl ein Großteil der Theorie von eingeführt wurde von Leonid Kantorovich im Jahr 1939. (Programmierung In diesem Zusammenhang bezieht sich nicht auf Computerprogrammierung, aber kommt von der Verwendung von Programm vom US -Militär, um sich auf die vorgeschlagene Ausbildung zu beziehen und Logistik Zeitpläne, die die Probleme waren, die Dantzig zu diesem Zeitpunkt untersuchte.) Dantzig veröffentlichte die Simplex -Algorithmus im Jahr 1947 und und John von Neumann entwickelte die Theorie von Dualität im selben Jahr.

Andere bemerkenswerte Forscher in der mathematischen Optimierung umfassen Folgendes:

Hauptunterfelder

• Konvexe Programmierung Untersucht den Fall, wenn die objektive Funktion ist konvex (Minimierung) oder konkav (Maximierung) und der Einschränkungssatz ist konvex. Dies kann als spezieller Fall einer nichtlinearen Programmierung oder als Verallgemeinerung der linearen oder konvexen quadratischen Programmierung angesehen werden.
  • Lineares Programmieren (LP), eine Art konvexer Programmierung, untersucht den Fall, in dem die Zielfunktion f ist linear und die Einschränkungen werden nur unter Verwendung linearer Gleichheiten und Ungleichheiten angegeben. Ein solcher Einschränkungsset heißt a Polyeder oder ein Polytope Wenn es so ist begrenzt.
  • Kegelprogrammierung zweiter Ordnung (SOCP) ist ein konvexes Programm und enthält bestimmte Arten von quadratischen Programmen.
  • Semidefinite Programmierung (SDP) ist ein Unterfeld der konvexen Optimierung, bei dem sich die zugrunde liegenden Variablen befinden semidefinit Matrizen. Es ist eine Verallgemeinerung der linearen und konvexen quadratischen Programmierung.
  • Kegelprogrammierung ist eine allgemeine Form der konvexen Programmierung. LP, SOCP und SDP können alle als Kegelprogramme mit der entsprechenden Art von Kegel angesehen werden.
  • Geometrische Programmierung ist eine Technik, bei der objektive und Ungleichheitsbeschränkungen als ausgedrückt werden als Posynome und Gleichstellungsbeschränkungen als Monome Kann in ein konvexes Programm umgewandelt werden.
• Ganzzahlprogrammierung Studien lineare Programme, bei denen einige oder alle Variablen aufgenommen werden ganze Zahl Werte. Dies ist nicht konvex und im Allgemeinen viel schwieriger als die normale lineare Programmierung.
• Quadratische Programmierung Ermöglicht die Objektivfunktion quadratische Begriffe, während der realisierbare Satz mit linearen Gleichheiten und Ungleichheiten angegeben werden muss. Für bestimmte Formen des quadratischen Terms ist dies eine Art konvexer Programmierung.
• Bruchprogrammierung Studienoptimierung der Verhältnisse von zwei nichtlinearen Funktionen. Die spezielle Klasse konkaver Bruchprogramme kann in ein konvexes Optimierungsproblem umgewandelt werden.
• Nichtlineare Programmierung Untersucht den allgemeinen Fall, in dem die objektive Funktion oder die Einschränkungen oder beide nichtlineare Teile enthalten. Dies kann ein konvexes Programm sein oder nicht. Ob das Programm konvex ist, wirkt sich im Allgemeinen auf die Schwierigkeit aus, es zu lösen.
• Stochastische Programmierung untersucht den Fall, in dem einige der Einschränkungen oder Parameter abhängen zufällige Variablen.
• Robuste Optimierung ist wie die stochastische Programmierung ein Versuch, die Unsicherheit in den Daten zu erfassen, die dem Optimierungsproblem zugrunde liegen. Eine robuste Optimierung zielt darauf ab, Lösungen zu finden, die unter allen möglichen Erkenntnissen der durch einen Unsicherheitssatz definierten Unsicherheiten gültig sind.
• Kombinatorische Optimierung befasst sich mit Problemen, bei denen der Satz machbarer Lösungen diskret ist oder auf a reduziert werden kann diskret eines.
• Stochastische Optimierung wird mit zufälligen (verrückten) Funktionsmessungen oder zufälligen Eingaben im Suchprozess verwendet.
• Unendlich dimensionale Optimierung Untersucht den Fall, wenn der Satz realisierbarer Lösungen eine Untergruppe einer unendlichendimensional Raum, wie ein Funktionsraum.
• Heuristik und Metaheuristik Machen Sie nur wenige oder keine Annahmen über das Problem, das optimiert wird. Normalerweise garantiert die Heuristiken nicht, dass eine optimale Lösung gefunden werden muss. Andererseits werden Heuristiken verwendet, um ungefähre Lösungen für viele komplizierte Optimierungsprobleme zu finden.
• Einschränkung Zufriedenheit Untersucht den Fall, in dem die Zielfunktion f ist konstant (dies wird in verwendet künstliche Intelligenz, speziell in automatisierte Argumentation).
  • Einschränkungsprogrammierung ist ein Programmierparadigma, bei dem die Beziehungen zwischen Variablen in Form von Einschränkungen angegeben werden.
• Eine disjunktive Programmierung wird verwendet, wenn mindestens eine Einschränkung erfüllt sein muss, aber nicht alle. Es ist von besonderer Bedeutung bei der Planung.
• Space Mapping ist ein Konzept für die Modellierung und Optimierung eines technischen Systems zu High-Fidelity-Modellgenauigkeit, die einen geeigneten physikalisch aussagekräftigen groben oder aussagekräftigen oder aussagekräftigen oder Ersatzmodell.

In einer Reihe von Unterfeldern dienen die Techniken hauptsächlich zur Optimierung in dynamischen Kontexten (dh Entscheidungsfindung im Laufe der Zeit):

• Variationskalkül Befasst sich mit der Suche nach dem besten Weg, um ein Ziel zu erreichen, z. B. eine Oberfläche zu finden, deren Grenze eine bestimmte Kurve ist, aber mit dem geringsten Bereich.
• Optimale Kontrolle Die Theorie ist eine Verallgemeinerung des Kalküls von Variationen, die Kontrollpolitik einführen.
• Dynamische Programmierung ist der Ansatz zur Lösung des Stochastische Optimierung Problem mit stochastischen, zufälligen und unbekannten Modellparametern. Es untersucht den Fall, in dem die Optimierungsstrategie auf der Aufteilung des Problems in kleinere Unterprobleme beruht. Die Gleichung, die die Beziehung zwischen diesen Unterproblemen beschreibt Bellman -Gleichung.
• Mathematische Programmierung mit Gleichgewichtsbeschränkungen Zu den Einschränkungen gehören Variationsungleichheiten oder Komplementaritäten.

Mehrzieloptimierung

Das Hinzufügen von mehr als einem Ziel zu einem Optimierungsproblem ergibt Komplexität. Um beispielsweise ein strukturelles Design zu optimieren, würde man sich ein Design wünschen, das sowohl leicht als auch starr ist. Wenn zwei Ziele konflikt, muss ein Kompromiss erstellt werden. Es kann ein leichteste Design, ein steifestes Design und eine unendliche Anzahl von Designs geben, die einen Kompromiss von Gewicht und Steifigkeit darstellen. Die Reihe von Kompromissentwürfen, die ein Kriterium auf Kosten eines anderen verbessern, wird als die bezeichnet Pareto -Set. Die Kurve erzeugte das Auftreten von Gewicht gegen Steifheit der besten Designs ist als die bekannt als die Pareto Frontier.

Ein Design wird als "pareto optimal" (gleichwertig, "pareto effizient" oder im Pareto -Set) beurteilt, wenn es nicht von einem anderen Design dominiert wird: Wenn es in gewisser Hinsicht schlechter ist als ein anderes Design und in irgendeiner Hinsicht nicht besser. Dann wird es dominiert und nicht pareto optimal.

Die Wahl zwischen "Pareto Optimal" -Lösungen zur Bestimmung der "Lieblingslösung" wird an den Entscheidungsträger delegiert. Mit anderen Worten, das Problem als Multi-Objektiv-Optimierungsoptimierungs zu definieren, werden einige Informationen fehlen In einigen Fällen können die fehlenden Informationen durch interaktive Sitzungen mit dem Entscheidungsträger abgeleitet werden.

Multi-Objektivoptimierungsprobleme wurden weiter verallgemeinert auf Vektoroptimierung Probleme, bei denen die (teilweise) Bestellung nicht mehr durch die Pareto -Bestellung angegeben wird.

Multimodale oder globale Optimierung

Optimierungsprobleme sind häufig multimodal; Das heißt, sie besitzen mehrere gute Lösungen. Sie könnten alle global gut sein (gleiche Kostenfunktionswert) oder es könnte eine Mischung aus global guten und lokal guten Lösungen geben. Das Erhalten aller (oder zumindest einige) der Mehrfachlösungen ist das Ziel eines multimodalen Optimierers.

Klassische Optimierungstechniken aufgrund ihres iterativen Ansatzes funktionieren nicht zufriedenstellend, wenn sie verwendet werden, um mehrere Lösungen zu erhalten, da nicht garantiert ist, dass verschiedene Lösungen auch mit unterschiedlichen Ausgangspunkten in mehreren Läufen des Algorithmus erhalten werden.

Häufige Ansätze an Globale Optimierung Probleme, bei denen mehrere lokale Extrema vorhanden sein können Evolutionsalgorithmen, Bayes'sche Optimierung und simuliertes Glühen.

Klassifizierung kritischer Punkte und Extrema

Machbarkeitsproblem

Das Erfüllbarkeitsproblem, auch die genannt Machbarkeitsproblem, ist nur das Problem, eines zu finden machbare Lösung überhaupt ohne Rücksicht auf den objektiven Wert. Dies kann als Sonderfall einer mathematischen Optimierung angesehen werden, bei der der objektive Wert für jede Lösung gleich ist, und daher ist jede Lösung optimal.

Viele Optimierungsalgorithmen müssen von einem praktikablen Punkt aus beginnen. Eine Möglichkeit, einen solchen Punkt zu erhalten, ist zu Entspannen Sie sich die Machbarkeitsbedingungen mit a Slack Variable; Bei genügend Lack ist jeder Ausgangspunkt machbar. Wenn die Slack null oder negativ ist, minimieren Sie dann diese Slack -Variable.

Existenz

Das Extremwert -Theorem von Karl Weierstrass Gibt an, dass eine kontinuierliche realvaluierte Funktion auf einem kompakten Satz ihren maximalen und minimalen Wert erreicht. Im Allgemeinen erreicht eine niedrigere halbkontinuierliche Funktion auf einem kompakten Satz ihr Minimum; Eine obere halbkontinuierliche Funktion eines kompakten Satzes erreicht ihren maximalen Punkt oder ihre maximale Ansicht.

Notwendige Bedingungen für Optimalität

Eine von Fermats Theoreme stellt fest, dass Optima von nicht eingeschränkten Problemen bei gefunden wird Stationäre Punkte, wo das erste Ableitungsgrad oder der Gradient der objektiven Funktion Null ist (siehe Erster Ableitungstest). Allgemeiner können sie bei gefunden werden kritische Punkte, wo der erste Derivat oder der Gradient der objektiven Funktion Null oder undefiniert ist oder an der Grenze des Auswahlsatzes. Eine Gleichung (oder eine Reihe von Gleichungen), die besagt, dass das erste Ableitungsmittel (s) gleich (s) Null bei einem inneren Optimum als „Bedingungen erster Ordnung“ oder als Set von Bedingungen erster Ordnung bezeichnet wird.

Optima der gleichheitlich begrenzten Probleme kann von der gefunden werden Lagrange -Multiplikator Methode. Das Optima an Problemen mit Gleichheit und/oder Ungleichheitsbeschränkungen kann mit der 'angegeben werden.Karush -Kuhn -Tucker -Bedingungen'.

Ausreichende Bedingungen für Optimalität

Während der erste Ableitungstest Punkte identifiziert, die möglicherweise extrem sind, unterscheidet dieser Test keinen Punkt, der ein Minimum von einem ist, das maximal oder keines ist. Wenn die Objektivfunktion zweimal differenzierbar ist, können diese Fälle durch Überprüfen der zweiten Ableitung oder der Matrix der zweiten Derivate (genannt der genannt Hessische Matrix) Bei nicht eingeschränkten Problemen oder der Matrix der zweiten Ableitungen der objektiven Funktion und der Einschränkungen, die als die genannt werden Grenze Hessian in eingeschränkten Problemen. Die Bedingungen, die Maxima oder Minima von anderen stationären Punkten unterscheiden, werden als "Bedingungen zweiter Ordnung" bezeichnet (siehe "Zweiter Ableitungstest'). Wenn eine Kandidatenlösung die Bedingungen erster Ordnung erfüllt, reicht auch die Zufriedenheit der Bedingungen zweiter Ordnung aus, um mindestens lokale Optimalität festzustellen.

Empfindlichkeit und Kontinuität von Optima

Das Umschlag Theorem beschreibt, wie sich der Wert einer optimalen Lösung bei einem zugrunde liegenden ändert Parameter Änderungen. Der Berechnungsprozess dieser Änderung wird genannt Vergleichende Statistiken.

Das Maximaler Satz von Claude Berge (1963) beschreibt die Kontinuität einer optimalen Lösung als Funktion der zugrunde liegenden Parameter.

Optimierungskalkül

Für nicht eingeschränkte Probleme mit zweimal differenzierbaren Funktionen, einige andere kritische Punkte kann gefunden werden, indem die Punkte finden, an denen die Gradient der objektiven Funktion ist Null (dh die stationären Punkte). Allgemeiner eine Null subgradient bescheinigt, dass ein lokales Minimum für gefunden wurde Minimierungsprobleme mit konvex Funktionen und andere örtlich Lipschitz Funktionen.

Darüber hinaus können kritische Punkte mit dem klassifiziert werden Bestimmtheit des Hessische Matrix: Wenn der Hessische ist positiv An einem kritischen Punkt definitiv ist der Punkt ein lokales Minimum; Wenn die hessische Matrix negativ ist, ist der Punkt ein lokales Maximum; Schließlich ist der Punkt eine Art von unbestimmte Zeit Sattelpunkt.

Eingeschränkte Probleme können oft mit Hilfe von nicht eingeschränkten Problemen umgewandelt werden Lagrange -Multiplikatoren. Lagrange -Entspannung kann auch ungefähre Lösungen für schwierige eingeschränkte Probleme liefern.

Wenn die objektive Funktion a ist Konvexe Funktiondann wird ein lokales Minimum auch ein globales Minimum sein. Es gibt effiziente numerische Techniken, um konvexe Funktionen zu minimieren, wie z. Innenpunktmethoden.

Globale Konvergenz

Wenn die Objektivfunktion keine quadratische Funktion ist, verwenden viele Optimierungsmethoden andere Methoden, um sicherzustellen, dass eine gewisse Subsequenz der Iterationen zu einer optimalen Lösung konvergiert. Die erste und noch beliebte Methode zur Sicherstellung der Konvergenz hängt davon ab Zeilensuche, die eine Funktion entlang einer Dimension optimieren. Eine zweite und immer beliebtere Methode zur Gewährleistung der Konvergenz verwendet Vertrauensregionen. Bei modernen Methoden von werden sowohl Zeilensuche als auch Vertrauensregionen verwendet Nicht differenzierbare Optimierung. Normalerweise ist ein globaler Optimierer viel langsamer als fortgeschrittene lokale Optimierer (wie z. BFGS), so oft kann ein effizienter globaler Optimierer konstruiert werden, indem der lokale Optimierer aus verschiedenen Ausgangspunkten gestartet wird.

Computeroptimierungstechniken

Um Probleme zu lösen, können Forscher verwenden Algorithmen das endet in einer begrenzten Anzahl von Schritten oder iterative Methoden das konvergiert zu einer Lösung (bei einigen festgelegten Problemen) oder Heuristik Dies kann ungefähre Lösungen für einige Probleme liefern (obwohl ihre Iteraten nicht konvergieren müssen).

Optimierungsalgorithmen

• Simplex -Algorithmus von George Dantzig, designed für Lineares Programmieren
• Erweiterungen des Simplex -Algorithmus, ausgelegt für Quadratische Programmierung und für Linear-Fraktion-Programmierung
• Varianten des Simplex -Algorithmus, die besonders geeignet sind Netzwerkoptimierung
• Kombinatorische Algorithmen
• Quantenoptimierungsalgorithmen

Iterative Methoden

Das iterative Methoden verwendet, um Probleme von zu lösen Nichtlineare Programmierung unterscheiden sich je nach ob sie auswerten Hesser, Gradienten oder nur Funktionswerte. Während die Bewertung der Hessianer (H) und Gradienten (G) die Konvergenzrate für Funktionen, für die diese Größen existieren Rechenkomplexität (oder Rechenkosten) jeder Iteration. In einigen Fällen kann die Rechenkomplexität übermäßig hoch sein.

Ein Hauptkriterium für Optimierer ist nur die Anzahl der erforderlichen Funktionsbewertungen, da dies häufig bereits ein großer Rechenaufwand ist, der normalerweise viel mehr Aufwand als innerhalb des Optimierers selbst ist, was hauptsächlich über die N -Variablen arbeiten muss. Die Derivate liefern detaillierte Informationen für solche Optimierer, sind jedoch noch schwerer zu berechnen, z. Das Approximieren des Gradienten erfordert mindestens N+1 -Funktionsbewertungen. Für Annäherungen der 2. Derivate (in der hessischen Matrix gesammelt) liegt die Anzahl der Funktionsbewertungen in der Größenordnung von n². Die Newton-Methode erfordert die Derivate der 2. Ordnung, daher ist für jede Iteration die Anzahl der Funktionsaufrufe in der Reihenfolge von N². Für einen einfacheren reinen Gradientenoptimierer ist es jedoch nur N. Die Gradientenoptimierer benötigen jedoch normalerweise mehr Iterationen als Newtons Algorithmus. Welches in Bezug auf die Anzahl der Funktionsaufrufe am besten ist, hängt vom Problem selbst ab.

• Methoden, die Hessianer bewerten (oder ungefähre Hessianer verwenden, verwenden endliche Unterschiede):
  • Newtons Methode
  • Sequentielle quadratische Programmierung: Eine Newton-basierte Methode für die Skala mit kleinem Medium eingeschränkt Probleme. Einige Versionen können mit großdimensionalen Problemen umgehen.
  • Innenpunktmethoden: Dies ist eine große Klasse von Methoden zur eingeschränkten Optimierung, von denen einige nur (Sub-) Gradienteninformationen verwenden, und andere erfordern die Bewertung von Hessiern.
• Methoden, die Gradienten bewerten oder Gradienten in irgendeiner Weise (oder sogar untergradierenden) annähern:
  • Abstieg koordinieren Methoden: Algorithmen, die eine einzelne Koordinate in jeder Iteration aktualisieren
  • Konjugate Gradientenmethoden: Iterative Methoden für große Probleme. (Theoretisch enden diese Methoden in einer begrenzten Anzahl von Schritten mit quadratischen objektiven Funktionen, diese endliche Beendigung wird jedoch in der Praxis nicht auf Finite -Prescision -Computern beobachtet.)
  • Gradientenabstieg (Alternativ "steilste Abstammung" oder "steilster Aufstieg"): Eine (langsame) Methode des historischen und theoretischen Interesses, das das Interesse für die Suche nach ungefähren Lösungen von enormen Problemen erneuert hat.
  • Subgradient -Methoden: Eine iterative Methode für große örtlich Lipschitz Funktionen Verwendung Verallgemeinerte Gradienten. Nach Boris T. Polyak ähneln Subgradient -Projection -Methoden den Konjugat -Gradient -Methoden.
  • Bündelmethode der Abstieg konvexe Minimierung Probleme (ähnlich wie konjugierte Gradientenmethoden).
  • Ellipsoid -Methode: Eine iterative Methode für kleine Probleme mit Quasiconvex Objektivfunktionen und großes theoretisches Interesse, insbesondere bei der Festlegung der Polynomzeitkomplexität einiger kombinatorischer Optimierungsprobleme. Es hat Ähnlichkeiten mit Quasi-Newton-Methoden.
  • Bedingte Gradientenmethode (Frank -Wolfe) Zur ungefähren Minimierung speziell strukturierter Probleme mit linearen Einschränkungen, insbesondere bei Verkehrsnetzwerken. Bei allgemeinen nicht eingeschränkten Problemen reduziert sich diese Methode auf die Gradientenmethode, die als veraltet angesehen wird (für fast alle Probleme).
  • Quasi-Newton-Methoden: Iterative Methoden für mittelgroße Probleme (z. B. n <1000).
  • Gleichzeitige Störungsstörungen stochastische Näherung (SPSA) -Methode zur stochastischen Optimierung; Verwendet eine zufällige (effiziente) Gradientenannäherung.
• Methoden, die nur Funktionswerte bewerten: Wenn ein Problem kontinuierlich differenzierbar ist, können Gradienten mithilfe endlicher Unterschiede angenähert werden. In diesem Fall kann eine gradientenbasierte Methode verwendet werden.
  • Interpolation Methoden
  • Mustersuche Methoden, die bessere Konvergenzeigenschaften haben als die Nelder -Mead Heuristic (mit Vereinfachungen), was unten aufgeführt ist.
  • Spiegelabstieg

Heuristik

Außerdem (endlich enden) Algorithmen und (konvergent) iterative Methoden, es gibt Heuristik. Eine Heuristik ist ein Algorithmus, der (mathematisch) nicht garantiert ist, um die Lösung zu finden, aber in bestimmten praktischen Situationen dennoch nützlich ist. Liste einiger bekannter Heuristiken:

Anwendungen

Mechanik

Probleme in Starrkörperdynamik (Insbesondere artikulierte starre Körperdynamik) erfordern häufig mathematische Programmierungstechniken, da Sie die starre Körperdynamik als Versuch betrachten können, eine zu lösen gewöhnliche Differentialgleichung auf einer Einschränkung.^[5] Die Einschränkungen sind verschiedene nichtlineare geometrische Einschränkungen wie "Diese beiden Punkte müssen immer zusammenfallen", "diese Oberfläche darf in keiner anderen eindringen" oder "dieser Punkt muss immer irgendwo auf dieser Kurve liegen". Außerdem kann das Problem der Berechnung von Kontaktkräften durch Lösen von a durchgeführt werden Lineares Komplementaritätsproblem, die auch als QP -Problem (quadratische Programmierung) angesehen werden können.

Viele Designprobleme können auch als Optimierungsprogramme ausgedrückt werden. Diese Anwendung wird als Designoptimierung bezeichnet. Eine Teilmenge ist die Engineering -Optimierungund eine weitere jüngste und wachsende Untergruppe dieses Feldes ist Multidisziplinäre Designoptimierung, was zwar in vielen Problemen nützlich ist, aber insbesondere auf angewendet wurde Raumfahrttechnik Probleme.

Dieser Ansatz kann in Kosmologie und Astrophysik angewendet werden.^[6]

Wirtschaft und Finanzen

Wirtschaft ist eng genug mit der Optimierung von verbunden Agenten dass eine einflussreiche Definition die Ökonomie zuletzt beschreibt qua Wissenschaft als "Studium des menschlichen Verhaltens als Beziehung zwischen den Enden und spärlich bedeutet "mit alternativen Verwendungen.^[7] Die moderne Optimierungstheorie umfasst die traditionelle Optimierungstheorie, überschneidet sich aber auch mit Spieltheorie und das Studium der Wirtschaftlichkeit Gleichgewichte. Das Journal of Economic Literature Codes Klassifizieren Sie die mathematische Programmierung, Optimierungstechniken und verwandte Themen unter Jel: C61-C63.

In der Mikroökonomie die Nützlichkeitsmaximierungsproblem und sein Dual Problem, das Ausgabenminimierungsproblem, sind wirtschaftliche Optimierungsprobleme. Soweit sie sich konsequent verhalten, Verbraucher werden angenommen, um ihre zu maximieren Dienstprogramm, während Firmen werden normalerweise angenommen, um ihre zu maximieren profitieren. Außerdem werden Agenten oft als Sein modelliert risikoaverseDadurch bevorzugt es, Risiken zu vermeiden. Vermögenspreise werden auch unter Verwendung der Optimierungstheorie modelliert, obwohl die zugrunde liegende Mathematik auf der Optimierung beruht stochastische Prozesse eher als auf statische Optimierung. Internationale Handelstheorie Verwendet auch Optimierung, um Handelsmuster zwischen den Nationen zu erklären. Die Optimierung von Portfolios ist ein Beispiel für eine multi-objektive Optimierung in der Ökonomie.

Seit den 1970er Jahren haben Ökonomen dynamische Entscheidungen im Laufe der Zeit modelliert Kontrolltheorie.^[8] Zum Beispiel dynamisch Suchmodelle werden zum Studium verwendet Arbeitsmarktverhalten.^[9] Eine entscheidende Unterscheidung besteht zwischen deterministischen und stochastischen Modellen.^[10] Makroökonomisten bauen Dynamisches stochastisches allgemeines Gleichgewicht (DSGE) Modelle, die die Dynamik der gesamten Wirtschaft als Ergebnis der voneinander abhängigen Optimierungsentscheidungen von Arbeitnehmern, Verbrauchern, Investoren und Regierungen beschreiben.^[11][12]

Elektrotechnik

Einige häufige Anwendungen von Optimierungstechniken in Elektrotechnik enthalten aktiver Filter Entwurf,^[13] Verringerung des streunenden Feldes in supraleitenden magnetischen Energiespeichersystemen, Space Mapping Design von Mikrowelle Strukturen,^[14] Mobilteilantennen,^[15][16][17] Elektromagnetisches Design. Elektromagnetisch validierte Designoptimierung von Mikrowellenkomponenten und Antennen hat eine ausführliche Verwendung einer geeigneten physikbasierten oder empirischen Verwendung genutzt Ersatzmodell und Space Mapping Methoden seit der Entdeckung von Space Mapping 1993.^[18][19]

Tiefbau

Die Optimierung wurde im Bauingenieurwesen häufig eingesetzt. Bauleitung und Verkehrstechnik gehören zu den Hauptzweigen der Bauingenieurwesen, die stark auf die Optimierung beruhen. Die häufigsten Probleme mit dem Bauingenieurwesen, die durch Optimierung gelöst werden, werden von Straßen geschnitten und gefüllt, Lebenszyklusanalyse von Strukturen und Infrastrukturen,^[20] Ressourcenniveau,^[21][22] Wasserressourcenzuweisung, Verkehr Management^[23] und Zeitplanoptimierung.

Unternehmensforschung

Ein weiteres Feld, das ausgiebig Optimierungstechniken verwendet, ist Unternehmensforschung.^[24] Operationsforschung verwendet auch stochastische Modellierung und Simulation, um eine verbesserte Entscheidungsfindung zu unterstützen. Zunehmend nutzt Operations Research Stochastische Programmierung dynamische Entscheidungen zu modellieren, die sich an Ereignisse anpassen; Solche Probleme können mit groß angelegter Optimierung gelöst werden und Stochastische Optimierung Methoden.

Steuerungstechnik

Die mathematische Optimierung wird für viel modernes Controller -Design verwendet. Hochrangige Controller wie z. Modellvorhersagekontrolle (MPC) oder Echtzeitoptimierung (RTO) verwenden mathematische Optimierung. Diese Algorithmen werden online ausgeführt und bestimmen wiederholt Werte für Entscheidungsvariablen, wie z. B. Choke -Öffnungen in einer Prozessanlage, indem ein Problem der mathematischen Optimierung iterativ gelöst wird, einschließlich Einschränkungen und einem Modell des zu kontrollierten Systems.

Geophysik

Optimierungstechniken werden regelmäßig in verwendet geophysisch Parameterschätzungsprobleme. Bei einer Reihe von geophysikalischen Messungen, z. seismische AufzeichnungenEs ist üblich, für die zu lösen physikalische Eigenschaften und geometrische Formen der zugrunde liegenden Felsen und Flüssigkeiten. Die meisten Probleme in der Geophysik sind nichtlinear, wobei sowohl deterministische als auch stochastische Methoden weit verbreitet sind.

Molekulare Modellierung

Nichtlineare Optimierungsmethoden sind in großer Bedeutung in Konformationsanalyse.

Biologie der Computersysteme

Optimierungstechniken werden in vielen Facetten der Biologie der Computersysteme verwendet, wie z. B. Modellbuilding, optimales experimentelles Design, Stoffwechseltechnik und synthetische Biologie.^[25] Lineares Programmieren wurde angewendet, um die maximal möglichen Ausbeuten von Fermentationsprodukten zu berechnen,^[25] und um Genregulierungsnetzwerke aus mehreren Microarray -Datensätzen zu schließen^[26] sowie Transkriptionsregulierungsnetze aus Hochdurchsatzdaten.^[27] Nichtlineare Programmierung wurde verwendet, um den Energiestoffwechsel zu analysieren^[28] und wurde zur Schätzung des Stoffwechseltechnik und der Parameterabschätzung in biochemischen Wegen angewendet.^[29]

Maschinelles Lernen

Löser

Siehe auch

Anmerkungen

Weitere Lektüre

• Boyd, Stephen P.; Vandenberghe, Lieven (2004). Konvexe Optimierung. Cambridge: Cambridge University Press. ISBN 0-521-83378-7.
• Gill, P. E.; Murray, W.; Wright, M. H. (1982). Praktische Optimierung. London: Akademische Presse. ISBN 0-12-283952-8.
• Lee, Jon (2004). Ein erster Kurs in kombinatorischer Optimierung. Cambridge University Press. ISBN 0-521-01012-8.
• Nozedal, Jorge; Wright, Stephen J. (2006). Numerische Optimierung (2. Aufl.). Berlin: Springer. ISBN 0-387-30303-0.
• Snyman, J. A.; Wilke, D. N. (2018). Praktische mathematische Optimierung: grundlegende Optimierungstheorie und gradientenbasierte Algorithmen (2. Aufl.). Berlin: Springer. ISBN 978-3-319-77585-2.

Externe Links

• "Entscheidungsbaum für Optimierungssoftware". Links zu Optimierungsquellcodes
• "Globale Optimierung".
• "EE364A: Konvexe Optimierung I". Kurs von der Stanford University.
• Varoquaux, Gaël. "Mathematische Optimierung: Minima von Funktionen finden".