Varat arī meklēt nevis labāko punktu gradienta virzienā, bet kādu labāku par pašreizējo.
Visvieglāk īstenojamā no visām vietējām optimizācijas metodēm. Ir diezgan vāji apstākļi konverģence, bet konverģences ātrums ir diezgan zems (lineārs). Gradienta metodes solis bieži tiek izmantots kā daļa no citām optimizācijas metodēm, piemēram, Flečera–Rīvesa metodes.
Apraksts [ | ]
Uzlabojumi[ | ]
Gradienta nolaišanās metode izrādās ļoti lēna, pārvietojoties pa gravu un palielinoties mainīgo skaitam mērķa funkcijašī metodes uzvedība kļūst tipiska. Lai cīnītos pret šo parādību, tas tiek izmantots, kura būtība ir ļoti vienkārša. Veicot divus gradienta nolaišanās soļus un iegūstot trīs punktus, trešais solis jāsper vektora virzienā, kas savieno pirmo un trešo punktu, gar gravas dibenu.
Funkcijām, kas ir tuvu kvadrātiskām, konjugētā gradienta metode ir efektīva.
Pielietojums mākslīgajos neironu tīklos[ | ]
Gradienta nolaišanās metode ar dažām modifikācijām tiek plaši izmantota perceptronu apmācībai, un mākslīgo neironu tīklu teorijā tā ir pazīstama kā backpropagation metode. Apmācot perceptrona tipa neironu tīklu, ir jāmaina tīkla svēršanas koeficienti, lai samazinātu vidējā kļūda neironu tīkla izejā, kad ievadei tiek piegādāta apmācības ievades datu secība. Formāli, lai veiktu tikai vienu soli, izmantojot gradienta nolaišanās metodi (veikt tikai vienu tīkla parametru izmaiņu), tīkla ievadei ir nepieciešams secīgi iesniegt absolūti visu apmācības datu kopu, aprēķināt kļūdu katram objektam. apmācību datus un aprēķināt nepieciešamo tīkla koeficientu korekciju (bet neveikt šo korekciju), un pēc visu datu iesniegšanas aprēķināt summu katra tīkla koeficienta korekcijā (gradientu summa) un labot koeficientus "viens solis" . Acīmredzot ar lielu apmācības datu kopu algoritms darbosies ārkārtīgi lēni, tāpēc praksē tīkla koeficienti bieži tiek koriģēti pēc katra apmācības elementa, kur gradienta vērtība tiek tuvināta ar izmaksu funkcijas gradientu, kas aprēķināts tikai vienā treniņā. elements. Šo metodi sauc stohastiskā gradienta nolaišanās vai operatīvā gradienta nolaišanās . Stohastiskā gradienta nolaišanās ir stohastiskās tuvināšanas veids. Stohastisko aproksimāciju teorija nodrošina nosacījumus stohastiskā gradienta nolaišanās metodes konverģencei.
Saites [ | ]
- J. Mathews. Stāvākā nolaišanās vai gradienta metodes modulis. (saite nav pieejama)
Literatūra [ | ]
- Akuličs I. L. Matemātiskā programmēšana piemēros un uzdevumos. - M.: Augstskola, 1986. - P. 298-310.
- Džils F., Marejs V., Raits M. Praktiskā optimizācija = Praktiskā optimizācija. - M.: Mir, 1985.
- Koršunovs Ju.M., Koršunovs Ju.M. Kibernētikas matemātiskie pamati. - M.: Energoatomizdat, 1972. gads.
- Maksimovs Ju.A., Filipovskaja E.A. Algoritmi nelineārās programmēšanas uzdevumu risināšanai. - M.: MEPhI, 1982. gads.
- Maksimovs Ju.A. Algoritmi lineārai un diskrētai programmēšanai. - M.: MEPhI, 1980. gads.
- Korns G., Korns T. Matemātikas rokasgrāmata zinātniekiem un inženieriem. - M.: Nauka, 1970. - P. 575-576.
- S. Ju. Gorodetskis, V. A. Grišagins. Nelineāra programmēšana un multiekstremāla optimizācija. - Ņižņijnovgoroda: Ņižņijnovgorodas universitātes izdevniecība, 2007. - 357.-363.lpp.
Stāvākā nolaišanās metode ir gradienta metode ar mainīgu pakāpienu. Katrā iterācijā soļa lielums k tiek izvēlēts no funkcijas f(x) minimuma nosacījuma nolaišanās virzienā, t.i.
Šis nosacījums nozīmē, ka kustība pa antigradientu notiek tik ilgi, kamēr funkcijas f (x) vērtība samazinās. No matemātiskā viedokļa katrā iterācijā ir jāatrisina viendimensijas minimizēšanas problēma pēc funkcijas
()=f (x (k) -f (x (k)))
Šim nolūkam izmantosim zelta griezuma metodi.
Stāvākās nolaišanās metodes algoritms ir šāds.
Ir norādītas sākuma punkta x (0) koordinātas.
Punktā x (k) , k = 0, 1, 2, ... aprēķina gradienta vērtību f (x (k)).
Soļa lielumu k nosaka viendimensijas minimizēšana, izmantojot funkciju
()=f (x (k) -f (x (k))).
Punkta x (k) koordinātas nosaka:
x i (k+1) = x i (k) - k f i (x (k)), i=1, …, n.
Tiek pārbaudīts iteratīvā procesa apturēšanas nosacījums:
||f (x (k +1))|| .
Ja tas ir izpildīts, tad aprēķini apstājas. Pretējā gadījumā mēs pārejam uz 1. darbību. Stāvākās nolaišanās metodes ģeometriskā interpretācija ir parādīta attēlā. 1.
Rīsi. 2.1. Stāvākās nolaišanās metodes blokshēma.
Metodes ieviešana programmā:
Stāvākā nolaišanās metode.
Rīsi. 2.2. Stāvākās nolaišanās metodes ieviešana.
Secinājums: mūsu gadījumā metode saplūda 7 iterācijās. Punkts A7 (0,6641; -1,3313) ir galējības punkts. Konjugācijas virzienu metode. Kvadrātiskajām funkcijām varat izveidot gradienta metodi, kurā konverģences laiks būs ierobežots un vienāds ar mainīgo skaitu n.
Nosauksim noteiktu virzienu un konjugēsim attiecībā pret kādu pozitīvu noteiktu Hesa matricu H, ja:
Tad, t.i., vienībai H konjugācijas virziens nozīmē to perpendikulāru. Vispārīgā gadījumā H nav triviāls. IN vispārējs gadījums konjugācija ir Hesa matricas pielietošana vektoram – tas nozīmē pagriezt šo vektoru par kādu leņķi, izstiept vai saspiest.
Un tagad vektors ir ortogonāls, t.i., konjugācija nav vektora ortogonalitāte, bet gan pagrieztā vektora ortogonalitāte.t.i.
Rīsi. 2.3. Konjugāta virzienu metodes blokshēma.
Metodes ieviešana programmā: Konjugācijas virzienu metode.
Rīsi. 2.4. Konjugēto virzienu metodes ieviešana.
Rīsi. 2.5. Konjugēto virzienu metodes grafiks.
Secinājums: Punkts A3 (0,6666; -1,3333) tika atrasts 3 iterācijās un ir ekstrēma punkts.
3. Funkcijas minimālās un maksimālās vērtības noteikšanas metožu analīze ierobežojumu klātbūtnē
Atgādināsim jums to kopīgs uzdevums nosacījuma optimizācija izskatās šādi
f(x) ® min, x О W,
kur W ir pareiza R m apakškopa. Problēmu apakšklase ar vienlīdzības tipa ierobežojumiem izceļas ar to, ka kopu nosaka formas ierobežojumi
f i (x) = 0, kur f i: R m ®R (i = 1, …, k).
Tādējādi W = (x О R m: f i (x) = 0, i = 1, …, k).
Mums būs ērti funkcijai f ierakstīt indeksu "0". Tādējādi optimizācijas problēma ar vienlīdzības tipa ierobežojumiem tiek uzrakstīta kā
f 0 (x) ® min, (3.1)
f i (x) = 0, i = 1, …, k. (3.2)
Ja tagad ar f apzīmējam funkciju uz R m ar vērtībām R k, kuras koordinātu apzīmējumam ir forma f(x) = (f 1 (x), ..., f k (x)), tad ( 3.1)–(3.2) to varam ierakstīt arī formā
f 0 (x) ® min, f(x) = Q.
Ģeometriski problēma ar vienādības tipa ierobežojumiem ir uzdevums atrast funkcijas f 0 grafika zemāko punktu virs kolektora (sk. 3.1. att.).
Punktus, kas atbilst visiem ierobežojumiem (t.i., kopas punkti), parasti sauc par pieņemamiem. Pieļaujamo punktu x* sauc par funkcijas f 0 nosacīto minimumu pie ierobežojumiem f i (x) = 0, i = 1, ..., k (vai problēmas (3.1)–(3.2) risinājumu, ja visiem pieļaujamajiem punktiem x f 0 (x *) f 0 (x). (3.3)
Ja (3.3) ir izpildīts tikai attiecībā uz pieļaujamo x, kas atrodas kādā punkta x* apkaimē V x *, tad mēs runājam par lokālo nosacīto minimumu. Nosacītu stingru lokālo un globālo minimumu jēdzieni tiek definēti dabiskā veidā.
Šajā gradienta metodes versijā minimizējošā secība (X k) arī tiek konstruēta saskaņā ar noteikumu (2.22). Tomēr soļa lielums a k tiek atrasts, risinot papildu viendimensijas minimizēšanas uzdevumu
min(j k (a) | a>0 ), (2,27)
kur j k (a)=f(X k - a· (X k)). Tādējādi katrā iterācijā antigradienta virzienā 
tiek veikta izsmeļoša nolaišanās. Lai atrisinātu problēmu (2.27), varat izmantot vienu no 1. sadaļā aprakstītajām viendimensijas meklēšanas metodēm, piemēram, bitu meklēšanas metodi vai zelta griezuma metodi.
Aprakstīsim stāvākās nolaišanās metodes algoritmu.
0. darbība. Iestatiet precizitātes parametru e>0, izvēlieties X 0 ОE n , iestatiet k=0.
1. darbība. Atrodiet (X k) un pārbaudiet nosacījumu noteiktās precizitātes sasniegšanai || (x k) ||£ e. Ja tas ir apmierināts, pārejiet uz 3. darbību, pretējā gadījumā — uz 2. darbību.
2. darbība. Atrisiniet uzdevumu (2.27), t.i. atrast k. Atrodiet nākamo punktu, ielieciet k=k+1 un pārejiet uz 1. darbību.
3. darbība Pabeidz aprēķinus, liekot X * = X k, f * = f(X k).
Minimizēt funkciju
f(x)=x 1 2 +4x 2 2 -6x 1 -8x 2 +13; (2,28)
Vispirms atrisināsim problēmu klasika metodi. Pierakstīsim vienādojumu sistēmu, kas attēlo nepieciešamos nosacījumus beznosacījuma galējība
To atrisinot, iegūstam stacionāru punktu X*=(3;1). Tālāk pārbaudīsim izpildi pietiekamā stāvoklī, kuram atrodam otro atvasinājumu matricu
Tā kā saskaņā ar Silvestra kritēriju šī matrica ir pozitīva, noteikta ", tad atrastais punkts X* ir funkcijas f(X) minimālais punkts. Minimālā vērtība f *=f(X*)=0. Šis ir precīzs problēmas (11) risinājums.
Veiksim vienu metodes atkārtojumu gradienta nolaišanās par (2.28). Izvēlēsimies sākumpunktu X 0 =(1;0), iestatīsim sākuma soli a=1 un parametru l=0,5. Aprēķināsim f(X 0)=8.
Atradīsim funkcijas f(X) gradientu punktā X 0
(X 0) = = (2,29)
Definēsim jaunu punktu X=X 0 -a· (X 0), aprēķinot tā koordinātas
x 1 = 
x 2 = 
(2.30)
Aprēķināsim f(X)= f(X 0 -a· (X 0))=200. Tā kā f(X)>f(X 0), mēs sadalām soli, pieņemot, ka a=a·l=1·0,5=0,5. Atkal aprēķinām, izmantojot formulas (2.30) x 1 =1+4a=3; x 2 =8a=4 un atrodiet vērtību f(X)=39. Tā kā atkal f(X)>f(X 0), mēs vēl vairāk samazinām soļa lielumu, iestatot a=a·l=0,5·0,5=0,25. Aprēķinām jaunu punktu ar koordinātēm x 1 =1+4·0,25=2; x 2 =8·0,25=2 un funkcijas vērtība šajā punktā f(X)=5. Tā kā nosacījums f(X) samazināšanai Veicam vienu iterāciju, izmantojot metodi stāvākais nobrauciens priekš (2.28) ar tādu pašu sākuma punktu X 0 =(1;0). Izmantojot jau atrasto gradientu (2.29), mēs atrodam X= X 0 -a· (X 0) un konstruē funkciju j 0 (a)=f(X 0 -a· (X 0))=(4a-2) 2 +4(8a-1) 2. Samazinot to, izmantojot nepieciešamo nosacījumu j 0 ¢(a)=8·(4a-2)+64·(8a-1)=0 atrodam soļa izmēra optimālo vērtību a 0 =5/34. Minimizācijas secības punkta noteikšana X 1 = X 0 -a 0 · (X 0) Diferencējamās funkcijas f(x) gradients punktā X sauca n- dimensiju vektors f(x)
, kuras komponentes ir funkcijas daļēji atvasinājumi f(x), punktā aprēķināts X, t.i. f"(x ) = (df(x)/dh 1 , …, df(x)/dx n) T . Šis vektors ir perpendikulārs plaknei, kas iet caur punktu X, un pieskares funkcijas līmeņa virsmai f(x), iet caur punktu X.Katrā šādas virsmas punktā funkcija f(x)ņem tādu pašu vērtību. Pielīdzinot funkciju dažādām konstantām vērtībām C 0 , C 1 , ..., iegūstam virkni virsmu, kas raksturo tās topoloģiju (2.8. att.). Gradienta vektors ir vērsts ātrākā funkcijas pieauguma virzienā dotajā punktā. Vektors pretējs gradientam (-f'(x))
, zvanīja pretgradients un ir vērsta uz ātrāko funkcijas samazināšanos. Minimālajā punktā funkcijas gradients ir nulle. Pirmās kārtas metodes, ko sauc arī par gradienta un minimizēšanas metodēm, ir balstītas uz gradientu īpašībām. Šo metožu izmantošana vispārīgā gadījumā ļauj noteikt funkcijas lokālo minimālo punktu. Acīmredzot, ja nav papildu informācijas, tad no sākuma punkta X ir prātīgi ķerties pie lietas X, kas atrodas antigradienta virzienā - ātrākais funkcijas samazinājums. Izvēloties kā nolaišanās virzienu R[k] pretgradients - f'(x[k] )
punktā X[k], iegūstam formas iteratīvu procesu X[ k+ 1] = x[k]-a k f"(x[k] )
,
un k > 0; k=0, 1, 2, ... Koordinātu formā šis process ir uzrakstīts šādi: x i [ k+1]=x i[k] - a kf(x[k] )
/x i i = 1, ..., n; k= 0, 1, 2,... Kā kritērijs iteratīvā procesa apturēšanai ir vai nu argumenta neliela pieauguma nosacījuma izpilde || x[k+l] -x[k] || <= e
,
либо выполнение условия малости градиента || f'(x[k+l] )
|| <= g
, Šeit e un g ir doti nelieli daudzumi. Ir iespējams arī kombinēts kritērijs, kas sastāv no noteikto nosacījumu vienlaicīgas izpildes. Gradienta metodes atšķiras viena no otras ar to, kā tās izvēlas soļa lielumu un k. Metodē ar nemainīgu soli visām iterācijām tiek izvēlēta noteikta nemainīga soļa vērtība. Diezgan mazs solis un k nodrošinās funkcijas samazināšanos, t.i., nevienlīdzību f(x[ k+1])
= f(x[k] – a k f’(x[k] ))
< f(x[k] )
. Tomēr tas var novest pie nepieciešamības veikt nepieņemami daudz atkārtojumu, lai sasniegtu minimālo punktu. No otras puses, pārāk liels solis var izraisīt negaidītu funkcijas pieaugumu vai izraisīt svārstības ap minimālo punktu (riteņbraukšana). Tā kā ir grūti iegūt nepieciešamo informāciju, lai izvēlētos soļa lielumu, metodes ar nemainīgiem soļiem praksē tiek izmantotas reti. Gradienti ir ekonomiskāki iterāciju skaita un uzticamības ziņā mainīgas soļu metodes, kad atkarībā no aprēķinu rezultātiem soļa lielums kaut kādā veidā mainās. Apskatīsim praksē izmantotos šādu metožu variantus. Izmantojot stāvākās nolaišanās metodi katrā iterācijā, soļa lielums un k ir izvēlēts no minimālā funkcijas nosacījuma f(x) nolaišanās virzienā, t.i. Šis nosacījums nozīmē, ka kustība pa antigradientu notiek tik ilgi, kamēr ir funkcijas vērtība f(x) samazinās. No matemātiskā viedokļa katrā iterācijā ir jāatrisina viendimensijas minimizēšanas problēma saskaņā ar A funkcijas Stāvākās nolaišanās metodes algoritms ir šāds. 1. Iestatiet sākuma punkta koordinātas X.
2. Punktā X[k],
k = 0, 1, 2, ... aprēķina gradienta vērtību f'(x[k])
. 3. Tiek noteikts pakāpiena izmērs a k, ar viendimensijas minimizēšanu virs A funkcijas j a) = f(x[k]-af"(x[k])).
4. Tiek noteiktas punkta koordinātas X[k+ 1]: x i [ k+ 1]= x i[k]– a k f’i (x[k]), i = 1,..., lpp. 5. Tiek pārbaudīti nosacījumi sterācijas procesa apturēšanai. Ja tie ir izpildīti, tad aprēķini apstājas. Pretējā gadījumā pārejiet uz 1. darbību. Apskatāmajā metodē kustības virziens no punkta X[k] pieskaras līmeņa līnijai punktā x[k+ 1] (2.9. att.). Nolaišanās trajektorija ir zigzagveida, un blakus esošās zigzaga saites ir ortogonālas viena pret otru. Patiešām, solis a k ir izvēlēts, samazinot ar A funkcijas? a) = f(x[k] -af"(x[k]))
. Nepieciešamais nosacījums funkcijas minimumam d j (a)/da = 0. Aprēķinot kompleksās funkcijas atvasinājumu, mēs iegūstam nosacījumu nolaišanās virzienu vektoru ortogonalitātei blakus punktos: dj (a)/da = -f’(x[k+ 1]f'(x[k])
= 0.
Gradienta metodes saplūst līdz minimumam lielā ātrumā (ģeometriskās progresēšanas ātrums), lai nodrošinātu vienmērīgas izliektas funkcijas. Šādām funkcijām ir vislielākā M un vismazāk m otro atvasinājumu matricas īpatnējās vērtības (Hesa matrica) maz atšķiras viens no otra, t.i., matrica N(x) labi kondicionēts. Atcerieties, ka īpašvērtības l i, i
=1, …, n, matricas ir raksturīgā vienādojuma saknes Tomēr praksē, kā likums, funkcijām, kas tiek minimizētas, ir slikti kondicionētas otro atvasinājumu matricas (t/m<<
1). Šādu funkciju vērtības dažos virzienos mainās daudz ātrāk (dažreiz par vairākām kārtām) nekā citos virzienos. To līdzenās virsmas vienkāršākā gadījumā ir stipri izstieptas (2.10. att.), un sarežģītākos gadījumos tās izliecas un izskatās pēc gravām. Funkcijas ar šādām īpašībām sauc noteka.Šo funkciju antigradienta virziens (sk. 2.10. att.) būtiski novirzās no virziena uz minimālo punktu, kas noved pie konverģences ātruma palēnināšanās. Gradientu metožu konverģences ātrums ir būtiski atkarīgs arī no gradienta aprēķinu precizitātes. Precizitātes zudums, kas parasti rodas minimālo punktu tuvumā vai notekcaurules situācijā, parasti var traucēt gradienta nolaišanās procesa konverģenci. Iepriekš minēto iemeslu dēļ problēmas risināšanas sākumposmā nereti tiek izmantotas gradienta metodes kombinācijā ar citām efektīvākām metodēm. Šajā gadījumā punkts X ir tālu no minimālā punkta, un soļi antigradienta virzienā ļauj panākt ievērojamu funkcijas samazināšanos. Iepriekš apskatītās gradienta metodes funkcijas minimālo punktu vispārīgā gadījumā atrod tikai bezgalīgā iterāciju skaitā. Konjugētā gradienta metode ģenerē meklēšanas virzienus, kas vairāk atbilst minimizējamās funkcijas ģeometrijai. Tas ievērojami palielina to konverģences ātrumu un ļauj, piemēram, samazināt kvadrātfunkciju f(x) = (x, Hx) + (b, x) + a ar simetrisku pozitīvu noteiktu matricu N ierobežotā soļu skaitā P, vienāds ar funkciju mainīgo skaitu. Jebkuru gludu funkciju minimālā punkta tuvumā var labi aproksimēt ar kvadrātfunkciju, tāpēc konjugētā gradienta metodes tiek veiksmīgi izmantotas, lai minimizētu nekvadrātiskās funkcijas. Šajā gadījumā tie pārstāj būt ierobežoti un kļūst iteratīvi. Pēc definīcijas divi n- dimensiju vektors X Un plkst sauca konjugēts attiecībā pret matricu H(vai H-konjugāts), ja skalārais reizinājums (x, Nu) = 0.Šeit N - simetriska pozitīva noteikta izmēra matrica P X P. Viena no būtiskākajām konjugētā gradienta metožu problēmām ir virzienu efektīvas konstruēšanas problēma. Flečera-Rīvesa metode atrisina šo problēmu, pārveidojot antigradientu katrā solī -f(x[k])
virzienā lpp[k],
H-konjugēt ar iepriekš atrastiem virzieniem R, R, ..., R[k-1]. Vispirms apskatīsim šo metodi saistībā ar minimizēšanas problēmu kvadrātiskā funkcija. Norādes R[k] aprēķina, izmantojot šādas formulas: p[ k] = -f'(x[k])
+b k-1 lpp[k-l], k>= 1; p = - f’(x)
. b vērtības k-1 ir izvēlēti tā, lai virzieni lpp[k], R[k-1] bija H- konjugāts :
(lpp[k], HP[k- 1])= 0.
Rezultātā kvadrātfunkcijai iteratīvajam minimizēšanas procesam ir forma x[ k+l] =x[k]+a k p[k], Kur R[k] -
nolaišanās virziens uz k- m solis; un k - soļa izmērs. Pēdējais ir izvēlēts no minimālā funkcijas nosacījuma f(x) Autors A kustības virzienā, t.i., viendimensionālās minimizācijas problēmas risināšanas rezultātā: f(x[ k] + a k r[k])
= f(x[k] + ar [k])
. Kvadrātiskajai funkcijai Flečera-Rīvesa konjugāta gradienta metodes algoritms ir šāds. 1. Punktā X aprēķināts lpp = -f'(x)
. 2. Ieslēgts k- m solis, izmantojot iepriekš minētās formulas, tiek noteikts solis A k .
un periods X[k+ 1]. 3. Tiek aprēķinātas vērtības f(x[k+1])
Un f'(x[k+1])
. 4. Ja f'(x)
= 0, tad punkts X[k+1] ir funkcijas minimālais punkts f(x). Pretējā gadījumā tiek noteikts jauns virziens lpp[k+l] no attiecības un tiek veikta pāreja uz nākamo iterāciju. Ar šo procedūru kvadrātiskās funkcijas minimums tiks atrasts ne vairāk kā P soļi. Samazinot nekvadrātiskās funkcijas, Flečera-Rīvesa metode kļūst iteratīva no ierobežotas. Šajā gadījumā pēc (p+ 1) 1.-4. procedūras atkārtojums tiek cikliski atkārtots ar nomaiņu X ieslēgts X[P+1] , un aprēķini beidzas ar , kur ir dots skaitlis. Šajā gadījumā tiek izmantotas šādas metodes modifikācijas: x[ k+l] = x[k]+a k p[k],
p[ k] = -f’(x[k])+
b k- 1 lpp[k-l], k>= 1; p = -f'( x); f(x[ k] + a k p[k])
= f(x[k] +ap[k];
Šeit es- daudzi indeksi: es= (0, n, 2 p, alga, ...), t.i., metode tiek atjaunināta katru reizi P soļi. Ģeometriskā nozīme Konjugētā gradienta metode ir šāda (2.11. att.). No dotā sākuma punkta X nolaišanās tiek veikta virzienā R = -f"(x). Punktā X tiek noteikts gradienta vektors f"(x). Tāpēc ka X ir funkcijas minimālais punkts virzienā R,
Tas f'(x)
ortogonāli vektoram R. Tad tiek atrasts vektors R , H- konjugēts ar R. Tālāk mēs atrodam funkcijas minimumu virzienā R utt. Konjugētā virziena metodes ir vienas no efektīvākajām minimizēšanas problēmu risināšanā. Tomēr jāņem vērā, ka tie ir jutīgi pret kļūdām, kas rodas skaitīšanas procesā. Izmantojot lielu skaitu mainīgo, kļūda var palielināties tik daudz, ka process būs jāatkārto pat kvadrātfunkcijai, t.i., process tai ne vienmēr iekļaujas P soļi. Stāvākā nolaišanās metode (angļu literatūrā “method of steepest descent”) ir iteratīva skaitliska metode (pirmās kārtas) optimizācijas uzdevumu risināšanai, kas ļauj noteikt mērķa funkcijas ekstrēmu (minimumu vai maksimumu): Saskaņā ar aplūkojamo metodi mērķa funkcijas ekstrēmu (maksimumu vai minimumu) nosaka funkcijas ātrākā pieauguma (samazinājuma) virzienā, t.i. funkcijas gradienta (pretgradienta) virzienā. Gradienta funkcija punktā kur i, j,…, n ir vienību vektori, kas ir paralēli koordinātu asīm. Gradients bāzes punktā Stāvākā nolaišanās metode ir tālākai attīstībai gradienta nolaišanās metode. Kopumā funkcijas ekstrēma atrašanas process ir iteratīva procedūra, kas tiek uzrakstīta šādi: kur "+" zīmi izmanto, lai atrastu funkcijas maksimumu, un "-" zīmi izmanto, lai atrastu funkcijas minimumu; Vienības virziena vektors, ko nosaka pēc formulas: Konstante, kas nosaka soļa lielumu un ir vienāda visiem i-tajiem virzieniem. Soļa lielumu izvēlas no mērķfunkcijas f(x) minimuma nosacījuma kustības virzienā, t.i., viendimensionālās optimizācijas problēmas risināšanas rezultātā gradienta jeb antigradienta virzienā: Citiem vārdiem sakot, soļa lielumu nosaka, atrisinot šo vienādojumu: Tādējādi aprēķina solis ir izvēlēts tāds, lai kustība tiktu veikta, līdz funkcija uzlabojas, tādējādi kādā brīdī sasniedzot ekstremitāti. Šajā brīdī atkal tiek noteikts meklēšanas virziens (izmantojot gradientu) un tiek meklēts jauns mērķa funkcijas optimālais punkts utt. Tādējādi šajā metodē meklēšana notiek lielākos soļos, un funkcijas gradients tiek aprēķināts mazākā punktu skaitā. Divu mainīgo funkcijas gadījumā šī metode ir šāda ģeometriskā interpretācija: kustības virziens no punkta pieskaras līmeņa līnijai punktā . Nolaišanās trajektorija ir zigzagveida, un blakus esošās zigzaga saites ir ortogonālas viena pret otru. Nosacījumu nolaišanās virzienu vektoru ortogonalitātei blakus punktos raksta ar šādu izteiksmi: Kustības trajektorija līdz galējam punktam, izmantojot stāvākās nolaišanās metodi, kas parādīta funkcijas f(x) vienāda līmeņa līnijas grafikā Optimālā risinājuma meklēšana beidzas, kad iteratīvā aprēķina posmā (vairāki kritēriji): Meklēšanas trajektorija paliek nelielā pašreizējā meklēšanas punkta apkārtnē: Mērķa funkcijas pieaugums nemainās: Mērķa funkcijas gradients lokālajā minimālajā punktā kļūst par nulli: Jāatzīmē, ka gradienta nolaišanās metode, pārvietojoties pa gravu, izrādās ļoti lēna, un, palielinoties mainīgo skaitam mērķa funkcijā, šī metodes uzvedība kļūst tipiska. Grava ir ieplaka, kuras līmeņu līnijas ir aptuveni elipses ar daudzkārt atšķirīgām pusasīm. Gravas klātbūtnē nolaišanās trajektorija izpaužas kā zigzaga līnija ar nelielu soli, kā rezultātā iegūtais nolaišanās ātrums līdz minimumam tiek ievērojami palēnināts. Tas izskaidrojams ar to, ka šo funkciju antigradienta virziens ievērojami novirzās no virziena uz minimālo punktu, kas rada papildu aizkavēšanos aprēķinā. Tā rezultātā algoritms zaudē skaitļošanas efektivitāti. Caurules funkcija Gradienta metode kopā ar tās daudzajām modifikācijām ir plaši izplatīta un efektīva metode pētāmo objektu optimālā meklēšana. Gradienta meklēšanas (kā arī iepriekš apskatīto metožu) trūkums ir tāds, ka, to izmantojot, var noteikt tikai funkcijas lokālo ekstrēmu. Lai atrastu citus vietējās galējības jāmeklē no citiem sākuma punktiem. Arī konverģences ātrums gradienta metodes arī būtiski atkarīgs no gradienta aprēķinu precizitātes. Precizitātes zudums, kas parasti rodas minimālo punktu tuvumā vai notekcaurules situācijā, parasti var traucēt gradienta nolaišanās procesa konverģenci. Aprēķina metode 1. darbība: Analītisku izteiksmju definīcija (simboliskā formā) funkcijas gradienta aprēķināšanai 2. darbība: iestatiet sākotnējo tuvinājumu 3. darbība: Tiek noteikta nepieciešamība restartēt algoritmisko procedūru, lai atiestatītu pēdējo meklēšanas virzienu. Restartēšanas rezultātā meklēšana atkal tiek veikta ātrākā nolaišanās virzienā.
.
f(x[k]–a k f’(x[k]))
= f(x[k] – af"(x[k]))
.
j a) = f(x[k]-af"(x[k]))
.
,
.
ir funkcijas argumenta vērtības (kontrolētie parametri) reālajā domēnā.ir vektors, kura projekcijas uz koordinātu asīm ir funkcijas daļējie atvasinājumi attiecībā pret koordinātām:
ir stingri ortogonāls pret virsmu, un tā virziens parāda ātrākā funkcijas pieauguma virzienu, un pretējais virziens (antigradients) attiecīgi parāda funkcijas ātrākās samazināšanās virzienu.
- gradienta modulis nosaka funkcijas pieauguma vai samazināšanās ātrumu gradienta vai antigradienta virzienā:
