Många optimeringsalgoritmer utan begränsningar kan anpassas till det begränsade fallet, ofta med hjälp av en straffmetod. De söksteg som tas av den obegränsade metoden kan dock vara oacceptabla för det begränsade problemet, vilket leder till bristande konvergens. Detta kallas Maratos-effekten.
JämlikhetsbegränsningarRedigera
SubstitutionsmetodRedigera
För mycket enkla problem, t.ex. en funktion av två variabler som är föremål för en enda jämlikhetsbegränsning, är det mest praktiskt att tillämpa substitutionsmetoden. Tanken är att ersätta begränsningen med målfunktionen för att skapa en sammansatt funktion som innehåller begränsningens effekt. Anta till exempel att målet är att maximera f ( x , y ) = x ⋅ y {\displaystyle f(x,y)=x\cdot y}
med förbehållet x + y = 10 {\displaystyle x+y=10}
. Begränsningen innebär att y = 10 – x {\displaystyle y=10-x}
, vilket kan ersättas i målfunktionen för att skapa p ( x ) = x ( 10 – x ) = 10 x – x 2 {\displaystyle p(x)=x(10-x)=10x-x^{2}}}
. Det nödvändiga villkoret av första ordningen ger ∂ p ∂ x = 10 – 2 x = 0 {\displaystyle {\frac {\partial p}{\partial x}}=10-2x=0}
, vilket kan lösas för x = 5 {\displaystyle x=5}
och följaktligen y = 10 – 5 = 5 {\displaystyle y=10-5=5}
.
Lagrange-multiplikatorEdit
Om det begränsade problemet endast har jämlikhetsbegränsningar kan metoden med Lagrange-multiplikatorer användas för att omvandla det till ett problem utan begränsningar vars antal variabler är det ursprungliga antalet variabler plus det ursprungliga antalet jämlikhetsbegränsningar. Alternativt, om begränsningarna är alla jämlikhetsbegränsningar och alla är linjära, kan de lösas för några av variablerna i termer av de andra, och de förstnämnda kan ersättas ur målfunktionen, vilket ger ett problem utan begränsningar med ett mindre antal variabler.
OlikhetsbegränsningarRedigera
Med olikhetsbegränsningar kan problemet karakteriseras i termer av de geometriska optimalitetsvillkoren, Fritz John-villkoren och Karush-Kuhn-Tucker-villkoren, under vilka enkla problem kan vara lösbara.
Linjär programmeringRedigera
Om målfunktionen och alla hårda begränsningar är linjära och vissa hårda begränsningar är olikheter är problemet ett linjärt programmeringsproblem. Detta kan lösas med simplexmetoden, som vanligtvis fungerar på polynomial tid i problemets storlek men inte garanterat, eller med metoder för inre punkter som garanterat fungerar på polynomial tid.
Icke-linjär programmeringRedigera
Om målfunktionen eller vissa av begränsningarna är icke-linjära och vissa begränsningar är ojämlikheter, så är problemet ett icke-linjärt programmeringsproblem.
Kvadratisk programmeringEdit
Om alla hårda begränsningar är linjära och vissa är ojämlikheter, men målfunktionen är kvadratisk, är problemet ett kvadratiskt programmeringsproblem. Det är en typ av icke-linjär programmering. Det kan fortfarande lösas på polynomtid med ellipsoidmetoden om målfunktionen är konvex, annars kan problemet vara NP-hårt.
KKT-villkorRedigera
Med ojämlikhetsvillkor generaliserar KKT-metoden för icke-linjär programmering metoden för Lagrange-multiplikatorer. Den kan tillämpas under differentierbarhet och konvexitet.
Branch and boundEdit
Optimering av begränsningar kan lösas med branch-and-bound-algoritmer. Dessa är backtracking-algoritmer som lagrar kostnaden för den bästa lösningen som hittas under utförandet och använder den för att undvika en del av sökningen. När algoritmen stöter på en dellösning som inte kan utvidgas för att bilda en lösning med bättre kostnad än den lagrade bästa kostnaden, går algoritmen bakåt i stället för att försöka utvidga denna lösning.
Antagen att kostnaden ska minimeras beror effektiviteten hos dessa algoritmer på hur den kostnad som kan erhållas genom att utvidga en dellösning utvärderas. Om algoritmen kan backa tillbaka från en dellösning, kan en del av sökningen överhoppas. Ju lägre den uppskattade kostnaden är, desto bättre är algoritmen, eftersom en lägre uppskattad kostnad med större sannolikhet är lägre än den bästa kostnaden för den lösning som hittats hittills.
Å andra sidan kan denna uppskattade kostnad inte vara lägre än den effektiva kostnaden som kan erhållas genom att förlänga lösningen, eftersom algoritmen annars skulle kunna backa tillbaka medan det finns en lösning som är bättre än den bästa som hittats hittills. Som ett resultat kräver algoritmen en övre gräns för den kostnad som kan erhållas genom att utvidga en partiell lösning, och denna övre gräns bör vara så liten som möjligt.
En variant av detta tillvägagångssätt som kallas Hansens metod använder sig av intervallmetoder. Den implementerar rektangulära begränsningar.
Förstahandsval av avgränsande funktionerRedigera
Ett sätt att utvärdera denna övre gräns för en partiell lösning är att betrakta varje mjuk begränsning separat. För varje mjukt tvång antas det högsta möjliga värdet för alla tilldelningar till de icke tilldelade variablerna. Summan av dessa värden är en övre gräns eftersom de mjuka begränsningarna inte kan anta ett högre värde. Den är exakt eftersom de maximala värdena för mjuka begränsningar kan härröra från olika utvärderingar: en mjuk begränsning kan vara maximal för x = a {\displaystyle x=a}
medan en annan begränsning är maximal för x = b {\displaystyle x=b}
.
Russian doll searchEdit
Denna metod kör en branch-and-bound-algoritm på n {\displaystyle n}
problem, där n {\displaystyle n}
är antalet variabler. Varje sådant problem är det delproblem som erhålls genom att ta bort en sekvens av variabler x 1 , … , x i {\displaystyle x_{1},\ldots ,x_{i}}
från det ursprungliga problemet, tillsammans med de begränsningar som innehåller dem. Efter problemet med variablerna x i + 1 , … , x n {\displaystyle x_{i+1},\ldots ,x_{n}}}
har lösts kan dess optimala kostnad användas som en övre gräns när man löser de andra problemen,
I synnerhet kan kostnadsuppskattningen av en lösning med x i + 1 , … , x n {\displaystyle x_{i+1},\ldots ,x_{n}}
som icke tilldelade variabler läggs till den kostnad som härrör från de utvärderade variablerna. Detta motsvarar praktiskt taget att ignorera de utvärderade variablerna och lösa problemet med de icke tilldelade variablerna, förutom att det sistnämnda problemet redan har lösts. Kostnaden för mjuka begränsningar som innehåller både tilldelade och icke tilldelade variabler uppskattas på samma sätt som ovan (eller med hjälp av en godtycklig annan metod). Kostnaden för mjuka begränsningar som endast innehåller icke tilldelade variabler uppskattas i stället med hjälp av den optimala lösningen på motsvarande problem, som redan är känd vid det här laget.
Det finns en likhet mellan Russian Doll Search-metoden och dynamisk programmering. I likhet med dynamisk programmering löser Russian Doll Search delproblem för att lösa hela problemet. Men medan dynamisk programmering direkt kombinerar de resultat som erhållits på delproblem för att få resultatet för hela problemet, använder Russian Doll Search dem bara som gränser under sökningen.
Bucket eliminationEdit
Algoritmen för bucket elimination kan anpassas för optimering av begränsningar. En given variabel kan faktiskt tas bort från problemet genom att alla mjuka begränsningar som innehåller den ersätts med en ny mjuk begränsning. Kostnaden för denna nya begränsning beräknas genom att anta ett maximalt värde för varje värde av den borttagna variabeln. Om x {\displaystyle x}
är den variabel som ska tas bort, C 1 , … , C n {\displaystyle C_{1},\ldots ,C_{n}}
är de mjuka begränsningar som innehåller den, och y 1 , … , y m {\displaystyle y_{1},\ldots ,y_{m}}
är deras variabler utom x {\displaystyle x}
definieras den nya mjuka begränsningen genom: 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}).}
Bucket elimination fungerar med en (godtycklig) ordning av variablerna. Varje variabel är associerad med en hink med begränsningar; en variabels hink innehåller alla begränsningar som variabeln har högst i ordningen. Eliminering av hinkar fortsätter från den sista variabeln till den första. För varje variabel ersätts alla begränsningar i skopan på samma sätt som ovan för att ta bort variabeln. Den resulterande begränsningen placeras sedan i lämplig hink.