Također možete tražiti ne najbolju tačku u smjeru gradijenta, već neku bolju od trenutne.
Najlakši za implementaciju od svih lokalnih metoda optimizacije. Ima dosta slabi uslovi konvergencija, ali je stopa konvergencije prilično niska (linearna). Korak metode gradijenta se često koristi kao dio drugih metoda optimizacije, kao što je Fletcher-Reeves metoda.
Opis [ | ]
Poboljšanja[ | ]
Metoda gradijentnog spuštanja pokazuje se vrlo sporom pri kretanju uzduž klisure, a s povećanjem broja varijabli ciljna funkcija Ovakvo ponašanje metode postaje tipično. Za borbu protiv ovog fenomena koristi se, čija je suština vrlo jednostavna. Nakon što su napravljena dva koraka gradijentnog spuštanja i dobijene tri tačke, treći korak treba napraviti u pravcu vektora koji povezuje prvu i treću tačku, po dnu jaruge.
Za funkcije bliske kvadratnim, efikasna je metoda konjugovanog gradijenta.
Primjena u umjetnim neuronskim mrežama[ | ]
Metoda gradijentnog spuštanja, uz određene modifikacije, široko se koristi za obuku perceptrona i poznata je u teoriji umjetnih neuronskih mreža kao metoda povratnog širenja. Kada trenirate neuronsku mrežu tipa perceptron, potrebno je promijeniti težinske koeficijente mreže kako bi se minimizirali prosečna greška na izlazu neuronske mreže kada se niz ulaznih podataka za obuku dostavlja na ulaz. Formalno, da bismo napravili samo jedan korak metodom gradijentnog spuštanja (učinili samo jednu promjenu parametara mreže), potrebno je na mrežni ulaz uzastopno dostaviti apsolutno cijeli skup podataka za obuku, izračunati grešku za svaki objekt od podatke o obuci i izračunati potrebnu korekciju mrežnih koeficijenata (ali ne raditi ovu korekciju), a nakon predaje svih podataka izračunati iznos u prilagođavanju svakog mrežnog koeficijenta (zbir nagiba) i ispraviti koeficijente „jedan korak“ . Očigledno, sa velikim skupom podataka o obuci, algoritam će raditi izuzetno sporo, tako da se u praksi mrežni koeficijenti često prilagođavaju nakon svakog elementa obuke, pri čemu je vrijednost gradijenta aproksimirana gradijentom funkcije troškova, izračunatom samo na jednom treningu. element. Ova metoda se zove stohastički gradijentni pad ili operativni gradijentni pad . Stohastički gradijentni pad je oblik stohastičke aproksimacije. Teorija stohastičkih aproksimacija daje uslove za konvergenciju metode stohastičkog gradijenta spuštanja.
Linkovi [ | ]
- J. Mathews. Modul za najstrmiji spust ili metod gradijenta. (nedostupan link)
Književnost [ | ]
- Akulich I. L. Matematičko programiranje u primjerima i problemima. - M.: Viša škola, 1986. - P. 298-310.
- Gill F., Murray W., Wright M. Praktična optimizacija = Praktična optimizacija. - M.: Mir, 1985.
- Korshunov Yu. M., Korshunov Yu. M. Matematičke osnove kibernetike. - M.: Energoatomizdat, 1972.
- Maksimov Yu. A., Filipovskaya E. A. Algoritmi za rješavanje problema nelinearnog programiranja. - M.: MIPhI, 1982.
- Maksimov Yu. A. Algoritmi za linearno i diskretno programiranje. - M.: MIPhI, 1980.
- Korn G., Korn T. Priručnik iz matematike za naučnike i inženjere. - M.: Nauka, 1970. - P. 575-576.
- S. Yu. Gorodetsky, V. A. Grishagin. Nelinearno programiranje i multiekstremalna optimizacija. - Nižnji Novgorod: Izdavačka kuća Univerziteta Nižnji Novgorod, 2007. - str. 357-363.
Metoda najstrmijeg spuštanja je metoda gradijenta s promjenjivim korakom. Pri svakoj iteraciji, veličina koraka k se bira iz uslova minimuma funkcije f(x) u smjeru spuštanja, tj.
Ovaj uvjet znači da se kretanje duž antigradijenta događa sve dok se vrijednost funkcije f (x) smanjuje. Sa matematičke tačke gledišta, na svakoj iteraciji potrebno je riješiti problem jednodimenzionalne minimizacije funkcijom
()=f (x (k) -f (x (k)))
Za to koristimo metodu zlatnog omjera.
Algoritam metode najstrmijeg spuštanja je sljedeći.
Navedene su koordinate početne tačke x (0).
U tački x (k), k = 0, 1, 2, ..., izračunava se vrijednost gradijenta f (x (k)).
Veličina koraka k je određena jednodimenzionalnom minimizacijom pomoću funkcije
()=f (x (k) -f (x (k))).
Određene su koordinate tačke x (k):
x i (k+1) = x i (k) - k f i (x (k)), i=1, …, n.
Provjerava se uvjet za zaustavljanje iterativnog procesa:
||f (x (k +1))|| .
Ako je ispunjen, onda se proračuni zaustavljaju. Inače, prelazimo na korak 1. Geometrijska interpretacija metode najstrmijeg spuštanja prikazana je na Sl. 1.
Rice. 2.1. Blok dijagram metode najstrmijeg spuštanja.
Implementacija metode u programu:
Metoda najstrmijeg spuštanja.
Rice. 2.2. Implementacija metode najstrmijeg spuštanja.
Zaključak: U našem slučaju metoda je konvergirala u 7 iteracija. Tačka A7 (0,6641; -1,3313) je tačka ekstrema. Metoda konjugiranih pravaca. Za kvadratne funkcije možete kreirati metodu gradijenta u kojoj će vrijeme konvergencije biti konačno i jednako broju varijabli n.
Nazovimo određeni pravac i konjugiramo u odnosu na neku pozitivno određenu Hessovu matricu H ako:
Dakle, za jedinicu H, konjugirani smjer znači njihovu okomicu. U opštem slučaju, H je netrivijalan. IN opšti slučaj konjugacija je primjena Hessove matrice na vektor - to znači rotirati ovaj vektor za neki ugao, rastegnuti ga ili komprimirati.
I sada je vektor ortogonan, tj. konjugacija nije ortogonalnost vektora, već ortogonalnost rotiranog vektora, tj.
Rice. 2.3. Blok dijagram metode konjugiranih pravaca.
Implementacija metode u programu: Metoda konjugiranih pravaca.
Rice. 2.4. Implementacija metode konjugiranih pravaca.
Rice. 2.5. Grafikon metode konjugiranih pravaca.
Zaključak: Tačka A3 (0,6666; -1,3333) pronađena je u 3 iteracije i predstavlja ekstremnu tačku.
3. Analiza metoda za određivanje minimalne i maksimalne vrijednosti funkcije u prisustvu ograničenja
Da vas podsjetimo na to zajednički zadatak uslovna optimizacija izgleda ovako
f(x) ® min, x O W,
gdje je W pravi podskup od R m. Podklasu problema sa ograničenjima tipa jednakosti razlikuje se po tome što je skup definiran ograničenjima oblika
f i (x) = 0, gdje je f i: R m ®R (i = 1, …, k).
Dakle,W = (x O R m: f i (x) = 0, i = 1, …, k).
Bilo bi nam zgodno napisati indeks "0" za funkciju f. Dakle, problem optimizacije sa ograničenjima tipa jednakosti zapisuje se kao
f 0 (x) ® min, (3.1)
f i (x) = 0, i = 1, …, k. (3.2)
Ako sada sa f označimo funkciju na R m sa vrijednostima u R k, čija koordinatna oznaka ima oblik f(x) = (f 1 (x), ..., f k (x)), tada ( 3.1)–(3.2) možemo to zapisati i u obliku
f 0 (x) ® min, f(x) = Q.
Geometrijski, problem sa ograničenjima tipa jednakosti je problem pronalaženja najniže tačke grafa funkcije f 0 preko mnogostrukosti (vidi sliku 3.1).
Tačke koje zadovoljavaju sva ograničenja (tj. tačke u skupu ) obično se nazivaju dopuštenim. Dopuštena tačka x* naziva se uslovni minimum funkcije f 0 pod ograničenjima f i (x) = 0, i = 1, ..., k (ili rešenje problema (3.1)–(3.2)), ako za sve dozvoljene tačke x f 0 (x *) f 0 (x). (3.3)
Ako je (3.3) zadovoljena samo za dopušteni x koji leži u nekom susjedstvu V x * tačke x*, onda govorimo o lokalnom uslovnom minimumu. Koncepti uvjetno strogih lokalnih i globalnih minimuma definirani su na prirodan način.
U ovoj verziji metode gradijenta, minimizirajući niz (X k) je također konstruiran prema pravilu (2.22). Međutim, veličina koraka a k se nalazi kao rezultat rješavanja pomoćnog problema jednodimenzionalne minimizacije
min(j k (a) | a>0 ), (2.27)
gdje je j k (a)=f(X k - a· (X k)). Dakle, pri svakoj iteraciji u smjeru antigradijenta 
vrši se iscrpno spuštanje. Da biste riješili problem (2.27), možete koristiti jednu od jednodimenzionalnih metoda pretraživanja opisanih u Odjeljku 1, na primjer, metodu pobitnog pretraživanja ili metodu zlatnog preseka.
Hajde da opišemo algoritam metode najstrmijeg spuštanja.
Korak 0. Podesite parametar tačnosti e>0, izaberite X 0 OE n , postavite k=0.
Korak 1. Pronađite (X k) i provjerite uvjet za postizanje navedene tačnosti || (x k) ||£ e. Ako je zadovoljan, idite na korak 3, u suprotnom - na korak 2.
Korak 2. Riješiti zadatak (2.27), tj. nađi k. Pronađite sljedeću tačku, stavite k=k+1 i idite na korak 1.
Korak 3 Završite proračune tako što ćete staviti X * = X k, f * = f(X k).
Minimizirajte funkciju
f(x)=x 1 2 +4x 2 2 -6x 1 -8x 2 +13; (2.28)
Hajde da prvo rešimo problem klasična metoda. Hajde da zapišemo sistem jednačina koji predstavlja neophodne uslove bezuslovni ekstrem
Nakon što smo ga riješili, dobijamo stacionarnu tačku X*=(3;1). Zatim, hajde da proverimo izvršenje dovoljno stanje, za koji nalazimo matricu drugih izvoda
Budući da je, prema Sylvesterovom kriteriju, ova matrica pozitivno određena za ", tada je pronađena tačka X* minimalna tačka funkcije f(X). Minimalna vrijednost f *=f(X*)=0. Ovo je tačno rješenje problema (11).
Izvršimo jednu iteraciju metode gradijentni spust za (2.28). Odaberemo početnu tačku X 0 =(1;0), postavimo početni korak a=1 i parametar l=0,5. Izračunajmo f(X 0)=8.
Nađimo gradijent funkcije f(X) u tački X 0
(X 0)= = (2.29)
Definirajmo novu tačku X=X 0 -a· (X 0) izračunavanjem njenih koordinata
x 1 = 
x 2 = 
(2.30)
Izračunajmo f(X)= f(X 0 -a· (X 0))=200. Pošto je f(X)>f(X 0), podijelimo korak, uz pretpostavku da je a=a·l=1·0,5=0,5. Ponovo izračunavamo koristeći formule (2.30) x 1 =1+4a=3; x 2 =8a=4 i pronađite vrijednost f(X)=39. Pošto je ponovo f(X)>f(X 0), dodatno smanjujemo veličinu koraka, postavljajući a=a·l=0.5·0.5=0.25. Računamo novu tačku sa koordinatama x 1 =1+4·0.25=2; x 2 =8·0,25=2 i vrijednost funkcije u ovoj tački f(X)=5. Pošto je uslov za smanjenje f(X) Izvršimo jednu iteraciju koristeći metodu najstrmiji spust za (2.28) sa istom početnom tačkom X 0 =(1;0). Koristeći već pronađeni gradijent (2.29), nalazimo X= X 0 -a· (X 0) i konstruisati funkciju j 0 (a)=f(X 0 -a· (X 0))=(4a-2) 2 +4(8a-1) 2. Minimiziranjem pomoću potrebnog uslova j 0 ¢(a)=8·(4a - 2)+64·(8a - 1)=0 nalazimo optimalnu vrijednost veličine koraka a 0 =5/34. Određivanje tačke minimizirajućeg niza X 1 = X 0 -a 0 · (X 0) Gradijent diferencijabilne funkcije f(x) u tački X pozvao n-dimenzionalni vektor f(x)
, čije su komponente parcijalni derivati funkcije f(x), izračunato u tački X, tj. f"(x ) = (df(x)/dh 1 , …, df(x)/dx n) T . Ovaj vektor je okomit na ravan kroz tačku X, i tangenta na ravnu površinu funkcije f(x), prolazeći kroz tačku X.U svakoj tački takve površine funkcija f(x) uzima istu vrijednost. Izjednačavajući funkciju različitim konstantnim vrijednostima C 0 , C 1 , ..., dobijamo niz površina koje karakteriziraju njenu topologiju (slika 2.8). Vektor gradijenta je usmjeren u smjeru najbržeg porasta funkcije u datoj tački. Vektor suprotan gradijentu (-f’(x))
, zvao anti-gradijent i usmjeren je na najbrži pad funkcije. U minimalnoj tački, gradijent funkcije je nula. Metode prvog reda, koje se nazivaju i metode gradijenta i minimizacije, zasnivaju se na svojstvima gradijenata. Korištenje ovih metoda u općenitom slučaju omogućava vam da odredite lokalnu minimalnu točku funkcije. Očigledno, ako nema dodatnih informacija, onda od početne tačke X mudro je preći na stvar X, koji leži u smjeru antigradijenta - najbrži pad funkcije. Odabir smjera spuštanja R[k] anti-gradijent - f'(x[k] )
u tački X[k], dobijamo iterativni proces oblika X[ k+ 1] = x[k]-a k f"(x[k] )
,
i k > 0; k=0, 1, 2, ... U koordinatnoj formi ovaj proces se piše na sljedeći način: x i [ k+1]=x i[k] - a kf(x[k] )
/x i i = 1, ..., n; k= 0, 1, 2,... Kao kriterijum za zaustavljanje iterativnog procesa, ili ispunjenje uslova malog prirasta argumenta || x[k+l] - x[k] || <= e
,
либо выполнение условия малости градиента || f'(x[k+l] )
|| <= g
, Ovdje su e i g date male količine. Moguć je i kombinovani kriterijum koji se sastoji u istovremenom ispunjavanju navedenih uslova. Metode gradijenta razlikuju se jedna od druge po načinu na koji biraju veličinu koraka i k. U metodi sa konstantnim korakom, određena konstantna vrijednost koraka se bira za sve iteracije. Sasvim mali korak i kće osigurati smanjenje funkcije, tj. nejednakosti f(x[ k+1])
= f(x[k] – a k f’(x[k] ))
< f(x[k] )
. Međutim, to može dovesti do potrebe za izvođenjem neprihvatljivo velikog broja iteracija kako bi se dosegla minimalna tačka. S druge strane, preveliki korak može uzrokovati neočekivano povećanje funkcije ili dovesti do oscilacija oko minimalne točke (cikliranje). Zbog poteškoća u dobivanju potrebnih informacija za odabir veličine koraka, metode s konstantnim koracima se rijetko koriste u praksi. Gradijentni su ekonomičniji u smislu broja iteracija i pouzdanosti metode varijabilnog koraka, kada se, u zavisnosti od rezultata proračuna, veličina koraka na neki način menja. Razmotrimo varijante takvih metoda koje se koriste u praksi. Kada koristite metodu najstrmijeg spuštanja na svakoj iteraciji, veličina koraka i k se bira iz minimalnog uslova funkcije f(x) u pravcu spuštanja, tj. Ovaj uvjet znači da se kretanje duž antigradijenta događa sve dok je vrijednost funkcije f(x) smanjuje se. Sa matematičke tačke gledišta, na svakoj iteraciji potrebno je riješiti problem jednodimenzionalne minimizacije prema A funkcije Algoritam metode najstrmijeg spuštanja je sljedeći. 1. Postavite koordinate početne tačke X.
2. U tački X[k],
k = 0, 1, 2, ... izračunava vrijednost gradijenta f'(x[k])
. 3. Veličina koraka je određena a k, jednodimenzionalnom minimizacijom preko A funkcije j (a) = f(x[k]-af"(x[k])).
4. Određuju se koordinate tačke X[k+ 1]: x i [ k+ 1]= x i[k]– a k f’ i (x[k]), i = 1,..., str. 5. Provjeravaju se uslovi za zaustavljanje procesa sterationa. Ako su ispunjeni, onda se kalkulacije zaustavljaju. U suprotnom, idite na korak 1. U metodi koja se razmatra, smjer kretanja od tačke X[k] dodiruje liniju nivoa u tački x[k+ 1] (sl. 2.9). Putanja spuštanja je cik-cak, sa susjednim cik-cak vezama ortogonalnim jedna prema drugoj. Zaista, korak a k se bira minimiziranjem po A funkcije? (a) = f(x[k] -af"(x[k]))
. Neophodan uslov za minimum funkcije d j (a)/da = 0. Izračunavši derivaciju kompleksne funkcije, dobijamo uslov za ortogonalnost vektora pravaca spuštanja u susednim tačkama: dj (a)/da = -f’(x[k+ 1]f'(x[k])
= 0.
Metode gradijenta konvergiraju na minimum pri velikoj brzini (brzina geometrijske progresije) za glatke konveksne funkcije. Takve funkcije imaju najveće M i najmanje m vlastite vrijednosti matrice drugih izvoda (Hessian matrica) malo se razlikuju jedni od drugih, odnosno matrica N(x) dobro kondicionirano. Podsjetimo da su vlastite vrijednosti l i, i
=1, …, n, matrice su korijeni karakteristične jednadžbe Međutim, u praksi, po pravilu, funkcije koje se minimiziraju imaju loše uvjetovane matrice drugih izvoda (t/m<<
1). Vrijednosti takvih funkcija duž nekih smjerova mijenjaju se mnogo brže (ponekad za nekoliko redova veličine) nego u drugim smjerovima. Ravne površine su im u najjednostavnijem slučaju jako izdužene (sl. 2.10), au složenijim slučajevima savijaju se i izgledaju kao jaruge. Pozivaju se funkcije s takvim svojstvima gully. Smjer antigradijenta ovih funkcija (vidi sliku 2.10) značajno odstupa od smjera prema minimalnoj tački, što dovodi do usporavanja brzine konvergencije. Stopa konvergencije gradijentnih metoda također značajno zavisi od tačnosti proračuna gradijenta. Gubitak preciznosti, koji se obično javlja u blizini minimalnih tačaka ili u situaciji jaruga, generalno može poremetiti konvergenciju procesa gradijenta spuštanja. Zbog navedenih razloga, gradijent metode se često koriste u kombinaciji sa drugim, efikasnijim metodama u početnoj fazi rješavanja problema. U ovom slučaju, poenta X je daleko od minimalne tačke, a koraci u pravcu antigradijenta omogućavaju da se postigne značajno smanjenje funkcije. Metode gradijenta o kojima smo gore govorili pronalaze minimalnu tačku funkcije u opštem slučaju samo u beskonačnom broju iteracija. Metoda konjugiranog gradijenta generiše smjerove pretraživanja koji su u skladu s geometrijom funkcije koja se minimizira. Ovo značajno povećava brzinu njihove konvergencije i omogućava, na primjer, minimiziranje kvadratne funkcije f(x) = (x, Hx) + (b, x) + a sa simetričnom pozitivno određenom matricom N u konačnom broju koraka P, jednak broju varijabli funkcije. Bilo koja glatka funkcija u blizini minimalne tačke može se dobro aproksimirati kvadratnom funkcijom, stoga se metode konjugiranog gradijenta uspješno koriste za minimiziranje nekvadratnih funkcija. U ovom slučaju, oni prestaju biti konačni i postaju iterativni. Po definiciji, dva n-dimenzionalni vektor X I at pozvao konjugirani u odnosu na matricu H(ili H-konjugat), ako je skalarni proizvod (x, Pa) = 0. Evo N - simetrična pozitivna određena matrica veličine P X P. Jedan od najznačajnijih problema u metodama konjugovanog gradijenta je problem efikasnog konstruisanja pravaca. Fletcher-Reeves metoda rješava ovaj problem transformacijom antigradijenta na svakom koraku -f(x[k])
u pravcu str[k],
H-konjugirati s prethodno pronađenim smjerovima R, R, ..., R[k-1]. Razmotrimo prvo ovu metodu u odnosu na problem minimizacije kvadratna funkcija. Upute R[k] se izračunava pomoću formula: p[ k] = -f'(x[k])
+b k-1 str[k-l], k>= 1; p = - f’(x)
. b vrijednosti k-1 su odabrani tako da smjerovi str[k], R[k-1] bili H-konjugat :
(str[k], HP[k- 1])= 0.
Kao rezultat, za kvadratnu funkciju iterativni proces minimizacije ima oblik x[ k+l] =x[k]+a k p[k], Gdje R[k] -
smjer spuštanja do k- m korak; i k - veličina koraka. Potonji se bira iz minimalnog uslova funkcije f(x) By A u smjeru kretanja, tj. kao rezultat rješavanja jednodimenzionalnog problema minimizacije: f(x[ k] + a k r[k])
= f(x[k] + ar [k])
. Za kvadratnu funkciju Algoritam metode Fletcher-Reeves konjugiranog gradijenta je sljedeći. 1. U tački X izračunati str = -f'(x)
. 2. Uključeno k- m korak, koristeći gornje formule, korak se određuje A k .
i tačka X[k+ 1]. 3. Vrijednosti su izračunate f(x[k+1])
I f'(x[k+1])
. 4. Ako f'(x)
= 0, zatim tačka X[k+1] je minimalna tačka funkcije f(x). U suprotnom, određuje se novi pravac str[k+l] iz relacije i vrši se prijelaz na sljedeću iteraciju. Ovaj postupak će pronaći minimum kvadratne funkcije u ne više od P stepenice. Kada se minimiziraju nekvadratne funkcije, Fletcher-Reeves metoda postaje iterativna od konačne. U ovom slučaju, nakon (p+ 1) iteracija postupka 1-4 se ponavlja ciklično sa zamjenom X on X[P+1] , a proračuni završavaju na , gdje je dati broj. U ovom slučaju se koristi sljedeća modifikacija metode: x[ k+l] = x[k]+a k p[k],
p[ k] = -f’(x[k])+
b k- 1 str[k-l], k>= 1; p = -f’( x); f(x[ k] + a k p[k])
= f(x[k] +ap[k];
Evo I- mnogo indeksa: I= (0, n, 2 p, plata, ...), tj. metoda se ažurira svaki put P stepenice. Geometrijsko značenje Metoda konjugiranog gradijenta je sljedeća (slika 2.11). Od date početne tačke X spuštanje se vrši u pravcu R = -f"(x). U tački X određen je vektor gradijenta f"(x). Zbog X je minimalna tačka funkcije u pravcu R,
To f'(x)
ortogonalno na vektor R. Tada je vektor pronađen R , H-konjugirati na R. Zatim, nalazimo minimum funkcije duž pravca R itd. Metode konjugiranih smjerova su među najefikasnijim za rješavanje problema minimizacije. Međutim, treba napomenuti da su oni osjetljivi na greške koje se javljaju tokom procesa brojanja. S velikim brojem varijabli greška se može povećati toliko da će se proces morati ponoviti čak i za kvadratnu funkciju, tj. proces za nju se ne uklapa uvijek u P stepenice. Metoda najstrmijeg spuštanja (u engleskoj literaturi "metoda najstrmijeg spuštanja") je iterativna numerička metoda (prvog reda) za rješavanje problema optimizacije, koja vam omogućava da odredite ekstrem (minimum ili maksimum) funkcije cilja: U skladu sa metodom koja se razmatra, ekstrem (maksimum ili minimum) ciljne funkcije se određuje u pravcu najbržeg porasta (opadanja) funkcije, tj. u smjeru gradijenta (anti-gradijent) funkcije. Funkcija gradijenta u tački gdje su i, j,…, n jedinični vektori paralelni koordinatnim osa. Gradijent u baznoj tački Najstrmiji način spuštanja je dalji razvoj metoda gradijentnog spuštanja. Općenito, proces pronalaženja ekstrema funkcije je iterativni postupak, koji se piše na sljedeći način: gdje se znak "+" koristi za pronalaženje maksimuma funkcije, a znak "-" za pronalaženje minimuma funkcije; Vektor jediničnog smjera, koji je određen formulom: Konstanta koja određuje veličinu koraka i ista je za sve i-te smjerove. Veličina koraka se bira iz uslova minimuma ciljne funkcije f(x) u smjeru kretanja, tj. kao rezultat rješavanja jednodimenzionalnog optimizacijskog problema u smjeru gradijenta ili antigradijenta: Drugim riječima, veličina koraka se određuje rješavanjem ove jednadžbe: Dakle, korak proračuna je odabran tako da se kretanje vrši sve dok se funkcija ne poboljša, čime se u nekom trenutku postiže ekstrem. U ovom trenutku ponovo se određuje smjer traženja (pomoću gradijenta) i traži se nova optimalna tačka funkcije cilja itd. Dakle, u ovoj metodi, pretraga se odvija u većim koracima, a gradijent funkcije se računa na manjem broju tačaka. U slučaju funkcije dvije varijable ovu metodu ima sledeću geometrijsku interpretaciju: pravac kretanja iz tačke dodiruje liniju nivoa u tački . Putanja spuštanja je cik-cak, sa susjednim cik-cak vezama ortogonalnim jedna prema drugoj. Uslov za ortogonalnost vektora pravaca silaska u susjednim tačkama zapisuje se sljedećim izrazom: Putanja kretanja do tačke ekstrema metodom najstrmijeg spuštanja, prikazana na grafu linije jednakog nivoa funkcije f(x) Potraga za optimalnim rješenjem završava se na iterativnom koraku proračuna (nekoliko kriterija): Putanja pretraživanja ostaje u malom susjedstvu trenutne točke pretraživanja: Prirast ciljne funkcije se ne mijenja: Gradijent funkcije cilja u lokalnoj minimalnoj tački postaje nula: Treba napomenuti da se metoda gradijentnog spuštanja pokazuje kao vrlo spora pri kretanju duž jaruge, a kako se broj varijabli u funkciji cilja povećava, ovakvo ponašanje metode postaje tipično. Jaruga je udubljenje čije ravnine linije približno imaju oblik elipse sa višestruko različitim poluosama. U prisutnosti jaruge, putanja spuštanja ima oblik cik-cak linije s malim korakom, zbog čega je rezultirajuća brzina spuštanja na minimum uvelike usporena. To se objašnjava činjenicom da smjer antigradijenta ovih funkcija značajno odstupa od smjera prema minimalnoj tački, što dovodi do dodatnog kašnjenja u proračunu. Kao rezultat, algoritam gubi računsku efikasnost. Gully funkcija Metoda gradijenta, zajedno sa svojim brojnim modifikacijama, je široko rasprostranjena i efikasan metod traženje optimuma za objekte koji se proučavaju. Nedostatak pretrage gradijenta (kao i metoda o kojima smo gore govorili) je u tome što se prilikom njegove upotrebe može otkriti samo lokalni ekstremum funkcije. Da nađem druge lokalni ekstremi potrebno je tražiti od drugih polazišta. Takođe i brzina konvergencije gradijent metode takođe značajno zavisi od tačnosti proračuna gradijenta. Gubitak preciznosti, koji se obično javlja u blizini minimalnih tačaka ili u situaciji jaruga, generalno može poremetiti konvergenciju procesa gradijenta spuštanja. Metoda kalkulacije Korak 1: Definicija analitičkih izraza (u simboličkom obliku) za izračunavanje gradijenta funkcije Korak 2: Postavite početnu aproksimaciju Korak 3: Utvrđena je potreba za ponovnim pokretanjem algoritamske procedure za resetiranje posljednjeg smjera pretraživanja. Kao rezultat ponovnog pokretanja, pretraga se ponovo provodi u smjeru najbržeg spuštanja.
.
f(x[k]–a k f’(x[k]))
= f(x[k] – af"(x[k]))
.
j (a) = f(x[k]-af"(x[k]))
.
,
.
su vrijednosti argumenta funkcije (kontrolirani parametri) na stvarnoj domeni.je vektor čije su projekcije na koordinatne ose parcijalni izvod funkcije u odnosu na koordinate:
je striktno ortogonalno na površinu, i njegov smjer pokazuje smjer najbržeg porasta funkcije, a suprotni smjer (antigradijent), respektivno, pokazuje smjer najbržeg pada funkcije.
- modul gradijenta određuje stopu povećanja ili smanjenja funkcije u smjeru gradijenta ili antigradijenta:
