Veel niet-gecontroleerde optimalisatiealgoritmen kunnen worden aangepast aan het geval met beperkingen, vaak via het gebruik van een straffenmethode. De zoekstappen van de niet-gecontroleerde methode kunnen echter onaanvaardbaar zijn voor het probleem met de beperking, waardoor de methode niet convergeert. Dit wordt het Maratos-effect genoemd.
GelijkheidsbeperkingenEdit
SubstitutiemethodeEdit
Voor zeer eenvoudige problemen, bijvoorbeeld een functie van twee variabelen waarvoor een enkele gelijkheidsbeperking geldt, is het het meest praktisch om de substitutiemethode toe te passen. Het idee is om de beperking in de doelfunctie te substitueren om een samengestelde functie te verkrijgen waarin het effect van de beperking is verwerkt. Stel bijvoorbeeld dat de doelstelling is om f ( x , y ) = x ⋅ y { te maximaliseren
onder de voorwaarde dat x + y = 10 {\displaystyle x+y=10}
. De beperking impliceert y = 10 – x {\displaystyle y=10-x}
, die in de doelfunctie kan worden gesubstitueerd tot p ( x ) = x ( 10 – x ) = 10 x – x 2 {\displaystyle p(x)=x(10-x)=10x-x^{2}}
. De noodzakelijke voorwaarde van de eerste orde geeft ∂ p ∂ x = 10 – 2 x = 0 {\displaystyle {{{{{{{}}}}=10-2x=0}
, die kan worden opgelost voor x = 5 {\displaystyle x=5}
en, bijgevolg, y = 10 – 5 = 5 {\displaystyle y=10-5=5}
.
Lagrange-multiplicatorEdit
Als het beperkte probleem alleen gelijkheidsbeperkingen heeft, kan de methode van Lagrange-multiplicatoren worden gebruikt om het om te zetten in een niet-beperkt probleem waarvan het aantal variabelen gelijk is aan het oorspronkelijke aantal variabelen plus het oorspronkelijke aantal gelijkheidsbeperkingen. Indien de beperkingen alle gelijkheidsbeperkingen zijn en alle lineair zijn, kunnen zij voor sommige variabelen worden opgelost in termen van de andere, en kunnen de eerstgenoemde uit de doelfunctie worden gesubstitueerd, zodat een ongedwongen probleem overblijft in een kleiner aantal variabelen.
OngelijkheidsbeperkingenEdit
Met ongelijkheidsbeperkingen kan het probleem worden gekarakteriseerd in termen van de geometrische optimaliteitsvoorwaarden, de Fritz John-voorwaarden en de Karush-Kuhn-Tucker-voorwaarden, waaronder eenvoudige problemen oplosbaar kunnen zijn.
Lineair programmerenEdit
Als de doelfunctie en alle harde beperkingen lineair zijn en sommige harde beperkingen ongelijkheden zijn, dan is het probleem een lineair programmeringsprobleem. Dit kan worden opgelost met de simplexmethode, die meestal in polynomiale tijd in de probleemgrootte werkt, maar dat niet garandeert, of met interior point methods die gegarandeerd in polynomiale tijd werken.
Niet-lineair programmerenEdit
Als de doelfunctie of sommige van de beperkingen niet-lineair zijn, en sommige beperkingen ongelijkheden zijn, dan is het probleem een niet-lineair programmeerprobleem.
Kwadratisch programmerenEdit
Als alle harde beperkingen lineair zijn en sommige ongelijkheden, maar de doelfunctie kwadratisch is, dan is het probleem een kwadratisch programmeringsprobleem. Het is een type niet-lineaire programmering. Het kan nog steeds in polynomiale tijd worden opgelost met de ellipsoïdenmethode als de doelfunctie convex is; anders kan het probleem NP-hard zijn.
KKT-voorwaardenEdit
De KKT-benadering van niet-lineair programmeren veralgemeent de methode van Lagrange-multiplicatoren, als ongelijkheidsbeperkingen worden toegestaan. Het kan worden toegepast onder differentiabiliteit en convexiteit.
Branch and boundEdit
Constraint optimalisatie kan worden opgelost door branch-and-bound algoritmen. Dit zijn backtracking-algoritmen die de kosten van de beste oplossing die tijdens de uitvoering is gevonden, opslaan en gebruiken om een deel van de zoektocht te vermijden. Om precies te zijn, als het algoritme een deeloplossing tegenkomt die niet kan worden uitgebreid tot een oplossing met betere kosten dan de opgeslagen beste kosten, gaat het algoritme terug in de tijd, in plaats van te proberen deze oplossing uit te breiden.
Aannemende dat de kosten moeten worden geminimaliseerd, hangt de efficiëntie van deze algoritmen af van de manier waarop de kosten die kunnen worden verkregen door een deeloplossing uit te breiden, worden geëvalueerd. Als het algoritme kan terugkeren van een gedeeltelijke oplossing, wordt immers een deel van de zoektocht overgeslagen. Hoe lager de geschatte kosten, hoe beter het algoritme, aangezien de kans groter is dat een lagere geschatte kostprijs lager is dan de beste kostprijs van de tot dusver gevonden oplossing.
Anderzijds kan deze geschatte kostprijs niet lager zijn dan de effectieve kostprijs die kan worden verkregen door de oplossing uit te breiden, aangezien het algoritme anders zou kunnen terugkrabbelen terwijl er een oplossing bestaat die beter is dan de beste tot dusver gevonden oplossing. Bijgevolg vereist het algoritme een bovengrens voor de kosten die kunnen worden verkregen door een gedeeltelijke oplossing uit te breiden, en deze bovengrens moet zo klein mogelijk zijn.
Een variant van deze aanpak, de methode van Hansen, maakt gebruik van intervalmethoden. Het implementeert inherent rechthoekige beperkingen.
First-choice bounding functionsEdit
Een manier om deze bovengrens voor een gedeeltelijke oplossing te evalueren is door elke zachte beperking afzonderlijk te beschouwen. Voor elke zachte beperking wordt de maximaal mogelijke waarde voor elke toewijzing aan de niet-toegewezen variabelen aangenomen. De som van deze waarden is een bovengrens omdat de zachte beperkingen geen hogere waarde kunnen aannemen. De som is exact omdat de maximale waarden van de soft constraints kunnen voortvloeien uit verschillende evaluaties: een soft constraint kan maximaal zijn voor x = a {Displaystyle x=a}
terwijl een andere constraint maximaal is voor x = b {{Displaystyle x=b}
.
Russische pop zoekenEdit
Deze methode voert een branch-and-bound algoritme uit op n {\displaystyle n}
problemen, waarbij n {{\displaystyle n}
het aantal variabelen is. Elk van deze problemen is het deelprobleem dat wordt verkregen door een reeks variabelen x 1 , … , x i {{1},\ldots,x_{i}}} te laten vallen.
uit het oorspronkelijke probleem te laten vallen, samen met de constraints die deze variabelen bevatten. Na het probleem over de variabelen x i + 1 , … , x n {\displaystyle x_{i+1},\ldots,x_{n}}
is opgelost, kunnen de optimale kosten ervan worden gebruikt als bovengrens bij het oplossen van de andere problemen,
In het bijzonder kan de kostenraming van een oplossing met x i + 1 , … , x n {\displaystyle x_{i+1},\ldots,x_{n}}
als niet-toegewezen variabelen wordt opgeteld bij de kosten die voortvloeien uit de geëvalueerde variabelen. In feite komt dit overeen met het negeren van de geëvalueerde variabelen en het oplossen van het probleem met de niet-toegewezen variabelen, behalve dat dit laatste probleem reeds is opgelost. Meer precies worden de kosten van zachte beperkingen die zowel toegekende als niet-toegewezen variabelen bevatten, geschat zoals hierboven (of met een willekeurige andere methode); de kosten van zachte beperkingen die alleen niet-toegewezen variabelen bevatten, worden daarentegen geschat met behulp van de optimale oplossing van het overeenkomstige probleem, die op dat moment al bekend is.
Er is een overeenkomst tussen de “Russian Doll Search”-methode en Dynamisch Programmeren. Net als bij dynamisch programmeren lost Russian Doll Search deelproblemen op om het hele probleem op te lossen. Maar terwijl Dynamic Programming de resultaten van de deelproblemen direct combineert om het resultaat van het hele probleem te verkrijgen, gebruikt Russian Doll Search ze alleen als grenzen tijdens het zoeken.
Emmer eliminatieEdit
Het emmer eliminatie-algoritme kan worden aangepast voor constraint optimalisatie. Een gegeven variabele kan inderdaad uit het probleem worden verwijderd door alle zachte constraints die deze variabele bevatten te vervangen door een nieuwe zachte constraint. De kosten van deze nieuwe beperking worden berekend uitgaande van een maximale waarde voor elke waarde van de verwijderde variabele. Formeel betekent dit dat als x {{1409>
zijn de zachte constraints die deze variabele bevatten, en y 1 , … , y m {\displaystyle y_{1},\ldots,y_{m}}
zijn de variabelen ervan, behalve x {{displaystyle x}
, de nieuwe zachte beperking wordt gedefinieerd door: C ( y 1 = a 1 , … , y n = a n ) = max a ∑ i C i ( x = a , y 1 = a 1 , … , y n = a n ) . {{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 werkt met een (willekeurige) ordening van de variabelen. Aan elke variabele is een emmer met beperkingen gekoppeld; de emmer van een variabele bevat alle beperkingen die de variabele het hoogst in de rangorde heeft. Emmer eliminatie gaat van de laatste variabele naar de eerste. Voor elke variabele worden alle constraints van de emmer vervangen zoals hierboven beschreven om de variabele te verwijderen. De resulterende constraint wordt dan in de juiste bucket geplaatst.