Navešću malo svog iskustva :)

Metoda koordinatnog spuštanja

Ideja ove metode je da se pretraga odvija u pravcu koordinatnog spuštanja tokom nove iteracije. Spuštanje se vrši postepeno duž svake koordinate. Broj koordinata direktno zavisi od broja varijabli.
Da biste demonstrirali kako ova metoda funkcionira, prvo morate uzeti funkciju z = f(x1, x2,…, xn) i odabrati bilo koju tačku M0(x10, x20,…, xn0) u n prostoru, što ovisi o broju karakteristike funkcije. Sljedeći korak je fiksiranje svih tačaka funkcije u konstantu, osim prve. Ovo se radi kako bi se potraga za višedimenzionalnom optimizacijom svela na rješenje pretrage na određenom segmentu problema jednodimenzionalne optimizacije, odnosno traženje argumenta x1.
Da bismo pronašli vrijednost ove varijable, potrebno je spustiti se duž te koordinate do nove tačke M1(x11, x21,…, xn1). Nadalje, funkcija se diferencira i tada možemo pronaći vrijednost nove sljedeće točke koristeći ovaj izraz:

Nakon pronalaženja vrijednosti varijable, potrebno je ponoviti iteraciju fiksirajući sve argumente osim x2 i započeti spuštanje duž nove koordinate do sljedeće nove tačke M2(x11,x21,x30…,xn0). Sada će se vrijednost nove točke pojaviti prema izrazu:

I opet, iteracija sa fiksacijom će se ponavljati sve dok se ne završe svi argumenti od xi do xn. Na posljednjoj iteraciji, uzastopno prolazimo kroz sve moguće koordinate u kojima smo već pronašli lokalne minimume, dakle ciljna funkcija na posljednjoj koordinati će dostići globalni minimum. Jedna od prednosti ove metode je u tome što je u svakom trenutku moguće prekinuti spuštanje i posljednja pronađena točka bit će minimalna tačka. Ovo je korisno kada metoda ide u beskonačnu petlju i posljednja pronađena koordinata može se smatrati rezultatom ove pretrage. Međutim, ciljna postavka traženja globalnog minimuma u tom području možda neće biti postignuta zbog činjenice da smo prekinuli potragu za minimumom (vidi sliku 1).

Slika 1 - Otkazivanje koordinatnog spuštanja

Proučavanje ove metode pokazalo je da je svaka pronađena izračunata tačka u prostoru globalna minimalna tačka datu funkciju, a funkcija z = f(x1, x2,…, xn) je konveksna i diferencijabilna.
Iz ovoga možemo zaključiti da je funkcija z = f(x1, x2,…, xn) konveksna i diferencibilna u prostoru, a svaka pronađena granična tačka u nizu M0(x10, x20,…, xn0) će biti globalni minimum tačka (vidi sliku 2) ove funkcije metodom koordinatnog spuštanja.

Slika 2 - Lokalne minimalne tačke na koordinatnoj osi

Može se zaključiti da se ovaj algoritam dobro nosi jednostavni zadaci multidimenzionalnu optimizaciju, sukcesivnim rješavanjem n broja jednodimenzionalnih optimizacijskih problema, na primjer, korištenjem metode zlatnog presjeka.

Napredak metode koordinatnog spuštanja odvija se prema algoritmu opisanom u blok dijagramu (vidi sliku 3). Iteracije izvršenja ove metode:
U početku se mora uneti nekoliko parametara: Epsilon tačnost, koja mora biti striktno pozitivna, početna tačka x1 od koje ćemo započeti izvršavanje našeg algoritma i postaviti Lambda j;
Sljedeći korak je uzimanje prve početne točke x1, nakon čega se rješava uobičajena jednodimenzionalna jednačina sa jednom promjenljivom i formula za pronalaženje minimuma će biti, gdje je k = 1, j=1:

Sada, nakon izračunavanja tačke ekstrema, morate provjeriti broj argumenata u funkciji i ako je j manji od n, onda morate ponoviti prethodni korak i redefinirati argument j = j + 1. U svim ostalim slučajevima, idite na sljedeći korak.
Sada je potrebno redefinirati varijablu x prema formuli x (k + 1) = y (n + 1) i pokušati izvršiti konvergenciju funkcije u datoj tačnosti prema izrazu:

Sada, pronalaženje tačke ekstrema zavisi od ovog izraza. Ako je ovaj izraz tačan, tada se izračunavanje ekstremne tačke svodi na x*= xk + 1. Ali često je potrebno izvršiti dodatne iteracije u zavisnosti od tačnosti, pa će vrednosti argumenata biti redefinisane y(1 ) = x(k + 1), a vrijednosti indeksa j =1, k = k + 1.

Slika 3 - Blok dijagram metode koordinatnog spuštanja

Ukupno imamo odličan i multifunkcionalan algoritam za višedimenzionalnu optimizaciju koji je u stanju da razbije složeni problem na nekoliko uzastopno iterativnih jednodimenzionalnih. Da, ova metoda je prilično jednostavna za implementaciju i ima jednostavnu definiciju tačaka u prostoru, jer ova metoda jamči konvergenciju na lokalnu minimalnu tačku. Ali čak i sa tako značajnim prednostima, metoda može ići u beskrajne petlje zbog činjenice da može pasti u neku vrstu jaruge.
Postoje funkcije jaruga u kojima postoje depresije. Algoritam, nakon što je upao u jedno od ovih korita, više ne može izaći, i već će tamo pronaći minimalnu tačku. Takođe, veliki broj uzastopnih upotreba iste jednodimenzionalne metode optimizacije može u velikoj meri uticati na slabe računare. Ne samo da je konvergencija u ovoj funkciji vrlo spora, jer je potrebno izračunati sve varijable i često visoka data preciznost povećava vrijeme rješavanja problema nekoliko puta, već je glavni nedostatak ovog algoritma njegova ograničena primjenjivost.
Provodeći proučavanje različitih algoritama za rješavanje problema optimizacije, treba napomenuti da kvaliteta ovih algoritama igra veliku ulogu. Također, ne zaboravite tako važne karakteristike kao što su vrijeme izvršenja i stabilnost, sposobnost pronalaženja najboljih vrijednosti koje minimiziraju ili maksimiziraju funkciju cilja i jednostavnost implementacije rješavanja praktičnih problema. Metoda koordinatnog spuštanja je jednostavna za korištenje, ali u problemima multivarijantne optimizacije, češće nego ne, morate izvoditi složene proračune umjesto particioniranja. cijeli zadatak za podzadatke.

Nelder-Mead metoda

Vrijedi napomenuti popularnost ovog algoritma među istraživačima metoda višedimenzionalne optimizacije. Nelder-Meadova metoda je jedna od rijetkih metoda zasnovana na konceptu sekvencijalne transformacije deformabilnog simpleksa oko tačke ekstrema i ne koristi algoritam kretanja prema globalnom minimumu.
Ovaj simpleks je pravilan i predstavljen je kao poliedar sa ekvidistantnim vrhovima simpleksa u N-dimenzionalnom prostoru. U različitim prostorima, simpleks se preslikava u R2-jednakostranični trokut, a u R3 u pravilan tetraedar.
Kao što je gore spomenuto, algoritam je razvoj Simplice metode Spendleya, Hoeksta i Himswortha, ali, za razliku od potonjeg, dozvoljava korištenje netačnih simplicesa. Simpleks je najčešće konveksni poliedar sa N + 1 vrhova, gde je N broj parametara modela u n-dimenzionalnom prostoru.
Da biste počeli koristiti ovu metodu, morate odrediti osnovni vrh svih dostupnih skupova koordinata koristeći izraz:

Najčudnija stvar kod ove metode je da simpleks ima sposobnost samostalnog obavljanja određenih funkcija:
Refleksija kroz centar gravitacije, refleksija sa kompresijom ili istezanjem;
istezanje;
Kompresija.
Prednost među ovim svojstvima daje se refleksiji, budući da je ovaj parametar najopcionalniji - funkcionalan. Iz bilo kojeg odabranog vrha moguće je napraviti odraz u odnosu na težište simpleksa izrazom:.

Gdje je xc centar gravitacije (vidi sliku 1).

Slika 1 - Refleksija kroz centar gravitacije

Sljedeći korak je izračunavanje argumenata ciljne funkcije na svim vrhovima reflektiranog simpleksa. Nakon toga ćemo dobiti potpunu informaciju o tome kako će se simpleks ponašati u prostoru, a samim tim i informaciju o ponašanju funkcije.
Da biste tražili minimalnu ili maksimalnu točku ciljne funkcije koristeći metode koje koriste simplice, morate se pridržavati sljedećeg niza:
Na svakom koraku se gradi simpleks, u čijoj je tački potrebno izračunati sve njegove vrhove, a zatim sortirati rezultate uzlaznim redom;
Sljedeći korak je refleksija. Potrebno je pokušati dobiti vrijednosti novog simpleksa, a refleksijom se možemo riješiti neželjenih vrijednosti koje pokušavaju da pomjere simpleks ne prema globalnom minimumu;
Da bismo dobili vrijednosti novog simpleksa, iz dobivenih sortiranih rezultata uzimamo dva vrha s najlošijim vrijednostima. Moguće je da neće biti moguće odmah odabrati odgovarajuće vrijednosti, tada ćete se morati vratiti na prvi korak i komprimirati simpleks do točke s najviše najmanju vrijednost;
Kraj potrage za točkom ekstrema je centar gravitacije, pod uslovom da vrijednost razlike između funkcija ima najmanje vrijednosti u tačkama simpleksa.

Nelder-Mead algoritam također koristi ove simpleks funkcije prema sljedećim formulama:

Funkcija refleksije kroz težište simpleksa izračunava se sljedećim izrazom:

Ova refleksija se izvodi striktno prema tački ekstrema i samo kroz centar gravitacije (vidi sliku 2).

Slika 2 – Refleksija simpleksa se dešava kroz centar gravitacije

Funkcija kompresije unutar simpleksa izračunava se sljedećim izrazom:

Da bi se izvršila kompresija, potrebno je odrediti tačku s najmanjom vrijednošću (vidi sliku 3).

Slika 3 - Simpleks je komprimiran na najmanji argument.

Funkcija refleksije simpleksne kontrakcije izračunava se sljedećim izrazom:

Da biste izvršili refleksiju sa kompresijom (vidi sliku 4), potrebno je zapamtiti rad dvije odvojene funkcije - to je refleksija kroz centar gravitacije i kompresija simpleksa na najmanju vrijednost.

Slika 4 - Refleksija sa kompresijom

Simpleksna funkcija refleksije rastezanja (vidi sliku 5) se javlja pomoću dvije funkcije - refleksije kroz centar gravitacije i rastezanja kroz najveću vrijednost.

Slika 5 – Refleksija sa istezanjem.

Da bismo demonstrirali rad Nelder-Mead metode, potrebno je pogledati blok dijagram algoritma (vidi sliku 6).
Prije svega, kao iu prethodnim primjerima, potrebno je postaviti parametar izobličenja ε, koji mora biti striktno veći od nule, a također postaviti potrebne parametre za izračunavanje α, β i a. Ovo će biti potrebno za izračunavanje funkcije f(x0), kao i za konstruiranje samog simpleksa.

Slika 6 – Prvi dio metode Nelder – Mead.

Nakon konstruiranja simpleksa, potrebno je izračunati sve vrijednosti funkcije cilja. Kao što je gore opisano o traženju ekstrema pomoću simpleksa, potrebno je izračunati simpleks funkciju f(x) u svim njenim tačkama. Zatim sortiramo gdje će biti bazna tačka:

Sada kada je bazna tačka izračunata, kao i sve ostale sortirane na listi, provjeravamo uvjet dosegljivosti na tačnost koju smo prethodno naveli:

Čim ovaj uslov postane istinit, tada će se tačka x(0) simpleksa smatrati željenom tačkom ekstrema. U suprotnom, idemo na sljedeći korak, gdje trebamo odrediti novu vrijednost centra gravitacije koristeći formulu:

Ako je ovaj uvjet ispunjen, tada će točka x(0) biti minimalna točka, u suprotnom morate prijeći na sljedeći korak u kojem trebate tražiti najmanji argument funkcije:

Iz funkcije je potrebno dobiti najmanju vrijednost argumenta kako bi se prešlo na sljedeći korak algoritma. Ponekad postoji problem da nekoliko argumenata odjednom ima istu vrijednost, izračunatu iz funkcije. Rješenje ovog problema može biti redefiniranje vrijednosti argumenta do desethiljaditih dionica.
Nakon ponovnog izračunavanja minimalnog argumenta, potrebno je ponovo pohraniti nove dobivene vrijednosti na n pozicija argumenata.

Slika 7 - Drugi dio metode Nelder - Mead.

Vrijednost izračunata iz prethodne funkcije mora se zamijeniti u fmin uvjet< f(xN). При истинном выполнении dato stanje, tačka x(N) će biti minimum grupe onih pohranjenih u sortiranoj listi i potrebno je da se vratite na korak u kojem smo izračunali težište, u suprotnom, komprimujemo simpleks 2 puta i vraćamo se na od samog početka sa novim skupom bodova.
Istraživanja ovog algoritma pokazuju da su metode s nepravilnim simplicitima (vidi sliku 8) još uvijek prilično slabo proučene, ali ih to ne sprječava da se savršeno nose sa svojim zadacima.
Dublji testovi pokazuju da je eksperimentalno moguće odabrati parametre funkcija istezanja, kompresije i refleksije koji su najpogodniji za problem, ali možete koristiti općeprihvaćene parametre ovih funkcija α = 1/2, β = 2, γ = 2 ili α = 1/4, β = 5/2, γ = 2. Stoga, prije nego što odbacite ovu metodu za rješavanje problema, morate shvatiti da za svako novo traženje bezuslovnog ekstremuma morate pažljivo pratiti ponašanje simpleksa tokom njegovog rada i uočiti nestandardna rješenja metode.

Slika 8 – Proces pronalaženja minimuma.

Statistike su pokazale da je jedan od najčešćih problema u radu ovog algoritma degeneracija deformabilnog simpleksa. To se dešava kada svaki put kada nekoliko vrhova simpleksa padne u jedan prostor, čija dimenzija ne zadovoljava zadatak.
Dakle, dimenzija tokom rada i data dimenzija bacaju nekoliko vrhova simpleksa u jednu pravu liniju, pokrećući metodu u beskonačnu petlju. Algoritam u ovoj modifikaciji još nije opremljen načinom da se izvuče iz ove situacije i pomakne jedan vrh u stranu, tako da morate kreirati novi simpleks sa novim parametrima kako se to ne bi dogodilo u budućnosti.
Još jedna karakteristika ove metode je da ne radi ispravno sa šest ili više vrhova simpleksa. Međutim, modifikacijom ove metode možete se riješiti ovog problema i čak ne izgubiti brzinu izvršavanja, ali će se vrijednost dodijeljene memorije primjetno povećati. Ova metoda se može smatrati cikličkom, jer je u potpunosti zasnovana na ciklusima, zbog čega se uočava netačan rad kod velikog broja vrhova.
Nelder-Mead algoritam se s pravom može smatrati jednim od najbolje prakse pronalaženje tačke ekstrema pomoću simpleksa i odlično je za korištenje u raznim vrstama inženjerskih i ekonomskih problema. Čak i unatoč cikličnosti, koristi vrlo malu količinu memorije u odnosu na istu metodu koordinatnog spuštanja, a za pronalaženje samog ekstrema potrebno je izračunati samo vrijednosti centra gravitacije i funkcije. Mali, ali dovoljan broj složenih parametara čini ovu metodu širokom primjenom u složenim matematičkim i stvarnim proizvodnim problemima.
Simpleks algoritmi su rub, čije horizonte nećemo uskoro otvarati, ali već sada svojom vizualnom komponentom uvelike pojednostavljuju naš život.

P.S. Tekst je u potpunosti moj. Nadam se da neko ove informacijeće biti od koristi.

gradijent metode optimizacija

Optimizacijski problemi sa nelinearnim ili teško proračunljivim odnosima koji određuju optimizacioni kriterijum i ograničenja su predmet nelinearnog programiranja. U pravilu, rješenja za probleme nelinearnog programiranja mogu se pronaći samo numeričkim metodama korištenjem kompjuterske tehnologije. Među njima se najčešće koriste gradijentne metode (metode opuštanja, gradijenta, najstrmijeg spuštanja i uspona), negradijentne determinističke metode pretraživanja (metode skeniranja, simpleks itd.) i metode slučajnog pretraživanja. Sve ove metode se koriste u numeričkom određivanju optima i široko su obrađene u stručnoj literaturi.

AT opšti slučaj vrijednost kriterija optimizacije R može se posmatrati kao funkcija R(x b xx..., x n), definisan u n-dimenzionalnom prostoru. Pošto ne postoji vizuelni grafički prikaz n-dimenzionalnog prostora, koristićemo slučaj dvodimenzionalnog prostora.

Ako R(l x 2) kontinuirano u regionu D, zatim oko optimalne tačke M°(xi°, x z°) moguće je nacrtati zatvorenu liniju u ovoj ravni, duž koje je vrijednost R= konst. Postoji mnogo takvih linija, koje se nazivaju linije jednakih nivoa, koje se mogu nacrtati oko optimalne tačke (u zavisnosti od koraka

Među metodama koje se koriste za rješavanje problema nelinearnog programiranja značajno mjesto zauzimaju metode pronalaženja rješenja zasnovane na analizi derivacije s obzirom na smjer funkcije koja se optimizira. Ako u svakoj tački prostora skalarna funkcija više varijabli poprima dobro definirane vrijednosti, onda se u ovom slučaju radi o skalarnom polju (temperaturno polje, polje pritiska, polje gustine itd.). Vektorsko polje (polje sila, brzina, itd.) definira se na sličan način. Izoterme, izobare, izohrone itd. - sve su to linije (površine) jednakih nivoa, jednakih vrijednosti funkcije (temperatura, pritisak, zapremina, itd.). Kako se vrijednost funkcije mijenja od tačke do tačke u prostoru, potrebno je odrediti brzinu promjene funkcije u prostoru, odnosno derivaciju u smjeru.

Koncept gradijenta se široko koristi u inženjerskim proračunima za pronalaženje ekstrema nelinearnih funkcija. Gradijentne metode su numeričke metode tipa pretraživanja. Oni su univerzalni i posebno efikasni u slučajevima traženja ekstrema nelinearnih funkcija sa ograničenjima, kao i kada je analitička funkcija potpuno nepoznata. Suština ovih metoda je odrediti vrijednosti varijabli koje daju ekstremum funkcije cilja kretanjem duž gradijenta (prilikom traženja max) ili u suprotnom smjeru (min). Različite metode gradijenta razlikuju se jedna od druge po načinu na koji se određuje kretanje prema optimumu. Suština je da ako su linije jednake razine R(xu x i) grafički okarakterizirati ovisnost R(x\jc?), tada se potraga za optimalnom tačkom može provesti na različite načine. Na primjer, nacrtajte mrežu na ravni x\, xr sa naznakom vrednosti R na čvorovima mreže (slika 2.13).

Tada možete birati između nodalnih vrijednosti ekstrema. Ovaj put nije racionalan, povezan je sa velikim brojem proračuna, a tačnost je niska, jer zavisi od koraka, a optimum se može locirati između čvorova.

Numeričke metode

Matematički modeli sadrže relacije sastavljene na osnovu teorijske analize proučavanih procesa ili dobijene kao rezultat obrade eksperimenata (tabele podataka, grafikoni). U svakom slučaju, matematički model samo približno opisuje stvarni proces. Dakle) pitanje tačnosti, adekvatnosti modela je najvažnije. Potreba za aproksimacijama javlja se u samom rješenju jednačina. Do nedavno, modeli koji sadrže nelinearne ili parcijalne diferencijalne jednadžbe nisu se mogli analitički rješavati. Isto važi i za brojne klase nesvlačećih integrala. Međutim, razvoj metoda za numeričku analizu omogućio je da se uvelike prošire granice mogućnosti analize. matematički modeli, posebno je to postalo realno upotrebom kompjutera.

Numeričke metode se koriste za aproksimaciju funkcija, za rješavanje diferencijalne jednadžbe i njihovi sistemi, za integraciju i diferencijaciju, za izračunavanje numeričkih izraza.

Funkcija se može definirati analitički, tabelarno, grafički. Prilikom istraživanja čest problem je aproksimacija funkcije analitičkim izrazom koji zadovoljava navedene uslove. Time se postižu četiri zadatka:

Odabir čvornih točaka, provođenje eksperimenata na određenim vrijednostima (nivoima) nezavisnih varijabli (ako je korak promjene faktora odabran pogrešno, ili ćemo "preskočiti" karakterističnu osobinu procesa koji se proučava, ili ćemo produžiti procedure i povećavaju složenost pronalaženja obrazaca);

Izbor aproksimirajućih funkcija u obliku polinoma, empirijskih formula, ovisno o sadržaju određenog problema (treba težiti maksimalnom pojednostavljenju aproksimirajućih funkcija);

Odabir i korištenje kriterija ispravnosti, na osnovu kojih se pronalaze parametri aproksimirajućih funkcija;

Ispunjenje zahtjeva zadate tačnosti do izbora aproksimativne funkcije.

U problemima aproksimacije funkcija polinomima koriste se tri klase

Linearna kombinacija funkcije snage(Taylor red, Lagrange, Newton polinomi, itd.);

Kombinacija funkcija cos nx, w njih(Fourierov red);

Polinom formiran funkcijama exp(-a, d).

Prilikom pronalaženja aproksimativne funkcije koriste se različiti kriteriji slaganja s eksperimentalnim podacima.

Vektor gradijenta je usmjeren prema najbržem porastu funkcije u datoj tački. Vektor suprotan gradijentu -grad(/(x)), naziva se antigradijent i usmjeren je u smjeru najbržeg opadanja funkcije. U minimalnoj tački, gradijent funkcije je nula. Metode prvog reda, koje se nazivaju i metode gradijenta, zasnivaju se na svojstvima gradijenta. Ako nema dodatnih informacija, onda je od početne tačke x (0 > bolje ići do tačke x (1) , koja leži u pravcu antigradijenta - najbrže smanjenje funkcije. Odabir antigradijenta -grad ( /(x (^)) u tački x (do dobijamo iterativni proces oblika

U koordinatnoj formi ovaj proces se piše na sljedeći način:

Kao kriterijum za zaustavljanje iterativnog procesa može se koristiti ili uslov (10.2) ili ispunjenje uslova za malenost gradijenta

Moguć je i kombinovani kriterijum koji se sastoji u istovremenom ispunjavanju navedenih uslova.

Metode gradijenta se razlikuju jedna od druge po načinu odabira veličine koraka. a U metodi konstantnog koraka, neka konstantna vrijednost koraka se bira za sve iteracije. Prilično mali korak a^ osigurava da se funkcija smanjuje, tj. ispunjenje nejednakosti

Međutim, to može dovesti do potrebe da se provede dovoljno veliki broj iteracije do minimalne tačke. S druge strane, preveliki korak može uzrokovati rast funkcije ili dovesti do fluktuacija oko minimalne točke. Za odabir veličine koraka potrebne su dodatne informacije, tako da se metode sa konstantnim korakom rijetko koriste u praksi.

Pouzdanije i ekonomičnije (u smislu broja iteracija) su gradijentne metode sa promjenjivim korakom, kada se, ovisno o dobivenoj aproksimaciji, veličina koraka na neki način mijenja. Kao primjer takve metode, razmotrite metodu najstrmijeg spuštanja. U ovoj metodi, pri svakoj iteraciji, vrijednost koraka n* se bira iz uslova minimuma funkcije /(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. Stoga je pri svakoj iteraciji potrebno riješiti problem jednodimenzionalne minimizacije s obzirom na π funkcije φ(λ) =/(x(/r) - - agrad^x^))). Algoritam metode najstrmijeg spuštanja je sljedeći.

• 1. Postavimo koordinate početne tačke x^°, tačnost približnog rješenja r. k = 0.
• 2. U tački x (/z) izračunavamo vrijednost gradijenta grad(/(x (^)).
• 3. Odredite veličinu koraka a^ jednodimenzionalnom minimizacijom u odnosu na i funkcije cp(i).
• 4. Definiramo novu aproksimaciju minimalnoj tački x (* +1 > prema formuli (10.4).
• 5. Provjerite uvjete za zaustavljanje iterativnog procesa. Ako su zadovoljni, onda kalkulacije prestaju. Inače, stavljamo kk+ 1 i idite na stavku 2.

U metodi najstrmijeg spuštanja, smjer kretanja od tačke x (*) dodiruje liniju nivoa u tački x (* +1). Putanja spuštanja je cik-cak, a susjedne cik-cak veze su ortogonalne jedna prema drugoj. Zaista, korak a^ se bira minimiziranjem a funkcije ( a). Neophodan uslov

minimum funkcije - = 0. Izračunavanje izvoda

kompleksne funkcije, dobivamo uvjet ortogonalnosti za vektore smjera spuštanja u susjednim točkama:

Problem minimiziranja funkcije φ(n) može se svesti na problem izračunavanja korijena funkcije jedne varijable g(a) =

Metode gradijenta konvergiraju na minimum brzinom geometrijske progresije za glatke konveksne funkcije. Takve funkcije imaju najveće i najmanje sopstvene vrijednosti matrice drugih izvoda (Hesove matrice)

malo se razlikuju jedno od drugog, tj. matrica H(x) je dobro uslovljena. Međutim, u praksi, minimizirane funkcije često imaju loše uvjetovane matrice drugih izvoda. Vrijednosti takvih funkcija u nekim smjerovima mijenjaju se mnogo brže nego u drugim smjerovima. Stopa 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, generalno može prekinuti konvergenciju procesa gradijentnog spuštanja. Stoga se metode gradijenta često koriste u kombinaciji s drugim, više efikasne metode u početnoj fazi rešavanja problema. U ovom slučaju, tačka x(0) je daleko od tačke minimuma, a koraci u pravcu antigradijenta omogućavaju da se postigne značajno smanjenje funkcije.

gradijent metode

Gradijentne neograničene optimizacijske metode koriste samo prve izvode funkcije cilja i predstavljaju metode linearne aproksimacije u svakom koraku, tj. ciljna funkcija u svakom koraku se zamjenjuje tangentnom hiperravninom na njen graf u trenutnoj tački.

On k-ta faza Gradijentne metode, prijelaz iz tačke Xk u tačku Xk+1 opisuje se relacijom:

gdje je k veličina koraka, k je vektor u smjeru Xk+1-Xk.

Metode najstrmih spuštanja

Po prvi put je takav metod razmatrao i primenio O. Cauchy u 18. veku. Njegova ideja je jednostavna: gradijent ciljne funkcije f(X) u bilo kojoj tački je vektor u smjeru najvećeg povećanja vrijednosti funkcije. Stoga će antigradijent biti usmjeren prema najvećem smanjenju funkcije i predstavlja smjer najstrmijeg spuštanja. Antigradijent (i gradijent) je ortogonan na površinu nivoa f(X) u tački X. Ako u (1.2) uvedemo pravac

onda će to biti pravac najstrmijeg spuštanja u tački Xk.

Dobijamo formulu prijelaza iz Xk u Xk+1:

Anti-gradijent daje samo smjer spuštanja, a ne veličinu koraka. Općenito, jedan korak ne daje minimalni poen, tako da se postupak spuštanja mora primijeniti nekoliko puta. U tački minimuma, sve komponente gradijenta su jednake nuli.

Sve metode gradijenta koriste gornju ideju i razlikuju se jedna od druge u tehničkim detaljima: izračunavanje izvoda analitičkom formulom ili aproksimacijom konačnih razlika; veličina koraka može biti konstantna, mijenjati se prema nekim pravilima ili biti odabrana nakon primjene jednodimenzionalnih metoda optimizacije u smjeru antigradijenta, itd. itd.

Nećemo se zadržavati u detaljima, jer. metoda najstrmijeg spuštanja se općenito ne preporučuje kao ozbiljna procedura optimizacije.

Jedan od nedostataka ove metode je što konvergira u bilo koju stacionarnu tačku, uključujući i tačku sedla, što ne može biti rješenje.

Ali najvažnija stvar je vrlo spora konvergencija najstrmijeg spuštanja u opštem slučaju. Poenta je da je spust "najbrži" u lokalnom smislu. Ako je hiperprostor pretraživanja jako izdužen („jaruga“), tada je antigradijent usmjeren skoro ortogonalno na dno „jaruge“, tj. najbolji pravac za dostizanje minimuma. U tom smislu, direktan prevod engleskog izraza "strmi spust", tj. spuštanje po najstrmijoj padini više odgovara stanju stvari nego termin "najbrži" usvojen u stručnoj literaturi na ruskom jeziku. Jedan izlaz u ovoj situaciji je korištenje informacija koje daju drugi parcijalni derivati. Drugi izlaz je promjena skale varijabli.

gradijent derivacije linearne aproksimacije

Fletcher-Reevesova metoda konjugiranog gradijenta

Metoda konjugiranog gradijenta konstruira niz pravaca pretraživanja koji su linearne kombinacije trenutnog najstrmijeg smjera spuštanja i prethodnih pravaca pretraživanja, tj.

a koeficijenti se biraju tako da se pravci traženja konjugiraju. To dokazao

a ovo je vrlo vrijedan rezultat koji vam omogućava da izgradite brz i efikasan algoritam optimizacije.

Fletcher-Reeves algoritam

1. U X0 se izračunava.

2. U k-tom koraku, jednodimenzionalnim pretraživanjem u pravcu, nalazi se minimum f(X) koji određuje tačku Xk+1.

• 3. Izračunajte f(Xk+1) i.
• 4. Smjer se određuje iz omjera:

• 5. Nakon (n+1)-te iteracije (tj. sa k=n), ponovno se pokreće: pretpostavlja se X0=Xn+1 i vrši se prijelaz na korak 1.
• 6. Algoritam se zaustavlja kada

gdje je proizvoljna konstanta.

Prednost Fletcher-Reeves algoritma je u tome što ne zahtijeva inverziju matrice i štedi memoriju računala, budući da mu nisu potrebne matrice koje se koriste u Newtonovim metodama, ali je u isto vrijeme gotovo jednako efikasan kao kvazi-Njutnovi algoritmi. Jer pravci pretraživanja su međusobno konjugirani, tada će kvadratna funkcija biti minimizirana u ne više od n koraka. U općem slučaju koristi se ponovno pokretanje, što vam omogućava da dobijete rezultat.

Fletcher-Reeves algoritam je osjetljiv na tačnost jednodimenzionalnog pretraživanja, tako da se sve greške zaokruživanja koje se mogu pojaviti moraju biti ispravljene kada se koristi. Takođe, algoritam može propasti u situacijama kada Hessian postane loše uslovljen. Algoritam nema garanciju konvergencije uvek i svuda, iako praksa pokazuje da algoritam skoro uvek daje rezultat.

Newtonove metode

Smjer traženja koji odgovara najstrmijem spuštanju povezan je s linearnom aproksimacijom funkcije cilja. Metode koje koriste druge izvode proizašle su iz kvadratne aproksimacije ciljne funkcije, odnosno kada se funkcija proširi u Taylorov red, termini trećeg i višeg reda se odbacuju.

gdje je Hessian matrica.

Minimum desne strane (ako postoji) dostiže se na istom mjestu kao i minimum kvadratnog oblika. Napišimo formulu za određivanje smjera pretrage:

Minimum je dostignut na

Optimizacijski algoritam u kojem se smjer pretraživanja određuje iz ove relacije naziva se Newtonov metod, a smjer je Newtonov smjer.

U problemima pronalaženja minimuma proizvoljne kvadratne funkcije sa pozitivnom matricom drugih izvoda, Newtonova metoda daje rješenje u jednoj iteraciji, bez obzira na izbor početne tačke.

Klasifikacija Njutnovskih metoda

Zapravo, Newtonova metoda se sastoji u jednoj primjeni Newtonovog smjera za optimizaciju kvadratne funkcije. Ako funkcija nije kvadratna, tačna je sljedeća teorema.

Teorema 1.4. Ako je Hessian matrica opće nelinearne funkcije f u minimalnoj tački X* pozitivno-definirana, početna tačka je odabrana dovoljno blizu X*, a dužine koraka su pravilno odabrane, tada Newtonova metoda konvergira na X* sa kvadratna brzina.

Njutnov metod se smatra referentnim i sa njim se porede svi razvijeni optimizacijski postupci. Međutim, Newtonova metoda radi samo s pozitivno određenom i dobro uvjetovanom Hessianom matricom (njena determinanta mora biti znatno veća od nule, tačnije, omjer najvećeg i najmanjeg sopstvene vrijednosti treba da bude blizu jedinstva). Da bi se otklonio ovaj nedostatak, koriste se modificirane Newtonove metode, koristeći Newtonove smjerove koliko god je to moguće i odstupajući od njih samo kada je to potrebno.

Opći princip modifikacija Newtonove metode je sljedeći: na svakoj iteraciji, neka pozitivno-definirana matrica "povezana" s najprije se konstruiše, a zatim izračunava po formuli

Pošto je pozitivno određen, onda će - nužno biti pravac spuštanja. Procedura konstrukcije je organizirana tako da se poklapa sa Hessian matricom ako je pozitivno određena. Ove procedure su izgrađene na osnovu nekih proširenja matrice.

Druga grupa metoda, koja je skoro jednako brza kao i Newtonova metoda, zasniva se na aproksimaciji Hesove matrice korištenjem konačnih razlika, jer nije potrebno koristiti tačne vrijednosti derivata za optimizaciju. Ove metode su korisne kada je analitičko izračunavanje derivata teško ili jednostavno nemoguće. Takve metode se nazivaju diskretne Newtonove metode.

Ključ efikasnosti metoda Newtonovog tipa je uzimanje u obzir informacija o zakrivljenosti funkcije koja se minimizira, a koja je sadržana u Hessian matrici i omogućava izgradnju lokalno egzaktnih kvadratnih modela ciljne funkcije. Ali moguće je prikupiti i akumulirati informacije o zakrivljenosti funkcije na osnovu posmatranja promjene gradijenta tokom iteracija spuštanja.

Odgovarajuće metode zasnovane na mogućnosti aproksimacije zakrivljenosti nelinearne funkcije bez eksplicitnog formiranja njene Hesove matrice nazivaju se kvazi-njutnovske metode.

Napominjemo da je prilikom konstruiranja optimizacijske procedure njutnovskog tipa (uključujući i kvazinjutnovsku) potrebno uzeti u obzir mogućnost pojave sedla. U ovom slučaju, vektor najboljeg smjera pretraživanja uvijek će biti usmjeren na tačku sedla, umjesto da se udaljava od nje u smjeru "dolje".

Newton-Raphsonova metoda

Ova metoda se sastoji u ponovljenoj upotrebi Newtonovog pravca pri optimizaciji funkcija koje nisu kvadratne.

Osnovna iterativna formula za multivarijantnu optimizaciju

se u ovoj metodi koristi pri odabiru smjera optimizacije iz relacije

Prava dužina koraka je skrivena u nenormalizovanom Njutnovom pravcu.

Budući da ova metoda ne zahtijeva vrijednost ciljne funkcije u trenutnoj točki, ponekad se naziva metodom indirektne ili analitičke optimizacije. Njegova sposobnost da odredi minimum kvadratne funkcije u jednom proračunu izgleda izuzetno atraktivno na prvi pogled. Međutim, ova "jedinstvena kalkulacija" je skupa. Prije svega, potrebno je izračunati n parcijalnih izvoda prvog reda i n(n+1)/2 - drugog. Osim toga, Hessian matrica mora biti invertirana. Ovo već zahtijeva oko n3 računskih operacija. Uz istu cijenu, metode konjugiranih smjerova ili metode konjugiranog gradijenta mogu uzeti oko n koraka, tj. postići skoro isti rezultat. Dakle, iteracija Newton-Raphsonove metode ne daje prednosti u slučaju kvadratne funkcije.

Ako funkcija nije kvadratna, onda

• - početni smjer već, općenito govoreći, ne ukazuje na stvarnu minimalnu tačku, što znači da se iteracije moraju ponavljati više puta;
• - korak jedinične dužine može dovesti do tačke sa lošijom vrijednošću funkcije cilja, a pretraga može dati pogrešan smjer ako, na primjer, Hessian nije pozitivno određen;
• - Hessian može postati loše uslovljen, čineći ga nemogućim invertiranje, tj. određivanje smjera za sljedeću iteraciju.

Sama strategija ne razlikuje kojoj se stacionarnoj tački (minimalnoj, maksimalnoj, tački sedla) približava pretraga, a ne vrši se izračunavanje vrijednosti funkcije cilja, pomoću kojih bi se moglo pratiti da li se funkcija povećava. Dakle, sve zavisi od toga koja je stacionarna tačka u zoni atrakcije početna tačka pretrage. Newton-Raphsonova strategija se rijetko koristi samostalno bez modifikacija ove ili one vrste.

Pearson metode

Pearson je predložio nekoliko metoda za aproksimaciju inverznog Hessiana bez eksplicitnog izračunavanja drugih izvoda, tj. posmatranjem promjena u smjeru antigradijenta. U ovom slučaju dobijaju se konjugirani pravci. Ovi algoritmi se razlikuju samo u detaljima. Evo onih koji se najčešće koriste u primijenjenim poljima.

Pearsonov algoritam #2.

U ovom algoritmu, inverzni Hessian se aproksimira matricom Hk izračunatom na svakom koraku po formuli

Kao početna matrica H0 bira se proizvoljna pozitivno-definirana simetrična matrica.

Ovaj Pearsonov algoritam često dovodi do situacija u kojima matrica Hk postaje loše uvjetovana, naime, počinje oscilirati, oscilirajući između pozitivno određenog i nepozitivno određenog, dok je determinanta matrice bliska nuli. Da bi se izbjegla ova situacija, potrebno je ponovo postaviti matricu na svakih n koraka, izjednačavajući je sa H0.

Pearsonov algoritam #3.

U ovom algoritmu, matrica Hk+1 se određuje iz formule

Hk+1 = Hk +

Putanja spuštanja koju generiše algoritam je slična ponašanju Davidon-Fletcher-Powell algoritma, ali su koraci nešto kraći. Pearson je također predložio varijantu ovog algoritma sa cikličnim preuređivanjem matrice.

Projektivni Newton-Raphson algoritam

Pearson je predložio ideju algoritma u kojem se matrica izračunava iz relacije

H0=R0, pri čemu je matrica R0 ista kao početne matrice u prethodnim algoritmima.

Kada je k višekratnik broja nezavisnih varijabli n, matrica Hk se zamjenjuje matricom Rk+1 izračunatom kao zbir

Vrijednost Hk(f(Xk+1) - f(Xk)) je projekcija vektora prirasta gradijenta (f(Xk+1)-f(Xk)), ortogonalna na sve vektore prirasta gradijenta u prethodnim koracima. Nakon svakih n koraka, Rk je aproksimacija inverznog Hessiana H-1(Xk), tako da se u suštini vrši (približno) Newtonovo pretraživanje.

Davidon-Fletcher-Powell metoda

Ova metoda ima i druge nazive - varijabilna metrička metoda, kvazi-njutnova metoda, jer on koristi oba ova pristupa.

Davidon-Fletcher-Powell (DFP) metoda je zasnovana na korištenju Newtonovih pravaca, ali ne zahtijeva izračunavanje inverznog Hessiana u svakom koraku.

Smjer traženja u koraku k je smjer

gdje je Hi pozitivno-definirana simetrična matrica koja se ažurira na svakom koraku i, u ograničenju, postaje jednaka inverznom Hessianu. Matrica identiteta se obično bira kao početna matrica H. Iterativni DFT postupak se može predstaviti na sljedeći način:

• 1. U koraku k, postoji tačka Xk i pozitivno određena matrica Hk.
• 2. Odaberite kao novi smjer pretraživanja

3. Jednodimenzionalno pretraživanje (obično kubnom interpolacijom) duž pravca određuje k minimizirajući funkciju.

4. Oslanja se.

5. Oslanja se.

6. Određeno i. Ako su Vk ili dovoljno mali, postupak se prekida.

• 7. Postavite Uk = f(Xk+1) - f(Xk).
• 8. Matrica Hk se ažurira prema formuli

9. Povećajte k za jedan i vratite se na korak 2.

Metoda je učinkovita u praksi ako je greška proračuna gradijenta mala i matrica Hk ne postane loše uvjetovana.

Matrica Ak osigurava konvergenciju Hk prema G-1, matrica Bk osigurava pozitivnu određenost Hk+1 u svim fazama i isključuje H0 u granici.

U slučaju kvadratne funkcije

one. DFP algoritam koristi konjugirane smjerove.

Dakle, DFT metoda koristi i ideje Newtonovog pristupa i svojstva konjugiranih pravaca, a kada se minimizira kvadratna funkcija, konvergira u najviše n iteracija. Ako funkcija koja se optimizira ima oblik blizak kvadratnoj funkciji, onda je DFP metoda efikasna zbog dobre aproksimacije G-1 (Newtonova metoda). Ako ciljna funkcija ima opšti oblik, onda je DFP metoda efikasna zbog upotrebe konjugiranih pravaca.

1. Koncept gradijentnih metoda. Neophodan uslov za postojanje ekstremuma neprekidne diferencijabilne funkcije su uslovi oblika

gdje su argumenti funkcije. Kompaktnije, ovaj uslov se može napisati u obliku

(2.4.1)

gdje je oznaka gradijenta funkcije u datoj tački.

Pozivaju se metode optimizacije koje koriste gradijent za određivanje ekstrema ciljne funkcije gradijent.Široko se koriste u sistemima optimalnog adaptivnog upravljanja stabilnim stanjima, u kojima se traži optimalno (u smislu izabranog kriterijuma) stabilno stanje sistema kada se promene njegovi parametri, struktura ili spoljni uticaji.

Jednačina (2.4.1) je općenito nelinearna. Direktno rješenje za to je ili nemoguće ili vrlo teško. Pronalaženje rješenja ovakvih jednačina moguće je organiziranjem posebne procedure za traženje tačke ekstrema na temelju upotrebe različitih vrsta rekurzivnih formula.

Procedura pretraživanja je izgrađena u obliku višestepenog procesa, u kojem svaki sljedeći korak dovodi do povećanja ili smanjenja ciljne funkcije, odnosno ispunjeni su uvjeti u slučaju traženja maksimuma, odnosno minimuma:

Kroz n i n– 1 označava brojeve koraka, a kroz i su vektori koji odgovaraju vrijednostima argumenata ciljne funkcije na n-m i ( P- 1)th koraci. Nakon r. koraka, može se dobiti

tj. nakon r - koraka - funkcija cilja se više neće povećavati (smanjivati) sa bilo kojom daljom promjenom svojih argumenata;. Ovo poslednje znači dostizanje tačke sa koordinatama za koje to možemo napisati

	(2.4.2)
	(2.4.3)

gdje je ekstremna vrijednost ciljne funkcije.

Za rješavanje (2.4.1) u opštem slučaju može se primijeniti sljedeći postupak. Zapišimo vrijednost koordinata funkcije cilja u formu

gdje je neki koeficijent (skalar) koji nije jednak nuli.

U tački ekstrema, pošto

Rješenje jednadžbe (2.4.1) na ovaj način moguće je ako je za bilo koju početnu vrijednost zadovoljen uslov konvergencije iterativnog procesa.

Metode za određivanje , zasnovane na rješenju jednadžbe (2.2.), razlikuju se jedna od druge po izboru , odnosno u izboru koraka promjene ciljne funkcije u procesu traženja ekstrema. Ovaj korak može biti trajan ili promenljiva U drugom slučaju, zakon promene vrednosti koraka, zauzvrat, može biti unapred određen ili. ovisi o trenutnoj vrijednosti (može biti nelinearna).

2. Metoda najstrmijeg spuštanja.Ideja metode najstrmijeg spuštanja je da se potraga za ekstremomom sprovodi u pravcu najveće promene gradijenta ili antigradijenta, pošto je to najkraći put do krajnje tačke. Prilikom implementacije, prije svega, potrebno je izračunati gradijent u datoj tački i odabrati vrijednost koraka.

Proračun gradijenta. Budući da su kao rezultat optimizacije pronađene koordinate tačke ekstrema, za koje je relacija tačna:

tada se računski postupak za određivanje gradijenta može zamijeniti postupkom za određivanje komponenti gradijenta u diskretnim tačkama u prostoru ciljne funkcije

	(2.4.5)

gdje je mala promjena u koordinatama

Pod pretpostavkom da je tačka definicije gradijenta u sredini

segment onda

Izbor (2.4.5) ili (2.4.6) zavisi od strmine funkcije na odseku - Ax;; ako strmina nije velika, prednost treba dati (2.4.5), jer ima manje proračuna; inače, tačniji rezultati se dobijaju proračunom prema (2.4.4). Povećanje tačnosti određivanja gradijenta moguće je i usrednjavanjem slučajnih odstupanja.

Odabir vrijednosti koraka Poteškoća u odabiru vrijednosti koraka je u tome što se smjer gradijenta može mijenjati od tačke do tačke. U ovom slučaju, preveliki korak će dovesti do odstupanja od optimalne putanje, odnosno od pravca duž gradijenta ili antigradijenta, a premali korak će dovesti do vrlo sporog kretanja prema ekstremumu zbog potrebe da se izvede velika količina proračuna.

Jedna od mogućih metoda za procjenu vrijednosti koraka je Newton-Raphsonova metoda. Razmotrimo ga na primjeru jednodimenzionalnog slučaja pod pretpostavkom da je ekstremum dostignut u tački određenoj rješenjem jednačine (slika 2.4.2).

Neka pretraga počne od tačke i, u blizini ove tačke, funkcija se može proširiti u konvergentni Taylorov red. Onda

Smjer gradijenta u tački je isti kao i smjer tangente. Prilikom traženja minimalne ekstremne tačke, promjena koordinata X kretanje duž gradijenta može se zapisati kao:

Slika 2.4.2 Šema za izračunavanje koraka prema Newton-Raphson metodi.

Zamjenom (2.4.7) u (2.4.8) dobijamo:

Budući da se, prema uslovu ovog primjera, vrijednost postiže u tački koja je određena rješenjem jednačine, onda možemo pokušati napraviti takav korak da tj. da

Zamijenite novu vrijednost na ciljnu funkciju. Ako se tada u tački, postupak određivanja ponavlja, kao rezultat toga se pronalazi vrijednost:

itd. proračun se zaustavlja ako su promjene ciljne funkcije male, tj.

gdje – dopustiva greška u određivanju ciljne funkcije.

Metoda optimalnog gradijenta. Ideja iza ove metode je sljedeća. U uobičajenoj metodi najstrmijeg spuštanja, korak se bira u opštem slučaju [kada] proizvoljno, vodeći se samo činjenicom da ne bi trebao prelaziti određenu vrijednost. U metodi optimalnog gradijenta, vrijednost koraka se bira na osnovu zahtjeva da se od date tačke treba kretati u smjeru gradijenta (antigradijent) sve dok se ciljna funkcija ne poveća (smanji). Ako ovaj zahtjev nije ispunjen, potrebno je zaustaviti kretanje i odrediti novi smjer kretanja (smjer gradijenta) itd. (dok se ne pronađe optimalna tačka).

Dakle, optimalne vrijednosti i za pronalaženje minimuma i maksimuma, respektivno, određuju se iz rješenja jednadžbi:

U (1) i (2), respektivno

Stoga se definicija na svakom koraku sastoji u pronalaženju iz jednačina (1) ili (2) za svaku tačku putanje kretanja duž gradijenta, počevši od prvobitne.