Gradient Descent. Metoda gradijenta prvog reda

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

Postoji razne načine odabir koraka, od kojih svaki specificira određenu opciju metod 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, sada se zove metoda najstrmiji spust.

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 algebarske jednačine sa simetričnim pozitivnim određenim matricama.

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 minimum i maksimum svojstvene 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. AT opšti slučaj, ako je funkcija koja se minimizira strogo konveksna i ima minimalnu tačku x, tada također, 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 su i minimum i maksimum sopstvene vrijednosti Hesove matrice

Napomena 2. Za kvadrat ciljna funkcija(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.

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-Fulfova 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. Različite modifikacije metode gradijenta 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:

šta 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.

Metoda gradijentnog spuštanja.

Smjer najstrmijeg spuštanja odgovara smjeru najvećeg pada funkcije. Poznato je da je smjer najvećeg porasta funkcije dvije varijable u = f(x, y) karakteriziran svojim gradijentom:

gdje su e1, e2 jedinični vektori (orths) u smjeru koordinatnih osa. Stoga će smjer suprotan gradijentu ukazati na smjer najvećeg smanjenja funkcije. Pozivaju se metode zasnovane na odabiru putanje optimizacije pomoću gradijenta gradijent.

Ideja koja stoji iza metode gradijentnog spuštanja je sljedeća. Biranje neke početne tačke

izračunavamo gradijent razmatrane funkcije u njemu. Napravimo korak u smjeru suprotnom od gradijenta:

Proces se nastavlja sve dok se ne dobije najmanja vrijednost ciljne funkcije. Strogo govoreći, kraj pretraživanja će doći kada pomicanje od dobivene točke bilo kojim korakom dovede do povećanja vrijednosti ciljne funkcije. Ako je minimum funkcije dostignut unutar razmatranog područja, tada je u ovom trenutku gradijent jednak nuli, što može poslužiti i kao signal o završetku procesa optimizacije.

Metoda gradijentnog spuštanja ima isti nedostatak kao i metoda koordinatnog spuštanja: u prisustvu jaruga na površini, konvergencija metode je vrlo spora.

U opisanoj metodi potrebno je izračunati gradijent funkcije cilja f(x) u svakom koraku optimizacije:

Formule za parcijalne izvode mogu se dobiti eksplicitno samo kada je ciljna funkcija data analitički. Inače, ovi derivati ​​se izračunavaju pomoću numeričke diferencijacije:

Kada se koristi gradijentni silazak u optimizacijskim problemima, glavna količina proračuna obično pada na izračunavanje gradijenta ciljne funkcije u svakoj tački putanje spuštanja. Stoga je preporučljivo smanjiti broj takvih točaka bez ugrožavanja samog rješenja. To se postiže nekim metodama koje su modifikacije gradijentnog spuštanja. Jedna od njih je metoda najstrmijeg spuštanja. Prema ovoj metodi, nakon određivanja smjera suprotnog gradijentu ciljne funkcije u početnoj tački, rješava se jednodimenzionalni problem optimizacije minimiziranjem funkcije duž ovog smjera. Naime, funkcija je minimizirana:

Da minimiziram može se koristiti jedna od jednodimenzionalnih metoda optimizacije. Također je moguće jednostavno kretati se u smjeru suprotnom od gradijenta, ne čineći jedan korak, već nekoliko koraka dok funkcija cilja ne prestane da se smanjuje. U pronađenoj novoj tački ponovo se određuje smjer spuštanja (pomoću gradijenta) i traži se nova minimalna tačka funkcije cilja itd. Kod ove metode spuštanje se odvija u mnogo većim koracima, a gradijent funkcija se računa na manjem broju tačaka. Razlika je u tome što je ovdje smjer jednodimenzionalne optimizacije određen gradijentom ciljne funkcije, dok se koordinatni spust vrši na svakom koraku duž jednog od koordinatnih pravaca.

Metoda najstrmijeg spuštanja za slučaj funkcije dvije varijable z = f(x,y).

Prvo, lako je pokazati da je gradijent funkcije okomit na tangentu na liniju nivoa u datoj tački. Stoga, u metodama gradijenta, spuštanje se dešava duž normale na liniju nivoa. Drugo, u tački u kojoj je dostignut minimum ciljne funkcije duž pravca, derivacija funkcije duž ovog pravca nestaje. Ali derivacija funkcije je nula u smjeru tangente na liniju nivoa. Iz toga slijedi da je gradijent funkcije cilja u novoj tački okomit na smjer jednodimenzionalne optimizacije u prethodnom koraku, odnosno spuštanje u dva uzastopna koraka se vrši u međusobno okomitim smjerovima.

Metoda se zasniva na sljedećoj iterativnoj modifikaciji formule

x k +1 = x k + a k s(x k),

x k+1 = x k - a k Ñ f(x k), gdje je

a - dati pozitivan koeficijent;

Ñ ​​f(x k) - gradijent funkcije cilja prvog reda.

Nedostaci:

potreba za odabirom odgovarajuće vrijednosti ;

spora konvergencija do tačke minimuma zbog male f(x k) u blizini ove tačke.

Metoda najstrmijeg spuštanja

Bez prvog nedostatka najjednostavnije metode gradijenta, budući da a k se izračunava rješavanjem problema minimizacije Ñ f(x k) duž pravca Ñ f(x k) korištenjem jedne od jednodimenzionalnih metoda optimizacije x k+1 = x k - a k Ñ f(x k).

Ova metoda se ponekad naziva i Cauchyjeva metoda.

Algoritam se odlikuje niskom stopom konvergencije u rješavanju praktičnih problema. Ovo se objašnjava činjenicom da promjena varijabli direktno ovisi o veličini gradijenta, koji teži nuli u blizini minimalne tačke, a mehanizma ubrzanja nema na posljednjim iteracijama. Stoga se, uzimajući u obzir stabilnost algoritma, metoda najstrmijeg spuštanja često koristi kao početni postupak za pronalaženje rješenja (iz tačaka koje se nalaze na značajnim udaljenostima od minimalne tačke).

Metoda konjugiranog smjera

Opšti problem nelinearnog programiranja bez ograničenja je sljedeći: minimizirati f(x), x E n , gdje je f(x) ciljna funkcija. Prilikom rješavanja ovog problema koristimo metode minimizacije koje vode do stacionarne točke f(x) definirane jednadžbom f(x *)=0. Metoda konjugiranog smjera odnosi se na neograničene metode minimizacije koje koriste derivate. Zadatak: minimizirati f(x), x E n , gdje je f(x) ciljna funkcija n nezavisnih varijabli. Važna karakteristika je brza konvergencija zbog činjenice da se pri odabiru smjera koristi Hessian matrica, koja opisuje područje topologije površine odgovora. Konkretno, ako je ciljna funkcija kvadratna, tada se minimalna točka može dobiti u najviše nekoliko koraka jednakih dimenziji problema.

Da bi se metoda primijenila u praksi, ona mora biti dopunjena procedurama za provjeru konvergencije i linearne nezavisnosti sistema pravca. Metode drugog reda

Newtonova metoda

Uzastopna primjena kvadratne aproksimacijske sheme dovodi do implementacije Newtonove optimizacijske metode prema formuli

x k +1 = x k - Ñ 2 f(x k -1) Ñ f(x k).

Nedostatak Newtonove metode je njena nedovoljna pouzdanost pri optimizaciji nekvadratnih ciljnih funkcija. Stoga se često modificira:

x k +1 = x k - a k Ñ 2 f(x k -1) Ñ f(x k), gdje je

a k je parametar odabran tako da je f(x k+1) min.

2. Pronalaženje ekstrema funkcije bez ograničenja

Neka funkcija f(x) data je na otvorenom intervalu (a, c) promjene argumenta x. Pretpostavljamo da exst postoji unutar ovog intervala (mora se reći da se, u opštem slučaju, to ne može matematički iskazati unaprijed; međutim, u tehničkim aplikacijama, prisustvo exst vrlo često unutar određenog intervala varijacije varijacije argumenta interval se može predvidjeti iz fizičkih razmatranja).

Definicija ekst. Funkcija f (x) data na intervalu (a, c) ima u tački x * max (min), ako ova tačka može biti okružena takvim intervalom (x * -ε, x * + ε) sadržanim u interval (a, c) , da za sve njegove tačke x koje pripadaju intervalu (x * -ε, x * +ε), vrijedi sljedeća nejednakost:

f(x) ≤ f(x *) → za maks

f(x) ≥ f(x *) → za min

Ova definicija ne nameće nikakva ograničenja za klasu funkcija f(x), što je, naravno, vrlo vrijedno.

Ako se za funkcije f(x) ograničimo na prilično uobičajenu, ali ipak užu klasu glatkih funkcija (pod glatkim funkcijama podrazumijevamo funkcije koje su kontinuirane zajedno sa svojim derivatima na intervalu promjene argumenta), tada možemo koristiti Fermatov teorem, koji daje potrebne uslove za postojanje ekst.

Fermatova teorema. Neka je funkcija f(x) definirana u nekom intervalu (a, b) iu tački "c" ovog intervala uzima najveću (najmanju) vrijednost. Ako postoji dvostrani konačni izvod u ovoj tački, tada je neophodno postojanje exst.

Bilješka. Dvostrani izvod karakteriše svojstvo, drugim rečima, poenta je da je u tački "c" derivacija u granici ista kada se tački "c" približava sa leve i desne strane, tj. f(x ) je glatka funkcija.

* U slučaju da postoji min, a kada →max. Konačno, ako je na x=x 0, onda upotreba 2. derivata ne pomaže i trebate koristiti, na primjer, definiciju exst.

Prilikom rješavanja Zadatka I vrlo često se koriste potrebni uslovi exst (tj. Fermatova teorema).

Ako jednadžba exst ima realne korijene, tada su tačke koje odgovaraju ovim korijenima sumnjive za exst (ali ne nužno i sami ekstremi, jer se radi o potrebnim, a ne o potrebnim i dovoljnim uslovima). Tako, na primjer, u tački pregiba X p se odvija, međutim, kao što znate, ovo nije ekstrem.

Napomenimo i to:

iz potrebnih uslova nemoguće je reći koji tip ekstremuma je pronađen max ili min: potrebne su dodatne studije da se to utvrdi;

nemoguće je iz potrebnih uslova utvrditi da li se radi o globalnom ili lokalnom ekstremumu.

Stoga, kada se pronađu tačke sumnjive za exst, one se dodatno istražuju, na primjer, na osnovu definicije exst ili 2. derivacije.

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.