Predavanje 6

Gradijentne metode za rješavanje problema nelinearnog programiranja.

pitanja: 1. opšte karakteristike metode.

2. Metoda gradijenta.

3. Metoda najstrmijeg spuštanja.

4. Frank-Fulf metoda.

5. Metoda kaznenih funkcija.

1. Opće karakteristike metoda.

Gradijentne metode su aproksimativne (iterativne) metode za rješavanje problema nelinearnog programiranja i omogućavaju rješavanje gotovo svakog problema. Međutim, ovo definiše lokalni ekstrem. Stoga je preporučljivo primijeniti ove metode za rješavanje problema konveksnog programiranja u kojima je svaki lokalni ekstremum također globalan. Proces rješavanja problema sastoji se u tome da se, počevši od neke tačke x (početne), izvrši sekvencijalni prijelaz u smjeru gradF (x), ako je određena tačka maksimuma, i -gradF (x) (anti -gradijent), ako je određena minimalna tačka, do tačke , koja je rešenje problema. U ovom slučaju, ova tačka može biti i unutar raspona dopuštenih vrijednosti i na njegovoj granici.

Gradijentne metode se mogu podijeliti u dvije klase (grupe). U prvu grupu spadaju metode u kojima sve proučavane tačke pripadaju dozvoljenom području. U ove metode spadaju: metoda gradijenta, najstrmijeg spuštanja, Frank-Wolf, itd. U drugu grupu spadaju metode u kojima ispitivane tačke možda ne pripadaju dozvoljenom području. Najčešća od ovih metoda je metoda kaznenih funkcija. Sve metode kaznenih funkcija razlikuju se jedna od druge po načinu određivanja "kazne".

Glavni koncept koji se koristi u svim metodama gradijenta je koncept gradijenta funkcije, kao smjera najbržeg povećanja funkcije.

Prilikom određivanja rješenja metodom gradijenta, iterativni proces se nastavlja sve dok:

Ili grad F(x*) = 0, (tačno rješenje);

Gdje
- dva uzastopna poena,
je mali broj koji karakterizira tačnost rješenja.

2. Metoda gradijenta.

Zamislite osobu koja stoji na padini jaruge koja treba da se spusti (do dna). Najprirodnije je, čini se, pravac prema najstrmijoj padini, tj. smjer (-grad F(x)). Rezultirajuća strategija, tzv metod gradijenta, je niz koraka, od kojih svaki sadrži dvije operacije:

a) određivanje pravca najveće strmine spuštanja (uspona);

b) kretati se u odabranom smjeru za neki korak.

Odabir pravog koraka je od suštinskog značaja. Što je korak manji, to je rezultat precizniji, ali više proračuna. Razne modifikacije metod gradijenta i sastoje se u korištenju različitih metoda za određivanje koraka. Ako se ni u jednom koraku vrijednost F(x) nije smanjila, to znači da je minimalna tačka „preskočena“, u ovom slučaju je potrebno vratiti se na prethodnu tačku i smanjiti korak, na primjer, za pola.

Shema rješenja.

pripada dozvoljenoj površini

3. Izbor koraka h.

x(k+1) = x(k)

"-" - ako je min.

5. Definicija F(x (k +1)) i:

Ako
, rješenje je pronađeno;

Komentar. Ako je grad F(x (k)) = 0, tada će rješenje biti tačno.

Primjer. F(x) = -6x 1 + 2x 1 2 – 2x 1 x 2 + 2x 2 2
min,

x1 +x2 2x1 0,x2 0,= 0,1.

3. Metoda najstrmijeg spuštanja.

Za razliku od metode gradijenta, u kojoj se gradijent određuje na svakom koraku, kod metode najstrmijeg spuštanja gradijent se nalazi na početnoj tački i kretanje u pronađenom smjeru se nastavlja u jednakim koracima sve dok se vrijednost funkcije ne smanji (poveća ). Ako se na bilo kojem koraku F(x) poveća (smanji), tada se kretanje u ovom smjeru zaustavlja, posljednji korak se uklanja u potpunosti ili prepola i izračunava se nova vrijednost gradijenta i novi smjer.

Shema rješenja.

1. Definicija x 0 \u003d (x 1, x 2, ..., x n),

pripada dozvoljenoj zoni,

i F(x 0), k = 0.

2. Definicija gradF(x 0) ili –gradF(x 0).

3. Izbor koraka h.

4. Određivanje sljedeće tačke po formuli

x(k+1) = x(k) h grad F(x (k)), "+" - ako je max,

"-" - ako je min.

5. Definicija F(x (k +1)) i:

Ako
, rješenje je pronađeno;

Ako ne:

a) pri traženju min: - ako je F(x (k +1))

Ako je F(x (k +1)) >F(x (k)) – idi na stavku 2;

b) pri traženju max: - ako je F(x (k +1)) >F(x (k)) – idite na korak 4;

Ako je F(x (k + 1))

napomene: 1. Ako je grad F(x (k)) = 0, tada će rješenje biti tačno.

2. Prednost metode najstrmijeg spuštanja je njena jednostavnost i

smanjenje proračuna, jer se grad F(x) ne računa u svim tačkama, što

važno za probleme velikih razmjera.

3. Nedostatak je što koraci moraju biti mali da ne bi

preskočite optimalnu tačku.

Primjer. F(x) \u003d 3x 1 - 0,2x 1 2 + x 2 - 0,2x 2 2
max,

x 1 + x 2 7x1 0,

x1 + 2x2 10x2 0.

4. Frank-Wolfe metoda.

Metoda se koristi za optimizaciju nelinearne ciljne funkcije pod linearnim ograničenjima. U blizini tačke koja se proučava, nelinearna ciljna funkcija je zamijenjena linearnom funkcijom, a problem se svodi na sekvencijalno rješavanje problema linearnog programiranja.

Shema rješenja.

1. Određivanje x 0 = (x 1, x 2,…, x n), koje pripada dozvoljenoj površini, i F(x 0), k = 0.

2. Definicija grada F(x (k)).

3. Izgradite funkciju

(min - "-"; max - "+").

4. Određivanje max(min)f(x) pod početnim ograničenjima. Neka je ovo tačka z (k) .

5. Određivanje koraka proračuna x (k +1) = x (k) + (k) (z (k) –x (k)), gdje je (k) – korak, koeficijent, 0 1. (k) se bira tako da je vrijednost funkcije F(x) max (min) u tački x (k +1) . Da biste to učinili, riješite jednačinu
i izaberite najmanji (najveći) od korijena, ali 0 1.

6. Određivanje F(x (k +1)) i provjeriti potrebu za daljim proračunima:

Ako
ili grad F(x (k + 1)) = 0, onda je rješenje pronađeno;

Ako ne, idite na korak 2.

Primjer. F(x) = 4x 1 + 10x 2 –x 1 2 –x 2 2
max,

x1 +x2 4x1 0,

x2 2x2 0.

5. Metoda kaznenih funkcija.

Neka je potrebno pronaći F(x 1 ,x 2 ,…,x n)
max(min),

g i (x 1 , x 2 ,…,x n) b i , i =
, xj 0, j = .

Funkcije F i g i su konveksne ili konkavne.

Ideja metode kaznene funkcije je pronaći optimalnu vrijednost nove funkcije cilja Q(x) = F(x) + H(x), koja je zbir izvorne funkcije cilja i neke funkcije H(x ) određena sistemom ograničenja i naziva se funkcija kazne. Kaznene funkcije su izgrađene tako da obezbjeđuju ili brz povratak u dozvoljeno područje ili nemogućnost izlaska iz njega. Metoda kaznenih funkcija svodi problem uslovnog ekstremuma na rješavanje niza zadataka za bezuvjetni ekstrem, što je jednostavnije. Postoji mnogo načina da se konstruiše funkcija kazne. Najčešće izgleda ovako:

H(x) =
,

Gdje

- neki pozitivni Const.

Bilješka:

Što manje , što se rješenje brže pronađe, međutim, točnost se smanjuje;

Započnite rješenje s malim i povećavajte ih u narednim koracima.

Koristeći funkciju kazne, jedan se uzastopno kreće od jedne do druge tačke dok se ne dobije prihvatljivo rješenje.

Shema rješenja.

1. Određivanje početne tačke x 0 \u003d (x 1, x 2, ..., x n), F (x 0) i k = 0.

2. Odaberite korak proračuna h.

3. Definirajte parcijalne izvode I .

4. Odredite koordinate sljedeće tačke po formuli:

x j (k+1)
.

5. Ako je x (k+1) Važeće područje, provjerite:

i ako
- rješenje je pronađeno, ako nije, idite na korak 2.

b) ako je grad F(x (k + 1)) = 0, tada je pronađeno tačno rješenje.

Ako je x(k+1) Važeća oblast, postavite novu vrijednost i idite na korak 4.

Primjer. F(x) = – x 1 2 – x 2 2
max,

(x 1 -5) 2 + (x 2 -5) 2 8x1 0,x2 0.

Konačno, parametar m se može postaviti konstantnim na svim iteracijama. Međutim, za velike vrijednosti m, proces pretraživanja može se razlikovati. Dobar način da odaberete m može biti da ga odredite na prvoj iteraciji iz uslova ekstremuma u smjeru gradijenta. U narednim iteracijama, m ostaje konstantan. Ovo još više pojednostavljuje proračune.

Na primjer, za funkciju sa sa projekcijama gradijenta određena metodom najstrmijeg spuštanja. Prihvatamo konstantu parametra na svim iteracijama.

Izračunajte x koordinate (1):

Za izračunavanje koordinata tačke x (2) nalazimo projekciju gradijenta u tački x (1) : , tada

itd.

Ovaj niz također konvergira.

metod stepena gradijenta

Ovu metodu su razvili inženjeri i leži u činjenici da se korak za jednu od varijabli uzima konstantan, a za ostale varijable se bira na osnovu proporcionalnosti nagiba tačaka. Time se, takoreći, skalira ekstremna površina, jer konvergencija nije ista za sve varijable. Stoga, odabirom različitih koraka za koordinate, pokušavaju učiniti stopu konvergencije približno istom za sve varijable.

Neka su data odvojiva funkcija i početna tačka . Postavimo konstantan korak duž x 1 koordinate, neka je Dx 1 =0,2. Korak duž koordinate x 2 nalazi se iz omjera nagiba i koraka.

Razmotrimo problem bezuslovne minimizacije diferencijabilne funkcije nekoliko varijabli, a vrijednost gradijenta u tački neka se približi minimumu. U metodi gradijenta koji se razmatra u nastavku, pravac spuštanja od tačke se direktno bira. Dakle, prema metodi gradijenta

Postoje različiti načini odabira koraka, od kojih svaki definira određenu varijantu metode gradijenta.

1. Metoda najstrmijeg spuštanja.

Razmotrite funkciju jedne skalarne varijable i odaberite kao vrijednost za koju je jednakost

Ova metoda, koju je 1845. godine predložio O. Cauchy, danas se naziva metodom najstrmijeg spuštanja.

Na sl. 10.5 prikazuje geometrijsku ilustraciju ove metode za minimiziranje funkcije dvije varijable. Od početne tačke, okomito na liniju nivoa u pravcu, spuštanje se nastavlja sve dok se ne postigne minimalna vrednost funkcije duž zraka. U pronađenoj tački ova zraka dodiruje liniju nivoa. Zatim se od tačke spušta u smjeru okomitom na liniju nivoa sve dok odgovarajući snop ne dodirne liniju nivoa koja prolazi kroz ovu tačku u tački itd.

Napominjemo da pri svakoj iteraciji izbor koraka podrazumijeva rješenje jednodimenzionalnog problema minimizacije (10.23). Ponekad se ova operacija može izvesti analitički, na primjer, za kvadratnu funkciju.

Primjenjujemo metodu najstrmijeg spuštanja kako bismo minimizirali kvadratnu funkciju

sa simetričnom pozitivno određenom matricom A.

Prema formuli (10.8), u ovom slučaju, dakle, formula (10.22) izgleda ovako:

primeti, to

Ova funkcija je kvadratna funkcija parametra a i dostiže minimum na takvoj vrijednosti za koju

Dakle, primijenjeno na minimizaciju kvadrata

funkcija (10.24), metoda najstrmijeg spuštanja je ekvivalentna proračunu po formuli (10.25), gdje je

Napomena 1. Budući da se minimalna tačka funkcije (10.24) poklapa sa rješenjem sistema, metoda najstrmijeg spuštanja (10.25), (10.26) može se koristiti i kao iterativna metoda za rješavanje sistema linearnih algebarskih jednačina sa simetričnim pozitivnim određene matrice.

Napomena 2. Imajte na umu da je gdje je Rayleighova relacija (vidi § 8.1).

Primjer 10.1. Primjenjujemo metodu najstrmijeg spuštanja kako bismo minimizirali kvadratnu funkciju

Imajte na umu da nam je, dakle, tačna vrijednost minimalne točke unaprijed poznata. Ovu funkciju zapisujemo u obliku (10.24), gdje su matrica i vektor Kao što je lako vidjeti,

Uzimamo početnu aproksimaciju i proračune ćemo izvršiti pomoću formula (10.25), (10.26).

I iteracija.

II iteracija.

Može se pokazati da će se za sve na iteraciji dobiti vrijednosti

Imajte na umu da sa Dakle,

sekvenca dobijena metodom najstrmijeg spuštanja konvergira brzinom geometrijske progresije, čiji je imenilac

Na sl. 10.5 prikazuje tačno putanju spuštanja koja je dobijena u ovom primjeru.

Za slučaj minimiziranja kvadratne funkcije vrijedi sljedeći opći rezultat.

Teorema 10.1. Neka je A simetrična pozitivno određena matrica i neka je kvadratna funkcija (10.24) minimizirana. Tada, za bilo koji izbor početne aproksimacije, metoda najstrmijeg spuštanja (10.25), (10.26) konvergira i sljedeća procjena greške je tačna:

Ovdje i Lado su minimalne i maksimalne vlastite vrijednosti matrice A.

Imajte na umu da ova metoda konvergira brzinom geometrijske progresije, čiji nazivnik, osim toga, ako su blizu, onda je mali i metoda konvergira prilično brzo. Na primjer, u primjeru 10.1 imamo i, prema tome, If Asch, onda 1, i treba očekivati ​​da će metoda najstrmijeg spuštanja polako konvergirati.

Primjer 10.2. Primjena metode najstrmijeg spuštanja za minimiziranje kvadratne funkcije u početnoj aproksimaciji daje niz aproksimacija gdje je putanja spuštanja prikazana na Sl. 10.6.

Niz se ovdje konvergira brzinom geometrijske progresije, čiji je nazivnik, tj., mnogo sporiji,

nego u prethodnom primjeru. Pošto se ovdje dobijeni rezultat u potpunosti slaže sa procjenom (10.27).

Napomena 1. Formulisali smo teoremu o konvergenciji metode najstrmijeg spuštanja u slučaju kada je ciljna funkcija kvadratna. U opštem slučaju, ako je funkcija koja se minimizira strogo konveksna i ima minimalnu tačku x, tada, bez obzira na izbor početne aproksimacije, niz dobiven ovom metodom konvergira na x na . U ovom slučaju, nakon što padne u dovoljno malu okolinu minimalne tačke, konvergencija postaje linearna i nazivnik odgovarajuće geometrijske progresije se procjenjuje odozgo po vrijednosti i gdje i minimalne i maksimalne vlastite vrijednosti Hessiove matrice

Napomena 2. Za kvadratnu ciljnu funkciju (10.24), rješenje jednodimenzionalnog problema minimizacije (10.23) može se naći u obliku jednostavne eksplicitne formule (10.26). Međutim, to se ne može učiniti za većinu drugih nelinearnih funkcija, a za izračunavanje najstrmijeg spuštanja potrebno je primijeniti numeričke metode jednodimenzionalne minimizacije, kao što su one razmatrane u prethodnom poglavlju.

2. Problem "jaruga".

Iz gornje rasprave slijedi da metoda gradijenta konvergira prilično brzo ako su površine nivoa za minimiziranu funkciju blizu sfera (kada su linije nivoa blizu kružnice). Za takve funkcije i 1. Teorema 10.1, primjedba 1 i rezultat primjera 10.2 pokazuju da stopa konvergencije naglo opada kao vrijednost . U dvodimenzionalnom slučaju, reljef odgovarajuće površine podsjeća na teren sa jarugom (sl. 10.7). Stoga se takve funkcije obično nazivaju jarugama. Duž pravaca koji karakteriziraju "dno jaruge" funkcija jaruge se neznatno mijenja, dok se u ostalim pravcima koji karakteriziraju "padinu jaruge" dolazi do oštre promjene funkcije.

Ako početna tačka pada na "padinu jaruge", tada se smjer gradijenta spuštanja pokazuje da je gotovo okomit na "dno jaruge", a sljedeća aproksimacija pada na suprotnu "padinu jaruge". Sljedeći korak prema "dnu jaruge" vraća prilaz prvobitnoj "padini jaruge". Kao rezultat toga, umjesto da se kreće duž „dna jaruge“ prema minimalnoj tački, putanja spuštanja čini cik-cak skokove preko „jaruge“, gotovo da se ne približava cilju (Sl. 10.7).

Da bi se ubrzala konvergencija metode gradijenta uz minimiziranje funkcija jaruga, razvijen je niz posebnih metoda "jaruga". Hajde da damo ideju o jednoj od najjednostavnijih metoda. Sa dvije bliske početne tačke, pravi se nagibni spust do "dna jaruge". Kroz pronađene tačke se povlači prava linija duž koje se pravi veliki korak "jaruga" (slika 10.8). Od ovako pronađene tačke ponovo se pravi jedan korak gradijentnog spuštanja do tačke, a zatim se pravi drugi "jaruški" korak duž prave linije koja prolazi kroz tačke . Kao rezultat toga, kretanje duž "dna jaruge" do minimalne točke značajno je ubrzano.

Više informacija o problemu metoda "jaruga" i "jaruga" možete pronaći, na primjer, u , .

3. Drugi pristupi određivanju koraka spuštanja.

Kao što je lako razumjeti, pri svakoj iteraciji bilo bi poželjno odabrati smjer spuštanja blizak smjeru kojim kretanje vodi od tačke do tačke x. Nažalost, antigradijent (po pravilu je neuspešan pravac spuštanja. Ovo je posebno izraženo za funkcije jaruge. Stoga postoji sumnja u upotrebljivost temeljnog traganja za rešenjem problema jednodimenzionalne minimizacije (10.23) a postoji želja da se napravi samo takav korak u pravcu koji bi obezbedio "značajno smanjenje" funkcije. Štaviše, u praksi se ponekad zadovoljava definisanjem vrednosti koja jednostavno obezbeđuje smanjenje vrednosti cilja. funkcija.

Metode optimizacije gradijenta

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.

U opštem slučaju, vrednost kriterijuma 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 uveliko prošire granice mogućnosti analize matematičkih modela, posebno korišćenjem računara.

Numeričke metode se koriste za aproksimaciju funkcija, za rješavanje diferencijalnih jednadžbi i njihovih sistema, za integraciju i diferenciranje, 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 funkcija stepena (Taylorov red, Lagrangeov, Njutnov polinom, 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.

Metoda opuštanja

Algoritam metode se sastoji u pronalaženju aksijalnog smjera duž kojeg se ciljna funkcija najjače smanjuje (prilikom traženja minimuma). Razmotrite problem neograničene optimizacije

Da bi se odredio aksijalni smjer na početnoj tački pretraživanja, derivacije , , određuju se iz područja u odnosu na sve nezavisne varijable. Aksijalni smjer odgovara najvećoj derivaciji u apsolutnoj vrijednosti.

Neka je aksijalni smjer, tj. .

Ako je predznak derivacije negativan, funkcija opada u smjeru ose, ako je pozitivan, u suprotnom smjeru:

Izračunajte u tački. U smjeru opadajuće funkcije čini se jedan korak, određuje se, a ako se kriterij poboljša, koraci se nastavljaju dok se ne pronađe minimalna vrijednost u odabranom smjeru. U ovom trenutku se ponovo određuju derivati ​​u odnosu na sve varijable, osim onih preko kojih se vrši spuštanje. Ponovo se pronalazi aksijalni smjer najbržeg pada, duž kojeg se poduzimaju daljnji koraci i tako dalje.

Ovaj postupak se ponavlja sve dok se ne postigne optimalna tačka, od koje nema daljeg smanjenja ni u jednom aksijalnom smjeru. U praksi, kriterijum za prekid pretrage je uslov

što pri prelazi u tačan uslov da su derivacije jednake nuli u tački ekstrema. Naravno, uslov (3.7) se može koristiti samo ako je optimum unutar dozvoljenog opsega nezavisnih varijabli. Ako, pak, optimum pada na granicu područja , tada je kriterij tipa (3.7) neprikladan, a umjesto njega treba primijeniti pozitivnost svih derivacija u odnosu na dopuštene aksijalne smjerove.

Algoritam spuštanja za odabrani aksijalni smjer može se zapisati kao

(3.8)

gdje je vrijednost varijable na svakom koraku spuštanja;

Vrijednost k + 1 korak, koja može varirati ovisno o broju koraka:

je funkcija predznaka z;

Vektor tačke u kojoj su izvode poslednji put izračunate;

Znak “+” u algoritmu (3.8) uzima se kada se traži max I, a znak “-” se uzima kada se traži min I. Što je manji korak h., to je veći broj proračuna na putu do optimalno. Ali ako je vrijednost h prevelika, blizu optimalne, može doći do petlje u procesu pretraživanja. Blizu optimuma, potrebno je da uslov h

Najjednostavniji algoritam za promjenu koraka h je sljedeći. Na početku spuštanja, korak se postavlja jednak, na primjer, 10% raspona d; mijenja se ovim korakom, spuštanje se vrši u odabranom smjeru dok se ne ispune uvjeti za sljedeća dva proračuna

Ako je uvjet prekršen u bilo kojem koraku, smjer spuštanja na osi je obrnut i spuštanje se nastavlja od posljednje točke sa veličinom koraka smanjenom za polovicu.

Formalna notacija ovog algoritma je sljedeća:

(3.9)

Kao rezultat korištenja takve strategije, spuštanje Sha će se smanjiti u području optimala u ovom smjeru, a pretraga u smjeru može se zaustaviti kada E postane manji.

Tada se pronalazi novi aksijalni smjer, početni korak za daljnje spuštanje, obično manji od onog koji se kretao duž prethodnog aksijalnog smjera. Priroda optimalnog kretanja u ovoj metodi prikazana je na slici 3.4.

Slika 3.5 - Putanja kretanja do optimuma u metodi relaksacije

Poboljšanje algoritma pretraživanja ovom metodom može se postići primjenom jednoparametarskih metoda optimizacije. U ovom slučaju može se predložiti šema za rješavanje problema:

Korak 1. - aksijalni smjer,

; , Ako ;

Korak 2 - novi aksijalni pravac;

metod gradijenta

Ova metoda koristi funkciju gradijenta. Funkcija gradijenta u tački naziva se vektor čije su projekcije na koordinatne ose parcijalni izvod funkcije u odnosu na koordinate (slika 6.5)

Slika 3.6 - Gradijent funkcije

.

Smjer gradijenta je smjer najbržeg porasta funkcije (najstrmiji “nagib” površine odziva). Smjer suprotan njemu (smjer antigradijenta) je smjer najbržeg pada (smjer najbržeg „spuštanja“ vrijednosti).

Projekcija gradijenta na ravan varijabli je okomita na tangentu na liniju nivoa, tj. gradijent je ortogonan na linije konstantnog nivoa ciljne funkcije (slika 3.6).

Slika 3.7 - Putanja kretanja do optimuma u metodi

gradijent

Za razliku od metode opuštanja, u metodi gradijenta koraci se poduzimaju u smjeru najbržeg smanjenja (porasta) funkcije .

Potraga za optimumom odvija se u dvije faze. U prvoj fazi se pronalaze vrijednosti parcijalnih izvoda u odnosu na sve varijable, koje određuju smjer gradijenta u tački koja se razmatra. U drugoj fazi se pravi korak u smjeru gradijenta kada se traži maksimum ili u suprotnom smjeru kada se traži minimum.

Ako je analitički izraz nepoznat, tada se smjer gradijenta određuje traženjem probnih kretanja na objektu. Neka početna tačka. Zadaje se povećanje, dok je . Definirajte prirast i izvod

Derivati ​​u odnosu na druge varijable određuju se slično. Nakon pronalaženja komponenti gradijenta, probni pokreti se zaustavljaju i počinju radni koraci u odabranom smjeru. Štoviše, veličina koraka je veća, što je veća apsolutna vrijednost vektora.

Kada se izvrši korak, vrijednosti svih nezavisnih varijabli se mijenjaju istovremeno. Svaki od njih dobija povećanje proporcionalno odgovarajućoj komponenti gradijenta

, (3.10)

ili u vektorskom obliku

, (3.11)

gdje je pozitivna konstanta;

“+” – kada se traži max I;

“-” – kada se traži min I.

U obrascu je primijenjen algoritam za pretraživanje gradijenta za normalizaciju gradijenta (podjela po modulu).

; (3.12)

(3.13)

Određuje količinu koraka u smjeru gradijenta.

Algoritam (3.10) ima prednost u tome što se pri približavanju optimalu dužina koraka automatski smanjuje. A sa algoritmom (3.12), strategija promjene se može izgraditi bez obzira na apsolutnu vrijednost koeficijenta.

U metodi gradijenta svaki se dijeli na jedan radni korak, nakon čega se derivacije ponovo izračunavaju, određuje se novi smjer gradijenta i nastavlja se proces pretraživanja (slika 3.5).

Ako je veličina koraka odabrana premala, tada će kretanje do optimuma biti predugo zbog potrebe za izračunavanjem u previše tačaka. Ako je korak odabran prevelik, može doći do petlje u području optimala.

Proces pretraživanja se nastavlja sve dok , , ne postane blizu nule ili dok se ne dostigne granica područja za podešavanje varijable.

U algoritmu sa automatskim preciziranjem koraka, vrijednost se rafinira tako da se promjena smjera gradijenta u susjednim tačkama i

Kriterijumi za završetak potrage za optimumom:

; (3.16)

; (3.17)

Gdje je norma vektora.

Pretraga se završava kada se ispuni jedan od uslova (3.14) - (3.17).

Nedostatak pretraživanja gradijenta (kao i metoda o kojima smo gore govorili) je u tome što se prilikom njegove upotrebe može pronaći samo lokalni ekstremum funkcije. Da biste pronašli druge lokalne ekstreme, potrebno je tražiti od drugih polaznih tačaka.