Gradientmetoder er numeriske metoder til at løse problemer ved hjælp af en gradient , som reduceres til at finde yderpunkterne af en funktion.
Opgaven med at løse et ligningssystem :
(en)
c svarer til problemet med at minimere funktionen
(2)
eller en anden stigende funktion af de absolutte værdier af residualer (fejl) , . Problemet med at finde minimum (eller maksimum) af en funktion af variable er i sig selv af stor praktisk betydning.
For at løse dette problem ved hjælp af iterative metoder , starter man med vilkårlige værdier og konstruerer successive tilnærmelser:
eller koordineret:
(3)
som konvergerer til en eller anden løsning for .
Forskellige metoder adskiller sig i valget af "retning" for det næste trin, det vil sige valget af relationer
.
Trinværdien (afstanden til at bevæge sig i en given retning på jagt efter et ekstremum) bestemmes af værdien af parameteren, der minimerer værdien som funktion af . Denne funktion tilnærmes normalt ved dens Taylor-udvidelse eller ved et interpolationspolynomium over tre til fem valgte værdier . Den sidste metode er anvendelig til at finde max og min for en tabelfunktion .
Hovedideen med metoderne er at gå i retning af den stejleste nedstigning, og denne retning er givet af antigradienten :
hvor er valgt:
Vælg , hvor alle afledede er beregnet til , og formindsk trinlængden , når du nærmer dig minimum af funktionen .
Til analytiske funktioner og små værdier giver Taylor-udvidelsen mulighed for at vælge den optimale trinstørrelse
(5)
hvor alle derivater er beregnet til . Parabolisk funktionsinterpolation kan være mere praktisk.
AlgoritmeDenne metode er navngivet i analogi med Gauss-Seidel-metoden til løsning af et system af lineære ligninger. Forbedrer den tidligere metode på grund af det faktum, at nedstigningen ved næste iteration udføres gradvist langs hver af koordinaterne, men nu er det nødvendigt at beregne nye én gang i et trin.
AlgoritmeDen konjugerede gradientmetode er baseret på koncepterne fra den direkte metode til multidimensionel optimering - metoden for konjugerede retninger .
Anvendelse af metoden på kvadratiske funktioner i bestemmer minimum i trin.
AlgoritmeOptimeringsmetoder _ | |
---|---|
Endimensionel |
|
Nul orden | |
Første ordre | |
anden orden | |
Stokastisk | |
Lineære programmeringsmetoder _ | |
Ikke-lineære programmeringsmetoder |