Metoda najstrmiji spust(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:
su vrijednosti argumenta funkcije (kontrolirani parametri) na stvarnoj domeni.
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 je vektor čije su projekcije na koordinatne ose parcijalni izvod funkcije u odnosu na koordinate:
gdje su i, j,…, n jedinični vektori paralelni koordinatnim osa.
Gradijent u baznoj tački 
je strogo ortogonalno na površinu, i njegov smjer pokazuje smjer najbržeg porasta funkcije, a suprotni smjer (antigradijent), respektivno, pokazuje smjer najbržeg pada funkcije.
Najstrmiji način spuštanja je dalji razvoj metoda gradijentnog spuštanja. IN opšti slučaj 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:
- modul gradijenta određuje stopu povećanja ili smanjenja funkcije u smjeru gradijenta ili antigradijenta:
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, brzina konvergencije gradijentnih metoda 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.
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 metod gradijentačesto se koristi kao dio drugih metoda optimizacije, kao što je Fletcher-Reeves metoda.
Opis [ | ]
Poboljšanja[ | ]
Metoda gradijentnog spuštanja se ispostavi da je vrlo spora pri kretanju duž jaruge, a kako se broj varijabli u funkciji cilja povećava, ovakvo ponašanje metode postaje tipično. Za borbu protiv ovog fenomena koristi se, čija je suština vrlo jednostavna. Nakon dva koraka gradijentnog spuštanja i dobijenih 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 za obuku, algoritam će raditi izuzetno sporo, tako da se u praksi mrežni koeficijenti često prilagođavaju nakon svakog elementa treninga, 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. (link nedostupan)
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.
Pravila za unos funkcije
IN metoda najstrmijeg spuštanja vektor čiji je smjer suprotan smjeru vektora gradijenta funkcije ▽f(x) je odabran kao smjer pretraživanja. Od matematička analiza poznato je da vektor grad f(x)=▽f(x) karakterizira smjer najbržeg porasta funkcije (vidi gradijent funkcije). Stoga se vektor - grad f (X) = -▽f(X) naziva anti-gradijent i je pravac njegovog najbržeg pada. Rekurentna relacija kojom se implementira metoda najstrmijeg spuštanja ima oblik X k +1 =X k - λ k ▽f(x k), k = 0,1,...,
gdje je λ k >0 veličina koraka. Ovisno o izboru veličine koraka, možete dobiti razne opcije metod gradijenta. Ako je tokom procesa optimizacije veličina koraka λ fiksna, tada se metoda naziva metodom gradijenta sa diskretnim korakom. Proces optimizacije u prvim iteracijama može se značajno ubrzati ako se λ k odabere iz uslova λ k =min f(X k + λS k) .
Za određivanje λ k koristi se bilo koja metoda jednodimenzionalne optimizacije. U ovom slučaju, metoda se naziva metodom najstrmijeg spuštanja. U pravilu, u općem slučaju, jedan korak nije dovoljan za postizanje minimuma funkcije, proces se ponavlja sve dok naknadni proračuni ne poboljšaju rezultat.
Ako je prostor u nekim varijablama jako izdužen, tada se formira “jaruga”. Potraga se može usporiti i cik-cak po dnu "jaruge". Ponekad se rješenje ne može dobiti u prihvatljivom vremenskom okviru.
Drugi nedostatak metode može biti kriterij zaustavljanja ||▽f(X k)||<ε k , так как этому условию удовлетворяет и седловая точка, а не только оптимум.
Primjer. Počevši od tačke x k =(-2, 3), odredite tačku x k +1 koristeći metodu najstrmijeg spuštanja da biste minimizirali funkciju.
Kao smjer pretraživanja, odaberite vektor gradijenta u trenutnoj tački 
Provjerimo kriterij zaustavljanja. Imamo 
Izračunajmo vrijednost funkcije u početnoj tački f(X 1) = 35. Uradimo
koračaj u pravcu antigradijenta
Izračunajmo vrijednost funkcije u novoj tački
f(X 2) = 3(-2 + 19λ 1) 2 + (3-8λ 1) 2 - (-2 + 19λ 1)(3-8λ 1) - 4(-2 + 19λ 1)
Nađimo korak takav da ciljna funkcija dostigne minimum duž ovog smjera. Od neophodnog uslova za postojanje ekstremuma funkcije
f’(X 2) = 6(-2 + 19λ 1) 19 + 2(3-8λ 1)(-8) – (73 - 304 λ 1) – 4*19
ili f’(X 2) = 2598 λ 1 – 425 = 0.
Dobijamo korak λ 1 = 0,164
Završetak ovog koraka će dovesti do tačke 
u kojoj je vrijednost gradijenta 
, vrijednost funkcije f(X 2) = 0,23. Preciznost nije postignuta, od tačke idemo korakom u pravcu antigradijenta.
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.008λ 1)
f’(X 2) = 11,76 – 6,12λ 1 = 0
Dobijamo λ 1 = 0,52 
Napomena: Ovo predavanje naširoko pokriva takve metode multiparametarske optimizacije kao što su metoda najstrmijeg spuštanja i Davidon–Fletcher–Powell metoda. Pored toga, vrši se komparativna analiza navedenih metoda kako bi se odredila najefikasnija, identifikovane su njihove prednosti i nedostaci; a također razmatra višedimenzionalne probleme optimizacije, kao što su metoda jaruge i multiekstremalna metoda.
1. Metoda najstrmijeg spuštanja
Suština ove metode je da se koristi prethodno pomenuta metoda koordinatnog spuštanja pretraga se vrši od date tačke u pravcu paralelnom jednoj od osi do minimalne tačke u ovom pravcu. Pretraživanje se zatim izvodi u smjeru paralelnom s drugom osom, i tako dalje. Uputstva su, naravno, fiksna. Čini se razumnim pokušati modificirati ovu metodu tako da se u svakoj fazi potraga za minimalnom tačkom vrši duž "najboljeg" smjera. Nije jasno koji je pravac "najbolji", ali se to zna smjer gradijenta je smjer najbržeg porasta funkcije. Stoga je suprotan smjer smjer najbržeg opadanja funkcije. Ovo svojstvo se može opravdati na sljedeći način.
Pretpostavimo da se krećemo od tačke x do sledeće tačke x + hd, gde je d određeni pravac, a h korak određene dužine. Prema tome, kretanje se vrši od tačke (x 1, x 2, ..., x n) do tačke (x 1 + zx 1, x 2 + zx 2, ..., x n + zx n), Gdje
Promjena vrijednosti funkcije određena je relacijama
| (1.3) |
Do prvog reda zx i , sa parcijalnim derivacijama koje se računaju u tački x . Kako odabrati pravce d i koji zadovoljavaju jednačinu (1.2) da bi se dobila najveća vrijednost promjene funkcije df? Ovdje nastaje problem maksimizacije s ograničenjem. Primijenimo metodu Lagrangeovih množitelja uz pomoć kojih određujemo funkciju
Vrijednost df koja zadovoljava ograničenje (1.2) dostiže svoj maksimum kada funkcija
Dostiže maksimum. Njegov derivat
dakle,
 |
(1.6) |
Tada je di ~ df/dx i i pravac d je paralelan sa smjerom V/(x) u tački x.
dakle, najveće lokalno povećanje funkcija za dati mali korak h javlja se kada je d smjer Vf(x) ili g(x) . Stoga je pravac najstrmijeg spuštanja pravac
U jednostavnijem obliku, jednačina (1.3) se može napisati na sljedeći način:
Gdje je ugao između vektora Vf(x) i dx. Za datu vrijednost dx minimiziramo df odabirom da se smjer dx poklapa sa smjerom -Vf(x) .
Komentar. Smjer gradijenta okomito na bilo koju tačku na liniji konstantnog nivoa, budući da je duž ove linije funkcija konstantna. Dakle, ako je (d 1, d 2, ..., d n) mali korak duž linije nivoa, onda
I zbog toga
 |
(1.8) |
