Viele Algorithmen der nicht-zwanghaften Optimierung können an den zwanghaften Fall angepasst werden, oft durch die Verwendung einer Strafmethode. Allerdings können die Suchschritte, die von der ungebundenen Methode unternommen werden, für das gebundene Problem inakzeptabel sein, was zu einem Mangel an Konvergenz führt. Dies wird als Maratos-Effekt bezeichnet.
GleichheitsbedingungenBearbeiten
SubstitutionsmethodeBearbeiten
Für sehr einfache Probleme, z. B. eine Funktion von zwei Variablen, die einer einzigen Gleichheitsbedingung unterliegen, ist es am praktischsten, die Substitutionsmethode anzuwenden. Die Idee ist, die Bedingung in der Zielfunktion zu ersetzen, um eine zusammengesetzte Funktion zu erstellen, die die Wirkung der Bedingung einschließt. Nehmen wir zum Beispiel an, das Ziel sei die Maximierung von f ( x , y ) = x ⋅ y {\displaystyle f(x,y)=x\cdot y}
in Abhängigkeit von x + y = 10 {\displaystyle x+y=10}
. Die Nebenbedingung impliziert y = 10 – x {\displaystyle y=10-x}
, was in die Zielfunktion eingesetzt werden kann, um p ( x ) = x ( 10 – x ) = 10 x – x 2 {\displaystyle p(x)=x(10-x)=10x-x^{2}}
. Die notwendige Bedingung erster Ordnung ergibt ∂ p ∂ x = 10 – 2 x = 0 {\displaystyle {\frac {\partial p}{\partial x}}=10-2x=0}
, die für x = 5 {\displaystyle x=5} gelöst werden kann
und demzufolge y = 10 – 5 = 5 {\displaystyle y=10-5=5}
.
Lagrange-MultiplikatorBearbeiten
Wenn das beschränkte Problem nur Gleichheitsbedingungen hat, kann die Methode der Lagrange-Multiplikatoren verwendet werden, um es in ein ungebundenes Problem umzuwandeln, dessen Anzahl der Variablen die ursprüngliche Anzahl der Variablen plus die ursprüngliche Anzahl der Gleichheitsbedingungen ist. Wenn die Nebenbedingungen alle Gleichheitsbedingungen sind und alle linear sind, können sie für einige der Variablen in Form der anderen gelöst werden, und die ersteren können aus der Zielfunktion ersetzt werden, so dass ein ungebundenes Problem mit einer geringeren Anzahl von Variablen übrig bleibt.
UngleichheitsbeschränkungenBearbeiten
Mit Ungleichheitsbeschränkungen kann das Problem durch die geometrischen Optimalitätsbedingungen, die Fritz-John-Bedingungen und die Karush-Kuhn-Tucker-Bedingungen charakterisiert werden, unter denen einfache Probleme lösbar sein können.
Lineare ProgrammierungEdit
Wenn die Zielfunktion und alle harten Nebenbedingungen linear sind und einige harte Nebenbedingungen Ungleichungen sind, dann ist das Problem ein lineares Programmierproblem. Dies kann durch die Simplex-Methode gelöst werden, die in der Regel in polynomialer Zeit in der Problemgröße arbeitet, aber nicht garantiert ist, oder durch Innenpunktmethoden, die garantiert in polynomialer Zeit arbeiten.
Nichtlineare ProgrammierungEdit
Wenn die Zielfunktion oder einige der Nebenbedingungen nichtlinear sind und einige Nebenbedingungen Ungleichungen sind, dann ist das Problem ein nichtlineares Programmierproblem.
Quadratische ProgrammierungBearbeiten
Wenn alle harten Nebenbedingungen linear und einige Ungleichungen sind, aber die Zielfunktion quadratisch ist, dann ist das Problem ein quadratisches Programmierproblem. Es ist eine Art der nichtlinearen Programmierung. Es kann immer noch in polynomialer Zeit durch die Ellipsoid-Methode gelöst werden, wenn die Zielfunktion konvex ist; andernfalls kann das Problem NP-hart sein.
KKT-BedingungenBearbeiten
Der KKT-Ansatz für nichtlineare Programmierung verallgemeinert die Methode der Lagrange-Multiplikatoren, wenn Ungleichheitsbedingungen zugelassen werden. Er kann unter Differenzierbarkeit und Konvexität angewandt werden.
Branch-and-BoundEdit
Die Optimierung von Nebenbedingungen kann durch Branch-and-Bound-Algorithmen gelöst werden. Dabei handelt es sich um Backtracking-Algorithmen, die die Kosten der besten Lösung, die während der Ausführung gefunden wurde, speichern und sie verwenden, um einen Teil der Suche zu vermeiden. Genauer gesagt, wann immer der Algorithmus auf eine Teillösung stößt, die nicht erweitert werden kann, um eine Lösung mit besseren Kosten als die gespeicherten besten Kosten zu bilden, geht der Algorithmus zurück, anstatt zu versuchen, diese Lösung zu erweitern.
Angenommen, dass die Kosten minimiert werden sollen, hängt die Effizienz dieser Algorithmen davon ab, wie die Kosten, die durch die Erweiterung einer Teillösung erzielt werden können, bewertet werden. Wenn der Algorithmus nämlich von einer Teillösung aus zurückgehen kann, wird ein Teil der Suche übersprungen. Je niedriger die geschätzten Kosten sind, desto besser ist der Algorithmus, da es wahrscheinlicher ist, dass die geschätzten Kosten niedriger sind als die besten Kosten der bisher gefundenen Lösung.
Andererseits dürfen die geschätzten Kosten nicht niedriger sein als die effektiven Kosten, die durch die Erweiterung der Lösung erzielt werden können, da der Algorithmus sonst zurückgehen könnte, obwohl eine bessere Lösung als die beste bisher gefundene existiert. Folglich benötigt der Algorithmus eine obere Schranke für die Kosten, die durch die Erweiterung einer Teillösung erzielt werden können, und diese obere Schranke sollte so klein wie möglich sein.
Eine Variante dieses Ansatzes, die Hansen-Methode, verwendet Intervallmethoden. Sie implementiert inhärent rechteckige Nebenbedingungen.
Begrenzungsfunktionen erster WahlBearbeiten
Eine Möglichkeit, diese obere Grenze für eine Teillösung zu bewerten, besteht darin, jede weiche Nebenbedingung separat zu betrachten. Für jede weiche Bedingung wird der maximal mögliche Wert für jede Zuordnung zu den nicht zugeordneten Variablen angenommen. Die Summe dieser Werte ist eine obere Schranke, da die weichen Bedingungen keinen höheren Wert annehmen können. Sie ist exakt, weil sich die Maximalwerte von Soft Constraints aus verschiedenen Bewertungen ergeben können: Ein Soft Constraint kann maximal sein für x = a {\displaystyle x=a}
, während eine andere Bedingung für x = b maximal ist {\displaystyle x=b}
.
Russian doll searchEdit
Diese Methode führt einen Branch-and-Bound-Algorithmus auf n {\displaystyle n}
Probleme, wobei n {\displaystyle n}
die Anzahl der Variablen ist. Jedes dieser Probleme ist das Teilproblem, das man durch Weglassen einer Folge von Variablen x 1 , … , x i {\displaystyle x_{1},\ldots ,x_{i}}
aus dem ursprünglichen Problem, zusammen mit den sie enthaltenden Nebenbedingungen. Nach dem Problem auf Variablen x i + 1 , … , x n {\displaystyle x_{i+1},\ldots ,x_{n}}
gelöst ist, können seine optimalen Kosten als obere Schranke bei der Lösung der anderen Probleme verwendet werden,
insbesondere kann die Kostenschätzung einer Lösung mit x i + 1 , … , x n {\displaystyle x_{i+1},\ldots ,x_{n}}
als nicht zugeordnete Variablen hat, wird zu den Kosten addiert, die sich aus den bewerteten Variablen ergeben. Dies entspricht praktisch dem Ignorieren der bewerteten Variablen und dem Lösen des Problems mit den nicht bewerteten Variablen, mit dem Unterschied, dass das letztere Problem bereits gelöst wurde. Genauer gesagt, werden die Kosten von Soft Constraints, die sowohl zugewiesene als auch nicht zugewiesene Variablen enthalten, wie oben (oder mit einer beliebigen anderen Methode) geschätzt; die Kosten von Soft Constraints, die nur nicht zugewiesene Variablen enthalten, werden stattdessen anhand der optimalen Lösung des entsprechenden Problems geschätzt, die zu diesem Zeitpunkt bereits bekannt ist.
Es gibt Ähnlichkeiten zwischen der Russian Doll Search Methode und der Dynamischen Programmierung. Wie die Dynamische Programmierung löst die Russian Doll Search Teilprobleme, um das Gesamtproblem zu lösen. Aber während die Dynamische Programmierung die Ergebnisse der Teilprobleme direkt kombiniert, um das Ergebnis des Gesamtproblems zu erhalten, verwendet Russian Doll Search sie nur als Grenzen während der Suche.
Bucket EliminationEdit
Der Bucket Elimination Algorithmus kann für die Constraint Optimierung angepasst werden. Eine gegebene Variable kann in der Tat aus dem Problem entfernt werden, indem alle weichen Nebenbedingungen, die sie enthalten, durch eine neue weiche Nebenbedingung ersetzt werden. Die Kosten dieser neuen Bedingung werden unter der Annahme eines Maximalwertes für jeden Wert der entfernten Variablen berechnet. Wenn x {\displaystyle x}
die zu entfernende Variable ist, werden C 1 , … , C n {\displaystyle C_{1},\ldots ,C_{n}}
sind die weichen Beschränkungen, die sie enthalten, und y 1 , … , y m {\displaystyle y_{1},\ldots ,y_{m}}
ihre Variablen sind, außer x {\displaystyle x}
, ist die neue weiche Bedingung definiert durch: C ( y 1 = a 1 , … , y n = a n ) = max a ∑ i C i ( x = a , y 1 = a 1 , … , y n = a n ) . {\displaystyle C(y_{1}=a_{1},\ldots ,y_{n}=a_{n})=\max _{a}\sum _{i}C_{i}(x=a,y_{1}=a_{1},\ldots ,y_{n}=a_{n}).}
Die Bucket-Elimination arbeitet mit einer (beliebigen) Ordnung der Variablen. Jeder Variablen ist ein Bucket von Constraints zugeordnet; der Bucket einer Variablen enthält alle Constraints, bei denen die Variable in der Reihenfolge die höchste ist. Die Bucket-Elimination erfolgt von der letzten Variable zur ersten. Für jede Variable werden alle Beschränkungen des Bereichs wie oben beschrieben ersetzt, um die Variable zu entfernen. Die sich ergebende Bedingung wird dann in den entsprechenden Bucket gesetzt.