Gradiens módszerek

A gradiens módszerek numerikus módszerek a problémák gradiens segítségével történő megoldására, amelyek egy függvény szélsőértékének megtalálására redukálódnak .

Egyenletrendszer megoldási feladatának megállapítása optimalizálási módszerek szempontjából

Egyenletrendszer megoldásának feladata :

$\left\{{\begin{array}{lcr}f_{1}(x_{1},x_{2},\ldots ,x_{n})&=&0\\\lpontok &&\\f_{n} (x_{1},x_{2},\ldots ,x_{n})&=&0\end{tömb}}\jobbra.$ (egy)

c egyenértékű a függvény minimalizálásának problémájával $n$ $x_{1},x_{2},\ldots ,x_{n}$

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

vagy a maradékok (hibák) abszolút értékének más növekvő függvénye , . A változók függvényének minimumának (vagy maximumának) megtalálásának problémája maga is nagy gyakorlati jelentőséggel bír. $|f_{i}|$ $f_{i}=f_{i}(x_{1},x_{2},\ldots ,x_{n})$ $i=1,2,\ldots ,n$ $n$

A probléma iteratív módszerekkel történő megoldásához tetszőleges értékekkel kezdjük , és egymás utáni közelítéseket készítünk: $x_{i}^{[0]}(i=1,2,...,n)$

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

vagy koordináta szerint:

$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)

amelyek valamilyen megoldáshoz konvergálnak . ${\vec {x}}^{[k]}$ ${j\to \infty }$

Különböző módszerek különböznek a következő lépés „irányának” megválasztásában, vagyis a kapcsolatok megválasztásában

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

A lépésértéket (az extrémum keresése során adott irányban eltöltött távolságot) az értéket minimalizáló paraméter értéke határozza meg a függvényében . Ezt a függvényt általában a Taylor-kiterjesztés vagy egy interpolációs polinom közelíti meg három-öt választott értéken . Az utolsó módszer egy táblázatfüggvény max és minimum értékének meghatározására használható . $\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})$

Gradiens Methods

A módszerek fő gondolata az, hogy a legmeredekebb ereszkedés irányába menjenek, és ezt az irányt az anti-gradiens adja : $-\nabla F$

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

hol van kiválasztva: $\lambda ^{[j]}$

állandó, ebben az esetben a módszer eltérhet;
töredékes lépés, vagyis a süllyedés folyamatában a lépés hosszát elosztjuk egy bizonyos számmal;
leggyorsabb ereszkedés: $\lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F({\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F({ \vec {x}}^{[j]}))$

Legmeredekebb süllyedés módszere ( gradiens módszer )

Válassza ki azt a lehetőséget, ahol az összes derivált számításakor , és csökkentse a lépéshosszt , ahogy közeledik a függvény minimumához . $v_{i}^{[j]}=-{\frac {\partial F}{\partial x_{i))}$ $x_{i}=x_{i}^{[j]}$ $\lambda ^{[j]}$ $F$

Analitikai függvények és kis értékek esetén a Taylor bővítés lehetővé teszi az optimális lépésméret kiválasztását $F$ $f_{i}$ $F(\lambda ^{[j]})$

$\lambda ^{[j]}={\frac {\sum _{k=1}^{n}({\frac {\partial F}{\partial x_{k))})^{2)){ \sum _{k=1}^{n}\sum _{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)

ahol az összes származékot . A parabolafüggvény- interpoláció kényelmesebb lehet . $x_{i}=x_{i}^{[j]}$ $F(\lambda ^{[j]})$

Algoritmus

A kezdeti közelítés és a számítási pontosság be van állítva ${\vec {x}}^{0}\!,\,\epsilon$
Számold meg hol ${\vec {x}}^{[j+1]}={\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F\left({\vec {x}}^{[j]}\jobbra)$ $\lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F\left({\vec {x}}^{[j]}-\lambda ^{[j]} \nabla F\left({\vec {x}}^{[j]}\jobbra)\jobbra)$
Ellenőrizze a leállás állapotát:
- Ha , akkor folytassa a 2. lépéssel. $\left|{\vec {x}}^{[j+1]}-{\vec {x}}^{[j]}\right|>\epsilon$ $j=j+1$
- Ellenkező esetben álljon meg. ${\vec {x}}={\vec {x}}^{[j+1]}$

Gauss-Seidel koordináta süllyedés módszere

Ezt a módszert a Gauss-Seidel módszerrel analóg módon nevezték el lineáris egyenletrendszer megoldására. Javítja az előző módszert, mivel a következő iterációnál az ereszkedést fokozatosan hajtják végre az egyes koordináták mentén, de most egy lépésben egyszer újakat kell kiszámítani . $\lambda \quad n$

Algoritmus

A kezdeti közelítés és a számítási pontosság be van állítva ${\vec {x}}_{0}^{0},\quad \varepsilon$
Számold meg hol $\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]})}{\ részleges x_{n}}}{\vec {e}}_{n}\end{array}}\jobbra.$ $\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}\jobbra)$
Ellenőrizze a leállás állapotát:
- Ha , akkor folytassa a 2. lépéssel. $|{\vec {x}}_{n}^{[j]}-{\vec {x}}_{0}^{[j]}|>\varepsilon$ ${\vec {x}}_{0}^{[j+1]}={\vec {x}}_{n}^{[j]},\quad j=j+1$
- Ellenkező esetben álljon meg. ${\vec {x}}={\vec {x}}_{n}^{[j]}$

Konjugált gradiens módszer

A konjugált gradiens módszer a többdimenziós optimalizálás direkt módszere – a konjugált irányok módszere – elvein alapul .

A módszer másodfokú függvényekre történő alkalmazása lépésenként határozza meg a minimumot . $\mathbb {R} ^{n}$ $n$

Algoritmus

Ezeket a kezdeti közelítés és hiba adja meg: ${\vec {x}}_{0},\quad \varepsilon ,\quad k=0$
Számítsa ki a kiindulási irányt: $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}}}$
- Ha vagy , akkor hagyja abba. $||{\vec {S}}_{k}^{j+1}||<\varepszilon$ $||{\vec {x}}_{k}^{j+1}-{\vec {x}}_{k}^{j}||<\varepszilon$ ${\vec {x}}={\vec {x}}_{k}^{j+1}$
- Másképp
  - ha , akkor lépjen a 3-ra; $(j+1)<n$ $j=j+1$
  - ellenkező esetben lépjen a 2-re. ${\vec {x}}_{k+1}={\vec {x}}_{k}^{j+1},\quad k=k+1$

Lásd még

Interpolációs képletek
Matematikai programozás
- gradiens módszer
- Konjugált gradiens módszer
- Közvetlen módszerek
Taylor képlet
Numerikus módszerek
- Egyenletek numerikus megoldása
- Nelder-Mead módszer

Irodalom

Akulich I.L. Matematikai programozás példákban és feladatokban: Proc. diákgazdasági juttatás. szakember. egyetemek. - M . : Feljebb. iskola, 1986.
Gill F., Murray W., Wright M. Gyakorlati optimalizálás. Per. angolról. - M .: Mir, 1985.
Korshunov Yu.M., Korshunov Yu.M. A kibernetika matematikai alapjai. - M .: Energoatomizdat, 1972.
Maksimov Yu.A., Filipovskaya E.A. Algoritmusok nemlineáris programozási problémák megoldására. — M. : MEPhI, 1982.
Maksimov Yu.A. Algoritmusok lineáris és diszkrét programozáshoz. — M. : MEPhI, 1980.
Korn G., Korn T. Matematikai kézikönyv tudósok és mérnökök számára. - M . : Nauka, 1970. - S. 575-576.

Optimalizálási módszerek
Egydimenziós	aranymetszet módszer Kettősség Parabola módszer Rács keresés Egységes blokkkeresési módszer Fibonacci módszer Háromszoros keresés Piyavsky módszer Strongin módszer
Nulla sorrend	Gauss módszer Nelder-Mead módszer Hook-Jeeves módszer Rosenbrock módszer Powell-módszer
Első rendelés	gradiens süllyedés Zeutendijk módszer Koordináta süllyedés Konjugált gradiens módszer Kvázi-Newtoni módszerek Levenberg-Marquardt algoritmus
másodrendű	Newton módszere Newton-Raphson módszer Broyden-Fletcher-Goldfarb-Shanno algoritmus (BFGS)
Sztochasztikus	Monte Carlo módszer Szimulált lágyítás Evolúciós algoritmusok differenciális evolúció Hangya algoritmus Részecskeraj módszer Méhtelep algoritmus Véletlenszerű séta módszer
Lineáris programozási módszerek	Simplex módszer Gomori algoritmusa Ellipszoid módszer Potenciális módszer
Nemlineáris programozási módszerek	Szekvenciális kvadratikus programozás