Optimierungsproblem

Im Mathematik, Informatik und Wirtschaft, ein Optimierungsproblem ist der Problem das finden Beste Lösung von allen realisierbare Lösungen.

Optimierungsprobleme können in zwei Kategorien unterteilt werden, je nachdem, ob die Variablen sind kontinuierlich oder diskret:

Ein Optimierungsproblem mit diskreten Variablen ist als Diskrete Optimierung, in welchem ein Objekt wie ein ganze Zahl, Permutation oder Graph muss von a gefunden werden Zählbar.
Ein Problem mit kontinuierlichen Variablen ist als continuous optimization, in dem ein optimaler Wert von a kontinuierliche Funktion muss gefunden werden. Sie können einschließen eingeschränkte Probleme und multimodale Probleme.

Problem mit kontinuierlichem Optimierung

Das Standardform von a kontinuierlich Optimierungsproblem ist^[1]

{\ displayStyle {\ begin {aligned} & {\ UnderSet {x} {\ operatorname {minimieren}}} && f (x) \\ & \ operatorname {subjekt \; to} && g_ {i} (x) \ leq 0, \ quad i = 1, \ dots, m \\ &&& h_ {j} (x) = 0, \ quad j = 1, \ dots, p \ end {ausgerichtet}}}}

wo

$f : ℝ n \to ℝ$ ist der Zielfunktion über die minimiert werden $n$ -Variabler Vektor $x$ ,
$g i (x) \leq 0$ werden genannt Ungleichheit Einschränkungen
$h j (x) = 0$ werden genannt Gleichheitsbeschränkungen, und
$m \geq 0$ und $p \geq 0$ .

Wenn $m = p = 0$ Das Problem ist ein nicht eingeschränktes Optimierungsproblem. Nach Übereinkommen definiert das Standardformular a Minimierungsproblem. EIN Maximierungsproblem kann behandelt werden von negieren die objektive Funktion.

Kombinatorisches Optimierungsproblem

Formal, a Kombinatorische Optimierung Problem $A$ ist ein Vierfach $(I, f, m, g)$ , wo

$I$ ist ein einstellen von Instanzen;
eine Instanz gegeben $x \in I$ , $f (x)$ ist der Satz von realisierbaren Lösungen;
eine Instanz gegeben $x$ und eine realisierbare Lösung $y$ von $x$ , $m (x, y)$ bezeichnet die messen von $y$ , was normalerweise a ist positiv real.
$g$ ist die Zielfunktion und ist entweder $Mindest$ oder $Max$ .

Das Ziel ist es dann, für einen Fall zu finden $x$ ein optimale Lösungdas heißt eine praktikable Lösung $y$ mit

{\ displayStyle m (x, y) = g \ links \ {m (x, y '): y' \ in f (x) \ rechts \}.}

Für jedes kombinatorische Optimierungsproblem gibt es eine entsprechende Entscheidungsproblem Das fragt, ob es eine praktikable Lösung für eine bestimmte Maßnahme gibt $m 0$ . Zum Beispiel, wenn es a gibt Graph $G$ das enthält Eckpunkte $u$ und $v$ Ein Optimierungsproblem könnte sein "einen Weg finden aus $u$ zu $v$ Das verwendet die wenigsten Kanten ". Dieses Problem könnte eine Antwort auf beispielsweise 4 haben. Ein entsprechendes Entscheidungsproblem wäre" Es gibt einen Weg von $u$ zu $v$ Das verwendet 10 oder weniger Kanten? "Dieses Problem kann mit einem einfachen" Ja "oder" Nein "beantwortet werden.

Auf dem Gebiet der NäherungsalgorithmenAlgorithmen sind so konzipiert, dass sie nahezu optimale Lösungen für harte Probleme finden. Die übliche Entscheidungsversion ist dann eine unzureichende Definition des Problems, da sie nur akzeptable Lösungen spezifiziert. Obwohl wir geeignete Entscheidungsprobleme einführen könnten, wird das Problem als Optimierungsproblem natürlicher charakterisiert.^[2]

Siehe auch

Zählproblem (Komplexität)- Art des Computerproblems
Designoptimierung
Ekellands Variationsprinzip
Funktionsproblem- Art des Computerproblems
Handschuhproblem
Unternehmensforschung- Disziplin in Bezug auf die Anwendung fortschrittlicher Analysemethoden
Zufriedenstellend- Kognitive Heuristik für die Suche nach einer akzeptablen Entscheidung - Das Optimum muss nicht gefunden werden, nur eine "gut genug" Lösung.
Suchproblem
Semi-infinite programming

Verweise

^ Boyd, Stephen P.; Vandenberghe, Lieven (2004). Konvexe Optimierung (PDF). Cambridge University Press. p. 129. ISBN 978-0-521-83378-3.
^ Ausiello, Giorgio; et al. (2003), Komplexität und Näherung (Korrigiert.), Springer, ISBN 978-3-540-65431-5

Externe Links

"Wie die Verkehrsformung die Netzwerkbandbreite optimiert". IPC. 12. Juli 2016. Abgerufen 13. Februar 2017.

[1] Boyd, Stephen P.; Vandenberghe, Lieven (2004). Konvexe Optimierung (PDF). Cambridge University Press. p. 129. ISBN 978-0-521-83378-3.

[Ausiello03-2] Ausiello, Giorgio; et al. (2003), Komplexität und Näherung (Korrigiert.), Springer, ISBN 978-3-540-65431-5

[1]

[2]

Konvexe Analyse und Variationsanalyse
Themen (Liste)	Choquet -Theorie Konvexe Geometrie Konvexe Optimierung Dualität Lagrange -Multiplikator Legendre -Transformation Lokal konvexer topologischer Vektorraum Simplex
Karten	Konvexes Konjugat Konkav (Abgeschlossen K- Logarithmisch Richtig Pseudo- Quasi-) Konvexe Funktion Invex function Legendre -Transformation Halbkontinuität Subderivativ
Hauptergebnisse (Liste)	Ekellands Variationsprinzip Fenchel -Moreau -Theorem Fenchel-Young-Ungleichheit Jensens Ungleichheit Hermite -Hadamard -Ungleichheit Krein -Milman -Theorem Mazurs Lemma Shapley–Folkman lemma Robinson-UseScu Simons Urescu
Sets	Konvexer Rumpf (Pseudo-) Konvexes Set Wirksame Domäne Epigraph Hypografie John Ellipsoid Zonotop
Serie	Konvexe Serie verwandt ((CS, LCS) -Sclosed, (CS, BCS) -Complete, (niedriger) idealerweise konvex, (Hx), und (HWx))
Dualität	Duales System Dualitätslücke Starke Dualität Schwache Dualität