Derivatfri optimering

Derivatfri optimering (ibland kallad blackbox-optimering ), är en disciplin inom matematisk optimering som inte använder derivatinformation i klassisk mening för att hitta optimala lösningar: Ibland är information om derivatan av objektivfunktionen f otillgänglig, otillförlitlig eller opraktisk för att uppnå. Till exempel f vara ojämn, eller tidskrävande att utvärdera, eller på något sätt brusig, så att metoder som förlitar sig på derivator eller approximerar dem via ändliga skillnader är till liten användning. Problemet att hitta optimala punkter i sådana situationer kallas derivatfri optimering, algoritmer som inte använder derivator eller ändliga skillnader kallas derivatfria algoritmer .

Introduktion

Problemet som ska lösas är att numeriskt optimera en objektivfunktion $f\colon A\to \mathbb {R}$ för någon uppsättning $A$ (vanligtvis $A\subset \mathbb {R} ^{n}$ ), dvs hitta $x_{0}\in A$ så att utan förlust av generalitet $f (x_{0})\leq f(x)$ för alla $x\in A$ .

I tillämpliga fall är ett vanligt tillvägagångssätt att iterativt förbättra en parametergissning genom lokal bergsklättring i det objektiva funktionslandskapet. Derivatbaserade algoritmer använder derivatinformation av $f$ för att hitta en bra sökriktning, eftersom till exempel gradienten ger riktningen för den brantaste uppstigningen. Derivatbaserad optimering är effektiv för att hitta lokala optima för kontinuerliga domäns smidiga enkelmodala problem. Däremot kan de ha problem när t.ex. $A$ är frånkopplad, eller (bland-)heltal, eller när $f$ är dyrt att utvärdera, eller är ojämnt eller brusigt, så att (numerisk approximationer av) derivat ger inte användbar information. Ett lite annorlunda problem är när $f$ är multimodal, i vilket fall lokala derivatbaserade metoder bara ger lokal optima, men kan missa den globala.

I derivatfri optimering används olika metoder för att hantera dessa utmaningar med endast funktionsvärden för ${\displaystyle f} ,$ men inga derivator. Vissa av dessa metoder kan bevisas upptäcka optima, men vissa är ganska metaheuristiska eftersom problemen i allmänhet är svårare att lösa jämfört med konvex optimering . För dessa är ambitionen snarare att effektivt hitta "bra" parametervärden som kan vara nära optimala givet tillräckligt med resurser, men optimalitetsgarantier kan vanligtvis inte ges. Man bör tänka på att utmaningarna är olika, så att man vanligtvis inte kan använda en algoritm för alla typer av problem.

Algoritmer

Anmärkningsvärda derivatfria optimeringsalgoritmer inkluderar:

• Bayesiansk optimering
• Koordinatnedstigning och adaptiv koordinatnedstigning
• Göksök
• Beetle Antennae Search (BAS)
• GJORT
• Evolutionsstrategier , Naturliga evolutionsstrategier ( CMA-ES , xNES, SNES)
• Genetiska algoritmer
• MCS algoritm
• Nelder-Mead metod
• Partikelsvärmoptimering
• Mönstersökning
• Slumpmässig sökning (inklusive Luus–Jaakola )
• Simulerad glödgning
• Stokastisk optimering
• Subgradientmetod

Se även

• Matematisk optimering

externa länkar

• Audet, Charles; Kokkolaras, Michael (2016). "Blackbox och derivatfri optimering: teori, algoritmer och applikationer" . Optimering och teknik . 17 : 1–2. doi : 10.1007/s11081-016-9307-4 .