Gjeni pikën e palëvizshme të funksionit duke përdorur metodën e zbritjes më të pjerrët. Metoda e zbritjes më të pjerrët

Rregullat për futjen e një funksioni

NË metoda më e pjerrët e zbritjes si drejtim i kërkimit zgjidhet një vektor, drejtimi i të cilit është i kundërt me drejtimin e vektorit të gradientit të funksionit ▽f(x). Nga analiza matematikore dihet se vektori grad f(x)=▽f(x) karakterizon drejtimin e rritjes më të shpejtë të funksionit (shih gradientin e funksionit). Prandaj thirret vektori - grad f (X) = -▽f(X). anti-gradient dhe është drejtimi i rënies më të shpejtë të tij. Lidhja e përsëritjes me të cilën zbatohet metoda e zbritjes më të pjerrët ka formën X k +1 =X k - λ k ▽f(x k), k = 0,1,...,
ku λ k >0 është madhësia e hapit. Në varësi të zgjedhjes së madhësisë së hapit, mund të merrni opsione të ndryshme për metodën e gradientit. Nëse gjatë procesit të optimizimit është fiksuar madhësia e hapit λ, atëherë metoda quhet metoda e gradientit me një hap diskret. Procesi i optimizimit në përsëritjet e para mund të përshpejtohet ndjeshëm nëse λ k zgjidhet nga kushti λ k =min f(X k + λS k) .
Për të përcaktuar λ k, përdoret çdo metodë optimizimi njëdimensionale. Në këtë rast, metoda quhet metoda më e pjerrët e zbritjes. Si rregull, në rastin e përgjithshëm, një hap nuk mjafton për të arritur minimumin e funksionit, procesi përsëritet derisa llogaritjet pasuese të përmirësojnë rezultatin.
Nëse hapësira është shumë e zgjatur në disa variabla, atëherë formohet një "gropë". Kërkimi mund të ngadalësohet dhe të kalojë me zigzag në fund të "gropës". Ndonjëherë një zgjidhje nuk mund të merret brenda një afati kohor të pranueshëm.
Një tjetër disavantazh i metodës mund të jetë kriteri i ndalimit ||▽f(X k)||<ε k , так как этому условию удовлетворяет и седловая точка, а не только оптимум.

Shembull. Duke u nisur nga pika x k =(-2, 3), përcaktoni pikën x k +1 duke përdorur metodën e zbritjes më të pjerrët për të minimizuar funksionin.
Si drejtim kërkimi, zgjidhni vektorin e gradientit në pikën aktuale

Le të kontrollojmë kriterin e ndalimit. Ne kemi
Le të llogarisim vlerën e funksionit në pikën fillestare f(X 1) = 35. Le të bëjmë
hap përgjatë drejtimit antigradient

Le të llogarisim vlerën e funksionit në një pikë të re
f(X 2) = 3(-2 + 19λ 1) 2 + (3-8λ 1) 2 - (-2 + 19λ 1)(3-8λ 1) - 4(-2 + 19λ 1)
Le të gjejmë një hap të tillë që funksioni objektiv të arrijë një minimum përgjatë këtij drejtimi. Nga kushti i domosdoshëm për ekzistimin e një ekstremi të funksionit
f’(X 2) = 6(-2 + 19λ 1) 19 + 2(3-8λ 1)(-8) – (73 - 304 λ 1) – 4*19
ose f’(X 2) = 2598 λ 1 – 425 = 0.
Marrim hapin λ 1 = 0,164
Përfundimi i këtij hapi do të çojë në pikën

në të cilën vlera e gradientit , vlera e funksionit f(X 2) = 0,23. Saktësia nuk arrihet, nga momenti kur bëjmë një hap përgjatë drejtimit të antigradientit.

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λ)
f’(X 2) = 11,76 – 6,12λ 1 = 0
Marrim λ 1 = 0,52

Shembulli 6.8.3-1. Gjeni minimumin e funksionit Q(x,y) duke përdorur metodën GDS.

Le të Q(x,y) = x 2 +2y 2 ; x 0 = 2; y 0 = 1.

Le të kontrollojmë kushtet e mjaftueshme për ekzistencën e një minimumi:

Le të bëjmë një përsëritje sipas algoritmit.

1. Q(x 0,y 0) = 6.

2. Për x = x 0 dhe y = y 0,

3. Hapi l k = l 0 = 0,5

Pra 4< 8, следовательно, условие сходимости не выполняется и требуется, уменьшив шаг (l=l /2), повторять п.п.3-4 до выполнения условия сходимости. То есть, полученный шаг используется для нахождения следующей точки траектории спуска.

Thelbi i metodës është si më poshtë. Nga pika e zgjedhur (x 0 ,y 0) zbritja kryhet në drejtim të antigradientit derisa të arrihet vlera minimale e funksionit objektiv Q(x, y) përgjatë rrezes (Fig. 6.8.4-1). . Në pikën e gjetur, rrezja prek vijën e nivelit. Më pas, nga kjo pikë, zbritja kryhet në drejtim të antigradientit ( pingul me vijën e nivelit) derisa rrezja përkatëse të prekë vijën e nivelit që kalon nëpër të në një pikë të re, etj.

Le të shprehim funksionin objektiv Q(x, y) në terma të hapit l. Në këtë rast, ne paraqesim funksionin e synuar në një hap të caktuar si funksion të një ndryshoreje, d.m.th. madhësia e hapit

Madhësia e hapit në çdo përsëritje përcaktohet nga kushti minimal:

Min( (l)) l k = l*(x k, y k), l >0.

Kështu, në çdo përsëritje, zgjedhja e hapit l k përfshin zgjidhjen e një problemi optimizimi njëdimensional. Sipas metodës së zgjidhjes së këtij problemi, ato dallohen:

· metoda analitike (NAA);

· Metoda numerike (NMS).

Në metodën NSA, vlera e hapit merret nga kushti dhe në metodën NSF, vlera l k gjendet në një segment me një saktësi të caktuar, duke përdorur një nga metodat e optimizimit njëdimensional.

Shembulli 6.8.4-1. Gjeni minimumin e funksionit Q(x,y)=x 2 + 2y 2 me saktësi e=0.1, në kushtet fillestare: x 0 =2; y 0 =1.

Le të bëjmë një përsëritje duke përdorur metodën NSA.

=(x-2lx) 2 +2 (y-4ly) 2 = x 2 -4lx 2 +4l 2 x 2 +2y 2 -16ly 2 +32l 2 y 2 .

Nga kushti ¢(l)=0 gjejmë vlerën e l*:

Funksioni që rezulton l=l(x,y) ju lejon të gjeni vlerën e l. Për x=2 dhe y=1 kemi l=0,3333.

Le të llogarisim koordinatat e pikës vijuese:

Le të kontrollojmë përmbushjen e kriterit për përfundimin e përsëritjeve në k=1:

Meqenëse |2*0.6666|>0.1 dhe |-0.3333*4|>0.1, atëherë kushtet për përfundimin e procesit të përsëritjes nuk janë plotësuar, d.m.th. minimumi nuk u gjet. Prandaj, duhet të llogarisni vlerën e re të l për x=x 1 dhe y=y 1 dhe të merrni koordinatat e pikës tjetër të zbritjes. Llogaritjet vazhdojnë derisa të plotësohen kushtet e përfundimit të zbritjes.

Dallimi midis metodës numerike NN dhe asaj analitike është se kërkimi i vlerës së l në çdo përsëritje ndodh duke përdorur një nga metodat numerike të optimizimit njëdimensional (për shembull, metoda e dikotomisë ose metoda e seksionit të artë). Në këtë rast, diapazoni i vlerave të lejuara l - shërben si interval i pasigurisë.

Gradienti i funksionit të diferencueshëm f(x) në pikë X thirrur n-vektor dimensional f(x) , komponentët e të cilit janë derivate të pjesshëm të funksionit f (x), llogaritur në pikën X, d.m.th.

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

Ky vektor është pingul me rrafshin përmes pikës X, dhe tangjente me sipërfaqen e nivelit të funksionit f (x), duke kaluar nëpër një pikë X.Në çdo pikë të sipërfaqes së tillë funksioni f(x) merr të njëjtën vlerë. Duke barazuar funksionin me vlera të ndryshme konstante C 0 , C 1 , ..., marrim një seri sipërfaqesh që karakterizojnë topologjinë e tij (Fig. 2.8).

Vektori i gradientit drejtohet në drejtimin e rritjes më të shpejtë të funksionit në një pikë të caktuar. Vektor i kundërt me gradientin (-f'(x)) , thirri anti-gradient dhe drejtohet drejt uljes më të shpejtë të funksionit. Në pikën minimale, gradienti i funksionit është zero. Metodat e rendit të parë, të quajtura gjithashtu metoda gradienti dhe minimizimi, bazohen në vetitë e gradientëve. Përdorimi i këtyre metodave në rastin e përgjithshëm ju lejon të përcaktoni pikën minimale lokale të një funksioni.

Natyrisht, nëse nuk ka informacion shtesë, atëherë nga pika e fillimit Xështë e mençur të shkosh në pikën X, shtrirë në drejtim të antigradientit - rënia më e shpejtë e funksionit. Zgjedhja si drejtimi i zbritjes R[k] anti-gradient - f'(x[k] ) në pikën X[k], marrim një proces përsëritës të formës

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

Në formë koordinative, ky proces shkruhet si më poshtë:

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

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

Si kriter për ndalimin e procesit iterativ, ose plotësimi i kushtit të rritjes së vogël të argumentit || x[k+l] -x[k] || <= e , либо выполнение условия малости градиента

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

Këtu e dhe g janë dhënë sasi të vogla.

Një kriter i kombinuar është gjithashtu i mundur, i cili konsiston në përmbushjen e njëkohshme të kushteve të specifikuara. Metodat e gradientit ndryshojnë nga njëra-tjetra në mënyrën se si zgjedhin madhësinë e hapit dhe k.

Në metodën me hap konstant, zgjidhet një vlerë e caktuar hapi konstante për të gjitha përsëritjet. Një hap mjaft i vogël dhe k do të sigurojë që funksioni të zvogëlohet, d.m.th., pabarazia

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

Megjithatë, kjo mund të çojë në nevojën për të kryer një numër të papranueshëm të madh përsëritjesh për të arritur pikën minimale. Nga ana tjetër, një hap shumë i madh mund të shkaktojë një rritje të papritur të funksionit ose të çojë në lëkundje rreth pikës minimale (çiklizëm). Për shkak të vështirësisë në marrjen e informacionit të nevojshëm për zgjedhjen e madhësisë së hapit, metodat me hapa konstante përdoren rrallë në praktikë.

Ato me gradient janë më ekonomike për sa i përket numrit të përsëritjeve dhe besueshmërisë metodat e hapave të ndryshueshëm, kur, në varësi të rezultateve të llogaritjeve, madhësia e hapit ndryshon në një farë mënyre. Le të shqyrtojmë variantet e metodave të tilla të përdorura në praktikë.

Kur përdorni metodën e zbritjes më të pjerrët në çdo përsëritje, madhësia e hapit dhe k zgjidhet nga kushti minimal i funksionit f(x) në drejtim të zbritjes, d.m.th.
f(x[k]–a k f’(x[k])) = f(x[k] – af" (x[k])) .

Kjo gjendje do të thotë që lëvizja përgjatë antigradientit ndodh për aq kohë sa vlera e funksionit f(x) zvogëlohet. Nga pikëpamja matematikore, në çdo përsëritje është e nevojshme të zgjidhet problemi i minimizimit njëdimensional sipas A funksione
j (a) = f(x[k]-af" (x[k])) .

Algoritmi i metodës së zbritjes më të pjerrët është si më poshtë.

1. Vendosni koordinatat e pikës së fillimit X.

2. Në pikën X[k], k = 0, 1, 2, ... llogarit vlerën e gradientit f'(x[k]) .

3. Përcaktohet madhësia e hapit a k, nga minimizimi njëdimensional mbi A funksionet j (a) = f(x[k]-af" (x[k])).

4. Përcaktohen koordinatat e pikës X[k+ 1]:

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

5. Kontrollohen kushtet për ndalimin e procesit të sterimit. Nëse plotësohen, atëherë llogaritjet ndalojnë. Përndryshe, shkoni në hapin 1.

Në metodën në shqyrtim, drejtimi i lëvizjes nga pika X[k] prek vijën e nivelit në pikë x[k+ 1] (Fig. 2.9). Trajektorja e zbritjes është zigzag, me lidhje zigzag ngjitur në mënyrë ortogonale me njëra-tjetrën. Në të vërtetë, një hap a k zgjidhet duke minimizuar nga A funksione? (a) = f(x[k] -af" (x[k])) . Kusht i domosdoshëm për minimumin e një funksioni d j (a)/da = 0. Pasi kemi llogaritur derivatin e një funksioni kompleks, marrim kushtin për ortogonalitetin e vektorëve të drejtimeve të zbritjes në pikat fqinje:

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

Metodat e gradientit konvergojnë në minimum me shpejtësi të lartë (shpejtësia e progresionit gjeometrik) për funksione konvekse të lëmuara. Funksione të tilla kanë më të mëdhatë M dhe më së paku m eigenvlerat e matricës së derivateve të dytë (matrica Hessian)

ndryshojnë pak nga njëra-tjetra, pra matricë N(x) i kushtëzuar mirë. Kujtojmë se vlerat e veta l i, i =1, …, n, matricat janë rrënjët e ekuacionit karakteristik

Megjithatë, në praktikë, si rregull, funksionet që minimizohen kanë matrica të pakushtëzuara të derivateve të dytë (t/m<< 1). Vlerat e funksioneve të tilla përgjatë disa drejtimeve ndryshojnë shumë më shpejt (nganjëherë me disa renditje të madhësisë) sesa në drejtime të tjera. Sipërfaqet e tyre të nivelit në rastin më të thjeshtë janë fort të zgjatura (Fig. 2.10), dhe në raste më komplekse ato përkulen dhe duken si lugina. Funksionet me veti të tilla quhen grykë. Drejtimi i antigradientit të këtyre funksioneve (shih Fig. 2.10) devijon ndjeshëm nga drejtimi në pikën minimale, gjë që çon në një ngadalësim të shpejtësisë së konvergjencës.

Shkalla e konvergjencës së metodave të gradientit varet gjithashtu në mënyrë të konsiderueshme nga saktësia e llogaritjeve të gradientit. Humbja e saktësisë, e cila zakonisht ndodh në afërsi të pikave minimale ose në një situatë gryke, në përgjithësi mund të prishë konvergjencën e procesit të zbritjes së gradientit. Për arsyet e mësipërme, metodat e gradientit shpesh përdoren në kombinim me metoda të tjera më efektive në fazën fillestare të zgjidhjes së një problemi. Në këtë rast, pika Xështë larg nga pika minimale, dhe hapat në drejtim të antigradientit bëjnë të mundur arritjen e një rënie të ndjeshme të funksionit.

Metodat e gradientit të diskutuara më sipër gjejnë pikën minimale të një funksioni në rastin e përgjithshëm vetëm në një numër të pafund përsëritjesh. Metoda e gradientit të konjuguar gjeneron drejtime kërkimi që janë më në përputhje me gjeometrinë e funksionit që minimizohet. Kjo rrit ndjeshëm shpejtësinë e konvergjencës së tyre dhe lejon, për shembull, të minimizojë funksionin kuadratik

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

me një matricë të caktuar simetrike pozitive N në një numër të kufizuar hapash P, e barabartë me numrin e variablave të funksionit. Çdo funksion i qetë në afërsi të pikës minimale mund të përafrohet mirë nga një funksion kuadratik, prandaj metodat e gradientit të konjuguar përdoren me sukses për të minimizuar funksionet jo-kuadratike. Në këtë rast, ato pushojnë së qeni të fundme dhe bëhen përsëritëse.

Sipas përkufizimit, dy n-vektor dimensional X Dhe në thirrur të konjuguara në lidhje me matricën H(ose H-konjuguar), nëse produkti skalar (x, Epo) = 0. Këtu N - matrica simetrike pozitive e caktuar e madhësisë P X P.

Një nga problemet më të rëndësishme në metodat e gradientit të konjuguar është problemi i ndërtimit me efikasitet të drejtimeve. Metoda Fletcher-Reeves e zgjidh këtë problem duke transformuar antigradientin në çdo hap -f(x[k]) në drejtim fq[k], H-konjugohet me drejtimet e gjetura më parë R, R, ..., R[k-1].

Le ta shqyrtojmë fillimisht këtë metodë në lidhje me problemin e minimizimit të një funksioni kuadratik. R[k Drejtimet

] llogaritet duke përdorur formulat: k] = -f'(x[k]) p[ fq[k+b k-1 k>= 1;

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

f k b vlerat fq[k], R[k-1 janë zgjedhur në mënyrë që drejtimet H-1] ishin :

(fq[k], -konjuguar[HP 1])= 0.

k-

,

Si rezultat, për funksionin kuadratik

procesi i minimizimit iterativ ka formën k+l] x[[k]=x[k],

+a k f R[k] - Ku HP drejtimi i zbritjes në hap m; dhe k - madhësia e hapit. Kjo e fundit zgjidhet nga kushti minimal i funksionit f(x) A Nga

f(x[ k] + në drejtim të lëvizjes, pra si rezultat i zgjidhjes së problemit të minimizimit njëdimensional:[k]) = f(x[k] + a k r [k]) .

ar

Për një funksion kuadratik

Algoritmi i metodës së gradientit të konjuguar Fletcher-Reeves është si më poshtë. X 1. Në pikën fq = -f'(x) .

e llogaritur HP 2. Aktiv A hapi m, duke përdorur formulat e mësipërme, përcaktohet hapi . k X[k+ 1].

dhe periudha f(x[k+1]) 3. Vlerat janë llogaritur f'(x[k+1]) .

Dhe f'(x) 4. Nëse X[k= 0, pastaj pikë +1] është pika minimale e funksionit f(x). fq[k Përndryshe, përcaktohet një drejtim i ri

+l] nga relacioni P dhe kryhet kalimi në përsëritjen tjetër. Kjo procedurë do të gjejë minimumin e një funksioni kuadratik në jo më shumë se hapat. Kur minimizohen funksionet jo-kuadratike, metoda Fletcher-Reeves bëhet përsëritëse nga e fundme. Në këtë rast, pas(p+ X 1) përsëritja e procedurës 1-4 përsëriten në mënyrë ciklike me zëvendësim X[P në

procesi i minimizimit iterativ ka formën k+l] +1] , dhe llogaritjet përfundojnë në , ku është një numër i dhënë. Në këtë rast, përdoret modifikimi i mëposhtëm i metodës:[k]=x[k],

] llogaritet duke përdorur formulat: k] = x[k])+ = -f'(x HP 1 fq[k+b k-1 k>= 1;

b x);

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

.

+ap Këtu I Këtu- shumë indekse: = (0, n, 2 p, paga, ...) P, pra metoda përditësohet çdo

hapat. X Kuptimi gjeometrik i metodës së gradientit të konjuguar është si më poshtë (Fig. 2.11). Nga një pikënisje e caktuar R = zbritja kryhet në drejtim-f"(x X). Në pikën përcaktohet vektori i gradientit f" (x X). Sepse R, është pika minimale e funksionit në drejtim f'(x) Se R ortogonal në vektor R , H. Pastaj gjendet vektori R-konjuguar me R. Më pas, gjejmë minimumin e funksionit përgjatë drejtimit

Metodat e drejtimit të konjuguar janë ndër më efektivet për zgjidhjen e problemeve të minimizimit. Megjithatë, duhet theksuar se ata janë të ndjeshëm ndaj gabimeve që ndodhin gjatë procesit të numërimit. Me një numër të madh variablash, gabimi mund të rritet aq shumë sa që procesi do të duhet të përsëritet edhe për një funksion kuadratik, d.m.th. procesi për të nuk përshtatet gjithmonë në P, pra metoda përditësohet çdo

Kur përdorni metodën e zbritjes më të pjerrët në çdo përsëritje, madhësia e hapit A k zgjidhet nga kushti minimal i funksionit f(x) në drejtim të zbritjes, d.m.th.

f(x[k] -a k përcaktohet vektori i gradientit[k])) = f(x[k] -af" (x[k])) .

Kjo gjendje do të thotë që lëvizja përgjatë antigradientit ndodh për aq kohë sa vlera e funksionit f(x) zvogëlohet. Nga pikëpamja matematikore, në çdo përsëritje është e nevojshme të zgjidhet problemi i minimizimit njëdimensional sipas A funksione

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

Algoritmi i metodës së zbritjes më të pjerrët është si më poshtë.

• 1. Vendosni koordinatat e pikës së fillimit X.
• 2. Në pikën X[k], k = 0, 1, 2, ... llogarit vlerën e gradientit përcaktohet vektori i gradientit[k]) .
• 3. Përcaktohet madhësia e hapit a k, nga minimizimi njëdimensional mbi A funksionet j (a) = f(x[k]-af" (x[k])).
• 4. Përcaktohen koordinatat e pikës X[k+ 1]:

X i [k+ 1]+1] , dhe llogaritjet përfundojnë në , ku është një numër i dhënë. Në këtë rast, përdoret modifikimi i mëposhtëm i metodës: i [k] -A k f" i (X[k]), i = 1,..., fq.

5. Kontrollohen kushtet për ndalimin e procesit të sterimit. Nëse plotësohen, atëherë llogaritjet ndalojnë. Përndryshe, shkoni në hapin 1.

Në metodën në shqyrtim, drejtimi i lëvizjes nga pika X[k] prek vijën e nivelit në pikë x[k+ 1] (Fig. 2.9). Trajektorja e zbritjes është zigzag, me lidhje zigzag ngjitur në mënyrë ortogonale me njëra-tjetrën. Në të vërtetë, një hap a k zgjidhet duke minimizuar nga A funksione? (a) = f(x[k] -af" (x[k])) . Kusht i domosdoshëm për minimumin e një funksioni d j (a)/da = 0. Pasi kemi llogaritur derivatin e një funksioni kompleks, marrim kushtin për ortogonalitetin e vektorëve të drejtimeve të zbritjes në pikat fqinje:

d j (a)/da = -f"(x[k+ 1]përcaktohet vektori i gradientit[k]) = 0.

Oriz. 2.9.

Metodat e gradientit konvergojnë në minimum me një shpejtësi të lartë (shkalla e progresionit gjeometrik) për funksione konvekse të lëmuara. Funksione të tilla kanë më të mëdhatë M dhe më së paku m eigenvlerat e matricës së derivateve të dytë (matrica Hessian)

ndryshojnë pak nga njëra-tjetra, pra matrica N(x) i kushtëzuar mirë. Kujtojmë që vlerat e veta l i, i =1, …, n, matricat janë rrënjët e ekuacionit karakteristik

Megjithatë, në praktikë, si rregull, funksionet që minimizohen kanë matrica të pakushtëzuara të derivateve të dytë (t/m<< 1). Vlerat e funksioneve të tilla përgjatë disa drejtimeve ndryshojnë shumë më shpejt (nganjëherë me disa renditje të madhësisë) sesa në drejtime të tjera. Sipërfaqet e tyre të nivelit në rastin më të thjeshtë janë fort të zgjatura (Fig. 2.10), dhe në rastet më komplekse ato përkulen dhe duken si lugina. Funksionet me veti të tilla quhen grykë. Drejtimi i antigradientit të këtyre funksioneve (shih Fig. 2.10) devijon ndjeshëm nga drejtimi në pikën minimale, gjë që çon në një ngadalësim të shpejtësisë së konvergjencës.

Oriz. 2.10.

Shkalla e konvergjencës së metodave të gradientit varet gjithashtu në mënyrë të konsiderueshme nga saktësia e llogaritjeve të gradientit. Humbja e saktësisë, e cila zakonisht ndodh në afërsi të pikave minimale ose në një situatë gryke, në përgjithësi mund të prishë konvergjencën e procesit të zbritjes së gradientit. Për arsyet e mësipërme, metodat e gradientit shpesh përdoren në kombinim me metoda të tjera më efektive në fazën fillestare të zgjidhjes së një problemi. Në këtë rast, pika Xështë larg nga pika minimale, dhe hapat në drejtim të antigradientit bëjnë të mundur arritjen e një rënie të ndjeshme të funksionit.

Metoda e zbritjes më të pjerrët (në literaturën angleze "metoda e zbritjes më të pjerrët") është një metodë numerike përsëritëse (rendi i parë) për zgjidhjen e problemeve të optimizimit, e cila ju lejon të përcaktoni ekstremin (minimumin ose maksimal) të funksionit objektiv:

janë vlerat e argumentit të funksionit (parametrat e kontrolluar) në domenin real.

Në përputhje me metodën në shqyrtim, ekstremi (maksimumi ose minimal) i funksionit objektiv përcaktohet në drejtim të rritjes (uljes) më të shpejtë të funksionit, d.m.th. në drejtim të gradientit (antigradientit) të funksionit. Funksioni i gradientit në një pikë është një vektor, projeksionet e të cilit në boshtet e koordinatave janë derivatet e pjesshme të funksionit në lidhje me koordinatat:

ku i, j,…, n janë vektorë njësi paralel me boshtet koordinative.

Gradient në pikën bazë është rreptësisht ortogonal me sipërfaqen, dhe drejtimi i tij tregon drejtimin e rritjes më të shpejtë të funksionit, dhe drejtimi i kundërt (antigradienti), përkatësisht, tregon drejtimin e rënies më të shpejtë të funksionit.

Metoda më e pjerrët e zbritjes është një zhvillim i mëtejshëm i metodës së zbritjes me gradient. Në përgjithësi, procesi i gjetjes së ekstremit të një funksioni është një procedurë përsëritëse, e cila shkruhet si më poshtë:

ku shenja "+" përdoret për të gjetur maksimumin e një funksioni dhe shenja "-" përdoret për të gjetur minimumin e një funksioni;

Vektori i drejtimit të njësisë, i cili përcaktohet nga formula:

- moduli i gradientit përcakton shkallën e rritjes ose uljes së funksionit në drejtim të gradientit ose anti-gradientit:

Një konstante që përcakton madhësinë e hapit dhe është e njëjtë për të gjitha drejtimet i-të.

Madhësia e hapit zgjidhet nga kushti i minimumit të funksionit objektiv f(x) në drejtim të lëvizjes, d.m.th., si rezultat i zgjidhjes së problemit të optimizimit njëdimensional në drejtim të gradientit ose antigradientit:

Me fjalë të tjera, madhësia e hapit përcaktohet duke zgjidhur këtë ekuacion:

Kështu, hapi i llogaritjes zgjidhet i tillë që lëvizja të kryhet derisa funksioni të përmirësohet, duke arritur kështu një ekstrem në një moment. Në këtë pikë, përsëri përcaktohet drejtimi i kërkimit (duke përdorur gradientin) dhe kërkohet një pikë e re optimale e funksionit objektiv, etj. Kështu, në këtë metodë, kërkimi ndodh në hapa më të mëdhenj, dhe gradienti i funksionit llogaritet në një numër më të vogël pikash.

Në rastin e një funksioni të dy variablave, kjo metodë ka interpretimin gjeometrik të mëposhtëm: drejtimi i lëvizjes nga një pikë prek vijën e nivelit në pikën . Trajektorja e zbritjes është zigzag, me lidhje zigzag ngjitur në mënyrë ortogonale me njëra-tjetrën. Kushti për ortogonalitetin e vektorëve të drejtimeve të zbritjes në pikat fqinje shkruhet me shprehjen e mëposhtme:

Trajektorja e lëvizjes në pikën ekstreme duke përdorur metodën e zbritjes më të pjerrët, e paraqitur në grafikun e vijës së nivelit të barabartë të funksionit f(x)

Kërkimi për një zgjidhje optimale përfundon kur në hapin e llogaritjes përsëritëse (disa kritere):

Trajektorja e kërkimit mbetet në një lagje të vogël të pikës aktuale të kërkimit:

Rritja e funksionit objektiv nuk ndryshon:

Gradienti i funksionit objektiv në pikën minimale lokale bëhet zero:

Duhet të theksohet se metoda e zbritjes së gradientit rezulton të jetë shumë e ngadaltë kur lëviz përgjatë një përroske dhe me rritjen e numrit të variablave në funksionin objektiv, kjo sjellje e metodës bëhet tipike. Gryka është një gropë, vijat e nivelit të së cilës përafërsisht kanë formën e elipseve me gjysmëboshte të ndryshme shumëfish. Në prani të një përroske, trajektorja e zbritjes merr formën e një linje zigzag me një hap të vogël, si rezultat i së cilës shpejtësia që rezulton e zbritjes në minimum ngadalësohet shumë. Kjo shpjegohet me faktin se drejtimi i antigradientit të këtyre funksioneve devijon ndjeshëm nga drejtimi në pikën minimale, gjë që çon në një vonesë shtesë në llogaritjen. Si rezultat, algoritmi humbet efikasitetin llogaritës.

Funksioni Gully

Metoda e gradientit, së bashku me modifikimet e saj të shumta, është një metodë e zakonshme dhe efektive për kërkimin e optimumit të objekteve në studim. Disavantazhi i kërkimit me gradient (si dhe metodat e diskutuara më sipër) është se kur përdoret, mund të zbulohet vetëm ekstremi lokal i funksionit. Për të gjetur ekstreme të tjera lokale, është e nevojshme të kërkoni nga pika të tjera fillestare. Gjithashtu, shkalla e konvergjencës së metodave të gradientit gjithashtu varet ndjeshëm nga saktësia e llogaritjeve të gradientit. Humbja e saktësisë, e cila zakonisht ndodh në afërsi të pikave minimale ose në një situatë gryke, në përgjithësi mund të prishë konvergjencën e procesit të zbritjes së gradientit.

Mënyra e llogaritjes

Hapi 1: Përkufizimi i shprehjeve analitike (në formë simbolike) për llogaritjen e gradientit të një funksioni

Hapi 2: Vendosni përafrimin fillestar

Hapi 3: Përcaktohet nevoja për të rifilluar procedurën algoritmike për të rivendosur drejtimin e fundit të kërkimit. Si rezultat i rifillimit, kërkimi kryhet përsëri në drejtim të zbritjes më të shpejtë.