Metoda nejprudší sestup(v anglické literatuře „method of strmější sestup“) je iterativní numerická metoda (prvního řádu) pro řešení optimalizačních problémů, která vám umožňuje určit extrém (minimum nebo maximum) účelové funkce:
jsou hodnoty argumentu funkce (řízené parametry) na skutečné doméně.
V souladu s uvažovanou metodou se určuje extrém (maximum nebo minimum) účelové funkce ve směru nejrychlejšího nárůstu (poklesu) funkce, tzn. ve směru gradientu (antigradientu) funkce. Gradientní funkce v bodě je vektor, jehož průměty na souřadnicové osy jsou parciální derivace funkce vzhledem k souřadnicím:
kde i, j,…, n jsou jednotkové vektory rovnoběžné se souřadnicovými osami.
Gradient v základním bodě 
je přísně ortogonální k povrchu a jeho směr ukazuje směr nejrychlejšího nárůstu funkce a opačný směr (antigradient) ukazuje směr nejrychlejšího poklesu funkce.
Nejstrmější způsob sestupu je další vývoj gradientová metoda sestupu. V obecný případ Proces hledání extrému funkce je iterativní procedura, která je napsána následovně:
kde znaménko "+" se používá k nalezení maxima funkce a znaménko "-" se používá k nalezení minima funkce;
Jednotkový směrový vektor, který je určen vzorcem:
- gradientový modul určuje rychlost nárůstu nebo poklesu funkce ve směru gradientu nebo antigradientu:
Konstanta, která určuje velikost kroku a je stejná pro všechny i směry.
Velikost kroku se volí z podmínky minima účelové funkce f(x) ve směru pohybu, tedy v důsledku řešení úlohy jednorozměrné optimalizace ve směru gradientu nebo antigradientu:
Jinými slovy, velikost kroku je určena řešením této rovnice:
Krok výpočtu je tedy zvolen tak, že pohyb je prováděn, dokud se funkce nezlepší, čímž v určitém bodě dosáhne extrému. V tomto bodě se opět určí směr hledání (pomocí gradientu) a hledá se nový optimální bod účelové funkce atd. V této metodě tedy probíhá vyhledávání ve větších krocích a gradient funkce se počítá v menším počtu bodů.
V případě funkce dvou proměnných tato metoda má následující geometrickou interpretaci: směr pohybu z bodu se dotýká čáry úrovně v bodě . Trajektorie klesání je klikatá, se sousedními klikatými spoji navzájem kolmými. Podmínku ortogonality vektorů sestupných směrů v sousedních bodech zapisujeme následujícím výrazem:
Trajektorie pohybu k extrémnímu bodu metodou nejstrmějšího sestupu zobrazená na grafu přímky stejné úrovně funkce f(x)
Hledání optimálního řešení končí v kroku iterativního výpočtu (několik kritérií):
Trajektorie vyhledávání zůstává v malém sousedství aktuálního vyhledávacího bodu:
Přírůstek účelové funkce se nemění:
Gradient účelové funkce v bodě lokálního minima bude nulový:
Je třeba poznamenat, že metoda gradientního klesání se při pohybu podél rokle ukazuje jako velmi pomalá a se zvyšujícím se počtem proměnných v objektivní funkci se toto chování metody stává typickým. Rokle je prohlubeň, jejíž úrovňové linie mají přibližně tvar elips s mnohonásobně se lišícími poloosami. V přítomnosti rokle má sestupová trajektorie podobu klikaté čáry s malým krokem, v důsledku čehož je výsledná rychlost klesání na minimum značně zpomalena. To se vysvětluje tím, že směr antigradientu těchto funkcí se výrazně odchyluje od směru k minimálnímu bodu, což vede k dodatečnému zpoždění ve výpočtu. V důsledku toho algoritmus ztrácí výpočetní efektivitu.
Funkce Gully
Gradientová metoda je spolu s mnoha jejími modifikacemi rozšířená a účinná metoda hledání optima studovaných objektů. Nevýhodou gradientního vyhledávání (stejně jako výše diskutovaných metod) je, že při jeho použití lze detekovat pouze lokální extrém funkce. Abych našel další lokální extrémy je třeba hledat z jiných východisek. Také rychlost konvergence gradientních metod také významně závisí na přesnosti gradientových výpočtů. Ztráta přesnosti, ke které obvykle dochází v blízkosti minimálních bodů nebo v situaci ve vpusti, může obecně narušit konvergenci procesu gradientního klesání.
Metoda výpočtu
Krok 1: Definice analytických výrazů (v symbolické formě) pro výpočet gradientu funkce
Krok 2: Nastavte počáteční aproximaci
Krok 3: Je určena potřeba restartovat algoritmickou proceduru pro resetování posledního směru hledání. V důsledku restartu se vyhledávání opět provádí ve směru nejrychlejšího klesání.
Můžete také hledat ne nejlepší bod ve směru gradientu, ale nějaký lepší než ten aktuální.
Nejjednodušší implementace ze všech lokálních optimalizačních metod. Má docela slabé podmínky konvergence, ale míra konvergence je poměrně nízká (lineární). Krok gradientová metodačasto se používá jako součást jiných optimalizačních metod, jako je metoda Fletcher–Reeves.
Popis [ | ]
Vylepšení[ | ]
Gradientní metoda klesání se při pohybu podél rokle ukazuje jako velmi pomalá a se zvyšujícím se počtem proměnných v objektivní funkci se toto chování metody stává typickým. K potírání tohoto jevu se používá, jehož podstata je velmi jednoduchá. Po dvou krocích gradientního klesání a získání tří bodů by měl být třetí krok proveden ve směru vektoru spojujícího první a třetí bod podél dna rokle.
Pro funkce blízké kvadratickému je efektivní metoda konjugovaného gradientu.
Aplikace v umělých neuronových sítích[ | ]
Metoda gradientního sestupu s určitou modifikací je široce používána pro trénování perceptronů a je známá v teorii umělých neuronových sítí jako metoda zpětného šíření. Při trénování neuronové sítě typu perceptron je nutné změnit váhové koeficienty sítě tak, aby byly minimalizovány průměrná chyba na výstupu neuronové sítě, když je na vstup dodávána sekvence trénovacích vstupních dat. Formálně, aby bylo možné provést pouze jeden krok pomocí metody gradientního sestupu (provést pouze jednu změnu v parametrech sítě), je nutné postupně odeslat na síťový vstup absolutně celou sadu trénovacích dat, vypočítat chybu pro každý objekt trénovací data a vypočítejte potřebnou korekci síťových koeficientů (tuto opravu však neprovádějte) a po odeslání všech dat vypočítejte částku v korekci každého síťového koeficientu (součet gradientů) a opravte koeficienty „jeden krok“ . Je zřejmé, že s velkou sadou trénovacích dat bude algoritmus pracovat extrémně pomalu, takže v praxi se síťové koeficienty často upravují po každém trénovacím prvku, kde je hodnota gradientu aproximována gradientem nákladové funkce, vypočítaným pouze na jednom tréninku. živel. Tato metoda se nazývá stochastický gradientní sestup nebo operační gradient klesání . Stochastický gradient klesání je formou stochastické aproximace. Teorie stochastických aproximací poskytuje podmínky pro konvergenci metody stochastického gradientu.
Odkazy [ | ]
- J. Mathews. Modul pro metodu nejstrmějšího klesání nebo gradientu. (nedostupný odkaz)
Literatura [ | ]
- Akulich I. L. Matematické programování v příkladech a úlohách. - M.: Vyšší škola, 1986. - S. 298-310.
- Gill F., Murray W., Wright M. Praktická optimalizace = Praktická optimalizace. - M.: Mir, 1985.
- Korshunov Yu., Korshunov Yu. Matematické základy kybernetiky. - M.: Energoatomizdat, 1972.
- Maksimov Yu A., Fillipovskaya E. A. Algoritmy pro řešení problémů nelineárního programování. - M.: MEPhI, 1982.
- Maksimov Ju. Algoritmy pro lineární a diskrétní programování. - M.: MEPhI, 1980.
- Korn G., Korn T. Příručka matematiky pro vědce a inženýry. - M.: Nauka, 1970. - S. 575-576.
- S. Yu Gorodetsky, V. A. Grishagin. Nelineární programování a multiextrémní optimalizace. - Nižnij Novgorod: Univerzitní nakladatelství Nižnij Novgorod, 2007. - s. 357-363.
Pravidla pro zadání funkce
V nejstrmější způsob sestupu jako směr hledání je zvolen vektor, jehož směr je opačný než směr gradientového vektoru funkce ▽f(x). Z matematická analýza je známo, že vektor grad f(x)=▽f(x) charakterizuje směr nejrychlejšího nárůstu funkce (viz gradient funkce). Proto je volán vektor - grad f (X) = -▽f(X). anti-gradient a je směrem jeho nejrychlejšího poklesu. Rekurentní vztah, se kterým je implementována metoda nejstrmějšího klesání, má tvar X k +1 =X k - λ k ▽f(x k), k = 0,1,...,
kde λ k >0 je velikost kroku. V závislosti na volbě velikosti kroku můžete získat různé možnosti gradientová metoda. Pokud je během optimalizačního procesu velikost kroku λ pevná, pak se metoda nazývá gradientní metoda s diskrétním krokem. Optimalizační proces v prvních iteracích lze výrazně urychlit, pokud λ k vybereme z podmínky λ k =min f(X k + λS k) .
K určení λ k se používá jakákoliv jednorozměrná optimalizační metoda. V tomto případě se metoda nazývá metoda nejstrmějšího sestupu. Obecně platí, že jeden krok k dosažení minima funkce nestačí, proces se opakuje, dokud následující výpočty nezlepší výsledek.
Pokud je prostor v některých proměnných velmi protáhlý, vytvoří se „rokle“. Hledání se může zpomalit a klikatit přes dno „rokle“. Někdy nelze řešení dosáhnout v přijatelném časovém rámci.
Další nevýhodou metody může být kritérium zastavení ||▽f(X k)||<ε k , так как этому условию удовлетворяет и седловая точка, а не только оптимум.
Příklad. Počínaje bodem x k =(-2, 3) určete bod x k +1 pomocí metody nejstrmějšího sestupu, abyste minimalizovali funkci.
Jako směr hledání vyberte vektor přechodu v aktuálním bodě 
Podívejme se na kritérium zastavení. My máme 
Vypočítejme hodnotu funkce v počátečním bodě f(X 1) = 35. Udělejme
krok po antigradientním směru
Pojďme vypočítat hodnotu funkce v novém bodě
f(X 2) = 3(-2 + 19λ 1) 2 + (3-8λ 1) 2 - (-2 + 19λ 1)(3-8λ 1) - 4(-2 + 19λ 1)
Najdeme takový krok, aby účelová funkce dosáhla minima v tomto směru. Z nutné podmínky pro existenci extrému funkce
f’(X 2) = 6(-2 + 19λ 1) 19 + 2(3-8λ 1)(-8) – (73 – 304 λ 1) – 4*19
nebo f'(X 2) = 2598 λ 1 – 425 = 0.
Dostaneme krok λ 1 = 0,164
Dokončení tohoto kroku povede k věci 
ve kterém je hodnota gradientu 
, funkční hodnota f(X 2) = 0,23. Přesnost není dosažena, z bodu uděláme krok ve směru antigradientu.
f(X 2) = 3(1,116 – 1,008λ 1) 2 + (1,688-2,26λ 1) 2 - (1,116 – 1,008λ 1)(1,688-2,26λ 1) - 4 (1,116 – 1,016 λ
f’(X 2) = 11,76 – 6,12λ 1 = 0
Dostaneme λ 1 = 0,52 
Anotace: Tato přednáška široce pokrývá takové metody multiparametrové optimalizace, jako je metoda nejstrmějšího sestupu a metoda Davidon–Fletcher–Powell. Kromě toho je provedena srovnávací analýza výše uvedených metod za účelem určení té nejúčinnější, jsou identifikovány jejich výhody a nevýhody; a také zvažuje multidimenzionální optimalizační problémy, jako je roklinová metoda a multiextrémní metoda.
1. Metoda nejstrmějšího klesání
Podstatou této metody je použití výše zmíněného metoda souřadnicového sestupu vyhledávání se provádí z daného bodu ve směru rovnoběžném s jednou z os k minimálnímu bodu v tomto směru. Hledání se pak provádí ve směru rovnoběžném s druhou osou a tak dále. Směry jsou samozřejmě pevně dané. Zdá se rozumné pokusit se tuto metodu upravit tak, aby v každé fázi bylo hledání minimálního bodu prováděno v "nejlepším" směru. Není jasné, který směr je „nejlepší“, ale to se ví směr gradientu je směr nejrychlejšího nárůstu funkce. Opačný směr je tedy směr nejrychlejšího poklesu funkce. Tuto vlastnost lze zdůvodnit následovně.
Předpokládejme, že se pohybujeme z bodu x do dalšího bodu x + hd, kde d je určitý směr a h je krok určité délky. V důsledku toho se pohyb provádí z bodu (x 1, x 2, ..., x n) do bodu (x 1 + zx 1, x 2 + zx 2, ..., x n + zx n), Kde
Změna hodnot funkcí je určena vztahy
| (1.3) |
Až do prvního řádu zx i , přičemž parciální derivace se počítají v bodě x . Jak zvolit směry d i, které splňují rovnici (1.2), abychom získali co největší hodnotu změny funkce df? Zde nastává problém maximalizace s omezením. Aplikujme metodu Lagrangeových multiplikátorů, s jejichž pomocí určíme funkci
Hodnota df splňující omezení (1.2) dosáhne svého maxima, když funkce
Dosahuje maxima. Jeho derivát
Proto,
 |
(1.6) |
Potom di ~ df/dx i a směr d je rovnoběžný se směrem V/(x) v bodě x.
Tím pádem, největší lokální nárůst funkce pro daný malý krok h nastane, když d je směr Vf(x) nebo g(x) . Proto je směr nejstrmějšího klesání směr
V jednodušší podobě lze rovnici (1.3) napsat takto:
Kde je úhel mezi vektory Vf(x) a dx. Pro danou hodnotu dx minimalizujeme df zvolením, že směr dx se shoduje se směrem -Vf(x) .
Komentář. Směr přechodu kolmo k libovolnému bodu na přímce konstantní úrovně, protože podél této přímky je funkce konstantní. Pokud je tedy (d 1, d 2, ..., d n) malý krok podél linie úrovně, pak
A proto
 |
(1.8) |
