linjesøk

Linjesøk er en metode innen optimering som brukes for å finne en passende skrittlengde langs en gitt retning i målfunksjonen f. Målet er å redusere funksjonsverdien på hvert steg ved å velge et passende skritt α slik at x_k+αp_k gir bedret objektivverdi enn x_k, der x_k er gjeldende punkt og p_k er søke retningen (oftest et synkende alternativ som -∇f(x_k)).

Hovedideen er å definere φ(α) = f(x_k + α p_k) og å minimere φ over α ≥ 0. Exakt linjesøk søker α som gir den beste reduksjonen langs p_k, mens inexact linjesøk tilfører akseptkriterier som gjør beregningen raskere og mer robust. Vanlige inexact-tilnærminger inkluderer Armijo (tilstrekkelig reduksjon) og Wolfe-betingelser (kombinasjon av tilstrekkelig reduksjon og tilstrekkelig kurvatur). En enkel praktisk variant er backtracking, der man starter med α = 1 og reduserer α med en faktor β (0 < β < 1) inntil Armijo-betingelsen er oppfylt.

Linjesøk er en viktig komponent i mange gradientbaserte metoder, som gradient descent, konjugert gradient og quasi-Newton-metoder. Ved å velge passende α unngås små eller overdrevne steg som kan hindere konvergensen, og det oppnås ofte bedre praksisytelse og stabilitet enn ved å bruke faste skritt. Exakt linjesøk kan være kostbart fordi det krever flere verdier av f langs samme retning; derfor brukes ofte inexact-varianten i praksis, spesielt i store skaleringsoppgaver.

Linjesøk anvendes i både ubegrenset og begrenset optimering som en del av algoritmer som søker etter stasjonære punkter eller lokalt minste. Det gir en mekanisme for kontrollert fremdrift mot reduksjon i målfunksjonen.