Gradiens süllyedés

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. július 17-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A gradiens süllyedés, a gradiens süllyedés módszere egy numerikus módszer egy függvény lokális minimumának vagy maximumának meghatározására egy gradiens mentén történő mozgással, amely a modern optimalizálás egyik fő numerikus módszere.

A számítási matematikában nem csak optimalizálási (minimalizálási) feladatok közvetlen megoldására, hanem az optimalizáló nyelven átírható feladatokra is aktívan alkalmazzák (nemlineáris egyenletek megoldása, egyensúlyok keresése, inverz feladatok stb.). A gradiens süllyedés módszere használható optimalizálási feladatok végtelen dimenziós terekben, például optimális szabályozási feladatok numerikus megoldására.

Az utóbbi években a gradiens módszerek iránti különösen nagy érdeklődés annak köszönhető, hogy a gradiens süllyedések és azok sztochasztikus/randomizált változatai szinte minden modern adatelemzési tanulási algoritmus alapját képezik.

Leírás

A célfüggvény nézzen ki így:

F({\vec {x}}):\;\mathbb {X} \to \mathbb {R}

És az optimalizálási probléma a következő:

F({\vec {x}})\to \min _({\vec {x}}\in \mathbb {X}} }

Abban az esetben, ha használat helyett a maximumot kell megtalálni $F({\vec {x)))$ $-F({\vec {x)))$

A módszer fő gondolata, hogy a legmeredekebb ereszkedés irányába menjünk, és ezt az irányt az antigradiens adja : $-\nabla F$

{\vec {x}}^{[j+1]}={\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F\left({\vec {x}}^{[j]}\jobbra)

ahol a gradiens süllyedési sebességét határozza meg, és választható $\lambda ^{[j]}$

állandó (ebben az esetben a módszer eltérhet);
csökkenő a gradiens süllyedés során;
garantálja a leggyorsabb ereszkedést:
1. Hogy megtaláljuk a minimumot, megkapjuk $F\left({\vec {x}}\right)$ $\lambda ^{[j]}=\mathrm {argmin} _{\lambda }F\left({\vec {x}}^{[j+1]}\right)=\mathrm {argmin} _{\lambda }\,F\left({\vec {x}}^{[j]}-\lambda \nabla F\left({\vec {x}}^{[j]}\jobbra)\ jobb)$
2. Hogy megtaláljuk a maximumot, megkapjuk $F\left({\vec {x}}\right)$ $\lambda ^{[j]}=\mathrm {argmax} _{\lambda }F\left({\vec {x}}^{[j+1]}\right)=\mathrm {argmax} _{\lambda }\,F\left({\vec {x}}^{[j]}+\lambda \nabla F\left({\vec {x}}^{[j]}\jobbra)\ jobb)$

Algoritmus

Állítsa be a kezdeti közelítést és a számítási pontosságot ${\vec {x}}^{0},\varepsilon$
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 \nabla F\left( {\vec {x}}^{[j]}\jobbra)\jobbra)$
Ellenőrizze a leállás állapotát:
- Ha , vagy (válasszon egyet a feltételek közül), akkor folytassa a 2. lépéssel. $\left|{\vec {x}}^{[j+1]}-{\vec {x}}^{[j]}\right|>\varepsilon$ $\left|F\left({\vec {x}}^{[j+1]}\right)-F\left({\vec {x}}^{[j]}\jobb)\ jobbra|>\varepsilon$ $\left\|\nabla F\left({\vec {x}}^{[j+1]}\right)\right\|>\varepsilon$ $j=j+1$
- Ellenkező esetben álljon meg. ${\vec {x}}={\vec {x}}^{[j+1]}$

A Kantorovich-reláció

Az alak másodfokú függvényében a legmeredekebb gradiens keresési módszer bármely kiindulási pontból egy geometriai haladási sebességgel (lineárisan) konvergál , amelynek nevezője nem haladja meg a . Ebben az esetben a következő becslések érvényesek: ${\frac {x^{T}\Gamma x}{2}}+c^{T}x,\Gamma ^{T}=\Gamma$ $x_{0}$ $q$

\exists a=a(x_{0}),T>0:0\leq a\leq q={\frac {\left(\lambda _{min}/\lambda _{max}-1\right)^ {2}}{\left(\lambda _{min}/\lambda _{max}+1\right)^{2}}}

f(x_{k})-f(x^{*})\leq a^{k}(f(x_{0})-f(x^{*}))

\|x_{k}-x^{*}\|\leq Ta^{k/2}\|x_{0}-x^{*}\|

ahol és a második derivált mátrixának minimális és maximális sajátértéke . $\lambda _{min}$ $\lambda _{max}$ $\nabla ^{2}f(x)=\Gamma$

Így, mivel a függvény kis mértékben közel van a másodfokú közelítéséhez, a konvergencia sebessége a minimumpont közelében a sajátértékek arányától függ. Minél nagyobb ez az arány, annál rosszabb a módszer konvergenciája.

Példa

Alkalmazzuk a gradiens módszert a függvényre . Ekkor az egymást követő közelítések így fognak kinézni: $F(x,y)=\sin \left({\frac {1}{2}}x^{2}-{\frac {1}{4}}y^{2}+3\right)\cos (2x+1-e^{y})$

Ez egy tipikus példa a szakadék funkcióra. A gradiens módszer "ugrik" a szakadék egyik lejtőjéről a másikra és vissza, néha szinte anélkül, hogy a megfelelő irányba mozdulna el, ami jelentősen lelassítja a konvergenciát. Egy másik példa a tesztvízcsatorna függvényre a Rosenbrock függvény .

Fejlesztések, módosítások

A gradiens irányú függvényének minimalizálására egydimenziós optimalizálási módszereket alkalmaznak , például az aranymetszet módszert . Nem is a gradiens irányában kereshet a legjobb pontot, hanem az aktuálisnál jobbat.

A gradiens süllyedés módszere a legkönnyebben megvalósítható az összes helyi optimalizálási módszer közül. Meglehetősen gyengék a konvergencia feltételei, de a konvergencia ráta meglehetősen kicsi (lineáris). A gradiens módszer lépését gyakran használják más optimalizálási módszerek, például a Fletcher-Reeves módszer részeként .

A gradiens süllyedés módszere nagyon lassúnak bizonyul szakadék mentén haladva, és a célfüggvény-változók számának növekedésével a módszernek ez a viselkedése válik jellemzővé. A jelenség leküzdésére a szakadékos módszert alkalmazzák , amelynek lényege nagyon egyszerű. Két lépcsős ereszkedési lépés megtétele és három pont megszerzése után a harmadik lépést az első és harmadik pontot összekötő vektor irányába kell megtenni, a szakadék alján.

A másodfokúhoz közeli függvények esetén a konjugált gradiens módszer hatékony .

Alkalmazások mesterséges neurális hálózatokban

A gradiens leereszkedési módszert némi módosítással széles körben használják a perceptron képzésére, és a mesterséges neurális hálózatok elméletében backpropagation módszerként ismert . Perceptron típusú neurális hálózat betanításakor a hálózat súlyegyütthatóit úgy kell megváltoztatni, hogy a neurális hálózat kimenetének átlagos hibája minimális legyen, amikor a betanítási bemeneti adatok sorozatát betáplálják a bemenetre. . Formálisan ahhoz, hogy a gradiens süllyedés módszere szerint csak egy lépést tegyen meg (csak egy változtatást hajtson végre a hálózati paraméterekben), szükséges, hogy a teljes képzési adatkészletet szekvenciálisan betápláljuk a hálózati bemenetre, és ki kell számítani a hibát minden betanítási adatra. objektumot, és számítsa ki a hálózati együtthatók szükséges korrekcióját (de ne végezze el ezt a korrekciót), majd az összes adat elküldése után számítsa ki az egyes hálózati együtthatók korrekciójának összegét (gradiensek összege), és javítsa ki az együtthatókat „egy lépéssel” . Nyilvánvaló, hogy nagy mennyiségű betanítási adathalmaz esetén az algoritmus rendkívül lassan fog működni, ezért a gyakorlatban a hálózati együtthatókat gyakran minden egyes betanítási elem után módosítják, ahol a gradiens értékét a költségfüggvény csak egyre számított gradiensével közelítik. képzési elem. Ezt a módszert sztochasztikus gradiens süllyedésnek vagy operatív gradiens süllyedésnek nevezik . A sztochasztikus gradiens süllyedés a sztochasztikus közelítés egyik formája. A sztochasztikus közelítések elmélete feltételeket ad a sztochasztikus gradiens süllyedés módszerének konvergenciájához.

Linkek

J. Mathews. A legmeredekebb süllyedés vagy gradiens módszer modulja.
A leggyorsabb Pyu módszer metaforikus interaktív bemutatója

Irodalom

Polyak B. T. Bevezetés az optimalizálásba. - M . : Tudomány. Fizikai és matematikai irodalom főkiadása, 1983. - 384 p.
Nesterov Yu. E. A konvex optimalizálás módszerei . - M. : MTSNMO Kiadó, 2010. - 281 p.
Gasnikov AV Modern numerikus optimalizálási módszerek. Az egyetemes gradiens süllyedés módszere: Tanulmányi útmutató . - M. : MIPT, 2018. - 291 p. - ISBN 978-5-7417-0667-1 .
Akulich IL Matematikai programozás példákban és feladatokban. - M . : Felsőiskola, 1986. - S. 298-310.
Gill F., Murray W., Wright M. Gyakorlati optimalizálás = Practical Optimization. - M .: Mir, 1985.
Korshunov Yu. M., Korshunov Yu. M. A kibernetika matematikai alapjai. - M .: Energoatomizdat, 1972.
Maksimov Yu. A., Filippovskaya EA Algoritmusok nemlineáris programozási problémák megoldására. — M. : MEPhI, 1982.
Maksimov Yu. A. Lineáris és diszkrét programozási algoritmusok. — 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.
Gorodetsky S. Yu., Grishagin VA Nemlineáris programozás és multi-extremális optimalizálás. - Nyizsnyij Novgorod: Nyizsnyij Novgorod Egyetem Kiadója, 2007. - S. 357-363.

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