Noteikumi funkcijas ievadīšanai
IN stāvākā nolaišanās metode par meklēšanas virzienu tiek izvēlēts vektors, kura virziens ir pretējs funkcijas ▽f(x) gradienta vektora virzienam. No matemātiskā analīze zināms, ka vektors grad f(x)=▽f(x) raksturo funkcijas ātrākā pieauguma virzienu (sk. funkcijas gradientu). Tāpēc tiek izsaukts vektors - grad f (X) = -▽f(X). pretgradients un ir tā straujākā samazinājuma virziens. Atkārtošanās sakarībai, ar kuru tiek realizēta stāvākā nolaišanās metode, ir forma X k +1 =X k - λ k ▽f(x k), k = 0,1,...,
kur λ k > 0 ir soļa izmērs. Atkarībā no pakāpiena izmēra izvēles jūs varat iegūt dažādas iespējas gradienta metode. Ja optimizācijas procesā tiek fiksēts soļa lielums λ, tad metodi sauc par gradienta metodi ar diskrētu soli. Optimizācijas procesu pirmajās iterācijās var ievērojami paātrināt, ja λ k ir izvēlēts no nosacījuma λ k =min f(X k + λS k) .
Lai noteiktu λ k, tiek izmantota jebkura viendimensijas optimizācijas metode. Šajā gadījumā metodi sauc par stāvākās nolaišanās metodi. Kā likums, iekšā vispārējs gadījums Ar vienu soli nepietiek, lai sasniegtu funkcijas minimumu, process tiek atkārtots, līdz nākamie aprēķini ļauj rezultātu uzlabot.
Ja telpa dažos mainīgajos ir ļoti iegarena, tad veidojas “grava”. Meklēšana var palēnināties un virzīties zigzagā pāri “gravas” apakšai. Dažreiz risinājumu nevar iegūt pieņemamā laika posmā.
Vēl viens metodes trūkums var būt apturēšanas kritērijs ||▽f(X k)||<ε k , так как этому условию удовлетворяет и седловая точка, а не только оптимум.
Piemērs. Sākot no punkta x k =(-2, 3), nosakiet punktu x k +1, izmantojot stāvākās nolaišanās metodi, lai samazinātu funkciju.
Kā meklēšanas virzienu atlasiet gradienta vektoru pašreizējā punktā 
Pārbaudīsim apstāšanās kritēriju. Mums ir 
Aprēķināsim funkcijas vērtību sākuma punktā f(X 1) = 35. Darīsim
soli pa antigradienta virzienu
Aprēķināsim funkcijas vērtību jaunā punktā
f(X 2) = 3 (-2 + 19 λ 1) 2 + (3-8 λ 1) 2 - (-2 + 19 λ 1) (3-8 λ 1) - 4 (-2 + 19 λ 1)
Atradīsim tādu soli, lai mērķa funkcija šajā virzienā sasniegtu minimumu. No nepieciešamā nosacījuma funkcijas ekstrēma pastāvēšanai
f’(X 2) = 6 (-2 + 19λ 1) 19 + 2 (3-8λ 1) (-8) - (73 - 304 λ 1) - 4*19
vai f’(X 2) = 2598 λ 1 – 425 = 0.
Mēs iegūstam soli λ 1 = 0,164
Šīs darbības pabeigšana novedīs pie lietas 
kurā gradienta vērtība 
, funkcijas vērtība f(X 2) = 0,23. Precizitāte netiek sasniegta, no punkta mēs speram soli pa antigradienta virzienu.
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,0)
f’(X 2) = 11,76–6,12λ 1 = 0
Mēs iegūstam λ 1 = 0,52 
Problēmas formulēšana
Lai funkcija ir dota f(x) Rn
Obligāti f(x) X = Rn
Meklēšanas stratēģija
x k
} , k = 0,1,...,
tāds, ka 
, k = 0,1,...
. Secības punkti ( x k
) tiek aprēķināti saskaņā ar noteikumu
kur ir jēga x 0 lietotājs definēts; soļa izmērs tk nosaka katrai vērtībai k no stāvokļa
Problēmu (3) var atrisināt, izmantojot nepieciešamo minimālo nosacījumu, kam seko pietiekamā minimālā nosacījuma pārbaude. Šo ceļu var izmantot vai nu ar pietiekami vienkāršu funkciju, lai to samazinātu, vai ar pietiekami provizorisku tuvinājumu sarežģīta funkcija 
polinoms P(t k)
(parasti otrās vai trešās pakāpes), un tad nosacījums tiek aizstāts ar nosacījumu un nosacījums tiek aizstāts ar nosacījumu 
Secība (xk)
beidzas punktā x k
, par kuru , kur ε
- dots neliels pozitīvs skaitlis vai k ≥ M
, Kur M
- ierobežojošs atkārtojumu skaits vai ar divām vienlaicīgām divu nevienādību izpildi 
, 
Kur ε 2
- mazs pozitīvs skaitlis. Jautājums ir, vai punkts var x k
tiek uzskatīts par vēlamā lokālā minimālā punkta atrasto tuvinājumu x*
, tiek atrisināts, veicot papildu pētījumus.
Metodes ģeometriskā interpretācija priekš n=2 attēlā. 4.
Koordinātu nolaišanās metode
Problēmas formulēšana
Lai funkcija ir dota f(x) , kas ierobežota zemāk par komplektu Rn un ar nepārtrauktiem daļējiem atvasinājumiem visos tā punktos.
f(x) par iespējamo risinājumu kopumu X = Rn , t.i. atrast tādu punktu
Meklēšanas stratēģija
Problēmas risināšanas stratēģija ir punktu secības izveidošana ( x k
} , k = 0,1,...,
tāds, ka , k = 0,1,...
. Secības punkti ( x k
) tiek aprēķināti pa cikliem saskaņā ar noteikumu
(4)
Kur j - aprēķinu cikla numurs; j = 0,1,2,...; k - iterācijas numurs cilpas iekšpusē, k = 0,1,... ,n - 1; e k +1 , k = 0,l,...,n - 1 - vienības vektors, (k+1) -kuras projekcija ir vienāda ar 1; punkts x 00 lietotāja definēts, soļa lielums tk ir izvēlēts no nosacījuma
vai 
.
Ja izvēlētais stāvoklis pie pašreizējā tk
nav izpildīts, solis ir uz pusi un punkts 
tiek aprēķināts vēlreiz. Ir viegli redzēt, ka fiksētam j vienā iterācijā ar skaitli k
mainās tikai viena punkta projekcija x jk
, kam ir numurs k+1
, un visa cikla laikā ar numuru j
, t.i. sākot ar k = 0
un beidzas k = n -1
, visas n punkta projekcijas mainās x j0
. Pēc šī punkta x j n
numurs ir piešķirts x j + 1,0
, un tas tiek ņemts par sākumpunktu aprēķiniem j+1
cikls. Aprēķins beidzas punktā x jk
ja ir izpildīts vismaz viens no trim uzskaites beigu kritērijiem: 
, vai , vai nevienlīdzību dubulta izpilde.
Aprēķinu rezultātā iegūtos punktus var ierakstīt kā secības elementus (xl), Kur l=n*j+k - punkta sērijas numurs,
Metodes ģeometriskā interpretācija n = 2 ir parādīta attēlā. 5.
4. Franka-Volfa metode .
Pieņemsim, ka mums jāatrod ieliektas funkcijas maksimālā vērtība
Apstākļos
Šīs problēmas raksturīga iezīme ir tā, ka tās ierobežojumu sistēma satur tikai lineāras nevienādības. Šī īpašība ir pamats, lai pētāmā punkta tuvumā aizstātu nelineāro mērķa funkcija lineārs, kura dēļ sākotnējās problēmas risinājums tiek reducēts uz lineārās programmēšanas uzdevumu secīgu risinājumu.
Problēmas risinājuma atrašanas process sākas ar punkta identificēšanu, kas pieder problēmas iespējamo risinājumu reģionam.
270
vasarnīcas Lai tas būtu galvenais X(k)
tad šajā punktā tiek aprēķināts funkcijas (57) gradients
Un izveidojiet lineāru funkciju
Pēc tam atrodiet šīs funkcijas maksimālo vērtību saskaņā ar ierobežojumiem (58) un (59). Lai šīs problēmas risinājumu nosaka punkts Z(k)
. Tad punkta koordinātas tiek pieņemtas kā jauns iespējamais sākotnējās problēmas risinājums X(k+1)
:
Kur λk - noteikts skaitlis, ko sauc par aprēķina soli un atrodas starp nulli un vienu (0<λk < 1). Это число λk pieņemts patvaļīgi vai noteikts
lai funkcijas vērtība punktā X (k +1) f (X (k +1)) , atkarībā no λk , bija maksimums. Lai to izdarītu, jums jāatrod vienādojuma risinājums un jāizvēlas tā mazākā sakne. Ja tā vērtība ir lielāka par vienu, tad mums vajadzētu likt λk=1 . Pēc skaitļa noteikšanas λk atrast punkta koordinātas X(k+1) aprēķināt tajā esošās mērķa funkcijas vērtību un noteikt nepieciešamību pāriet uz jaunu punktu X(k+2) . Ja ir tāda vajadzība, tad parēķiniet punktā X(k+1) Mērķa funkcijas gradientu, dodieties uz atbilstošo lineārās programmēšanas uzdevumu un atrodiet tās risinājumu. Nosakiet punkta koordinātas un X(k+2) un izpētīt vajadzību pēc turpmākiem aprēķiniem. Pēc noteikta soļu skaita tiek iegūts sākotnējās problēmas risinājums ar nepieciešamo precizitāti.
Tātad problēmas (57) - (59) risinājuma atrašanas process, izmantojot Frank-Wolfe metodi, ietver šādus posmus:
1. Nosakiet sākotnējo iespējamo problēmas risinājumu.
2. Atrodiet funkcijas (57) gradientu pieļaujamā risinājuma punktā.
3. Konstruējiet funkciju (60) un atrodiet tās maksimālo vērtību apstākļos (58) un (59).
4. Nosakiet aprēķina soli.
5. Izmantojot formulas (61), tiek atrastas jauna iespējama risinājuma sastāvdaļas.
6. Pārbaudiet nepieciešamību pāriet uz nākamo iespējamo risinājumu. Ja nepieciešams, pārejiet uz 2. posmu, pretējā gadījumā tiek atrasts pieņemams sākotnējās problēmas risinājums.
Soda funkciju metode.
Apsveriet ieliektās funkcijas maksimālās vērtības noteikšanas problēmu
f (x 1, x 2, .... x n) apstākļos g i (x 1, x 2, .... x n) ≤ b i (i=l, m) , x j ≥ 0 (j=1, n) , Kur g i (x 1, x 2, .... x n) - izliektas funkcijas.
Tā vietā, lai tieši atrisinātu šo problēmu, atrodiet funkcijas maksimālo vērtību F(x 1, x 2, ...., x n)= f(x 1, x 2, ...., x n) +H(x 1, x 2, ...., x n) kas ir problēmas mērķa funkcijas un kādas funkcijas summa
H(x 1, x 2, ...., x n), ko nosaka ierobežojumu sistēma un sauc soda funkcija. Soda funkciju var konstruēt dažādos veidos. Tomēr visbiežāk tā izskatās
A a i > 0
- daži nemainīgi skaitļi, kas atspoguļo svēruma koeficientus.
Izmantojot soda funkciju, tie secīgi pārvietojas no viena punkta uz otru, līdz iegūst pieņemamu risinājumu. Šajā gadījumā nākamā punkta koordinātas tiek atrastas, izmantojot formulu
No pēdējās attiecības izriet, ka, ja iepriekšējais punkts atrodas sākotnējās problēmas iespējamo risinājumu apgabalā, tad otrais vārds kvadrātiekavās ir vienāds ar nulli un pāreju uz nākamo punktu nosaka tikai mērķa gradients. funkciju. Ja norādītais punkts neietilpst pieļaujamo risinājumu apgabalā, tad šī termiņa dēļ turpmākajās iterācijās tiek panākta atgriešanās pie pieļaujamo risinājumu apgabala
lēmumus. Tajā pašā laikā, jo mazāk a i
, jo ātrāk tiek atrasts pieņemams risinājums, bet tā noteikšanas precizitāte samazinās. Tāpēc iteratīvais process parasti sākas ar salīdzinoši mazām vērtībām a i
un, to turpinot, šīs vērtības pakāpeniski palielinās.
Tātad izliektas programmēšanas problēmas risinājuma atrašanas process, izmantojot soda funkcijas metodi, ietver šādas darbības:
1. Nosakiet sākotnējo iespējamo risinājumu.
2. Izvēlieties aprēķina soli.
3. Atrodiet visiem mainīgajiem mērķa funkcijas daļējos atvasinājumus un funkcijas, kas nosaka problēmas iespējamo risinājumu diapazonu.
4. Izmantojot formulu (72), tiek atrastas punkta koordinātas, kas nosaka iespējamo jaunu problēmas risinājumu.
5. Pārbaudiet, vai atrastā punkta koordinātas apmierina problēmu ierobežojumu sistēmu. Ja nē, pārejiet uz nākamo posmu. Ja atrastā punkta koordinātas nosaka pieļaujamo problēmas risinājumu, tad tiek pētīta nepieciešamība pāriet uz nākamo pieļaujamo risinājumu. Ja nepieciešams, pārejiet uz 2. posmu, pretējā gadījumā ir atrasts pieņemams sākotnējās problēmas risinājums.
6. Iestatiet svēršanas koeficientu vērtības un pārejiet uz 4. darbību.
Bultas-Hurvica metode.
Meklējot risinājumus nelineārās programmēšanas problēmām, izmantojot soda funkcijas metodi, mēs izvēlējāmies vērtības a i , patvaļīgi, kas izraisīja ievērojamas svārstības noteikto punktu attālumā no iespējamo risinājumu reģiona. Šis trūkums tiek novērsts, risinot problēmu ar Arrow-Hurwitz metodi, saskaņā ar kuru nākamajā solī skaitļi a i (k) aprēķina pēc formulas
Kā sākotnējās vērtības a i (0) ņem patvaļīgus nenegatīvus skaitļus.
RISINĀJUMA PIEMĒRS
1. piemērs.
Atrodiet funkcijas lokālo minimumu
Punkta noteikšana x k
1. Uzstādām .
2. Liekam k = 0 .
trīsdesmit . Aprēķināsim
4 0 . Aprēķināsim 
. Pāriesim uz 5. darbību.
50 . Pārbaudīsim stāvokli 
. Pāriesim uz 6. darbību.
6 0 . Uzstādām t0 = 0,5 .
7 0 . Aprēķināsim
8 0 . Salīdzināsim 
. Mums ir 
. Secinājums: nosacījums k = 0
netiek izpildīts. Uzstādām t0 = 0,25
, turpiniet ar 7., 8. darbību atkārtošanu.
7 01. Aprēķināsim.
8 01. Salīdzināsim f (x 1) un f (x 0) . Secinājums: f (x 1)< f (x 0) . Pārejam uz 9. darbību.
9 0 . Aprēķināsim
Secinājums: mēs ticam k =1 un pārejiet uz 3. darbību.
3 1. Aprēķināsim
4 1. Aprēķināsim 
. Pāriesim uz 5. darbību.
5 1. Pārbaudīsim stāvokli k ≥ M: k = 1< 10 = M . Pāriesim uz 6. darbību.
6 1. Uzstādām t 1 = 0,25.
7 1. Aprēķināsim
8 1. Salīdzināsim f (x 2) ar f (x 1) . Secinājums: f (x 2)< f (х 1). Pārejam uz 9. darbību.
9 1. Aprēķināsim
Secinājums: mēs ticam k = 2 un pārejiet uz 3. darbību.
3 2. Aprēķināsim
4 2. Aprēķināsim. Pāriesim uz 5. darbību.
5 2. Pārbaudīsim stāvokli k ≥ M : k = 2< 10 = М , pārejiet uz 6. darbību.
6 2. Uzstādām t 2 =0,25 .
7 2. Aprēķināsim
8 2. Salīdzināsim f (x 3) Un f (x 2) . Secinājums: f (x 3)< f (х 2) .Pāriet uz 9. darbību.
9 2. Aprēķināsim 
Secinājums: mēs ticam k = 3 un pārejiet uz 3. darbību.
3 3 . Aprēķināsim
4 3 . Aprēķināsim. Pāriesim uz 5. darbību.
5 3. Pārbaudīsim stāvokli k ≥ M : k = 3<10 = М , pārejiet uz 6. darbību.
6 3. Uzstādām t 3 = 0,25.
7 3. Aprēķināsim
8 3. Salīdzināsim f (x 4) Un f (x 3) : f (x 4)< f (х 3) .
9 3. Aprēķināsim 
Nosacījumi ir izpildīti, kad k = 2,3 . Aprēķins
pabeigts. Punkts atrasts
Attēlā 3 iegūtie punkti ir savienoti ar punktētu līniju.
II. Punktu analīze x 4 .
Funkcija 
ir divreiz diferencējams, tāpēc punktā pārbaudīsim pietiekamus nosacījumus minimumam x 4
. Lai to izdarītu, analizēsim Hesenes matricu.
Matrica ir nemainīga un pozitīva noteikta (t.i. . H > 0
), jo abi tā leņķiskie nepilngadīgie ir pozitīvi. Tāpēc punkts 
ir atrastā vietējā minimālā punkta aproksimācija un vērtība 
ir atrastais vērtības tuvinājums f (x *) =0
. Ņemiet vērā, ka nosacījums H > 0
, tajā pašā laikā pastāv nosacījums stingrai funkcijas izliekumam 
. Līdz ar to ir atrasti globālā minimuma punkta tuvinājumi f(x)
un tā minimālā vērtība pie R 2
. ■
2. piemērs
Atrodiet funkcijas lokālo minimumu
I. Punkta definīcija x k, kurā ir izpildīts vismaz viens no aprēķinu pabeigšanas kritērijiem.
1. Uzstādām .
Atradīsim funkcijas gradientu patvaļīgā punktā
2. Liekam k = 0 .
trīsdesmit . Aprēķināsim
4 0 . Aprēķināsim . Pāriesim uz 5. darbību.
50 . Pārbaudīsim stāvokli 
. Pāriesim uz 6. darbību.
6° Nākamais punkts tiek atrasts pēc formulas
Aizstāsim iegūtās izteiksmes koordinātas uz
Atradīsim funkcijas minimumu f(t 0) Autors t 0 izmantojot nepieciešamos nosacījumus beznosacījuma galējībai:
No šejienes t 0 =0,24
. Jo 
, atrastā soļa vērtība nodrošina funkcijas minimumu f(t 0)
Autors t 0
.
Definēsim 
7 0 . Mēs atradīsim
8°. Aprēķināsim
Secinājums: mēs ticam k = 1 un pārejiet uz 3. darbību.
3 1. Aprēķināsim
4 1. Aprēķināsim 
5 1. Pārbaudīsim stāvokli k ≥ 1: k = 1< 10 = М.
6 1. Definēsim
7 1. Mēs atradīsim 
:
8 1. Aprēķināsim
Mēs ticam k = 2 un pārejiet uz 3. darbību.
3 2. Aprēķināsim
4 2. Aprēķināsim
5 2. Pārbaudīsim stāvokli k ≥ M: k = 2< 10 = M .
6 2. Definēsim
7 2. Mēs atradīsim 
8 2. Aprēķināsim
Mēs ticam k =3 un pārejiet uz 3. darbību.
3 3 . Aprēķināsim
4 3 . Aprēķināsim.
Aprēķins ir pabeigts. Punkts atrasts
II. Punktu analīze x 3 .
Piemērā 1.1 (2. nodaļa 1. punkts) tika parādīts, ka funkcija f(x) ir stingri izliekta, un tāpēc punktos3 ir atrastā globālā minimālā punkta tuvinājums X* .
3. piemērs.
Atrodiet funkcijas lokālo minimumu
I. Punkta definīcija xjk , kurā ir izpildīts vismaz viens no aprēķinu pabeigšanas kritērijiem.
1. Uzstādām
Atradīsim funkcijas gradientu patvaļīgā punktā 
2. Uzstādām j = 0.
trīsdesmit . Pārbaudīsim, vai nosacījums ir izpildīts
4 0 . Uzstādām k = 0.
50 . Pārbaudīsim, vai nosacījums ir izpildīts
6 0 . Aprēķināsim
7 0 . Pārbaudīsim stāvokli 
8 0 . Uzstādām
9 0 . Aprēķināsim 
, Kur
100 . Pārbaudīsim stāvokli
Secinājums: mēs pieņemam un pārejam uz 9. darbību.
9 01. Aprēķināsim x 01 pakāpēs
10 01. Pārbaudīsim stāvokli 
11 0 . Pārbaudīsim nosacījumus
Mēs ticam k =1 un pārejiet uz 5. darbību.
5 1. Pārbaudīsim stāvokli
6 1. Aprēķināsim
7 1. Pārbaudīsim stāvokli
8 1. Uzstādām
9 1. Aprēķināsim
10 1. Pārbaudīsim stāvokli 
:
11 1. Pārbaudīsim nosacījumus
Mēs ticam k = 2 , pārejiet uz 5. darbību.
5 2. Pārbaudīsim stāvokli. Iestatīsim, pārejiet uz 3. darbību.
3 1. Pārbaudīsim stāvokli
4 1. Uzstādām k = 0.
5 2. Pārbaudīsim stāvokli
6 2. Aprēķināsim
7 2. Pārbaudīsim stāvokli
8 2. Uzstādām
9 2. Aprēķināsim
10 2. Pārbaudīsim stāvokli 
11 2. Pārbaudīsim nosacījumus
Mēs ticam k =1 un pārejiet uz 5. darbību.
5 3. Pārbaudīsim stāvokli
6 3. Aprēķināsim
7 3. Pārbaudīsim nosacījumus
8 3. Uzstādām
9 3. Aprēķināsim
10 3. Pārbaudīsim stāvokli 
11 3. Pārbaudīsim nosacījumus
Uzstādām k = 2 un pārejiet uz 5. darbību.
5 4 . Pārbaudīsim stāvokli 
Mēs ticam j = 2, x 20 = x 12 un pārejiet uz 3. darbību.
3 2. Pārbaudīsim stāvokli
4 2. Uzstādām k =0 .
5 4 . Pārbaudīsim stāvokli
6 4. Aprēķināsim
7 4. Pārbaudīsim stāvokli
8 4. Uzstādām
9 4. Aprēķināsim
10 4. Pārbaudīsim stāvokli un pāriesim uz 11. darbību.
11 4. Pārbaudīsim nosacījumus
Nosacījumi tiek izpildīti divos secīgos ciklos ar skaitļiem j = 2 Un j -1 = 1 . Aprēķins pabeigts, punkts atrasts
Attēlā 6 iegūtie punkti ir savienoti ar punktētu līniju.
Koordinātu nolaišanās metodē mēs nolaižamies pa lauztu līniju, kas sastāv no taisniem segmentiem, kas ir paralēli koordinātu asīm.
II. Punkta x21 analīze.
Piemērā 1.1 tika parādīts, ka funkcija f(x)
ir stingri izliekta, tai ir unikāls minimums un līdz ar to punkts 
ir atrastā globālā minimālā punkta tuvinājums.
Visās iepriekš apskatītajās gradienta metodēs punktu secība (xk) saplūst uz funkcijas stacionāro punktu f(x) ar diezgan vispārīgiem priekšlikumiem par šīs funkcijas īpašībām. Konkrēti, teorēma ir patiesa:
Teorēma. Ja funkcija f(x) ir ierobežota zemāk, tās gradients apmierina Lipšica nosacījumu () un vērtības izvēli tn ko ražo ar kādu no iepriekš aprakstītajām metodēm, neatkarīgi no sākuma punkta x 0 :
plkst.
Shēmas praktiskajā īstenošanā
k = 1, 2, … n.
iterācijas apstājas, ja visiem i, i = 1, 2, ..., n , tādi apstākļi kā
,
kur ir noteikts skaitlis, kas raksturo minimuma atrašanas precizitāti.
Teorēmas apstākļos gradienta metode nodrošina funkcijas konverģenci vai precīzu apakšējo robežu (ja funkcija f(x) nav minimuma; rīsi. 7), vai funkcijas vērtībai kādā stacionārā punktā, kas ir secības robeža (x k). Nav grūti izdomāt piemērus, kad šajā brīdī tiek realizēts segls, nevis minimums. Praksē gradienta nolaišanās metodes pārliecinoši apiet seglu punktus un atrod mērķa funkcijas minimumus (vispārējā gadījumā lokālos).
SECINĀJUMS
Gradienta neierobežotas optimizācijas metožu piemēri tika apspriesti iepriekš. Paveiktā darba rezultātā var izdarīt šādus secinājumus:
1. Vairāk vai mazāk sarežģītu problēmu risināšanai ekstrēma atrašanā ierobežojumu klātbūtnē nepieciešama īpaša pieeja un metodes.
2. Daudzi algoritmi ierobežotu problēmu risināšanai ietver neierobežotu minimizēšanu kā kādu soli.
3. Dažādas metodes nolaišanās atšķiras viena no otras ar to, kā tiek izvēlēts nolaišanās virziens un soļa garums šajā virzienā.
4. Pagaidām nav teorijas, kas ņemtu vērā kādas funkcijas, kas raksturo problēmas formulējumu, iezīmes. Priekšroka jādod metodēm, kuras ir vieglāk pārvaldāmas problēmas risināšanas procesā.
Reālas lietišķās optimizācijas problēmas ir ļoti sarežģītas. Mūsdienu metodes optimizācijas ne vienmēr tiek galā ar reālu problēmu risināšanu bez cilvēka palīdzības.
BIBLIOGRĀFIJA
1. Kosorukovs O.A. Operāciju izpēte: mācību grāmata. 2003. gads
2. Pantļejevs A.V. Optimizācijas metodes piemēros un uzdevumos: mācību grāmata. Ieguvums. 2005. gads
3. Šiškins E.V. Operāciju izpēte: mācību grāmata. 2006. gads
4. Akulich I.L. Matemātiskā programmēšana piemēros un uzdevumos. 1986. gads
5. Ventzel E.S. Operāciju izpēte. 1980. gads
6. Ventzels E.S., Ovčarovs L.A. Varbūtību teorija un tās inženiertehniskie pielietojumi. 1988. gads
©2015-2019 vietne
Visas tiesības pieder to autoriem. Šī vietne nepretendē uz autorību, bet nodrošina bezmaksas lietošana.
Lapas izveides datums: 2017-07-02
Anotācija: Šī lekcija plaši aptver tādas daudzparametru optimizācijas metodes kā stāvākā nolaišanās metode un Davidona–Flečera–Pauela metode. Papildus tiek veikta augstāk minēto metožu salīdzinošā analīze, lai noteiktu efektīvāko, identificētas to priekšrocības un trūkumi; un arī aplūko daudzdimensiju optimizācijas problēmas, piemēram, gravu metodi un daudzekstrēmālo metodi.
1. Stāvākā nolaišanās metode
Būtība šī metode tas ir, izmantojot iepriekš minēto koordinātu nolaišanās metode meklēšana tiek veikta no dots punkts virzienā, kas ir paralēls vienai no asīm, līdz minimālajam punktam šajā virzienā. Pēc tam meklēšanu veic virzienā, kas ir paralēls otrai asij utt. Norādes, protams, ir fiksētas. Šķiet saprātīgi mēģināt modificēt šo metodi tā, lai katrā posmā minimālā punkta meklēšana tiktu veikta "labākajā" virzienā. Nav skaidrs, kurš virziens ir "labākais", taču tas ir zināms gradienta virziens ir funkcijas ātrākā pieauguma virziens. Tāpēc pretējais virziens ir funkcijas ātrākās samazināšanās virziens. Šo īpašumu var attaisnot šādi.
Pieņemsim, ka mēs virzāmies no punkta x uz nākamo punktu x + hd, kur d ir noteikts virziens un h ir noteikta garuma solis. Līdz ar to kustība tiek veikta no punkta (x 1, x 2, ..., x n) uz punktu (x 1 + zx 1, x 2 + zx 2, ..., x n + zx n), Kur
Funkciju vērtību izmaiņas nosaka attiecības
| (1.3) |
Līdz pirmās kārtas zx i , daļējos atvasinājumus aprēķina punktā x . Kā jāizvēlas virzieni d i, kas apmierina (1.2) vienādojumu, lai iegūtu lielāko funkcijas df izmaiņu vērtību? Šeit rodas maksimizācijas problēma ar ierobežojumu. Pielietosim Lagranža reizinātāju metodi, ar kuras palīdzību nosakām funkciju
Vērtība df atbilst ierobežojuma (1.2) sasniedz maksimumu, kad funkcija
Sasniedz maksimumu. Tā atvasinājums
Tāpēc
 |
(1.6) |
Tad di ~ df/dx i un virziens d ir paralēls virzienam V/(x) punktā x.
Tādējādi lielākais vietējais pieaugums funkcija noteiktam mazam solim h notiek, ja d ir Vf(x) vai g(x) virziens. Tāpēc stāvākās nolaišanās virziens ir virziens
Vairāk vienkāršā formā vienādojumu (1.3) var uzrakstīt šādi:
Kur ir leņķis starp vektoriem Vf(x) un dx. Priekš dotā vērtība dx mēs minimizējam df, izvēloties, ka dx virziens sakrīt ar virzienu -Vf(x) .
komentēt. Gradienta virziens perpendikulāri jebkuram nemainīga līmeņa līnijas punktam, jo šajā taisnē funkcija ir nemainīga. Tādējādi, ja (d 1, d 2, ..., d n) ir mazs solis pa līmeņa līniju, tad
Un tāpēc
 |
(1.8) |
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, 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. 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 . Stohastisks gradienta nolaišanās ir viena no stohastiskās tuvināšanas formām. 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.
Izmantojot stāvākās nolaišanās metodi katrā iterācijā, soļa lielums A k ir izvēlēts no minimālā funkcijas nosacījuma f(x) nolaišanās virzienā, t.i.
f(x[k] -a k f"(x[k])) = f(x[k] -af"(x[k])) .
Š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
j a) = f(x[k]-af"(x[k])) .
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])) . Priekšnoteikums minimālā funkcija 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:
d j (a)/da = -f"(x[k+ 1]f"(x[k]) = 0.
Rīsi. 2.9.
Gradienta metodes saplūst līdz minimumam ar liels ātrums(ar ātrumu ģeometriskā progresija) gludām izliektām funkcijām. Šā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. Atgādināsim jums to īpašvērtības es, 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.
Rīsi. 2.10.
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.
