Pregled gradijentnih metoda u problemima matematičke optimizacije. Gradijentne metode

Gradijentne metode

Gradijentne metode neograničene optimizacije koriste samo prve izvode funkcije cilja i linearne su aproksimacijske metode u svakom koraku, tj. ciljna funkcija u svakom koraku zamijenjena je tangentnom hiperravninom na njezin graf u trenutnoj točki.

U k-toj fazi gradijentnih metoda prijelaz iz točke Xk u točku Xk+1 opisuje se relacijom:

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

Metode najstrmijeg spusta

Ovu je metodu prvi razmatrao i primijenio O. Cauchy u 18. stoljeću. Njegova ideja je jednostavna: gradijent ciljne funkcije f(X) u bilo kojoj točki je vektor u smjeru najvećeg porasta vrijednosti funkcije. Prema tome, antigradijent će biti usmjeren u smjeru najvećeg pada funkcije i to je smjer najvećeg pada. Antigradijent (i gradijent) je okomit na plohu razine f(X) u točki X. Ako uvedemo pravac u (1.2)

onda će to biti smjer najvećeg spuštanja u točki Xk.

Dobivamo formulu za prijelaz s Xk na Xk+1:

Antigradijent daje samo smjer spuštanja, ali ne i veličinu koraka. Općenito, jedna stepenica ne daje minimalni bod, pa se postupak spuštanja mora primijeniti nekoliko puta. U točki minimuma sve komponente gradijenta jednake su nuli.

Sve gradijentne metode koriste navedenu ideju i razlikuju se jedna od druge u tehničkim detaljima: izračun derivacija pomoću analitičke formule ili aproksimacije konačnih razlika; veličina koraka može biti konstantna, mijenjati se prema nekim pravilima ili biti odabrana nakon primjene jednodimenzionalnih metoda optimizacije u antigradijentnom smjeru itd. i tako dalje.

Nećemo ulaziti u detalje, jer... Metoda najstrmijeg spuštanja općenito se ne preporučuje kao ozbiljan postupak optimizacije.

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

Ali najvažnija stvar je vrlo spora konvergencija najvećeg spuštanja u općem slučaju. Poanta je da je spust “najbrži” u lokalnom smislu. Ako je hiperprostor pretraživanja jako izdužen ("jaruga"), tada je antigradijent usmjeren gotovo ortogonalno na dno "jaruge", tj. najbolji smjer za postizanje minimuma. U tom smislu, izravni prijevod engleskog izraza "steepest descent", tj. spuštanje uz najstrmiju padinu više odgovara stanju stvari nego izraz "najbrži", usvojen u specijaliziranoj literaturi na ruskom jeziku. Jedan izlaz u ovoj situaciji je korištenje informacija koje pružaju druge parcijalne derivacije. Drugi izlaz je promijeniti skale varijabli.

linearna aproksimacija gradijent izvoda

Fletcher-Reevesova metoda konjugiranog gradijenta

U metodi konjugiranog gradijenta konstruira se slijed smjerova pretraživanja, koji su linearne kombinacije trenutnog smjera najvećeg spusta i prethodnih smjerova pretraživanja, tj.

Štoviše, koeficijenti su odabrani tako da smjerovi pretraživanja budu konjugirani. Dokazano je da

a ovo je vrlo vrijedan rezultat koji vam omogućuje da izgradite brz i učinkovit optimizacijski algoritam.

Fletcher-Reevesov algoritam

1. U X0 se računa.

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

• 3. f(Xk+1) i izračunavaju se.
• 4. Smjer se određuje iz odnosa:

• 5. Nakon (n+1)-te iteracije (tj. kada je k=n), ponovno se pokreće: pretpostavlja se X0=Xn+1 i provodi 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 računalnu memoriju, budući da ne treba matrice koje se koriste u Newtonovim metodama, ali je istovremeno gotovo jednako učinkovit kao kvazi-Newtonovi algoritmi. Jer smjerovi pretraživanja su međusobno konjugirani, tada će kvadratna funkcija biti minimizirana u najviše n koraka. U općem slučaju koristi se ponovno pokretanje, što vam omogućuje da dobijete rezultat.

Fletcher-Reevesov algoritam osjetljiv je na preciznost jednodimenzionalnog pretraživanja, pa se mora koristiti za eliminiranje svih pogrešaka zaokruživanja koje se mogu pojaviti. Osim toga, algoritam može zakazati u situacijama kada Hessian postane loše uvjetovan. Algoritam ne jamči konvergenciju uvijek i svugdje, iako praksa pokazuje da algoritam gotovo uvijek daje rezultate.

Newtonove metode

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

gdje je Hessian matrica.

Minimum desne strane (ako postoji) postiže se na istom mjestu kao i minimum kvadratne forme. Zapišimo formulu za određivanje smjera pretraživanja:

Minimum se postiže na

Optimizacijski algoritam u kojem se smjer pretraživanja određuje iz ovog odnosa naziva se Newtonova metoda, a smjer se naziva Newtonov smjer.

U problemima nalaženja minimuma proizvoljne kvadratne funkcije s pozitivnom matricom drugih derivacija, Newtonova metoda daje rješenje u jednoj iteraciji, neovisno o izboru polazišta.

Klasifikacija Newtonovih metoda

Sama Newtonova metoda sastoji se od jedne primjene Newtonovog smjera za optimizaciju kvadratne funkcije. Ako funkcija nije kvadratna, vrijedi sljedeći teorem.

Teorem 1.4. Ako je Hessova matrica nelinearne funkcije f općeg oblika u minimalnoj točki X* pozitivno određena, početna točka je odabrana dovoljno blizu X* i duljine koraka su ispravno odabrane, tada Newtonova metoda konvergira na X* s kvadratnom stopa.

Newtonova metoda se smatra referentnom metodom, s njom se uspoređuju svi razvijeni optimizacijski postupci. Međutim, Newtonova metoda je učinkovita samo za pozitivno određenu i dobro uvjetovanu Hessovu matricu (njezina determinanta mora biti znatno veća od nule, točnije, omjer najveće i najmanje svojstvene vrijednosti mora biti blizak jedinici). Da bi se prevladao ovaj nedostatak, koriste se modificirane Newtonove metode koje koriste Newtonove smjerove kad god je to moguće i odstupaju od njih samo kada je to potrebno.

Općenito načelo modifikacija Newtonove metode je sljedeće: pri svakoj iteraciji prvo se konstruira određena pozitivno definitivna matrica "pridružena" a zatim se izračunava pomoću formule

Budući da je pozitivno određen, tada - će nužno biti smjer spuštanja. Postupak konstrukcije organiziran je tako da se poklapa s Hessian-ovom matricom ako je pozitivno određena. Ovi se postupci temelje na određenim dekompozicijama matrice.

Druga skupina metoda, praktički ne inferiorna u brzini od Newtonove metode, temelji se na aproksimaciji Hessove matrice pomoću konačnih razlika, jer Za optimizaciju nije potrebno koristiti točne vrijednosti izvedenica. Ove metode su korisne kada je analitički izračun izvedenica težak ili jednostavno nemoguć. Takve se metode nazivaju diskretne Newtonove metode.

Ključ učinkovitosti Newtonovih metoda je uzimanje u obzir informacija o zakrivljenosti minimizirane funkcije, sadržane u Hessovoj matrici i omogućavanje konstrukcije lokalno točnih kvadratnih modela ciljne funkcije. Ali moguće je prikupiti i akumulirati informacije o zakrivljenosti funkcije na temelju promatranja promjene u gradijentu tijekom ponavljanja spuštanja.

Odgovarajuće metode, koje se temelje na mogućnosti aproksimacije zakrivljenosti nelinearne funkcije bez eksplicitnog formiranja njezine Hessove matrice, nazivaju se kvazi-Newtonove metode.

Imajte na umu da je prilikom konstruiranja postupka optimizacije Newtonovog tipa (uključujući kvazi-Newtonov) potrebno uzeti u obzir mogućnost pojave sedlaste točke. U tom će slučaju vektor najboljeg smjera pretraživanja uvijek biti usmjeren prema sedloj točki, umjesto da se udaljava od nje prema dolje.

Newton-Raphsonova metoda

Ova se metoda sastoji od opetovanog korištenja Newtonovog smjera pri optimizaciji funkcija koje nisu kvadratne.

Osnovna iterativna formula za višedimenzionalnu optimizaciju

koristi se u ovoj metodi pri izboru smjera optimizacije iz relacije

Stvarna duljina koraka skrivena je u nenormaliziranom Newtonovom smjeru.

Budući da ova metoda ne zahtijeva vrijednost funkcije cilja u trenutnoj točki, ponekad se naziva indirektna ili analitička optimizacijska metoda. Njegova sposobnost određivanja minimuma kvadratne funkcije u jednom izračunu izgleda iznimno privlačno na prvi pogled. Međutim, taj "jedinstveni izračun" zahtijeva značajne troškove. Prije svega, potrebno je izračunati n parcijalnih derivacija prvog reda i n(n+1)/2 - drugog reda. Osim toga, Hessian matrica mora biti obrnuta. To zahtijeva oko n3 računskih operacija. Uz isti trošak, metode konjugiranog smjera ili metode konjugiranog gradijenta mogu trajati oko n koraka, tj. postići gotovo isti rezultat. Dakle, iteracija Newton-Raphsonove metode ne daje prednosti u slučaju kvadratne funkcije.

Ako funkcija nije kvadratna, onda

• - početni smjer, općenito govoreći, više ne označava stvarnu minimalnu točku, što znači da se iteracije moraju ponavljati nekoliko puta;
• - korak jedinične duljine može dovesti do točke s lošijom vrijednošću funkcije cilja, a pretraga može dati krivi smjer ako npr. Hessian nije pozitivno određen;
• - Hessian može postati loše uvjetovan, čineći ga nemogućim invertirati, tj. određivanje smjera za sljedeću iteraciju.

Sama strategija ne razlikuje kojoj stacionarnoj točki (minimum, maksimum, sedlasta točka) se pretraga približava, a izračuni vrijednosti funkcije cilja, pomoću kojih bi se moglo pratiti raste li funkcija, nisu napravljeni. To znači da sve ovisi o tome koja je stacionarna točka početna točka potrage u zoni atrakcije. Newton-Raphsonova strategija rijetko se koristi sama za sebe bez modifikacije ove ili one vrste.

Pearsonove metode

Pearson je predložio nekoliko metoda koje aproksimiraju inverzni Hessian bez eksplicitnog izračunavanja druge derivacije, tj. promatranjem promjena smjera antigradijenta. U tom slučaju dobivaju se konjugirani pravci. Ovi se algoritmi razlikuju samo u detaljima. Predstavljamo one koji se najviše koriste u primijenjenim područjima.

Pearsonov algoritam br. 2.

U ovom algoritmu, inverzni Hessian se aproksimira matricom Hk, izračunatom u svakom koraku pomoću formule

Kao početna matrica H0 odabrana je proizvoljna pozitivno određena 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đene i nepozitivno određene, dok je determinanta matrice blizu nule. Da bi se izbjegla ova situacija, potrebno je redefinirati matricu svakih n koraka, izjednačavajući je s H0.

Pearsonov algoritam br. 3.

U ovom algoritmu matrica Hk+1 određena je iz formule

Hk+1 = Hk +

Putanja spuštanja koju generira algoritam slična je ponašanju algoritma Davidon-Fletcher-Powell, ali su koraci nešto kraći. Pearson je također predložio varijaciju ovog algoritma s cikličkim resetiranjem matrice.

Projektivni Newton-Raphsonov algoritam

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

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

Kada je k višekratnik broja neovisnih varijabli n, matrica Hk zamijenjena je matricom Rk+1, izračunatom kao zbroj

Veličina Hk(f(Xk+1) - f(Xk)) je projekcija vektora prirasta gradijenta (f(Xk+1) - f(Xk)), ortogonalna svim vektorima prirasta gradijenta u prethodnim koracima. Nakon svakih n koraka, Rk je aproksimacija inverznog Hessian H-1(Xk), tako da se zapravo izvodi (približno) Newtonovo pretraživanje.

Davidon-Fletcher-Powell metoda

Ova metoda ima i druga imena - metoda varijabilne metrike, kvazi-Newtonova metoda, jer on koristi oba ova pristupa.

Metoda Davidon-Fletcher-Powell (DFP) temelji se na korištenju Newtonovih pravaca, ali ne zahtijeva izračun inverznog Hessana u svakom koraku.

Smjer traženja u koraku k je smjer

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

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

3. Jednodimenzionalno pretraživanje (obično kubična interpolacija) duž pravca određuje k, što minimizira funkciju.

4. Oslanja se.

5. Oslanja se.

6. Odlučan je. Ako su Vk ili dovoljno mali, postupak završava.

• 7. Pretpostavlja se da je 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 pogreška u proračunu gradijenta mala i matrica Hk ne postaje loše uvjetovana.

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

U slučaju kvadratne funkcije

oni. DFP algoritam koristi konjugirane upute.

Dakle, DFT metoda koristi i ideje Newtonovog pristupa i svojstva konjugiranih pravaca, a kada minimizira kvadratnu funkciju, konvergira u ne više od n iteracija. Ako optimizirana funkcija ima oblik blizak kvadratnoj funkciji, tada je DFT metoda učinkovita zbog svoje dobre aproksimacije G-1 (Newtonova metoda). Ako funkcija cilja ima opći oblik, tada je DFT metoda učinkovita zbog korištenja konjugiranih pravaca.

Gradijentne metode optimizacije

Optimizacijski problemi s nelinearnim ili teškim za izračunavanje odnosima koji definiraju optimizacijske kriterije i ograničenja predmet su nelinearnog programiranja. Rješenja problema nelinearnog programiranja u pravilu se mogu pronaći samo numeričkim metodama pomoću računalne tehnologije. Među njima se najčešće koriste gradijentne metode (metode opuštanja, gradijenta, najvećeg spusta i uspona), bezgradijentne metode determinističkog pretraživanja (metode skeniranja, simpleks i dr.) te metode slučajnog pretraživanja. Sve ove metode koriste se u numeričkom određivanju optimuma i naširoko su obrađene u stručnoj literaturi.

Općenito, vrijednost kriterija optimizacije R može se smatrati funkcijom R(x b xx..., x n), definiran u n-dimenzionalnom prostoru. Budući da ne postoji vizualni grafički prikaz n-dimenzionalnog prostora, koristit ćemo se slučajem dvodimenzionalnog prostora.

Ako R(l b x 2) kontinuirano u regiji D, zatim oko optimalne točke M°(xi°, x g °) moguće je u zadanoj ravnini nacrtati zatvorenu liniju duž koje vrijednost R= konst. Mnoge takve linije, koje se nazivaju linijama jednakih razina, mogu se nacrtati oko optimalne točke (ovisno o koraku

Među metodama koje se koriste za rješavanje problema nelinearnog programiranja značajno mjesto zauzimaju metode za pronalaženje rješenja temeljene na analizi derivacije s obzirom na smjer funkcije koja se optimizira. Ako u svakoj točki prostora skalarna funkcija više varijabli poprima točno definirane vrijednosti, tada se u ovom slučaju radi o skalarnom polju (polje temperature, polje tlaka, polje gustoće itd.). Na sličan način definirano je i vektorsko polje (polje sila, brzina i sl.). Izoterme, izobare, izokrone itd. - sve su to linije (plohe) jednakih razina, jednakih vrijednosti funkcije (temperatura, tlak, volumen itd.). Budući da se vrijednost funkcije mijenja od točke do točke u prostoru, potrebno je odrediti brzinu promjene funkcije u prostoru, odnosno derivaciju po smjeru.

Koncept gradijenta naširoko se koristi u inženjerskim proračunima pri pronalaženju ekstrema nelinearnih funkcija. Gradijentne metode su numeričke metode pretraživanja. Univerzalni su i posebno učinkoviti u slučajevima traženja ekstrema nelinearnih funkcija s ograničenjima, kao i kada je analitička funkcija potpuno nepoznata. Bit ovih metoda je odrediti vrijednosti varijabli koje daju ekstrem funkcije cilja pomicanjem duž gradijenta (prilikom pretraživanja max) ili u suprotnom smjeru (min). Razne gradijentne metode razlikuju se jedna od druge po načinu na koji određuju kretanje prema optimumu. Zaključak je da ako linije jednakih razina R(xu x i) grafički okarakterizirati ovisnost R(x\jc?), tada se traženje optimalne točke može vršiti na različite načine. Na primjer, nacrtajte mrežu na ravnini x\, xr označavajući vrijednosti R u čvorovima mreže (slika 2.13).

Tada možete odabrati ekstremnu vrijednost iz vrijednosti čvora. Ovaj put nije racionalan, povezan je s velikim brojem izračuna, a točnost je niska jer ovisi o koraku, a optimum može biti između čvorova.

Numeričke metode

Matematički modeli sadrže odnose sastavljene na temelju teorijske analize procesa koji se proučavaju ili dobiveni kao rezultat eksperimenata obrade (podatkovne tablice, grafikoni). U svakom slučaju, matematički model samo približno opisuje stvarni proces. Stoga je pitanje točnosti i primjerenosti modela najvažnije. Potreba za aproksimacijama javlja se i kod samog rješavanja jednadžbi. Do nedavno, modeli koji sadrže nelinearne diferencijalne jednadžbe ili parcijalne diferencijalne jednadžbe nisu se mogli riješiti analitičkim metodama. Isto vrijedi i za brojne klase nebeskih integrala. Međutim, razvojem metoda numeričke analize omogućeno je beskrajno širenje granica mogućnosti analize matematičkih modela, a posebno je to postalo moguće korištenjem računala.

Numeričke metode koriste se za aproksimaciju funkcija, rješavanje diferencijalnih jednadžbi i njihovih sustava, integraciju i diferenciranje te izračunavanje numeričkih izraza.

Funkcija se može odrediti analitički, kao tablica ili kao grafikon. Pri izvođenju istraživanja čest zadatak je aproksimacija funkcije analitičkim izrazom koji zadovoljava navedene uvjete. Ovo rješava četiri problema:

Odabir čvornih točaka, provođenje eksperimenata na određenim vrijednostima (razinama) nezavisnih varijabli (ako je korak promjene faktora pogrešno odabran, ili ćemo "promašiti" karakterističnu značajku procesa koji se proučava ili ćemo produžiti postupak i povećati složenost traženja uzorka);

Izbor aproksimirajućih funkcija u obliku polinoma, empirijskih formula, ovisno o sadržaju konkretnog problema (treba težiti što većem pojednostavljenju aproksimirajućih funkcija);

Izbor i korištenje kriterija slaganja na temelju kojih se pronalaze parametri aproksimirajućih funkcija;

Ispunjavanje zahtjeva zadane točnosti za odabir aproksimacijske funkcije.

U problemima aproksimacije funkcija polinomima koriste se tri klase

Linearna kombinacija potencijskih funkcija (Taylorov red, Lagrangeov, Newtonov polinom itd.);

Kombinacija funkcija soz ph, w njima(Fourierov red);

Polinom formiran od funkcija eksp(-a, d).

Pri pronalaženju aproksimirajuće funkcije koriste se različiti kriteriji slaganja s eksperimentalnim podacima.

Kod optimizacije gradijentnom metodom, optimum promatranog objekta traži se u smjeru najbržeg porasta (smanjenja) izlazne varijable, tj. u smjeru gradijenta. Ali prije nego što napravite korak prema gradijentu, morate ga izračunati. Gradijent se može izračunati pomoću postojećeg modela

modeliranje polinoma dinamičkog gradijenta

gdje je parcijalna derivacija u odnosu na i-ti faktor;

i, j, k - jedinični vektori u smjeru koordinatnih osi faktorskog prostora, odnosno prema rezultatima n probnih pomaka u smjeru koordinatnih osi.

Ako matematički model statističkog procesa ima oblik linearnog polinoma, čiji su regresijski koeficijenti b i parcijalne derivacije proširenja funkcije y = f(X) u Taylorov niz po potencijama x i , tada je optimum tražena u smjeru gradijenta s određenim korakom h i:

pkfv n(H)= i 1 r 1 +i 2 r 2 +…+i t r t

Smjer se prilagođava nakon svakog koraka.

Gradijentna metoda, zajedno sa svojim brojnim modifikacijama, uobičajena je i učinkovita metoda za traženje optimuma proučavanih objekata. Razmotrimo jednu od modifikacija metode gradijenta - metodu strmog uspona.

Metoda strmog uspona, ili inače Box-Wilsonova metoda, kombinira prednosti triju metoda - Gauss-Seidelove metode, gradijentne metode i metode punih (ili frakcijskih) faktorskih eksperimenata, kao način dobivanja linearnog matematičkog modela. . Zadaća metode strmog uspona je izvršiti postupno kretanje u smjeru najbržeg porasta (ili smanjenja) izlazne varijable, odnosno duž grad y(X). Za razliku od metode gradijenta, smjer se ne prilagođava nakon svakog sljedećeg koraka, već kada se dosegne određeni ekstrem ciljne funkcije u nekoj točki u zadanom smjeru, kao što je to učinjeno u Gauss-Seidel metodi. U točki određenog ekstrema provodi se novi faktorski eksperiment, utvrđuje se matematički model i ponovno se izvodi strmi uspon. U procesu kretanja prema optimumu navedenom metodom redovito se provodi statistička analiza međurezultata pretraživanja. Pretraživanje se zaustavlja kada kvadratni efekti u regresijskoj jednadžbi postanu značajni. To znači da je postignuto optimalno područje.

Opišimo princip korištenja gradijentnih metoda na primjeru funkcije dviju varijabli

uz dva dodatna uvjeta:

Ovo se načelo (bez modifikacije) može primijeniti na bilo koji broj varijabli, kao i na dodatne uvjete. Promotrimo ravninu x 1 , x 2 (slika 1). Prema formuli (8), svaka točka odgovara određenoj vrijednosti F. Na slici 1, pravci F = const koji pripadaju ovoj ravnini prikazani su zatvorenim krivuljama koje okružuju točku M * u kojoj je F minimalna. Neka u početnom trenutku vrijednosti x 1 i x 2 odgovaraju točki M 0 . Ciklus izračuna počinje nizom probnih koraka. Prvo, vrijednost x 1 dobiva mali prirast; u ovom trenutku vrijednost x 2 je nepromijenjena. Zatim se određuje rezultirajući prirast u vrijednosti F, koji se može smatrati proporcionalnim vrijednosti parcijalnog izvoda

(ako je vrijednost uvijek ista).

Definicija parcijalnih derivacija (10) i (11) znači da je pronađen vektor s koordinatama i koji se naziva gradijent vrijednosti F i označava se na sljedeći način:

Poznato je da se smjer ovog vektora poklapa sa smjerom najvećeg porasta vrijednosti F. Suprotan smjer je "najoštriji pad", drugim riječima, najstrmiji pad vrijednosti F.

Nakon pronalaženja komponenti gradijenta, probni pokreti se zaustavljaju i radni koraci se izvode u smjeru suprotnom od smjera gradijenta, a što je veća apsolutna vrijednost vektora grad F, to je veća veličina koraka. Ovi uvjeti zadovoljeni su ako su vrijednosti radnih koraka proporcionalne prethodno dobivenim vrijednostima parcijalnih derivacija:

gdje je b pozitivna konstanta.

Nakon svakog radnog koraka procjenjuje se prirast vrijednosti F. Ako se pokaže da je negativan, tada se kretanje događa u pravom smjeru i trebate se pomaknuti dalje u istom smjeru M 0 M 1. Ako u točki M 1 rezultat mjerenja to pokaže, radna gibanja prestaju i započinje nova serija probnih gibanja. U tom slučaju se gradijent gradF određuje u novoj točki M 1, zatim se radni pokret nastavlja po novonađenom smjeru najvećeg spuštanja, odnosno po liniji M 1 M 2 itd. Ova metoda se naziva metoda najstrmijeg spusta/najstrmijeg uspona.

Kada je sustav blizu minimuma, što je naznačeno malom vrijednošću od

dolazi do prijelaza na "oprezniju" metodu pretraživanja, takozvanu gradijentnu metodu. Razlikuje se od metode najstrmijeg spuštanja po tome što se nakon određivanja gradijenta gradF radi samo jedan radni korak, a zatim ponovno počinje niz probnih kretanja na novoj točki. Ova metoda pretraživanja omogućuje točnije određivanje minimuma u usporedbi s metodom najvećeg spuštanja, dok potonja omogućuje brzo približavanje minimumu. Ako tijekom traženja točka M dođe do granice dopustivog područja i barem jedna od veličina M 1, M 2 promijeni predznak, metoda se mijenja i točka M se počinje kretati duž granice područja.

Učinkovitost metode strmog uspona ovisi o izboru skale varijabli i vrsti odzivne površine. Površina sa sfernim konturama osigurava brzo stezanje do optimalnog.

Nedostaci metode strmog uspona uključuju:

1. Ograničenja ekstrapolacije. Krećući se duž gradijenta, oslanjamo se na ekstrapolaciju parcijalnih derivacija funkcije cilja s obzirom na odgovarajuće varijable. Međutim, oblik odzivne površine može se promijeniti i mora se promijeniti smjer traženja. Drugim riječima, kretanje u ravnini ne može biti kontinuirano.

2. Poteškoće u pronalaženju globalnog optimuma. Metoda je primjenjiva za pronalaženje samo lokalnih optimuma.

Vektor gradijenta je usmjeren u smjeru najbržeg porasta funkcije u danoj točki. Vektor nasuprot gradijentu -grad(/(x)) naziva se antigradijent i usmjeren je u smjeru najbržeg opadanja funkcije. U točki minimuma, gradijent funkcije je nula. Metode prvog reda, koje se nazivaju i gradijentne metode, temelje se na svojstvima gradijenata. Ako nema dodatnih informacija, tada je od početne točke x (0 > bolje ići do točke x (1) koja leži u smjeru antigradijenta - najbrži pad funkcije. Odabir antigradijenta -grad(/( x (^)) u točki kao smjer spuštanja x(k dobivamo iterativni proces forme

U koordinatnom obliku ovaj proces je zapisan na sljedeći način:

Kao kriterij za zaustavljanje iterativnog procesa možete koristiti ili uvjet (10.2) ili ispunjenje uvjeta malog gradijenta

Moguć je i kombinirani kriterij koji se sastoji u istovremenom ispunjavanju navedenih uvjeta.

Metode gradijenta razlikuju se jedna od druge po načinu odabira veličine koraka A Kod metode s konstantnim korakom za sve iteracije bira se određena konstantna vrijednost koraka. Sasvim mali korak a^ osigurava smanjenje funkcije, tj. ispunjenje nejednakosti

Međutim, to može dovesti do potrebe za provođenjem prilično velikog broja ponavljanja kako bi se dosegla minimalna točka. S druge strane, preveliki korak može uzrokovati rast funkcije ili dovesti do fluktuacija oko minimalne točke. Za odabir veličine koraka potrebni su dodatni podaci, pa se metode s konstantnim koracima rijetko koriste u praksi.

Pouzdanije i ekonomičnije (u smislu broja iteracija) su gradijentne metode s promjenjivim koracima, kod kojih se veličina koraka na neki način mijenja ovisno o dobivenoj aproksimaciji. Kao primjer takve metode, razmotrite metodu najstrmijeg spuštanja. U ovoj metodi, pri svakoj iteraciji, veličina koraka i* odabire se iz uvjeta minimuma funkcije f(x) u smjeru spuštanja, tj.

Ovaj uvjet znači da se kretanje duž antigradijenta događa sve dok vrijednost funkcije /(x) opada. Stoga je u svakoj iteraciji potrebno riješiti problem jednodimenzionalne minimizacije s obzirom na φ funkcije φ(τ) =/(x(/r) - - agrad^x^))). Algoritam metode najvećeg spuštanja je sljedeći.

• 1. Postavimo koordinate početne točke x^° i točnost približnog rješenja r. Postavimo k = 0.
• 2. U točki x (/r) izračunavamo vrijednost gradijenta grad(/(x (^)).
• 3. Odredite veličinu koraka a^ jednodimenzionalnom minimizacijom funkcije cp(i) u odnosu na i.
• 4. Odredimo novu aproksimaciju minimalne točke x (* +1 > pomoću formule (10.4).
• 5. Provjerimo uvjete za zaustavljanje iterativnog procesa. Ako su ispunjeni, tada se obračuni zaustavljaju. Inače pretpostavljamo k k+ 1 i idite na korak 2.

U metodi najstrmijeg spuštanja, smjer kretanja iz točke x (*) dodiruje liniju razine u točki x (* +1). Staza spuštanja je cik-cak, a susjedne cik-cak karike su ortogonalne jedna na drugu. Doista, korak a^ odabire se minimiziranjem za A funkcije ( A). Preduvjet

minimum funkcije - = 0. Izračunavši derivaciju

kompleksne funkcije, dobivamo uvjet ortogonalnosti vektora pravaca spuštanja u susjednim točkama:

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

Metode gradijenta konvergiraju na minimum pri stopi geometrijske progresije za glatke konveksne funkcije. Takve funkcije imaju najveću i najmanju svojstvenu vrijednost matrice drugih derivacija (Hessian matrica)

međusobno se malo razlikuju, tj. matrica H(x) je dobro uvjetovana. Međutim, u praksi funkcije koje se minimiziraju često imaju loše uvjetovane matrice drugih izvodnica. Vrijednosti takvih funkcija mijenjaju se puno brže u nekim smjerovima nego u drugim smjerovima. Stopa konvergencije gradijentnih metoda također značajno ovisi o točnosti izračuna gradijenata. Gubitak preciznosti, koji se obično događa u blizini minimalnih točaka, općenito može poremetiti konvergenciju procesa spuštanja gradijenta. Stoga se metode gradijenta često koriste u kombinaciji s drugim, učinkovitijim metodama u početnoj fazi rješavanja problema. U ovom slučaju, točka x (0) je daleko od točke minimuma, a koraci u smjeru antigradijenta omogućuju postizanje značajnog smanjenja funkcije.

Ne postoje ograničenja u problemu neograničene optimizacije.

Podsjetimo se da je gradijent višedimenzionalne funkcije vektor koji je analitički izražen geometrijskom sumom parcijalnih derivacija

Gradijent skalarne funkcije F(x) u nekoj točki je usmjerena u smjeru najbržeg porasta funkcije i okomita je na liniju razine (površinu konstantne vrijednosti F(x), prolazeći kroz točku x k). Vektor suprotan gradijentu  antigradijent  usmjeren je prema najbržem opadanju funkcije F(x). U ekstremnoj točki dipl F(x)= 0.

U gradijentnim metodama kretanje točke pri traženju minimuma funkcije cilja opisuje se iterativnom formulom

Gdje  k  parametar koraka k iteracija duž antigradijenta. Za uzlazne metode (traženje maksimuma), morate se kretati duž gradijenta.

Razne varijante gradijentnih metoda razlikuju se jedna od druge po načinu odabira parametra koraka, kao i uzimanju u obzir smjera kretanja u prethodnom koraku. Razmotrimo sljedeće opcije za metode gradijenta: s konstantnim korakom, s promjenjivim parametrom koraka (podjela koraka), metodu najstrmijeg spuštanja i metodu konjugiranog gradijenta.

Metoda s konstantnim parametrom koraka. U ovoj metodi, parametar koraka je konstantan u svakoj iteraciji. Postavlja se pitanje: kako praktično odabrati vrijednost parametra koraka? Dovoljno mali parametar koraka može rezultirati neprihvatljivo velikim brojem ponavljanja potrebnih za postizanje minimalne točke. S druge strane, prevelik parametar koraka može dovesti do prekoračenja minimalne točke i do oscilatornog računskog procesa oko te točke. Ove okolnosti su nedostaci metode. Budući da je nemoguće unaprijed pogoditi prihvatljivu vrijednost parametra koraka  k, tada postoji potreba za korištenjem metode gradijenta s promjenjivim parametrom koraka.

Kako se približavamo optimumu, vektor gradijenta opada u vrijednosti, težeći nuli, pa kada  k = const duljina koraka postupno se smanjuje. Blizu optimuma, duljina vektora gradijenta teži nuli. Duljina vektora ili norma in n-dimenzionalni euklidski prostor određen je formulom

, Gdje n- broj varijabli.

Opcije za zaustavljanje optimalnog procesa pretraživanja:

S praktičnog gledišta, prikladnije je koristiti 3. kriterij zaustavljanja (budući da su vrijednosti projektnih parametara od interesa), međutim, da biste odredili blizinu ekstremne točke, morate se usredotočiti na 2. kriterij. Za zaustavljanje procesa izračuna može se koristiti nekoliko kriterija.

Pogledajmo primjer. Nađite minimum funkcije cilja F(x) = (x 1  2) 2 + (x 2  4) 2 . Točno rješenje problema X*= (2,0;4,0). Izrazi za parcijalne derivacije

,
.

Odabir koraka  k = 0,1. Tražimo od početne točke x 1 = . Prikažimo rješenje u obliku tablice.

Gradijentna metoda s dijeljenjem parametra koraka. U tom slučaju, tijekom procesa optimizacije, parametar koraka  k se smanjuje ako se nakon sljedećeg koraka funkcija cilja povećava (prilikom traženja minimuma). U tom slučaju, duljina koraka često se dijeli (podijeli) na pola, a korak se ponavlja od prethodne točke. To omogućuje točniji pristup ekstremnoj točki.

Metoda najstrmijeg spusta. Metode varijabilnog koraka su ekonomičnije u smislu broja ponavljanja. Ako je optimalna duljina koraka  k duž smjera antigradijenta rješenje jednodimenzionalnog problema minimizacije, tada se ova metoda naziva metoda najstrmijeg spuštanja. U ovoj se metodi pri svakoj iteraciji rješava problem jednodimenzionalne minimizacije:

F(X k+1 )=F(X k   k S k )=min F( k ), S k =  F(X);

 k >0

.

U ovoj metodi kretanje u smjeru antigradijenta se nastavlja sve dok se ne postigne minimum funkcije cilja (dok se vrijednost funkcije cilja smanjuje). Na primjeru razmotrimo kako se funkcija cilja može analitički napisati u svakom koraku ovisno o nepoznatom parametru

Primjer. min F(x 1 , x 2 ) = 2x 1 2 + 4x 2 3 – 3. Zatim  F(x)= [ 4x 1 ; 12x 2 2 ]. Neka točka x k = , stoga  F(x)= [ 8; 12], F(x k   S k ) =

2(2  8 ) 2 + 4(1  12 ) 3  3. Potrebno je pronaći  koji daje minimum za ovu funkciju.

Algoritam za metodu najstrmijeg spuštanja (za pronalaženje minimuma)

Inicijalni korak. Neka je   zaustavna konstanta. Odaberite početnu točku x 1 , staviti k = 1 i prijeđite na glavni korak.

Osnovni korak. Ako || gradF(x)||< , zatim završite pretragu, inače odredite  F(x k ) i pronaći  k  optimalno rješenje problema minimizacije F(x k   k S k ) na  k  0. Staviti x k +1 = x k   k S k, dodijeliti k =

k + 1 i ponovite glavni korak.

Da biste pronašli minimum funkcije jedne varijable u metodi najvećeg spuštanja, možete koristiti metode unimodalne optimizacije. Iz velike skupine metoda razmotrit ćemo metodu dihotomije (bisekcije) i zlatnog reza. Bit unimodalnih optimizacijskih metoda je sužavanje raspona nesigurnosti u položaju ekstremuma.

Metoda dihotomije (polavljanja)Inicijalni korak. Odaberite konstantu razlikovanja  i konačnu duljinu intervala nesigurnosti l. Vrijednost  treba biti što manja, ali ipak omogućiti razlikovanje između vrijednosti funkcije F( ) I F( ) . Neka [ a 1 , b 1 ] - početni interval nesigurnosti. Staviti k =

Glavna faza sastoji se od konačnog broja ponavljanja istog tipa.

k-ta iteracija.

Korak 1. Ako b k  a k  l, tada se izračuni završavaju. Riješenje x * = (a k + b k )/2. Inače

,
.

Korak 2. Ako F( k ) < F( k ), staviti a k +1 = a k ; b k +1 =  k. Inače a k +1 =  k I b k +1 = b k. Dodijeliti k = k + 1 i idite na korak 1.

Metoda zlatnog reza. Učinkovitija metoda od metode dihotomije. Omogućuje dobivanje zadane vrijednosti intervala nesigurnosti u manje ponavljanja i zahtijeva manje izračuna funkcije cilja. U ovoj se metodi nova točka podjele intervala nesigurnosti izračunava jednom. Nova točka se postavlja na daljinu

 = 0,618034 od kraja intervala.

Algoritam metode zlatnog reza

Inicijalni korak. Odaberite dopuštenu konačnu duljinu intervala nesigurnosti l > 0. Neka [ a 1 , b 1 ] - početni interval nesigurnosti. Staviti  1 = a 1 +(1   )(b 1  a 1 ) I  1 = a 1 +  (b 1  a 1 ) , Gdje  = 0,618 . Izračunati F( 1 ) I F( 1 ) , staviti k = 1 i idite na glavnu pozornicu.

Korak 1. Ako b k  a k  l, tada se izračuni završavaju x * = (a k + b k )/ 2. Inače ako F( k ) > F( k ) , zatim idite na korak 2; Ako F( k )  F( k ) , idite na korak 3.

Korak 2. Staviti a k +1 =  k , b k +1 = b k ,  k +1 =  k ,  k +1 = a k +1 +  (b k +1 – a k +1 ). Izračunati F( k +1 ), idite na korak 4.

3. korak Staviti a k +1 = a k , b k +1 =  k ,  k +1 =  k ,  k +1 = a k +1 + (1   )(b k +1 – a k +1 ). Izračunati F( k +1 ).

Korak 4. Dodijeliti k = k + 1, prijeđite na korak 1.

U prvoj iteraciji potrebna su dva proračuna funkcije, u svim sljedećim samo jedan.

Metoda konjugiranog gradijenta (Fletcher-Reeves). U ovoj metodi, odabirom smjera kretanja na k+ Korak 1 uzima u obzir promjenu smjera na k korak. Vektor smjera spuštanja je linearna kombinacija antigradijentnog smjera i prethodnog smjera traženja. U ovom slučaju, kada se minimiziraju funkcije jaruge (s uskim dugim depresijama), traženje nije okomito na jarugu, već duž nje, što omogućuje brzo postizanje minimuma. Koordinate točke kada se traži ekstremum metodom konjugiranog gradijenta izračunavaju se pomoću izraza x k +1 = x k   V k +1 , Gdje V k +1 – vektor izračunat pomoću sljedećeg izraza:

.

Prvo ponavljanje obično se oslanja V = 0 i pretraživanje se izvodi duž antigradijenta, kao u metodi najvećeg spuštanja. Tada smjer kretanja odstupa od smjera antigradijenta, tim više, što se značajnije mijenja duljina vektora gradijenta u zadnjoj iteraciji. Nakon n Koraci za ispravljanje rada algoritma provode se uobičajenim korakom protiv gradijenta.

Algoritam metode konjugiranog gradijenta

Korak 1. Unesite početnu točku x 0 , točnost  , dimenzija n.

Korak 2. Staviti k = 1.

3. korak Stavite vektor V k = 0.

Korak 4. Izračunati dipl F(x k ).

Korak 5. Izračunaj vektor V k +1.

Korak 6. Izvršite jednodimenzionalno vektorsko pretraživanje V k +1.

Korak 7 Ako k < n, staviti k = k + 1 i idite na korak 4, inače idite na korak 8.

Korak 8 Ako je duljina vektora V manje od , završite pretragu, inače  idite na korak 2.

Metoda konjugiranih smjerova jedna je od najučinkovitijih u rješavanju problema minimizacije. Metoda se u kombinaciji s jednodimenzionalnim pretraživanjem često praktično koristi u CAD-u. Međutim, treba napomenuti da je osjetljiv na pogreške koje se javljaju tijekom procesa brojanja.

Nedostaci gradijentnih metoda

U zadacima s velikim brojem varijabli teško je ili nemoguće dobiti derivacije u obliku analitičkih funkcija.

Pri izračunavanju derivacija korištenjem diferencijskih shema, rezultirajuća pogreška, osobito u blizini ekstrema, ograničava mogućnosti takve aproksimacije.