A gradiens algoritmus olyan algoritmus számára optimalizálása differenciálható. Ezért célja, hogy minimalizálják a valódi differenciálható függvény definiált egy euklideszi térben (például a térben N- tuple a valós számok, felruházva egy pont termék ), vagy még általánosabban, egy Hilbertian helyet . Az algoritmus iteratív, ezért egymást követő fejlesztésekkel halad. Az aktuális ponton egy elmozdulást hajtanak végre a gradienssel ellentétes irányban a funkció csökkentése érdekében. Az ezen irányú elmozdulást a lineáris keresés néven ismert numerikus technika határozza meg . Ez a leírás megmutatja, hogy az algoritmus az ereszkedési irányú algoritmusok családjának része .
Az optimalizálási algoritmusokat általában egy funkció minimalizálása céljából írják. Ha egy függvényt maximalizálni akarunk, akkor elegendő az ellenkezőjének minimalizálása.
Fontos szem előtt tartani azt a tényt, hogy a gradiens és ezért az elmozdulás iránya attól a skalár szorzattól függ, amely a Hilbert-teret felszereli; az algoritmus hatékonysága ezért ettől a skalár szorzattól függ.
A gradiens algoritmus is ismert a neve algoritmus legmeredekebb lejtő vagy a legmélyebb süllyedés ( legmeredekebb származású , angol nyelven), mert a gradiens a lejtőn a linearizált függvény az adott ponton, és ezért helyileg, legmeredekebb lejtőn (fogalom amely a skaláris szorzattól függ).
A legegyszerűbb változatban az algoritmus csak egy korlátozatlan optimalizálási probléma álló helyzetének (azaz egy olyan pontnak a megkeresését vagy megközelítését teszi lehetővé) (azaz egy olyan pontot, ahol a minimalizálandó függvény gradiense nulla) . Az ilyen pontok globális minimumok, ha a függvény domború. A kiterjesztések ismertek az egyszerű megszorításokkal, pl. A kötött korlátozásokkal kapcsolatos problémák miatt . A kielégítő elméleti konvergencia eredmények ellenére ez az algoritmus általában lassú, ha a gradienst meghatározó dot szorzat nem változik az aktuális ponttól megfelelő módon, vagyis ha a vektortér nem rendelkezik megfelelő Riemann-struktúrával , ráadásul nehéz előzetesen adja meg . Ezért őszintén szólva nem ajánlott két változó szigorúan domború másodfokú függvényének minimalizálása sem . Elméleti tulajdonságai azonban azt jelentik, hogy az algoritmus modellként szolgál az algoritmusok családjához, amelyek leszármazási vagy mentési irányúak a megbízhatósági régióval rendelkező algoritmusokban .
Ennek az algoritmusnak az elve legalább Cauchyig (1847) nyúlik vissza .
Hagy egy Hilbert-tér ( jelöljük skalár szorzat és jelöljük kapcsolódó norma ), és egy differenciálható függvény . Jelöljük a differenciál az en és a gradiens az en , úgy, hogy minden irányban , van .
Gradiens algoritmus - Adunk magunknak egy kezdeti pontot / iterációt és egy tolerancia küszöböt . A gradiens algoritmus iterációk sorozatát definiálja , amíg a stop teszt nem teljesül. Úgy megy , hogy a következő lépéseket.
A gyakorlatban szükséges lesz szedni ; ennek a toleranciának a nullértékét csak azért engedték meg, hogy egyszerűsítsék az alábbiakban a konvergencia eredményeinek kifejezését.
Ez a szerkezetileg nagyon egyszerű algoritmus azon a tényen alapul, hogy egy pont szomszédságában a függvény az en gradiensével ellentétes irányban , vagyis az irányban csökken a legerősebben . Pontosabban, ez az állítás szuggesztív módon fejezi ki azt a tényt, hogy ha az optimalizálási probléma megoldása
az irány , ezért a gradiens ellentéte felé irányul.
A legerősebb lejtés irányának fogalma valójában rosszul van meghatározva, mert erősen függ a skaláris szorzattól, amelyet az ember a Hilbert-térben ad magának . Valójában, ha van egy másik skaláris szorzat , létezik egy pozitív, határozott, önmagához kapcsolódó folytonos lineáris operátor, így az utolsó skaláris szorzat en gradiense fel van írva , amely kifejezetten megmutatja a gradiens függését a dot szorzattól. Ezért nincs egyetlen meredekebb lejtésirány, amely nem tűnik egyértelműen az előző bekezdés elején tett nyilatkozatban. Még azt is megmutathatjuk, hogy az en bármelyik leereszkedési iránya , vagyis bármilyen iránya ilyen , ellentétes az en gradiensével egy bizonyos skaláris szorzat esetén . A gradiens algoritmus hatékonysága tehát ennek a skaláris szorzatnak a megválasztásától függ.
Ha az irány egy irányt származású származó en , mivel annak érdekében, hogy mindenre elég kicsi, van
.
A lineáris keresésnek köszönhetően, amíg az algoritmus szigorúan csökkenti a függvényt minden egyes iterációnál:
A gradiens algoritmus akkor használható, ha a vektortér, amelyen a minimalizálandó funkció meghatározva van, végtelen méretű. Ebben az esetben az algoritmus nem valósítható meg, de tanulmánya érdekes lehet viselkedésének nagy dimenziókban történő megismeréséhez, vagy konvergencia tulajdonságainak elméleti célokra történő felhasználásához.
A gradiens algoritmus úgy értelmezhető, mint a közönséges differenciálegyenlet ( gradiens áramlás ) megoldásának explicit Euler-módszere , diszkrétizációs lépéssel lineáris kereséssel adaptálva az aktuális iterációra .
Először azt az esetet vesszük figyelembe, amikor a kritérium egy szigorúan konvex kvadratikus függvény, amelyet egy euklideszi téren határozunk meg (tehát véges dimenziójú):
hol és hol van pozitív határozott önadduktív operátor . Ebben az esetben a gradiens algoritmusa pontos lineáris kereséssel (azaz minden egyes iterációnál a kritérium minimálisra csökken a gradienssel ellentétes irány mentén) q-lineárisan konvergál a probléma egyedi minimumához. Pontosabban: a konvergencia következő eredménye van, amely az f kritérium hesseni H feltételezését használja , vagyis a legnagyobb sajátértéke és a legkisebb sajátértéke arányát ,
és a H-hez társított norma , amelyet az határoz meg
Konvergencia szigorúan konvex másodfokú függvényen - Legyen f másodfokú függvény szigorúan konvex egy euklideszi téren, Hessian H-n . Használt, hogy csökkentsék ezt a funkciót, a gradiens algoritmust fenti, és a pontos lineáris keresés , generál egy sorozatot konvergáló Q-lineárisan felé egyedi minimális x * a F . Pontosabban megvan
Mint a konvergencia sebességének fenti becslése az f ( x ) kritériumra is vonatkozik az optimális f ( x * ) érték felé .
Ez az eredmény vonzónak tűnhet, és arra utalhat, hogy a gradiens algoritmus hatékony módszer, de általában nem az. Egyrészt a lineáris konvergencia viszonylag gyenge tulajdonság a differenciálható optimalizálásban, annál gyengébb, mivel a konvergencia mértéke (itt ) közel 1. Ez akkor fordul elő a gradiens algoritmusban, amikor nagy, c ', azaz rosszul kondicionált problémák. Ezzel ellentétben, amikor (azaz a Hessianus az identitás többszöröse), az algoritmus 1 iterációban konvergál. Emlékeztetni kell arra is, hogy a szigorúan konvex másodfokú függvény minimalizálása érdekében a konjugált gradiens algoritmusa vagy a kapcsolódó lineáris rendszer megoldásának bármely közvetlen módszere véges számú művelet során megtalálja a minimumot (pontos számtanban), míg az algoritmus gradiens általában megköveteli végtelen számú iteráció.
Az iterációk evolúcióját az algoritmus során a jobb oldali ábra szemlélteti: f két változó konvex függvénye (a síkon definiálva ), grafikonja pedig egy tál alakú. Minden kék görbe egy standard görbe az F , a pontok helye, ahol f jelentése egy adott állandó. Mindegyik vörös vektor elmozdulást jelent , amely az gradiens irányának ellentétes irányú az x k-ban . Itt az x k gradiens az euklideszi skaláris szorzathoz társított gradiens , tehát ortogonális (az euklideszi skaláris szorzat esetében) az x k- nél lévő érintőhöz annak a kontúrvonalhoz, amelyhez x k tartozik. Az ábra szemlélteti az iterációk haladását a tál alja felé, vagyis azon pont felé, ahol az f értéke minimális.
A gradiens emelkedési módszer alkalmazása a függvényre
Tervnézet kontúrvonalakkal
Háromdimenziós nézet
Ennek a trigonometrikus függvénynek a fenti illusztrációja a gradiens módszer cikk-cakk jellegét mutatja, annak a ténynek köszönhető, hogy az egyik iterált gradiens merőleges az előző gradiensére. Meg kell jegyezni, hogy az algoritmus konvergenciája ellenére ez utóbbi viszonylag lassú e cikk-cakk előrelépés miatt.
A gradiens algoritmusának könnyen megfigyelhető hibája állandó lépcsőfokú, mivel nem konvergenciája a túl magas lépéseknél, ez még azoknak a függvényeknek is, amelyeknek elméletileg össze kellene vonniuk. Az alábbi funkció tipikus eset. A gyakorlatban 0,01 lépéssel az algoritmus kevesebb, mint 150 iterációban konvergál. De ha úgy döntünk, hogy választunk egy 0,1-es lépést, akkor az algoritmus egyszerűen nem fog közeledni. Ellenőrizhetjük, hogy az algoritmus korlátlanul hurkol-e ugyanazon két érték között.
A gradiens algoritmus számos problémával szembesülhet, különös tekintettel a konvergenciára, amikor a függvény minimuma egy keskeny völgy alján van (pontosabban, ha a Hessian-mátrix kondicionálása magas). Ilyen esetben az { x k } szekvenciája a völgy mindkét oldalán oszcillál és fáradságosan halad, még akkor is, ha az α k-t úgy választják meg, hogy minimalizálja az f ( b ) értéket .
Az alábbi ábra szemlélteti ezt a típusú viselkedést egy kétdimenziós Rosenbrock-függvény esetében .
A gradiens algoritmus két gyenge pontja:
Az algoritmus legtermészetesebb javulása a lineáris keresés Newton-módszere, amelynek konvergenciája kvadratikus, és garantált, ha a konvergencia eredményei részben említett feltételezésekkel rendelkezik.
Hatékony alternatíva a BFGS módszer , amely minden lépésben egy mátrix kiszámítását jelenti, amely a gradienssel megszorozva jobb irányt ad. Sőt, ez a módszer kombinálható egy hatékonyabb lineáris keresési módszerrel az α legjobb értékének elérése érdekében .
A gradiens algoritmus rosszul van definiálva a nem sima funkciók minimalizálása érdekében, még akkor is, ha domborúak. Ha a kritérium helyi értelemben Lipschitz-féle, és különösen, ha domború, akkor a tárcsa algoritmus orvosolja a konvergencia hiányát.
hol van az identitás, és a par-ban definiált operátor van-e (felismerjük a közvetlen BFGS- képletet az identitás frissítésére). Mivel az önadduktív és határozottan pozitív a dot termék számára , a bilinear térkép egy pont szorzat. Sőt, megvan , hogy a skaláris szorzat gradiense , amely érdemes , nem más, mint ahogyan bejelentettük.
J. Ch. Gilbert, A differenciálható optimalizálás elemei - elmélet és algoritmusok , tanterv az ENSTA ParisTech-en , Párizs.
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">