Barrierfunksjoner

Barrierfunksjoner er en type funksjoner som brukes i optimering for å håndtere begrensninger ved å gjøre målfunksjonen uendelig stor nær grensen av den tillatte mengden. En barrierfunksjon φ er definert i innside av en mengde C og går mot +∞ når man nærmer seg grensene. Hovedideen i barriermetoder, ofte kalt indre punkts-metoder, er å legge til φ i målfunksjonen slik at løsningen forblir inne i området.

For en mengde definert ved lineære ulikheter, C = { x | A x ≤ b }, kan en vanlig barrier være φ(x) = −∑_i log(b_i − a_i^T x). Denne funksjonen er definert i innside av C og går mot +∞ når noen av b_i − a_i^T x nærmer seg 0.

Et annet velkjent eksempel er log-barrieren for positive ortant: φ(x) = −∑_i log x_i, definert for x_i > 0. Her er gradienten ∇φ(x) = −1/x og Hessianen ∇^2 φ(x) = diag(1/x_i^2). Barrierer brukes i problemer av formen min f(x) + μ φ(x) over x i innside av C, der μ > 0 er en barrierparameter. Etter hvert som μ reduseres mot 0, blir løsningen nær den optimerte løsningen under begrensningene.

I praksis brukes barrierer også for andre koner, for eksempel -log det X som barrier for den positive semidefinite konen i semidefinite programmering. Barrierfunksjoner er spesielt nyttige fordi de holder løsninger inne i det ønskede området og gir godt oppførte skritt i Newton-baserte algoritmer, noe som bidrar til konvergensgarantier i indre punktsmetoder.