Metoda najstrmejšega spusta v kemijski tehnologiji. Minimalna funkcija po metodi najstrmejšega spusta

Pri uporabi metode najstrmejšega spusta pri vsaki ponovitvi velikost koraka A k je izbran iz minimalnega pogoja funkcije f(x) v smeri sestopa, tj.

f(x[k] -a k f"(x[k])) = f(x[k] -af"(x[k])) .

Ta pogoj pomeni, da se gibanje po antigradientu dogaja tako dolgo, kot je vrednost funkcije f(x) zmanjša. Z matematičnega vidika je treba pri vsaki iteraciji rešiti problem enodimenzionalne minimizacije po A funkcije

j (a) = f(x[k]-af"(x[k])) .

Algoritem metode najstrmejšega spusta je naslednji.

1. Nastavite koordinate začetne točke X.
2. Na točki X[k], k = 0, 1, 2, ... izračuna vrednost gradienta f"(x[k]) .
3. Velikost koraka je določena a k, z enodimenzionalno minimizacijo nad A funkcije j (a) = f(x[k]-af"(x[k])).
4. Določene so koordinate točke X[k+ 1]:

X jaz [k+ 1]= x jaz [k] -A k f" jaz (X[k]), i = 1,..., str.

5. Preverijo se pogoji za zaustavitev steracijskega procesa. Če so izpolnjeni, se izračuni ustavijo. V nasprotnem primeru pojdite na 1. korak.

Pri obravnavani metodi je smer gibanja od točke X[k] se v točki dotakne nivojske črte x[k+ 1] (slika 2.9). Pot spuščanja je cik-cak, s sosednjimi cik-cak povezavami pravokotnimi druga na drugo. Res, korak a k je izbran z minimiziranjem z A funkcije? (a) = f(x[k] -af"(x[k])) . Nujen pogoj za minimum funkcije d j (a)/da = 0. Po izračunu odvoda kompleksne funkcije dobimo pogoj pravokotnosti vektorjev smeri spusta v sosednjih točkah:

d j (a)/da = -f"(x[k+ 1]f"(x[k]) = 0.

riž. 2.9.

Gradientne metode konvergirajo na minimum pri visoki hitrosti (hitrost geometrijske progresije) za gladke konveksne funkcije. Takšne funkcije imajo največje M in najmanj m lastne vrednosti matrike drugih odvodov (Hessova matrika)

se med seboj malo razlikujejo, tj N(x) dobro kondicionirano. Spomnimo se, da lastne vrednosti l i, jaz =1, …, n, so matrike korenine karakteristične enačbe

Vendar pa imajo v praksi funkcije, ki jih minimiziramo, praviloma slabo pogojene matrike drugih odvodov (t/m<< 1). Vrednosti takšnih funkcij v nekaterih smereh se spreminjajo veliko hitreje (včasih za več vrst velikosti) kot v drugih smereh. Njihove ravne površine so v najpreprostejšem primeru močno podolgovate (sl. 2.10), v bolj zapletenih primerih pa se upognejo in izgledajo kot grape. Funkcije s takimi lastnostmi imenujemo gully. Smer antigradienta teh funkcij (glej sliko 2.10) bistveno odstopa od smeri do minimalne točke, kar vodi do upočasnitve hitrosti konvergence.

riž. 2.10.

Stopnja konvergence gradientnih metod je pomembno odvisna tudi od natančnosti izračunov gradientov. Izguba natančnosti, ki se običajno pojavi v bližini minimalnih točk ali v razmerah žlebov, lahko na splošno moti konvergenco procesa gradientnega spuščanja. Zaradi zgoraj navedenih razlogov se gradientne metode pogosto uporabljajo v kombinaciji z drugimi, bolj učinkovitimi metodami v začetni fazi reševanja problema. V tem primeru bistvo X daleč od minimalne točke, koraki v smeri antigradienta pa omogočajo znatno zmanjšanje funkcije.

Namen storitve. Spletni kalkulator za iskanje minimalna funkcija metoda najstrmejšega spusta oz Cauchyjeva metoda(glej primer). Rešitev je sestavljena v Word formatu.

Pravila za vnos funkcije

IN metoda najstrmejšega spusta kot smer iskanja je izbran vektor, katerega smer je nasprotna smeri vektorja gradienta funkcije ▽f(x). Iz matematične analize je znano, da vektor grad f(x)=▽f(x) označuje smer najhitrejšega naraščanja funkcije (glej gradient funkcije). Zato se imenuje vektor - grad f (X) = -▽f(X). anti-gradient in je smer njenega najhitrejšega upadanja. Rekurenčna relacija, s katero se izvaja metoda najstrmejšega spusta, ima obliko X k +1 =X k - λ k ▽f(x k), k = 0,1,...,
kjer je λ k >0 velikost koraka. Glede na izbiro velikosti koraka lahko dobite različne možnosti za metodo gradienta. Če je med procesom optimizacije velikost koraka λ fiksna, se metoda imenuje gradientna metoda z diskretnim korakom. Proces optimizacije v prvih iteracijah lahko bistveno pospešimo, če λ k izberemo iz pogoja λ k =min f(X k + λS k) .
Za določitev λ k se uporabi katera koli enodimenzionalna optimizacijska metoda. V tem primeru se metoda imenuje metoda najstrmejšega spusta. Praviloma en korak v splošnem ni dovolj za dosego minimuma funkcije; proces se ponavlja, dokler nadaljnji izračuni ne omogočijo izboljšanja rezultata.
Če je prostor v nekaterih spremenljivkah zelo raztegnjen, potem nastane "grapa". Iskanje se lahko upočasni in cik-cak po dnu "grape". Včasih rešitve ni mogoče doseči v sprejemljivem časovnem okviru.
Druga pomanjkljivost metode je lahko merilo ustavljanja ||▽f(X k)||<ε k , так как этому условию удовлетворяет и седловая точка, а не только оптимум.

Primer. Začenši s točko x k =(-2, 3), določite točko x k +1 z uporabo metode najstrmejšega spusta, da zmanjšate funkcijo.
Kot smer iskanja izberite vektor gradienta na trenutni točki

Preverimo kriterij ustavljanja. Imamo
Izračunajmo vrednost funkcije v začetni točki f(X 1) = 35. Naredimo
korak po antigradientni smeri

Izračunajmo vrednost funkcije na novi točki
f(X 2) = 3(-2 + 19λ 1) 2 + (3-8λ 1) 2 - (-2 + 19λ 1)(3-8λ 1) - 4(-2 + 19λ 1)
Poiščimo takšno stopnjo, da ciljna funkcija doseže minimum vzdolž te smeri. Iz nujnega pogoja za obstoj ekstrema funkcije
f’(X 2) = 6(-2 + 19λ 1) 19 + 2(3-8λ 1)(-8) – (73 - 304 λ 1) – 4*19
ali f’(X 2) = 2598 λ 1 – 425 = 0.
Dobimo korak λ 1 = 0,164
Če dokončate ta korak, boste prišli do bistva

v katerem je vrednost gradienta , vrednost funkcije f(X 2) = 0,23. Natančnost ni dosežena, od točke naredimo korak po smeri antigradienta.

f(X 2) = 3(1,116 – 1,008λ 1) 2 + (1,688-2,26λ 1) 2 - (1,116 – 1,008λ 1)(1,688-2,26λ 1) - 4(1,116 – 1,008λ 1)
f’(X 2) = 11,76 – 6,12λ 1 = 0
Dobimo λ 1 = 0,52

Oblikovanje problema

Naj bo funkcija podana f(x) Rn

Obvezno f(x) X = Rn

Strategija iskanja

x k } , k = 0,1,..., tako da , k = 0,1,... . Točke zaporedja ( x k ) se izračunajo po pravilu

kje je smisel x 0 uporabnik definiran; velikost koraka tk določeno za vsako vrednost k od stanja

Problem (3) je mogoče rešiti z uporabo potrebnega minimalnega pogoja, ki mu sledi preverjanje zadostnega minimalnega pogoja. To pot je mogoče uporabiti za dokaj preprosto funkcijo, ki jo je treba minimizirati, ali za predhodno aproksimacijo precej zapletene funkcije polinom P(t k) (običajno druge ali tretje stopnje), nato pa pogoj nadomesti pogoj, pogoj pa pogoj

Zaporedje (xk) konča na točki x k , za katerega , kje ε - dano malo pozitivno število, oz k ≥ M , Kje M - omejeno število ponovitev ali z dvema hkratnima izvajanjema dveh neenačb , Kje ε 2 - majhno pozitivno število. Vprašanje je, ali lahko točka x k obravnavati kot najdeni približek želene lokalne minimalne točke x* , se rešuje z dodatnimi raziskavami.

Geometrična razlaga metode za n=2 na sl. 4.

Metoda koordinatnega spuščanja

Oblikovanje problema

Naj bo funkcija podana f(x) , omejeno spodaj na nizu Rn in ima zvezne delne odvode na vseh svojih točkah.

f(x) na množici izvedljivih rešitev X = Rn , tj. najti takšno točko, da

Strategija iskanja

Strategija za rešitev problema je sestaviti zaporedje točk ( x k } , k = 0,1,..., tako da , k = 0,1,... . Točke zaporedja ( x k ) se izračunajo v ciklih v skladu s pravilom

(4)

Kje j - številko obračunskega cikla; j = 0,1,2,...; k - številka ponovitve znotraj zanke, k = 0,1,... ,n - 1; e k +1 , k = 0,l,...,n - 1 - enotski vektor, (k+1) -ta projekcija, ki je enaka 1; pika x 00 uporabniško določena, velikost koraka tk je izbran iz pogoja

oz .

Če je izbrano stanje pri trenutnem tk ni izpolnjen, se korak prepolovi in pika se ponovno izračuna. Zlahka je videti, da je za fiksni j v eni ponovitvi s številom k spremeni se samo ena projekcija točke x jk , ki ima številko k+1 , in v celotnem ciklu s številko j , tj. začenši z k = 0 in konec k = n -1 , se spremeni vseh n projekcij točke x j0 . Po tej točki x j n številka je dodeljena x j + 1,0 in se vzame kot izhodišče za izračune v j+1 cikel. Izračun se konča na točki x jk ko je izpolnjeno vsaj eno od treh meril ob koncu štetja: , ali , ali dvojna izvedba neenačb.

Točke, dobljene kot rezultat izračunov, lahko zapišemo kot elemente zaporedja (xl), Kje l=n*j+k - zaporedno številko točke,

Geometrična interpretacija metode za n = 2 je prikazana na sl. 5.

4. Metoda Frank-Wolfe .

Recimo, da moramo najti največjo vrednost konkavne funkcije

Pod pogoji

Značilnost tega problema je, da njegov sistem omejitev vsebuje samo linearne neenakosti. Ta lastnost je osnova za zamenjavo nelinearne ciljne funkcije z linearno v bližini preučevane točke, zaradi česar se rešitev prvotnega problema reducira na zaporedno reševanje problemov linearnega programiranja.
Proces iskanja rešitve problema se začne z identifikacijo točke, ki pripada območju izvedljivih rešitev problema.
270
dachas Naj bo to bistvo X(k) potem se na tej točki izračuna gradient funkcije (57).

In sestavite linearno funkcijo

Nato poiščite največjo vrednost te funkcije pri omejitvah (58) in (59). Naj bo rešitev tega problema določena s točko Z(k) . Nato se koordinate točke vzamejo kot nova izvedljiva rešitev prvotnega problema X(k+1) :

Kje λ k - določeno število, ki se imenuje korak izračuna in je med ničlo in ena (0<λ k < 1). Это число λ k samovoljno ali določeno

tako da vrednost funkcije v točki X (k +1) f(X (k +1)) , odvisno od λ k , je bil maksimum. Če želite to narediti, morate najti rešitev enačbe in izbrati njen najmanjši koren. Če je njegova vrednost večja od ena, potem moramo dati λ k=1 . Po določitvi št λ k poiščite koordinate točke X(k+1) izračunajte vrednost ciljne funkcije v njej in ugotovite potrebo po premiku na novo točko X(k+2) . Če obstaja takšna potreba, potem izračunajte na mestu X(k+1) gradient ciljne funkcije, pojdite na ustrezen problem linearnega programiranja in poiščite njegovo rešitev. Določite koordinate točke in X(k+2) in raziščite potrebo po nadaljnjih izračunih. Po končnem številu korakov dobimo rešitev prvotnega problema z zahtevano natančnostjo.

Torej postopek iskanja rešitve problema (57) - (59) z uporabo metode Frank-Wolfe vključuje naslednje stopnje:

1. Določite začetno izvedljivo rešitev problema.
2. Poiščite gradient funkcije (57) v točki dopustne rešitve.
3. Konstruirajte funkcijo (60) in poiščite njeno največjo vrednost pod pogoji (58) in (59).
4. Določite korak izračuna.
5. S pomočjo formul (61) poiščemo komponente nove izvedljive rešitve.
6. Preverite potrebo po prehodu na naslednjo izvedljivo rešitev. Po potrebi nadaljujte na 2. stopnjo, sicer se najde sprejemljiva rešitev za prvotni problem.

Metoda kazenskih funkcij.

Razmislite o problemu določanja največje vrednosti konkavne funkcije

f (x 1, x 2, .... x n) pod pogoji g i (x 1, x 2, .... x n) ≤ b i (i=l, m) , x j ≥ 0 (j=1, n) , Kje g i (x 1, x 2, .... x n) - konveksne funkcije.

Namesto da to težavo rešite neposredno, poiščite največjo vrednost funkcije F(x 1, x 2, ...., x n)= f(x 1, x 2, ...., x n) +H(x 1, x 2, ...., x n) ki je vsota ciljne funkcije problema in neke funkcije

H(x 1, x 2, ...., x n), opredeljen s sistemom omejitev in imenovan funkcijo kazni. Funkcijo kazni je mogoče konstruirati na različne načine. Vendar pa je najpogosteje videti

A a i > 0 - nekaj stalnih števil, ki predstavljajo utežne koeficiente.
S funkcijo kazni se zaporedno premikajo od ene točke do druge, dokler ne dobijo sprejemljive rešitve. V tem primeru se koordinate naslednje točke najdejo s formulo

Iz zadnje povezave sledi, da če je prejšnja točka v območju izvedljivih rešitev prvotnega problema, potem je drugi člen v oglatih oklepajih enak nič in je prehod na naslednjo točko določen le z gradientom cilja funkcijo. Če podana točka ne spada v območje dopustnih rešitev, se zaradi tega člena v naslednjih iteracijah doseže vrnitev v območje dopustnih rešitev.
odločitve. Hkrati manj a i , hitreje se najde sprejemljiva rešitev, vendar se zmanjša natančnost njene določitve. Zato se iterativni proces običajno začne pri relativno majhnih vrednostih a i in z nadaljevanjem se te vrednosti postopoma povečujejo.

Postopek iskanja rešitve problema konveksnega programiranja z uporabo metode kazenske funkcije vključuje naslednje korake:

1. Določite začetno izvedljivo rešitev.
2. Izberite korak izračuna.
3. Poiščite za vse spremenljivke parcialne odvode ciljne funkcije in funkcij, ki določajo obseg izvedljivih rešitev problema.

4. S formulo (72) najdemo koordinate točke, ki določa možno novo rešitev problema.
5. Preverite, ali koordinate najdene točke zadoščajo sistemu problemskih omejitev. Če ne, pojdite na naslednjo stopnjo. Če koordinate najdene točke določajo dopustno rešitev problema, se preuči potreba po prehodu na naslednjo dopustno rešitev. Po potrebi nadaljujte s stopnjo 2, sicer je bila najdena sprejemljiva rešitev za prvotni problem.
6. Nastavite vrednosti utežnih koeficientov in nadaljujte s 4. korakom.

Metoda Arrow-Hurwitz.

Pri iskanju rešitev problemov nelinearnega programiranja z metodo kazenske funkcije smo izbrali vrednosti a i , poljubno, kar je povzročilo znatna nihanja v oddaljenosti določenih točk od območja izvedljivih rešitev. Ta pomanjkljivost je odpravljena pri reševanju problema po metodi Arrow-Hurwitz, po kateri se v naslednjem koraku številke a i (k) izračunano po formuli

Kot začetne vrednosti a i (0) vzemite poljubna nenegativna števila.

PRIMER REŠITVE

Primer 1.

Poiščite lokalni minimum funkcije

Določitev točke x k

1. Postavimo .

2. Postavimo k = 0 .

trideset. Izračunajmo

4 0 . Izračunajmo . Pojdimo na 5. korak.

50. Preverimo stanje . Pojdimo na 6. korak.

6 0 . Postavimo t0 = 0,5 .

7 0 . Izračunajmo

8 0 . Primerjajmo . Imamo . Zaključek: pogoj za k = 0 se ne izvaja. Postavimo t0 = 0,25 , nadaljujte s ponavljanjem korakov 7, 8.

7 01. Izračunajmo.

8 01. Primerjajmo f (x 1) in f (x 0) . Zaključek: f (x 1)< f (x 0) . Pojdimo na 9. korak.

9 0 . Izračunajmo

Zaključek: verjamemo k =1 in pojdite na 3. korak.

3 1. Izračunajmo

4 1. Izračunajmo . Pojdimo na 5. korak.

5 1. Preverimo stanje k ≥ M: k = 1< 10 = M . Pojdimo na 6. korak.

6 1. Postavimo t 1 = 0,25.

7 1. Izračunajmo

8 1. Primerjajmo f (x 2) z f (x 1) . Zaključek: f (x 2)< f (х 1). Pojdimo na 9. korak.

9 1. Izračunajmo

Zaključek: verjamemo k = 2 in pojdite na 3. korak.

3 2. Izračunajmo

4 2. Izračunajmo. Pojdimo na 5. korak.

5 2. Preverimo stanje k ≥ M : k = 2< 10 = М , pojdite na 6. korak.

6 2. Postavimo t 2 =0,25 .

7 2. Izračunajmo

8 2. Primerjajmo f (x 3) in f (x 2) . Zaključek: f (x 3)< f (х 2) .Pojdite na 9. korak.

9 2. Izračunajmo

Zaključek: verjamemo k = 3 in pojdite na 3. korak.

3 3 . Izračunajmo

4 3 . Izračunajmo. Pojdimo na 5. korak.

5 3. Preverimo stanje k ≥ M : k = 3<10 = М , pojdite na 6. korak.

6 3. Postavimo t 3 = 0,25.

7 3. Izračunajmo

8 3. Primerjajmo f (x 4) in f (x 3) : f (x 4)< f (х 3) .

9 3. Izračunajmo

Pogoji so izpolnjeni, ko k = 2,3 . Izračun

Dokončano. Točka najdena

Na sl. 3 nastale točke so povezane s pikčasto črto.

II. Analiza točk x 4 .

funkcija je dvakrat diferencibilen, zato bomo preverili zadostne pogoje za minimum v točki x 4 . Da bi to naredili, analizirajmo Hessovo matriko.

Matrika je konstantna in pozitivno določena (tj. . H > 0 ), ker sta oba njegova kotna minora pozitivna. Zato bistvo je najdeni približek lokalne minimalne točke in vrednost je najdeni približek vrednosti f (x *) =0 . Upoštevajte, da je pogoj H > 0 , obstaja hkrati pogoj za strogo konveksnost funkcije . Posledično so najdeni približki globalne minimalne točke f(x) in njegova najmanjša vrednost pri R 2 . ■

Primer 2

Poiščite lokalni minimum funkcije

I. Opredelitev točke x k, pri katerem je izpolnjen vsaj eden od kriterijev za dokončanje izračunov.

1. Postavimo .

Poiščimo gradient funkcije v poljubni točki

2. Postavimo k = 0 .

trideset. Izračunajmo

4 0 . Izračunajmo . Pojdimo na 5. korak.

50. Preverimo stanje . Pojdimo na 6. korak.

6° Naslednjo točko najdemo s formulo

Dobljene izraze za koordinate nadomestimo v

Poiščimo minimum funkcije f(t 0) Avtor: t 0 z uporabo potrebnih pogojev za brezpogojni ekstrem:

Od tod t 0 =0,24 . Ker , najdena vrednost koraka zagotavlja minimum funkcije f(t 0) Avtor: t 0 .

Določimo

7 0 . Bomo našli

8°. Izračunajmo

Zaključek: verjamemo k = 1 in pojdite na 3. korak.

3 1. Izračunajmo

4 1. Izračunajmo

5 1. Preverimo stanje k ≥ 1: k = 1< 10 = М.

6 1. Določimo

7 1. Bomo našli :

8 1. Izračunajmo

Verjamemo k = 2 in pojdite na 3. korak.

3 2. Izračunajmo

4 2. Izračunajmo

5 2. Preverimo stanje k ≥ M: k = 2< 10 = M .

6 2. Določimo

7 2. Bomo našli

8 2. Izračunajmo

Verjamemo k =3 in pojdite na 3. korak.

3 3 . Izračunajmo

4 3 . Izračunajmo.

Izračun je končan. Točka najdena

II. Analiza točk x 3 .

V primeru 1.1 (poglavje 2 §1) je bilo pokazano, da funkcija f(x) je strogo konveksna in je zato v točkah3 najdena aproksimacija globalne minimalne točke X* .

Primer 3.

Poiščite lokalni minimum funkcije

I. Opredelitev točke xjk , pri katerem je izpolnjen vsaj eden od kriterijev za dokončanje izračunov.

1. Postavimo

Poiščimo gradient funkcije v poljubni točki

2. Postavimo j = 0.

trideset. Preverimo ali je pogoj izpolnjen

4 0 . Postavimo k = 0.

50. Preverimo ali je pogoj izpolnjen

6 0 . Izračunajmo

7 0 . Preverimo stanje

8 0 . Postavimo

9 0 . Izračunajmo , Kje

100 . Preverimo stanje

Zaključek: predpostavljamo in nadaljujemo na 9. korak.

9 01. Izračunajmo x 01 v korakih

10 01. Preverimo stanje

11 0 . Preverimo pogoje

Verjamemo k =1 in pojdite na 5. korak.

5 1. Preverimo stanje

6 1. Izračunajmo

7 1. Preverimo stanje

8 1. Postavimo

9 1. Izračunajmo

10 1. Preverimo stanje :

11 1. Preverimo pogoje

Verjamemo k = 2 , pojdite na 5. korak.

5 2. Preverimo stanje. Nastavimo, pojdimo na 3. korak.

3 1. Preverimo stanje

4 1. Postavimo k = 0.

5 2. Preverimo stanje

6 2. Izračunajmo

7 2. Preverimo stanje

8 2. Postavimo

9 2. Izračunajmo

10 2. Preverimo stanje

11 2. Preverimo pogoje

Verjamemo k =1 in pojdite na 5. korak.

5 3. Preverimo stanje

6 3. Izračunajmo

7 3. Preverimo pogoje

8 3. Postavimo

9 3. Izračunajmo

10 3. Preverimo stanje

11 3. Preverimo pogoje

Postavimo k = 2 in pojdite na 5. korak.

5 4. Preverimo stanje

Verjamemo j = 2, x 20 = x 12 in pojdite na 3. korak.

3 2. Preverimo stanje

4 2. Postavimo k =0 .

5 4. Preverimo stanje

6 4. Izračunajmo

7 4. Preverimo stanje

8 4 . Postavimo

9 4. Izračunajmo

10 4. Preverimo stanje in pojdimo na 11. korak.

11 4. Preverimo pogoje

Pogoji so izpolnjeni v dveh zaporednih ciklih s številkami j=2 in j -1= 1 . Izračun je končan, točka je najdena

Na sl. 6 nastalih točk je povezanih s pikčasto črto.

Pri metodi koordinatnega spuščanja se spuščamo po lomljeni črti, sestavljeni iz ravnih odsekov, vzporednih s koordinatnimi osemi.

II. Analiza točke x21.

V primeru 1.1 je bilo pokazano, da funkcija f(x) je strogo konveksen, ima edinstven minimum in zato točko je najdeni približek globalne minimalne točke.

V vseh zgoraj obravnavanih metodah gradienta zaporedje točk (xk) konvergira k stacionarni točki funkcije f(x) z dokaj splošnimi predlogi glede lastnosti te funkcije. Zlasti velja izrek:

Izrek. Če je funkcija f(x) omejena spodaj, njen gradient izpolnjuje Lipschitzev pogoj () in izbiro vrednosti tn proizvedeno z eno od zgoraj opisanih metod, nato pa ne glede na izhodišče x 0 :

ob .

Pri praktični izvedbi sheme

k =1, 2, … n.

ponovitve se ustavijo, če za vse i, i = 1, 2, ..., n , pogoji kot

kjer je določeno število, ki označuje natančnost iskanja minimuma.

V pogojih izreka gradientna metoda zagotavlja konvergenco v funkciji ali na natančno spodnjo mejo (če funkcija f(x) nima minimuma; riž. 7) ali na vrednost funkcije v neki stacionarni točki, ki je limita zaporedja (x k). Ni težko priti do primerov, ko je na tej točki realizirano sedlo in ne minimum. V praksi metode gradientnega spuščanja samozavestno obidejo sedla in najdejo minimume ciljne funkcije (v splošnem lokalne).

ZAKLJUČEK

Primeri metod gradientne neomejene optimizacije so bili obravnavani zgoraj. Kot rezultat opravljenega dela je mogoče narediti naslednje zaključke:

1. Bolj ali manj zapleteni problemi iskanja ekstrema ob prisotnosti omejitev zahtevajo posebne pristope in metode.

2. Mnogi algoritmi za reševanje omejenih problemov vključujejo neomejeno minimizacijo kot nekaj korakov.

3. Različni načini spusta se med seboj razlikujejo po načinu izbire smeri spusta in dolžini koraka po tej smeri.

4. Teorije, ki bi upoštevala kakršnekoli značilnosti funkcij, ki opisujejo formulacijo problema, še ni. Prednost je treba dati metodam, ki jih je lažje obvladati v procesu reševanja problema.

Resnični uporabni optimizacijski problemi so zelo kompleksni. Sodobne optimizacijske metode ne morejo vedno rešiti resničnih problemov brez človeške pomoči.

BIBLIOGRAFIJA

1. Kosorukov O.A. Operacijske raziskave: učbenik. 2003

2. Pantleev A.V. Optimizacijske metode v primerih in problemih: učbenik. Korist. 2005

3. Šiškin E.V. Operacijske raziskave: učbenik. 2006

4. Akulich I.L. Matematično programiranje v primerih in nalogah. 1986

5. Ventzel E.S. Operacijske raziskave. 1980

6. Ventzel E.S., Ovcharov L.A. Teorija verjetnosti in njene inženirske aplikacije. 1988

©2015-2019 stran
Vse pravice pripadajo njihovim avtorjem. To spletno mesto ne zahteva avtorstva, vendar omogoča brezplačno uporabo.
Datum nastanka strani: 2017-07-02

Gradient diferenciabilne funkcije f(x) v točki X klical n-dimenzionalni vektor f(x) , katere komponente so delni odvodi funkcije f(x), izračunano na točki X, tj.

f"(x ) = (df(x)/dh 1 , …, df(x)/dx n) T .

Ta vektor je pravokoten na ravnino skozi točko X, in tangenta na ravno površino funkcije f(x), ki poteka skozi točko X.V vsaki točki take površine funkcija f(x) ima enako vrednost. Če funkcijo enačimo z različnimi konstantnimi vrednostmi C 0 , C 1 , ..., dobimo vrsto površin, ki označujejo njeno topologijo (slika 2.8).

riž. 2.8. Gradient

Vektor gradienta je usmerjen proti najhitrejšemu naraščanju funkcije v dani točki. Vektor nasproti gradientu (-f’(x)) , poklical anti-gradient in je usmerjen v najhitrejše upadanje funkcije. V točki minimuma je gradient funkcije enak nič. Metode prvega reda, imenovane tudi gradientne in minimizacijske metode, temeljijo na lastnostih gradientov. Uporaba teh metod v splošnem primeru vam omogoča, da določite lokalno minimalno točko funkcije.

Očitno, če ni dodatnih informacij, potem od izhodišča X pametno je iti k bistvu X, ki leži v smeri antigradienta - najhitrejši upad funkcije. Izbira smeri spusta R[k] anti-gradient - f'(x[k] ) na točki X[k], dobimo iterativni proces oblike

X[ k+ 1] = x[k]-a k f"(x[k] ) , in k > 0; k=0, 1, 2, ...

V koordinatni obliki je ta proces zapisan na naslednji način:

x i [ k+1]=x i[k] - a kf(x[k] ) /x i

i = 1, ..., n; k= 0, 1, 2,...

Kot merilo za zaustavitev iterativnega procesa je bodisi izpolnjevanje pogoja majhnega prirastka argumenta || x[k+l] -x[k] || <= e , либо выполнение условия малости градиента

|| f'(x[k+l] ) || <= g ,

Tukaj sta e in g podani majhni količini.

Možen je tudi kombiniran kriterij, ki sestoji iz hkratnega izpolnjevanja navedenih pogojev. Gradientne metode se med seboj razlikujejo po načinu izbire velikosti koraka in k.

Pri metodi s konstantnim korakom se za vse iteracije izbere določena konstantna vrednost koraka. Čisto majhen korak in k bo zagotovil, da se funkcija zmanjša, to je neenakost

f(x[ k+1]) = f(x[k] – a k f'(x[k] )) < f(x[k] ) .

Vendar pa lahko to povzroči potrebo po izvedbi nesprejemljivo velikega števila ponovitev, da bi dosegli minimalno točko. Po drugi strani pa lahko prevelik korak povzroči nepričakovano povečanje funkcije ali povzroči nihanje okoli minimalne točke (cikliranje). Zaradi težav pri pridobivanju potrebnih informacij za izbiro velikosti koraka se metode s konstantnimi koraki v praksi redko uporabljajo.

Gradientne so bolj ekonomične glede števila iteracij in zanesljivosti metode spremenljivega koraka, ko se glede na rezultate izračunov velikost koraka na nek način spremeni. Razmislimo o različicah takšnih metod, ki se uporabljajo v praksi.

Pri uporabi metode najstrmejšega spusta pri vsaki ponovitvi velikost koraka in k je izbran iz minimalnega pogoja funkcije f(x) v smeri sestopa, tj.
f(x[k]–a k f’(x[k])) = f(x[k] – af"(x[k])) .

Ta pogoj pomeni, da se gibanje vzdolž antigradienta dogaja, dokler je vrednost funkcije f(x) zmanjša. Z matematičnega vidika je treba pri vsaki iteraciji rešiti problem enodimenzionalne minimizacije po A funkcije
j (a) = f(x[k]-af"(x[k])) .

Algoritem metode najstrmejšega spusta je naslednji.

1. Nastavite koordinate začetne točke X.

2. Na točki X[k], k = 0, 1, 2, ... izračuna vrednost gradienta f'(x[k]) .

3. Velikost koraka je določena a k, z enodimenzionalno minimizacijo nad A funkcije j (a) = f(x[k]-af"(x[k])).

4. Določene so koordinate točke X[k+ 1]:

x i [ k+ 1]= x i[k]– a k f’ i (x[k]), i = 1,..., str.

5. Preverijo se pogoji za zaustavitev steracijskega procesa. Če so izpolnjeni, se izračuni ustavijo. V nasprotnem primeru pojdite na 1. korak.

dj (a)/da = -f’(x[k+ 1]f'(x[k]) = 0.

riž. 2.9. Geometrična interpretacija metode najstrmejšega spusta

se med seboj malo razlikujejo, tj N(x) dobro kondicionirano. Spomnimo se, da lastne vrednosti l i, jaz =1, …, n, so matrike korenine karakteristične enačbe

riž. 2.10. Gullyjeva funkcija

Zgoraj obravnavane gradientne metode najdejo minimalno točko funkcije v splošnem primeru samo v neskončnem številu ponovitev. Metoda konjugiranega gradienta ustvari smeri iskanja, ki so bolj skladna z geometrijo funkcije, ki jo minimiziramo. To bistveno poveča hitrost njihove konvergence in omogoča, na primer, minimiziranje kvadratne funkcije

f(x) = (x, Hx) + (b, x) + a

s simetrično pozitivno določeno matriko n v končnem številu korakov P, enako številu funkcijskih spremenljivk. Vsako gladko funkcijo v bližini točke minimuma je mogoče dobro aproksimirati s kvadratno funkcijo, zato se metode konjugiranega gradienta uspešno uporabljajo za minimiziranje nekvadratnih funkcij. V tem primeru prenehajo biti končni in postanejo iterativni.

Po definiciji dve n-dimenzionalni vektor X in pri klical konjugiran glede na matrico H(oz H-konjugat), če je skalarni produkt (x, no) = 0. Tukaj N - simetrična pozitivno določena matrika velikosti p X p.

Eden najpomembnejših problemov pri metodah konjugiranega gradienta je problem učinkovite konstrukcije smeri. Metoda Fletcher-Reeves rešuje to težavo s transformacijo antigradienta na vsakem koraku -f(x[k]) v smeri str[k], H-konjugiran s predhodno najdenimi smermi R, R, ..., R[k-1].

Najprej razmislimo o tej metodi v povezavi s problemom minimiziranja kvadratne funkcije. R[k Navodila

] se izračuna po formulah: k] = -f'(x[k]) p[ str[k+b k-1 k>= 1;

-l], p = -’(x) .

f k b vrednosti str[k], R[k-1 so izbrani tako, da so smeri H-1] so bili :

(str[k], -konjugat[HP 1])= 0.

Kot rezultat, za kvadratno funkcijo

iterativni postopek minimizacije ima obliko k+l] x[[k]=x[k],

Kje R[k] - +a k str HP smer sestopa do m korak; in k- velikost koraka. Slednji je izbran iz minimalnega pogoja funkcije Avtor: A f(x)

f(x[ k] + v smeri gibanja, tj. kot rezultat reševanja problema enodimenzionalne minimizacije:[k]) = f(x[k] + a k r [k]) .

Za kvadratno funkcijo

Algoritem metode konjugiranega gradienta Fletcher-Reeves je naslednji. X 1. Na točki str = -f'(x) .

izračunano HP 2. Vklopljeno A m korak, z uporabo zgornjih formul se določi korak . k X[k+ 1].

in pika f(x[k+1]) 3. Vrednosti so izračunane f'(x[k+1]) .

in f'(x) 4. Če X[k= 0, nato točka +1] je najmanjša točka funkcije f(x). str[k V nasprotnem primeru je določena nova smer

+l] iz relacije p in izvede se prehod na naslednjo ponovitev. Ta postopek bo našel minimum kvadratne funkcije v največ koraki. Pri minimiziranju nekvadratnih funkcij Fletcher-Reevesova metoda iz končne postane iterativna. V tem primeru po(p+ X 1) ponovitev postopka 1-4 se ciklično ponavlja z zamenjavo X[p na

iterativni postopek minimizacije ima obliko k+l] = x[k]=x[k],

] se izračuna po formulah: k] +1] , izračuni pa se končajo pri , kjer je dano število. V tem primeru se uporablja naslednja modifikacija metode:[k])+ = -f’(x HP 1 str[k+b k-1 k>= 1;

b x);

f(x[ k] + p = -f’([k]) = f(x[k] a k str[k];

+ap Tukaj jaz Tukaj- veliko indeksov: = (0, n, 2 p, plača, ...) p, tj. metoda se posodobi vsakih

koraki. X Geometrični pomen metode konjugiranega gradienta je naslednji (slika 2.11). Iz danega izhodišča R = sestop izvedemo v smeri-f"(x X). Na točki f"(x vektor gradienta je določen X je najmanjša točka funkcije v smeri R, to f'(x) pravokoten na vektor R. Nato je vektor najden R , H-konjugiran na R. Nato poiščemo minimum funkcije vzdolž smeri R itd.

riž. 2.11 . Spustna trajektorija pri metodi konjugiranega gradienta

Metode konjugirane smeri so med najbolj učinkovitimi za reševanje problemov minimizacije. Vendar je treba upoštevati, da so občutljivi na napake, ki se pojavijo med postopkom štetja. Pri velikem številu spremenljivk se lahko napaka tako poveča, da bo treba postopek ponoviti tudi za kvadratno funkcijo, tj. postopek zanjo ne sodi vedno v p, tj. metoda se posodobi vsakih

Metoda najstrmejšega spusta (v angleški literaturi »method of steepest descent«) je iterativna numerična metoda (prvega reda) za reševanje optimizacijskih problemov, ki omogoča določitev ekstrema (minimum ali maksimum) ciljne funkcije:

so vrednosti argumenta funkcije (nadzorovanih parametrov) na realni domeni.

V skladu z obravnavano metodo se določi ekstrem (maksimum ali minimum) ciljne funkcije v smeri najhitrejšega naraščanja (padanja) funkcije, tj. v smeri gradienta (antigradienta) funkcije. Gradientna funkcija v točki je vektor, katerega projekcije na koordinatne osi so parcialni odvodi funkcije glede na koordinate:

kjer so i, j,…, n enotski vektorji, vzporedni s koordinatnimi osemi.

Gradient na osnovni točki je strogo pravokoten na površino in njegova smer kaže smer najhitrejšega naraščanja funkcije, nasprotna smer (antigradient) pa kaže smer najhitrejšega padanja funkcije.

Metoda najstrmejšega spusta je nadaljnji razvoj metode gradientnega spusta. Na splošno je postopek iskanja ekstrema funkcije iterativni postopek, ki ga zapišemo takole:

kjer se znak "+" uporablja za iskanje maksimuma funkcije, znak "-" pa se uporablja za iskanje minimuma funkcije;

Enotski smerni vektor, ki je določen s formulo:

- modul gradienta določa stopnjo naraščanja ali padanja funkcije v smeri gradienta ali antigradienta:

Konstanta, ki določa velikost koraka in je enaka za vse i-te smeri.

Velikost koraka je izbrana iz pogoja minimuma ciljne funkcije f(x) v smeri gibanja, to je kot rezultat reševanja enodimenzionalnega optimizacijskega problema v smeri gradienta ali antigradienta:

Z drugimi besedami, velikost koraka se določi z rešitvijo te enačbe:

Tako je korak izračuna izbran tako, da se premikanje izvaja, dokler se funkcija ne izboljša in tako na neki točki doseže ekstrem. Na tej točki se ponovno določi smer iskanja (z gradientom) in išče se nova optimalna točka ciljne funkcije itd. Tako pri tej metodi iskanje poteka v večjih korakih, gradient funkcije pa se izračuna na manjšem številu točk.

V primeru funkcije dveh spremenljivk ima ta metoda naslednjo geometrijsko interpretacijo: smer gibanja iz točke se dotika nivojske črte v točki . Pot spuščanja je cik-cak, s sosednjimi cik-cak povezavami pravokotnimi druga na drugo. Pogoj pravokotnosti vektorjev smeri spuščanja v sosednjih točkah je zapisan z naslednjim izrazom:

Trajektorija gibanja do ekstremne točke z uporabo metode najstrmejšega spusta, prikazana na grafu črte enakega nivoja funkcije f(x)

Iskanje optimalne rešitve se konča, ko je na koraku iterativnega izračuna (več kriterijev):

Trajektorija iskanja ostane v majhni soseščini trenutne točke iskanja:

Prirastek ciljne funkcije se ne spremeni:

Gradient ciljne funkcije v lokalni minimalni točki postane nič:

Treba je opozoriti, da se metoda gradientnega spuščanja pri premikanju po grapi izkaže za zelo počasno, in ko se število spremenljivk v funkciji cilja poveča, postane takšno obnašanje metode tipično. Grapa je depresija, katere ravninske črte imajo približno obliko elipse s polosemi, ki se večkrat razlikujejo. V prisotnosti grape ima pot spusta obliko cik-cak črte z majhnim korakom, zaradi česar se posledična hitrost spusta na minimum močno upočasni. To je razloženo z dejstvom, da smer antigradienta teh funkcij bistveno odstopa od smeri do minimalne točke, kar povzroči dodatno zamudo pri izračunu. Zaradi tega algoritem izgubi računsko učinkovitost.

Gullyjeva funkcija

Gradientna metoda je skupaj s številnimi modifikacijami pogosta in učinkovita metoda za iskanje optimuma proučevanih predmetov. Pomanjkljivost gradientnega iskanja (kot tudi zgoraj obravnavanih metod) je, da je pri njegovi uporabi mogoče zaznati le lokalni ekstrem funkcije. Za iskanje drugih lokalnih ekstremov je potrebno iskati iz drugih izhodišč. Tudi stopnja konvergence gradientnih metod je bistveno odvisna od natančnosti izračunov gradientov. Izguba natančnosti, ki se običajno pojavi v bližini minimalnih točk ali v razmerah žlebov, lahko na splošno moti konvergenco procesa gradientnega spuščanja.

Metoda izračuna

Korak 1: Definicija analitičnih izrazov (v simbolni obliki) za izračun gradienta funkcije

2. korak: Nastavite začetni približek

3. korak: Ugotovljena je potreba po ponovnem zagonu algoritemskega postopka za ponastavitev zadnje smeri iskanja. Zaradi ponovnega zagona se ponovno izvede iskanje v smeri najhitrejšega spusta.