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 metody gradientu se často používá jako součást jiných optimalizačních metod, jako je metoda Fletcher–Reeves.
Popis [ | ]
Vylepšení[ | ]
Metoda gradientového klesání se ukazuje jako velmi pomalá při pohybu podél rokle a se zvýšením počtu proměnných Objektivní funkce toto chování metody se stává typickým. K boji proti tomuto 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é je metoda konjugovaného gradientu účinná.
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.
Nejstrmější metodou klesání je metoda gradientu s proměnným krokem. Při každé iteraci se velikost kroku k volí z podmínky minima funkce f(x) ve směru sestupu, tzn.
Tento stav znamená, že k pohybu po antigradientu dochází tak dlouho, dokud hodnota funkce f (x) klesá. Z matematického hlediska je při každé iteraci nutné řešit problém jednorozměrné minimalizace funkcí
()=f (x (k) -f (x (k)))
Použijme k tomu metodu zlatého řezu.
Algoritmus metody nejstrmějšího sestupu je následující.
Jsou zadány souřadnice počátečního bodu x (0).
V bodě x (k) , k = 0, 1, 2, ... se vypočítá hodnota gradientu f (x (k)).
Velikost kroku k je určena jednorozměrnou minimalizací pomocí funkce
()=f (x(k)-f(x(k))).
Souřadnice bodu x (k) jsou určeny:
x i (k+1) = x i (k) - kf i (x (k)), i=1, …, n.
Kontroluje se podmínka pro zastavení iteračního procesu:
||f (x (k +1))|| .
Pokud je splněno, výpočty se zastaví. V opačném případě přistoupíme ke kroku 1. Geometrická interpretace metody nejstrmějšího klesání je uvedena na Obr. 1.
Rýže. 2.1. Blokové schéma metody nejstrmějšího klesání.
Implementace metody v programu:
Metoda nejstrmějšího klesání.
Rýže. 2.2. Realizace metody nejstrmějšího sestupu.
Závěr: V našem případě metoda konvergovala v 7 iteracích. Bod A7 (0,6641; -1,3313) je extrémní bod. Metoda konjugovaných směrů. Pro kvadratické funkce můžete vytvořit gradientní metodu, ve které bude čas konvergence konečný a rovný počtu proměnných n.
Nazvěme určitý směr a konjugujeme s ohledem na nějakou pozitivně definitní Hessovu matici H, pokud:
Tedy pro jednotku H znamená sdružený směr jejich kolmici. V obecném případě je H netriviální. V obecný případ konjugace je aplikace Hessovy matice na vektor - to znamená otočení tohoto vektoru o nějaký úhel, jeho natažení nebo stlačení.
A nyní je vektor ortogonální, tj. konjugace není ortogonalita vektoru, ale ortogonalita rotovaného vektoru, tj.
Rýže. 2.3. Blokové schéma metody sdružených směrů.
Implementace metody v programu: Metoda konjugovaných směrů.
Rýže. 2.4. Implementace metody konjugovaných směrů.
Rýže. 2.5. Graf metody konjugovaných směrů.
Závěr: Bod A3 (0,6666; -1,3333) byl nalezen ve 3 iteracích a je extrémním bodem.
3. Analýza metod pro stanovení minimální a maximální hodnoty funkce za přítomnosti omezení
Připomeňme si to společný úkol podmíněná optimalizace vypadá takto
f(x) ® min, x О W,
kde W je vlastní podmnožina R m. Podtřída problémů s omezeními typu rovnosti se vyznačuje tím, že množina je definována omezeními tvaru
fi (x) = 0, kde fi: Rm®R (i = 1, …, k).
TedyW = (x О R m: f i (x) = 0, i = 1, …, k).
Pro funkci f bude pro nás výhodné napsat index "0". Optimalizační problém s omezeními typu rovnosti je tedy zapsán jako
f 0 (x) ® min, (3,1)
f i (x) = 0, i = 1, …, k. (3.2)
Označíme-li nyní f funkci na R m s hodnotami v R k, jejíž souřadnicový zápis má tvar f(x) = (f 1 (x), ..., f k (x)), pak ( 3.1)–(3.2) můžeme napsat i ve tvaru
f0(x)® min, f(x) = Q.
Geometricky je problémem omezení typu rovnosti problém najít nejnižší bod grafu funkce f 0 nad varietou (viz obr. 3.1).
Body, které splňují všechna omezení (tj. body v množině ), se obvykle nazývají přípustné. Přípustný bod x* se nazývá podmíněné minimum funkce f 0 za podmínek f i (x) = 0, i = 1, ..., k (nebo řešení úlohy (3.1)–(3.2)), pokud pro všechny přípustné body x f 0 (x *) f 0 (x). (3.3)
Je-li (3.3) splněno pouze pro přípustné x ležící v nějakém okolí V x * bodu x*, pak hovoříme o lokálním podmíněném minimu. Koncepty podmíněných přísných lokálních a globálních minim jsou definovány přirozeným způsobem.
V této verzi gradientní metody je také minimalizační sekvence (X k) konstruována podle pravidla (2.22). Velikost kroku ak je však nalezena jako výsledek řešení pomocného jednorozměrného minimalizačního problému
min(j k (a) | a>0), (2,27)
kde jk(a)=f(Xk - a·(Xk)). Tedy při každé iteraci ve směru antigradientu 
je proveden vyčerpávající sestup. K vyřešení problému (2.27) můžete použít jednu z metod jednorozměrného vyhledávání popsaných v části 1, například metodu bitového vyhledávání nebo metodu zlatého řezu.
Popišme algoritmus metody nejstrmějšího sestupu.
Krok 0. Nastavte parametr přesnosti e>0, vyberte X 0 ОE n, nastavte k=0.
Krok 1. Najděte (X k) a zkontrolujte podmínku pro dosažení zadané přesnosti || (x k) ||£ e. Pokud je splněno, přejděte ke kroku 3, v opačném případě ke kroku 2.
Krok 2.Řešit problém (2.27), tzn. najít k. Najděte další bod, dejte k=k+1 a přejděte ke kroku 1.
Krok 3 Dokončete výpočty zadáním X * = X k, f * = f(X k).
Minimalizujte funkci
f(x)=x12+4x22-6x1-8x2+13; (2,28)
Nejprve vyřešme problém klasický metoda. Zapišme soustavu reprezentujících rovnic potřebné podmínky bezpodmínečný extrém
Po vyřešení dostaneme stacionární bod X*=(3;1). Dále zkontrolujeme provedení dostatečný stav, pro kterou najdeme matici druhých derivací
Protože podle Sylvesterova kritéria je tato matice kladně určitá pro ", pak nalezený bod X* je minimálním bodem funkce f(X). Minimální hodnota f *=f(X*)=0. Toto je přesné řešení problému (11).
Proveďme jednu iteraci metody gradientní sestup pro (2,28). Zvolme počáteční bod X 0 =(1;0), nastavíme počáteční krok a=1 a parametr l=0,5. Vypočítejme f(X 0)=8.
Najděte gradient funkce f(X) v bodě X 0
(X 0) = = (2,29)
Definujme nový bod X=X 0 -a· (X 0) výpočtem jeho souřadnic
x 1 = 
x 2 = 
(2.30)
Vypočítejme f(X)= f(X 0 -a· (X 0))=200. Protože f(X)>f(X 0), rozdělíme krok za předpokladu a=a·l=1·0,5=0,5. Počítáme opět pomocí vzorců (2.30) x 1 =1+4a=3; x 2 =8a=4 a najděte hodnotu f(X)=39. Protože opět f(X)>f(X 0), dále zmenšujeme velikost kroku nastavením a=a·l=0,5·0,5=0,25. Vypočítáme nový bod se souřadnicemi x 1 =1+4·0,25=2; x 2 =8·0,25=2 a hodnota funkce v tomto bodě f(X)=5. Protože podmínka pro snížení f(X) Proveďme jednu iteraci pomocí metody nejprudší sestup pro (2.28) se stejným počátečním bodem X 0 =(1;0). Pomocí již nalezeného gradientu (2.29) najdeme X= X 0 -a· (X 0) a sestrojte funkci j0(a)=f(X0-a·(X0))=(4a-2)2+4(8a-1)2. Jeho minimalizací pomocí nutné podmínky j 0 ¢(a)=8·(4a - 2)+64·(8a - 1)=0 najdeme optimální hodnotu velikosti kroku a 0 =5/34. Určení bodu minimalizační sekvence X 1 = X 0 -a 0 · (X 0) Gradient diferencovatelné funkce f(x) v bodě X volal n-rozměrný vektor f(x)
, jehož komponenty jsou parciálními derivacemi funkce f(x), vypočítané v bodě X, tj. f"(x ) = (df(x)/dh 1 , …, df(x)/dx n) T . Tento vektor je kolmý k rovině procházející bodem X a tečnou k rovnému povrchu funkce f(x), procházející bodem X.V každém bodě takové plochy funkce f(x) nabývá stejné hodnoty. Přirovnáním funkce k různým konstantním hodnotám C 0, C 1, ... získáme řadu povrchů charakterizujících její topologii (obr. 2.8). Vektor gradientu je směrován ve směru nejrychlejšího nárůstu funkce v daném bodě. Vektor opačný k přechodu (-f'(x))
, volal anti-gradient a směřuje k nejrychlejšímu poklesu funkce. V minimálním bodě je gradient funkce nulový. Metody prvního řádu, nazývané také gradientové a minimalizační metody, jsou založeny na vlastnostech gradientů. Použití těchto metod v obecném případě umožňuje určit lokální minimální bod funkce. Je zřejmé, že pokud neexistují žádné další informace, pak od výchozího bodu X je rozumné jít k věci X, ležící ve směru antigradientu - nejrychlejší pokles funkce. Volba jako směr sestupu R[k] anti-gradient - f'(x[k] )
na místě X[k], získáme iterační proces formuláře X[ k+ 1] = X[k]-a k f"(x[k] )
,
a k > 0; k=0, 1, 2, ... V souřadnicové formě je tento proces napsán takto: x i [ k+1]=x i[k] - a kf(x[k] )
/x i i = 1, ..., n; k= 0, 1, 2,... Jako kritérium pro zastavení iteračního procesu je buď splnění podmínky malého přírůstku argumentu || X[k+l] - X[k] || <= e
,
либо выполнение условия малости градиента || f'(x[k+l] )
|| <= g
, Zde e a g jsou uvedena malá množství. Možné je i kombinované kritérium spočívající v současném splnění stanovených podmínek. Gradientní metody se od sebe liší způsobem volby velikosti kroku a k. U metody s konstantním krokem je pro všechny iterace vybrána určitá hodnota konstantního kroku. Docela malý krok a k zajistí snížení funkce, tedy nerovnosti f(x[ k+1])
= f(x[k] – a k f'(x[k] ))
< f(x[k] )
. To však může vést k nutnosti provést nepřijatelně velký počet iterací, aby bylo dosaženo minimálního bodu. Na druhou stranu příliš velký krok může způsobit neočekávané zvýšení funkce nebo vést k oscilacím kolem minimálního bodu (cyklování). Vzhledem k obtížnosti získání potřebných informací pro výběr velikosti kroku se metody s konstantními kroky v praxi používají jen zřídka. Gradientní jsou ekonomičtější z hlediska počtu iterací a spolehlivosti metody variabilního kroku, kdy se v závislosti na výsledcích výpočtů nějakým způsobem změní velikost kroku. Uvažujme o variantách takových metod používaných v praxi. Při použití metody nejstrmějšího sestupu v každé iteraci velikost kroku a k se volí z minimální podmínky funkce f(x) ve směru sestupu, tzn. Tento stav znamená, že k pohybu podél antigradientu dochází tak dlouho, dokud je hodnota funkce f(x) klesá. Z matematického hlediska je při každé iteraci nutné řešit problém jednorozměrné minimalizace podle A funkcí Algoritmus metody nejstrmějšího sestupu je následující. 1. Nastavte souřadnice počátečního bodu X.
2. Na místě X[k],
k = 0, 1, 2, ... vypočítá hodnotu gradientu f'(x[k])
. 3. Je určena velikost kroku A k, jednorozměrnou minimalizací přes A funkce j (A) = f(x[k]-af"(x[k])).
4. Stanoví se souřadnice bodu X[k+ 1]: x i [ k+ 1]= xi[k]– a k f’ i (x[k]), i = 1,..., str. 5. Kontrolují se podmínky pro zastavení procesu sterace. Pokud jsou splněny, výpočty se zastaví. V opačném případě přejděte ke kroku 1. V uvažované metodě směr pohybu z bodu X[k] se dotkne čáry úrovně v bodě X[k+ 1] (obr. 2.9). Trajektorie klesání je klikatá, se sousedními klikatými spoji navzájem kolmými. Opravdu, krok A k se volí minimalizací o A funkce? (A) = f(x[k] -af"(x[k]))
. Nutná podmínka pro minimum funkce d j (a)/da = 0. Po výpočtu derivace komplexní funkce získáme podmínku pro ortogonalitu vektorů sestupných směrů v sousedních bodech: dj (a)/da = -f'(x[k+ 1]f'(x[k])
= 0.
Gradientové metody konvergují k minimu vysokou rychlostí (geometrická rychlost progrese) pro hladké konvexní funkce. Takové funkce mají největší M a nejméně m vlastní čísla matice druhých derivací (Hessova matice) se od sebe málo liší, tedy matice N(x) dobře upravená. Připomeňme, že vlastní čísla l i, i
=1, …, n, matice jsou kořeny charakteristické rovnice V praxi však mají minimalizované funkce zpravidla špatně podmíněné matice druhých derivací (t/m<<
1). Hodnoty takových funkcí se v některých směrech mění mnohem rychleji (někdy o několik řádů) než v jiných směrech. Jejich rovné plochy jsou v nejjednodušším případě silně protáhlé (obr. 2.10), ve složitějších případech se prohýbají a vypadají jako rokle. Funkce s takovými vlastnostmi se nazývají rokle. Směr antigradientu těchto funkcí (viz obr. 2.10) se výrazně odchyluje od směru k minimálnímu bodu, což vede ke zpomalení rychlosti konvergence. Míra 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í. Z výše uvedených důvodů jsou gradientové metody často používány v kombinaci s jinými, efektivnějšími metodami v počáteční fázi řešení problému. V tomto případě bod X je daleko od minimálního bodu a kroky ve směru antigradientu umožňují dosáhnout výrazného poklesu funkce. Gradientní metody diskutované výše nacházejí minimální bod funkce v obecném případě pouze v nekonečném počtu iterací. Metoda konjugovaného gradientu generuje směry hledání, které jsou konzistentnější s geometrií minimalizované funkce. To výrazně zvyšuje rychlost jejich konvergence a umožňuje například minimalizovat kvadratickou funkci f(x) = (x, Hx) + (b, x) + a se symetrickou pozitivně definitní maticí N v konečném počtu kroků P, roven počtu funkčních proměnných. Jakoukoli hladkou funkci v okolí minimálního bodu lze dobře aproximovat kvadratickou funkcí, proto se úspěšně používají metody konjugovaných gradientů k minimalizaci nekvadratických funkcí. V tomto případě přestávají být konečné a stávají se iterativními. Podle definice dva n-rozměrný vektor X A na volal konjugovaný vzhledem k matrici H(nebo H-konjugovat), pokud je skalární součin (X, no) = 0. Tady N - symetrická pozitivně definitní matice velikosti P X P. Jedním z nejvýznamnějších problémů v metodách sdružených gradientů je problém efektivní konstrukce směrů. Fletcher-Reevesova metoda řeší tento problém transformací antigradientu v každém kroku -f(x[k])
ve směru p[k],
H-konjugovat s dříve nalezenými směry R, R, ..., R[k-1]. Podívejme se nejprve na tuto metodu ve vztahu k problému minimalizace. kvadratická funkce R[k Pokyny ] se vypočítá pomocí vzorců: k] = -f'(x[k])
p[ p[k+b k-1 k>= 1; -l], p = -’(X)
. F k Hodnoty b p[k], R[k-1 se volí tak, že směry H-1] byly :
(p[k], -sdružené[HP 1])= 0.
k- V důsledku toho pro kvadratickou funkci iterativní proces minimalizace má podobu k+l] X[[k]=x[k], +a k p R[k] -
Kde HP směr sestupu do m krok; a k- velikost kroku. Ten je vybrán z minimální podmínky funkce f(x) A Podle f(x[ k] + ve směru pohybu, tedy v důsledku řešení problému jednorozměrné minimalizace:[k])
= f(x[k] + a k r [k])
. ar Pro kvadratickou funkci Algoritmus Fletcher-Reevesovy metody konjugovaného gradientu je následující. X 1. Na místě p = -f'(x)
. vypočítané HP 2. Zapnuto A m kroku, pomocí výše uvedených vzorců se určí krok .
k X[k+ 1]. a tečka f(x[k+1])
3. Hodnoty jsou vypočteny f'(x[k+1])
. A f'(x)
4. Pokud X[k= 0, pak bod +1] je minimální bod funkce f(x). p[k V opačném případě je určen nový směr +l] ze vztahu P a provede se přechod na další iteraci. Tento postup najde minimum kvadratické funkce za ne více než kroky. Při minimalizaci nekvadratických funkcí se Fletcher-Reevesova metoda mění z konečné na iterativní. V tomto případě po(p+ X 1) iterace postupu 1-4 se cyklicky opakují s výměnou X[P na iterativní proces minimalizace má podobu k+l] +1] a výpočty končí na , kde je dané číslo. V tomto případě se používá následující modifikace metody:[k]=x[k],
] se vypočítá pomocí vzorců: k] = x[k])+
= -f'(x HP 1 p[k+b k-1 k>= 1; b X); f(x[ k] + p = -f'([k])
= f(x[k] a k p[k];
+ap Tady já Tady- mnoho indexů: = (0, n, 2 p, plat, ...) P, tj. metoda je aktualizována každý kroky. Geometrický význam X Metoda konjugovaného gradientu je následující (obr. 2.11). Z daného výchozího bodu R = sestup se provádí ve směru-f"(x X). Na místě je určen gradientový vektor f"(x X je minimální bod funkce ve směru R,
Že f'(x)
ortogonální k vektoru R. Poté je vektor nalezen R , H- konjugovat k R. Dále najdeme minimum funkce podél směru R atd. Metody sdruženého směru patří k nejúčinnějším pro řešení problémů minimalizace. Je však třeba poznamenat, že jsou citlivé na chyby, ke kterým dochází během procesu počítání. S velkým počtem proměnných se chyba může zvýšit natolik, že proces bude muset být opakován i pro kvadratickou funkci, tj. proces pro ni vždy nezapadá do P, tj. metoda je aktualizována každý Metoda nejstrmějšího sestupu (v anglické literatuře „metoda strmého sestupu“) 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: 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ě kde i, j,…, n jsou jednotkové vektory rovnoběžné se souřadnicovými osami. Gradient v základním bodě Nejstrmější způsob sestupu je další vývoj gradientní sestupová metoda. Obecně platí, že 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: 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ů směrů sestupu v sousedních bodech zapisujeme následujícím výrazem: Trajektorie pohybu k extrémnímu bodu metodou nejstrmějšího klesání, znázorněná 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 Gradientní 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í metody také významně závisí na přesnosti výpočtů gradientu. 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í.
.
f(x[k]–a k f’(x[k]))
= f(x[k] – af“ (x[k]))
.
j (A) = f(x[k]-af"(x[k]))
.
,
.
jsou hodnoty argumentu funkce (řízené parametry) na skutečné doméně.je vektor, jehož průměty na souřadnicové osy jsou parciální derivace funkce vzhledem k souřadnicím:
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.
- gradientový modul určuje rychlost nárůstu nebo poklesu funkce ve směru gradientu nebo antigradientu:
