Mange ubegrænsede optimeringsalgoritmer kan tilpasses til det begrænsede tilfælde, ofte ved hjælp af en strafmetode. De søgetrin, der tages af den ubegrænsede metode, kan imidlertid være uacceptable for det begrænsede problem, hvilket fører til manglende konvergens. Dette kaldes Maratos-effekten.
LighedsbegrænsningerRediger
SubstitutionsmetodeRediger
For meget enkle problemer, f.eks. en funktion af to variabler, der er underlagt en enkelt lighedsbegrænsning, er det mest praktisk at anvende substitutionsmetoden. Ideen er at substituere begrænsningen i målfunktionen for at skabe en sammensat funktion, der inkorporerer virkningen af begrænsningen. Antag f.eks., at målet er at maksimere f ( x , y ) = x ⋅ y {\displaystyle f(x,y)=x\cdot y}
med forbehold for x + y = 10 {\displaystyle x+y=10}
. Denne begrænsning indebærer, at y = 10 – x {\displaystyle y=10-x}
, hvilket kan sættes ind i målfunktionen for at skabe p ( x ) = x ( 10 – x ) = 10 x – x 2 {\displaystyle p(x)=x(10-x)=10x-x^{2}}}
. Den nødvendige betingelse af første orden giver ∂ p ∂ x = 10 – 2 x = 0 {\displaystyle {\frac {\partial p}{\partial x}}=10-2x=0}
, som kan løses for x = 5 {\displaystyle x=5}
og følgelig y = 10 – 5 = 5 {\displaystyle y=10-5=5}
.
Lagrange-multiplikatorRediger
Hvis det begrænsede problem kun har lighedsbegrænsninger, kan metoden med Lagrange-multiplikatorer bruges til at omdanne det til et ubegrænset problem, hvis antal variabler er det oprindelige antal variabler plus det oprindelige antal lighedsbegrænsninger. Alternativt, hvis begrænsningerne alle er lighedsbegrænsninger og alle er lineære, kan de løses for nogle af variablerne i form af de andre, og de førstnævnte kan erstattes af målfunktionen, hvorved et ubegrænset problem med et mindre antal variabler bliver tilbage.
UlighedsbetingelserRediger
Med ulighedsbetingelser kan problemet karakteriseres i form af de geometriske optimalitetsbetingelser, Fritz John-betingelser og Karush-Kuhn-Tucker-betingelser, under hvilke simple problemer kan være opløselige.
Lineær programmeringRediger
Hvis målfunktionen og alle de hårde begrænsninger er lineære, og nogle af de hårde begrænsninger er uligheder, er problemet et lineært programmeringsproblem. Det kan løses ved simplexmetoden, som normalt fungerer på polynomial tid i forhold til problemets størrelse, men som ikke er garanteret, eller ved interior point-metoder, som garanteret fungerer på polynomial tid.
Ikke-lineær programmeringRediger
Hvis målfunktionen eller nogle af begrænsningerne er ikke-lineære, og nogle af begrænsningerne er uligheder, er problemet et ikke-lineært programmeringsproblem.
Quadratisk programmeringRediger
Hvis alle de hårde begrænsninger er lineære, og nogle er uligheder, men målfunktionen er kvadratisk, er problemet et kvadratisk programmeringsproblem. Det er en type af ikke-lineær programmering. Det kan stadig løses på polynomial tid ved hjælp af ellipsoidmetoden, hvis målfunktionen er konveks; ellers kan problemet være NP-hårdt.
KKT-betingelserRediger
Med hensyn til ulighedsbetingelser generaliserer KKT-tilgangen til ikke-lineær programmering metoden med Lagrange-multiplikatorer. Den kan anvendes under differentiabilitet og konveksitet.
Branch and boundRediger
Konstraintoptimering kan løses ved hjælp af branch-and-bound-algoritmer. Disse er backtracking-algoritmer, der gemmer omkostningerne ved den bedste løsning, der er fundet under udførelsen, og bruger dem til at undgå en del af søgningen. Mere præcist: når algoritmen støder på en delløsning, der ikke kan udvides til at danne en løsning med bedre omkostninger end de lagrede bedste omkostninger, går algoritmen tilbage i stedet for at forsøge at udvide denne løsning.
Antages det, at omkostningerne skal minimeres, afhænger effektiviteten af disse algoritmer af, hvordan de omkostninger, der kan opnås ved at udvide en delløsning, vurderes. Hvis algoritmen kan gå tilbage fra en delløsning, springes en del af søgningen nemlig over. Jo lavere de anslåede omkostninger er, jo bedre er algoritmen, da det er mere sandsynligt, at en lavere anslået omkostning er lavere end den hidtil bedste løsning, der er fundet.
På den anden side kan denne anslåede omkostning ikke være lavere end den effektive omkostning, der kan opnås ved at udvide løsningen, da algoritmen ellers kunne gå tilbage, mens der findes en løsning, der er bedre end den hidtil bedste løsning, der er fundet. Som følge heraf kræver algoritmen en øvre grænse for de omkostninger, der kan opnås ved at udvide en delvis løsning, og denne øvre grænse bør være så lille som muligt.
En variant af denne fremgangsmåde, kaldet Hansens metode, anvender intervalmetoder. Den implementerer i sagens natur rektangulære begrænsninger.
Første valg af afgrænsende funktionerRediger
En måde at evaluere denne øvre grænse for en delvis løsning på er ved at betragte hver blød begrænsning separat. For hver blød begrænsning antages den maksimalt mulige værdi for enhver tildeling til de ikke-tildelte variabler. Summen af disse værdier er en øvre grænse, fordi de bløde begrænsninger ikke kan antage en højere værdi. Den er nøjagtig, fordi de maksimale værdier af bløde begrænsninger kan stamme fra forskellige evalueringer: en blød begrænsning kan være maksimal for x = a {\displaystyle x=a}
, mens en anden begrænsning er maksimal for x = b {\displaystyle x=b}
.
Russisk dukke searchEdit
Denne metode kører en branch-and-bound-algoritme på n {\displaystyle n}
problemer, hvor n {\displaystyle n}
er antallet af variabler. Hvert af disse problemer er det delproblem, der opnås ved at udelade en sekvens af variabler x 1 , … , x i {\displaystyle x_{1},\ldots ,x_{i}}
fra det oprindelige problem sammen med de bindinger, der indeholder dem. Efter problemet på variablerne x i + 1 , … , x n {\displaystyle x_{i+1},\ldots ,x_{n}}}
er løst, kan dets optimale omkostninger anvendes som en øvre grænse under løsningen af de andre problemer,
I særdeleshed kan omkostningsestimatet for en løsning med x i + 1 , … , x n {\displaystyle x_{i+1},\ldots ,x_{n}}}
som ikke-tildelte variabler lægges til de omkostninger, der stammer fra de evaluerede variabler. Dette svarer praktisk talt til at ignorere de evaluerede variabler og løse problemet med de ikke-tildelte variabler, bortset fra at sidstnævnte problem allerede er blevet løst. Mere præcist vurderes omkostningerne ved bløde begrænsninger, der indeholder både tildelte og ikke-tildelte variabler, som ovenfor (eller ved hjælp af en vilkårlig anden metode); omkostningerne ved bløde begrænsninger, der kun indeholder ikke-tildelte variabler, vurderes i stedet ved hjælp af den optimale løsning af det tilsvarende problem, som allerede er kendt på dette tidspunkt.
Der er lighed mellem Russian Doll Search-metoden og dynamisk programmering. Ligesom dynamisk programmering løser Russian Doll Search delproblemer med henblik på at løse hele problemet. Men mens dynamisk programmering direkte kombinerer de resultater, der er opnået på delproblemer, for at få resultatet af hele problemet, bruger Russian Doll Search dem kun som grænser under søgningen.
Bucket eliminationRediger
Algoritmen til bucket elimination kan tilpasses til optimering af begrænsninger. En given variabel kan nemlig fjernes fra problemet ved at erstatte alle bløde begrænsninger, der indeholder den, med en ny blød begrænsning. Omkostningerne ved denne nye begrænsning beregnes under antagelse af en maksimal værdi for hver værdi af den fjernede variabel. Formelt set, hvis x {\displaystyle x}
er den variabel, der skal fjernes, skal C 1 , … , C n {\displaystyle C_{1},\ldots ,C_{n}}
er de bløde begrænsninger, der indeholder den, og y 1 , … , y m {\displaystyle y_{1},\ldots ,y_{m}}
er deres variabler undtagen x {\displaystyle x}
, er den nye bløde begrænsning defineret ved: 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 virker med en (vilkårlig) rækkefølge af variablerne. Hver variabel er tilknyttet en spand med begrænsninger; spanden til en variabel indeholder alle begrænsninger, som variablen har den højeste i rækkefølgen. Eliminering af spande foregår fra den sidste variabel til den første. For hver variabel erstattes alle begrænsninger i spanden som ovenfor for at fjerne variablen. Den resulterende begrænsning placeres derefter i den relevante spand.