Gradientmetoder

Gradientmetoder är numeriska metoder för att lösa problem med hjälp av en gradient , som reduceras till att hitta ytterligheterna för en funktion.

Redogörelse för problemet med att lösa ett ekvationssystem i termer av optimeringsmetoder

Uppgiften att lösa ett ekvationssystem :

$\left\{{\begin{array}{lcr}f_{1}(x_{1},x_{2},\ldots ,x_{n})&=&0\\\ldots &&\\f_{n} (x_{1},x_{2},\ldots,x_{n})&=&0\end{array}}\right.$ (ett)

c är ekvivalent med problemet med att minimera funktionen $n$ $x_{1},x_{2},\ldots ,x_{n}$

$F(x_{1},x_{2},\ldots ,x_{n})\ekvivalent \summa _{i=1}^{n}|f_{i}(x_{1},x_{2}, ...,x_{n})|^{2}$ (2)

eller någon annan ökande funktion av de absoluta värdena av residualer (fel) , . Problemet med att hitta minimum (eller maximum) för en funktion av variabler är i sig av stor praktisk betydelse. $|f_{i}|$ $f_{i}=f_{i}(x_{1},x_{2},\ldots ,x_{n})$ $i=1,2,\ldots ,n$ $n$

För att lösa detta problem med iterativa metoder , börjar man med godtyckliga värden och konstruerar successiva approximationer: $x_{i}^{[0]}(i=1,2,...,n)$

${\vec {x}}^{[j+1]}={\vec {x}}^{[j]}+\lambda ^{[j]}{\vec {v}}^{[j] }$

eller koordinatmässigt:

$x_{i}^{[j+1]}=x_{i}^{[j]}+\lambda ^{[j]}v_{i}^{[j]},\quad i=1,2 ,\ldots ,n,\quad j=0,1,2,\ldots$ (3)

som konvergerar till någon lösning för . ${\vec {x}}^{[k]}$ ${j\to \infty }$

Olika metoder skiljer sig åt i valet av "riktning" för nästa steg, det vill säga valet av relationer

$v_{1}^{[j]}:v_{2}^{[j]}:\ldots :v_{n}^{[j]}$ .

Stegvärdet (avståndet att röra sig i en given riktning på jakt efter ett extremum) bestäms av värdet på parametern som minimerar värdet som en funktion av . Denna funktion är vanligtvis approximerad av dess Taylor-expansion eller av ett interpolationspolynom över tre till fem valda värden . Den sista metoden är användbar för att hitta max och min för en tabellfunktion . $\lambda ^{[j]}$ $F(x_{1}^{[j+1]},x_{2}^{[j+1]},\ldots ,x_{n}^{[j+1]})$ $\lambda ^{[j]}$ $\lambda ^{[j]}$ $F(x_{1},x_{2},...,x_{n})$

Gradientmetoder

Huvudidén med metoderna är att gå i riktning mot den brantaste nedstigningen, och denna riktning ges av antigradienten : $-\nabla F$

${\överhögerpil {x}}^{[j+1]}={\överhögerpil {x}}^{[j]}-\lambda ^{[j]}\nabla F({\överhögerpil {x}}^ {[j]})$

var är valt: $\lambda ^{[j]}$

konstant, i vilket fall metoden kan divergera;
bråksteg, det vill säga längden på steget i nedstigningsprocessen delas med ett visst antal;
snabbaste nedstigning: $\lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F({\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F({ \vec {x}}^{[j]}))$

Brantaste nedstigningsmetod ( gradientmetod )

Välj , där alla derivator beräknas vid , och minska steglängden när du närmar dig funktionens minimum . $v_{i}^{[j]}=-{\frac {\partial F}{\partial x_{i))}$ $x_{i}=x_{i}^{[j]}$ $\lambda ^{[j]}$ $F$

För analytiska funktioner och små värden tillåter Taylor-expansionen att välja den optimala stegstorleken $F$ $f_{i}$ $F(\lambda ^{[j]})$

$\lambda ^{[j]}={\frac {\sum _{k=1}^{n}({\frac {\partial F}{\partial x_{k))})^{2)){ \sum _{k=1}^{n}\summa _{h=1}^{n}{\frac {\partial ^{2}F}{\partial x_{k}dx_{h))}{ \frac {\partial F}{\partial x_{k))}{\frac {\partial F}{\partial x_{h))))}$ (5)

där alla derivat är beräknade till . Parabolfunktionsinterpolation kan vara bekvämare. $x_{i}=x_{i}^{[j]}$ $F(\lambda ^{[j]})$

Algoritm

Initial approximation och beräkningsnoggrannhet är inställda ${\vec {x}}^{0}\!,\,\epsilon$
Räkna var ${\vec {x}}^{[j+1]}={\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F\left({\vec {x}}^{[j]}\höger)$ $\lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F\left({\vec {x}}^{[j]}-\lambda ^{[j]} \nabla F\left({\vec {x}}^{[j]}\höger)\höger)$
Kontrollera stopptillståndet:
- Om , gå sedan till steg 2. $\left|{\vec {x}}^{[j+1]}-{\vec {x}}^{[j]}\right|>\epsilon$ $j=j+1$
- Annars sluta. ${\vec {x}}={\vec {x}}^{[j+1]}$

Gauss-Seidel metod för koordinatnedstigning

Denna metod kallas analogt med Gauss-Seidel-metoden för att lösa ett system av linjära ekvationer. Förbättrar den tidigare metoden på grund av det faktum att vid nästa iteration utförs nedstigningen gradvis längs var och en av koordinaterna, men nu är det nödvändigt att beräkna nya en gång i ett steg. $\lambda \quad n$

Algoritm

Initial approximation och beräkningsnoggrannhet är inställda ${\vec {x}}_{0}^{0},\quad \varepsilon$
Räkna var $\left\{{\begin{array}{lcr}{\vec {x}}_{1}^{[j]}&=&{\vec {x}}_{0}^{[j]} -\lambda _{1}^{[j]}{\frac {\partial F({\vec {x}}_{0}^{[j]})}{\partial x_{1}}}{ \vec {e}}_{1}\\\ldots &&\\{\vec {x}}_{n}^{[j]}&=&{\vec {x}}_{n-1} ^{[j]}-\lambda _{n}^{[j]}{\frac {\partial F({\vec {x))_{n-1}^{[j]})}{\ partiell x_{n}}}{\vec {e}}_{n}\end{array}}\right.$ $\lambda _{i}^{[j]}=\mathrm {argmin} _{\lambda }\,F\left({\vec {x))_{i-1}^{[j]}-\ lambda ^{[j]}{\frac {\partial F({\vec {x}}_{i-1}^{[j]})}{\partial x_{i}}}{\vec {e }}_{i}\right)$
Kontrollera stopptillståndet:
- Om , gå sedan till steg 2. $|{\vec {x}}_{n}^{[j]}-{\vec {x}}_{0}^{[j]}|>\varepsilon$ ${\vec {x}}_{0}^{[j+1]}={\vec {x}}_{n}^{[j]},\quad j=j+1$
- Annars sluta. ${\vec {x}}={\vec {x}}_{n}^{[j]}$

Konjugerad gradientmetod

Den konjugerade gradientmetoden är baserad på koncepten för den direkta metoden för flerdimensionell optimering - metoden för konjugerade riktningar .

Att tillämpa metoden på kvadratiska funktioner i bestämmer minimum i steg. $\mathbb {R} ^{n}$ $n$

Algoritm

De ges av den initiala approximationen och felet: ${\vec {x}}_{0},\quad \varepsilon ,\quad k=0$
Beräkna startriktningen: $j=0,\quad {\vec {S}}_{k}^{j}=-\nabla f({\vec {x}}_{k}),\quad {\vec {x}}_ {k}^{j}={\vec {x}}_{k}$
${\vec {x}}_{k}^{j+1}={\vec {x}}_{k}^{j}+\lambda {\vec {S}}_{k}^{j },\quad \lambda =\arg \min _{\lambda }f({\vec {x}}_{k}^{j}+\lambda {\vec {S}}_{k}^{j }),\quad {\vec {S}}_{k}^{j+1}=-\nabla f({\vec {x}}_{k}^{j+1})+\omega { \vec {S}}_{k}^{j},\quad \omega ={\frac {||\nabla f({\vec {x}}_{k}^{j+1})|| ^{2}}{||\nabla f({\vec {x}}_{k}^{j})||^{2}}}$
- Om eller , sluta då. $||{\vec {S}}_{k}^{j+1}||<\varepsilon$ $||{\vec {x}}_{k}^{j+1}-{\vec {x}}_{k}^{j}||<\varepsilon$ ${\vec {x}}={\vec {x}}_{k}^{j+1}$
- Annat
  - om , gå sedan till 3; $(j+1)<n$ $j=j+1$
  - annars , gå till 2. ${\vec {x}}_{k+1}={\vec {x}}_{k}^{j+1},\quad k=k+1$

Se även

Interpolationsformler
Matematisk programmering
- gradientmetod
- Konjugerad gradientmetod
- Direkta metoder
Taylor formel
Numeriska metoder
- Numerisk lösning av ekvationer
- Nelder-Mead metod

Litteratur

Akulich I.L. Matematisk programmering i exempel och uppgifter: Proc. bidrag för studenters ekonomi. specialist. universitet. - M . : Högre. skola, 1986.
Gill F., Murray W., Wright M. Praktisk optimering. Per. från engelska. — M .: Mir, 1985.
Korshunov Yu.M., Korshunov Yu.M. Matematiska grunder för cybernetik. — M .: Energoatomizdat, 1972.
Maksimov Yu.A., Filipovskaya E.A. Algoritmer för att lösa problem med icke-linjär programmering. — M .: MEPhI, 1982.
Maksimov Yu.A. Algoritmer för linjär och diskret programmering. — M .: MEPhI, 1980.
Korn G., Korn T. Handbok i matematik för vetenskapsmän och ingenjörer. - M . : Nauka, 1970. - S. 575-576.

Optimeringsmetoder _
En-dimensionell	gyllene snittmetoden Dikotomi Parabolmetoden Rutnätssökning Enhetlig blocksökningsmetod Fibonacci-metoden Ternär sökning Piyavsky-metoden Strongin metod
Noll ordning	Gauss metod Nelder-Mead metod Hook-Jeeves metod Rosenbrock-metoden Powell metod
Första beställning	lutning nedstigning Zeutendijk-metoden Koordinera nedstigning Konjugerad gradientmetod Kvasi-newtonska metoder Levenberg-Marquardts algoritm
andra beställning	Newtons metod Newton-Raphson-metoden Broyden-Fletcher-Goldfarb-Shanno-algoritm (BFGS)
Stokastisk	Monte Carlo metoden Simulerad glödgning Evolutionära algoritmer differentiell evolution Myralgoritm Partikelsvärmmetod Algoritm för bikoloni Random walk-metod
Linjära programmeringsmetoder _	Enkel metod Gomoris algoritm Ellipsoid metod Potentiell metod
Icke -linjära programmeringsmetoder	Sekventiell kvadratisk programmering