Aktivasetmetoder

Aktivasetmetoder er en gruppe algoritmer for konfigurerte optimeringsproblemer der begrensninger spiller en sentral rolle. Hovedideen er å opprettholde et arbeidssett av begrensninger som ved den aktuelle løsningen behandles som likninger, mens resten antas å være ikke-bindende og dermed ikke påvirker det lokale subproblemet. Arbeidssettet kalles det aktive settet, og metoden søker en løsning ved å løse et redusert problem der de aktive begrensningene er likninger.

Prosessen starter med et feasibelt startpunkt og et initialt aktivt sett. For hvert steg løses det reduserte problemet som fås når alle begrensningene i det aktive settet betraktes som likninger. Etter å ha funnet en løsning beregnes Lagrange-multiplikatorer for de aktive begrensningene. Vanligvis kreves det at multiplikatorene oppfyller visse betingelser (komplementaritetsbetingelser) før løsningen aksepteres som optimal for subproblemet. Hvis betingelsene ikke er oppfylt, oppdateres arbeidssettet ved å flytte en eller flere begrensninger mellom aktive og ikke-aktive, eller ved å legge til eller fjerne begrensninger. Prosessen gjentas til konvergensmotivasjonen er oppnådd eller til det ikke finnes en forbedring i løsningen.

Anvendelser og egenskaper: Aktivasetmetoder brukes ofte i kvadratiske programmer og andre konveks optimeringsproblemer der det er mange begrensninger og der man ønsker å utnytte strukturen i et arbeidssett. De er også vanlige i bound-konstrained optimering og i store skala-problemer der man vil kunne starte fra en gyldig løsning og forbedre den iterativt.

Fordeler og utfordringer: Metodene kan være effektive og enkle å tilpasse til spesifikke strukturer, spesielt når man kan dra nytte av sparsitet og varmstart. Utfordringer inkluderer degeneracy og behovet for robuste regler for oppdatering av arbeidssettet, samt avhengigheten av problemdesign og implementasjon. Sammenlignet med interior-point-metoder er aktivasetmetoder ofte konkurransedyktige på visse problemtyper, særlig når aktive betingelser gir rask konvergens.