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ë, drejtimi i kërkimit përcaktohet përsëri (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ë pjerrët.

Fig.3. Interpretimi gjeometrik i metodës së zbritjes më të pjerrët. Në çdo hap, zgjidhet në mënyrë që përsëritja tjetër të jetë pika minimale e funksionit në rreze L.

Ky version i metodës së gradientit bazohet në zgjedhjen e hapit nga konsideratat e mëposhtme. Nga pika do të lëvizim në drejtim të antigradientit derisa të arrijmë minimumin e funksionit f në këtë drejtim, pra në rreze:

Me fjalë të tjera, zgjidhet në mënyrë që përsëritja tjetër të jetë pika minimale e funksionit f në rreze L (shih Fig. 3). Ky version i metodës së gradientit quhet metoda më e pjerrët e zbritjes. Vini re, meqë ra fjala, se në këtë metodë drejtimet e hapave ngjitur janë ortogonale.

Metoda më e pjerrët e zbritjes kërkon zgjidhjen e një problemi optimizimi njëdimensional në çdo hap. Praktika tregon se kjo metodë shpesh kërkon më pak operacione sesa metoda e gradientit me një hap konstant.

Sidoqoftë, në situatën e përgjithshme, shkalla teorike e konvergjencës së metodës së zbritjes më të pjerrët nuk është më e lartë se shkalla e konvergjencës së metodës së gradientit me një hap konstant (optimal).

Shembuj numerikë

Metoda e zbritjes gradient me hap të vazhdueshëm

Për të studiuar konvergjencën e metodës së zbritjes së gradientit me një hap konstant, u zgjodh funksioni:

Nga rezultatet e marra, mund të konkludojmë se nëse hendeku është shumë i madh, metoda ndryshon nëse hendeku është shumë i vogël, ai konvergon ngadalë dhe saktësia është më e keqe. Është e nevojshme të zgjidhni hapin më të madh nga ato në të cilat metoda konvergon.

Metoda e gradientit me ndarje hapash

Për të studiuar konvergjencën e metodës së zbritjes së gradientit me ndarjen e hapit (2), u zgjodh funksioni:

Përafrimi fillestar është pika (10,10).

Kriteri i ndalimit i përdorur:

Rezultatet e eksperimentit tregohen në tabelë:

Nga rezultatet e marra mund të konkludojmë se zgjedhja optimale e parametrave është: , megjithëse metoda nuk është shumë e ndjeshme ndaj zgjedhjes së parametrave.

metoda më e pjerrët e zbritjes

Për të studiuar konvergjencën e metodës së zbritjes më të pjerrët, u zgjodh funksioni i mëposhtëm:

Përafrimi fillestar është pika (10,10). Kriteri i ndalimit i përdorur:

Për të zgjidhur problemet e optimizimit njëdimensional, u përdor metoda e seksionit të artë.

Metoda arriti një saktësi prej 6e-8 në 9 përsëritje.

Nga kjo mund të konkludojmë se metoda e zbritjes më të pjerrët konvergon më shpejt se metoda e gradientit të ndarjes me hap dhe metoda e zbritjes me gradient me hap konstant.

Disavantazhi i metodës së zbritjes më të pjerrët është se kërkon zgjidhjen e një problemi optimizimi njëdimensional.

Kur programoni metodat e zbritjes së gradientit, duhet të jeni të kujdesshëm kur zgjidhni parametrat, përkatësisht

• · Metoda e zbritjes së gradientit me një hap konstant: hapi duhet të zgjidhet më pak se 0,01, përndryshe metoda divergjente (metoda mund të divergjojë edhe me një hap të tillë, në varësi të funksionit që studiohet).
• · Metoda e gradientit me ndarje hapash nuk është shumë e ndjeshme ndaj zgjedhjes së parametrave. Një nga opsionet për zgjedhjen e parametrave:
• · Metoda e zbritjes më të pjerrët: Metoda e raportit të artë (kur është e aplikueshme) mund të përdoret si një metodë optimizimi njëdimensionale.

Metoda e gradientit të konjuguar është një metodë përsëritëse për optimizim të pakufizuar në një hapësirë ​​shumëdimensionale. Avantazhi kryesor i metodës është se ajo zgjidh një problem të optimizimit kuadratik në një numër të kufizuar hapash. Prandaj, fillimisht përshkruhet metoda e gradientit të konjuguar për optimizimin e funksionit kuadratik, nxirren formulat përsëritëse dhe jepen vlerësimet e shkallës së konvergjencës. Pas kësaj, tregohet se si metoda adjoint përgjithësohet për të optimizuar një funksional arbitrar, merren parasysh variante të ndryshme të metodës dhe diskutohet konvergjenca.

Deklarata e problemit të optimizimit

Le të jepet një grup dhe të përcaktohet një funksion objektiv në këtë grup. Problemi i optimizimit konsiston në gjetjen e kufirit të saktë të sipërm ose të saktë të poshtëm të funksionit objektiv në grup. Përcaktohet grupi i pikave në të cilat arrihet kufiri i poshtëm i funksionit objektiv.

Nëse, atëherë problemi i optimizimit quhet i pakufizuar. Nëse, atëherë problemi i optimizimit quhet i kufizuar.

Metoda e gradientit të konjuguar për funksionalitetin kuadratik

Deklarata e metodës

Merrni parasysh problemin e mëposhtëm të optimizimit:

Këtu është një matricë simetrike pozitive me madhësi të caktuar. Ky problem optimizimi quhet kuadratik. Vini re se. Kushti për një ekstrem të një funksioni është i barabartë me sistemin. Funksioni arrin kufirin e tij të poshtëm në një pikë të vetme të përcaktuar nga ekuacioni. Kështu, ky problem optimizimi reduktohet në zgjidhjen e një sistemi ekuacionesh lineare Ideja e metodës së gradientit të konjuguar është si më poshtë: Le të jetë baza. Pastaj për çdo pikë vektori zgjerohet në bazë Kështu, ai mund të përfaqësohet në formë

Çdo përafrim pasues llogaritet duke përdorur formulën:

Përkufizimi. Dy vektorë dhe thuhet se janë të konjuguar në lidhje me matricën simetrike B nëse

Le të përshkruajmë metodën e ndërtimit të një baze në metodën e gradientit të konjuguar Ne zgjedhim një vektor arbitrar si një përafrim fillestar. Në çdo përsëritje zgjidhen rregullat e mëposhtme:

Vektorët bazë llogariten duke përdorur formulat:

Koeficientët janë zgjedhur në mënyrë që vektorët të jenë të konjuguar në lidhje me A.

Nëse shënojmë me , atëherë pas disa thjeshtësimeve marrim formulat përfundimtare të përdorura gjatë zbatimit të metodës së gradientit të konjuguar në praktikë:

Për metodën e gradientit të konjuguar, vlen teorema e mëposhtme: Teorema Let, ku është një matricë e caktuar pozitive simetrike e madhësisë. Pastaj metoda e gradientit të konjuguar konvergon në jo më shumë se hapa dhe relacionet e mëposhtme vlejnë:

Konvergjenca e metodës

Nëse të gjitha llogaritjet janë të sakta dhe të dhënat fillestare janë të sakta, atëherë metoda konvergjon në zgjidhjen e sistemit në jo më shumë se përsëritje, ku është dimensioni i sistemit. Një analizë më e rafinuar tregon se numri i përsëritjeve nuk tejkalon, ku është numri i eigenvlerave të ndryshme të matricës A. Për të vlerësuar shkallën e konvergjencës, vlerësimi i mëposhtëm (mjaft i përafërt) është i saktë:

Ju lejon të vlerësoni shkallën e konvergjencës nëse dihen vlerësimet për eigenvalutat maksimale dhe minimale të matricës në praktikë, kriteri i mëposhtëm i ndalimit përdoret më shpesh:

Kompleksiteti llogaritës

Në çdo përsëritje të metodës, kryhen operacione. Ky numër operacionesh kërkohet për të llogaritur produktin - kjo është procedura që kërkon më shumë kohë në çdo përsëritje. Llogaritjet e tjera kërkojnë operacione O(n). Kompleksiteti total llogaritës i metodës nuk kalon - pasi numri i përsëritjeve nuk është më shumë se n.

Shembull numerik

Le të zbatojmë metodën e gradientit të konjuguar për të zgjidhur një sistem ku, duke përdorur metodën e gradientit të konjuguar, zgjidhja e këtij sistemi merret në dy përsëritje. Eigenvlerat e matricës janë 5, 5, -5 - midis tyre ka dy të ndryshme, prandaj, sipas vlerësimit teorik, numri i përsëritjeve nuk mund të kalonte dy

Metoda e gradientit të konjuguar është një nga metodat më efektive për zgjidhjen e SLAE-ve me një matricë të caktuar pozitive. Metoda garanton konvergjencë në një numër të kufizuar hapash dhe saktësia e kërkuar mund të arrihet shumë më herët. Problemi kryesor është se për shkak të akumulimit të gabimeve, mund të cenohet ortogonaliteti i vektorëve bazë, gjë që dëmton konvergjencën.

Metoda e gradientit të konjuguar në përgjithësi

Le të shqyrtojmë tani një modifikim të metodës së gradientit të konjuguar për rastin kur funksioni i minimizuar nuk është kuadratik: Do ta zgjidhim problemin:

Funksioni vazhdimisht i diferencueshëm. Për të modifikuar metodën e gradientit të konjuguar për të zgjidhur këtë problem, është e nevojshme të merret për formulat që nuk përfshijnë matricën A:

mund të llogaritet duke përdorur një nga tre formulat:

1. - Metoda Fletcher-Reeves

• 2. - Metoda Polak-Ribi`ere

Nëse funksioni është kuadratik dhe rreptësisht konveks, atëherë të tre formulat japin të njëjtin rezultat. Nëse është një funksion arbitrar, atëherë secila prej formulave korrespondon me modifikimin e vet të metodës së gradientit të konjuguar. Formula e tretë përdoret rrallë sepse kërkon funksionin dhe llogaritjen e Hessian-it të funksionit në çdo hap të metodës.

Nëse funksioni nuk është kuadratik, metoda e gradientit të konjuguar mund të mos konvergojë në një numër të kufizuar hapash. Për më tepër, llogaritja e saktë në çdo hap është e mundur vetëm në raste të rralla. Prandaj, akumulimi i gabimeve çon në faktin se vektorët nuk tregojnë më drejtimin e uljes së funksionit. Pastaj në një hap ata besojnë. Bashkësia e të gjithë numrave në të cilët pranohet do të shënohet me. Numrat quhen momente të përditësimit të metodës. Në praktikë, shpesh zgjidhet se ku është dimensioni i hapësirës.

Konvergjenca e metodës

Për metodën Fletcher-Reeves, ekziston një teoremë konvergjence që imponon kushte jo shumë strikte për funksionin që minimizohet: Teorema. Le të plotësohen kushtet e mëposhtme:

Shumëllojshmëria është e kufizuar

Derivati ​​plotëson kushtin Lipschitz me një konstante në disa lagje

vendos M: .

Për metodën Polak-Reiber, konvergjenca vërtetohet nën supozimin se është një funksion rreptësisht konveks. Në rastin e përgjithshëm, është e pamundur të vërtetohet konvergjenca e metodës Polak-Reiber. Përkundrazi, teorema e mëposhtme është e vërtetë: Teorema. Le të supozojmë se në metodën Polak-Reiber vlerat në çdo hap llogariten saktësisht. Pastaj ka një funksion dhe një supozim fillestar, i tillë që.

Megjithatë, në praktikë metoda Polak-Reiber funksionon më mirë. Kriteret më të zakonshme të ndalimit në praktikë: Norma e gradientit bëhet më e vogël se një prag i caktuar Vlera e funksionit ka mbetur pothuajse e pandryshuar për m përsëritje të njëpasnjëshme

Kompleksiteti llogaritës

Në çdo përsëritje të metodave Polak-Reiber ose Fletcher-Reeves, funksioni dhe gradienti i tij llogariten një herë dhe zgjidhet problemi i optimizimit njëdimensional. Kështu, kompleksiteti i një hapi të metodës së gradientit të konjuguar është i të njëjtit rend të madhësisë si kompleksiteti i një hapi të metodës së zbritjes më të pjerrët. Në praktikë, metoda e gradientit të konjuguar tregon shpejtësinë më të mirë të konvergjencës.

Ne do të kërkojmë për minimumin e funksionit duke përdorur metodën e gradientit të konjuguar

Minimumi i këtij funksioni është 1 dhe arrihet në pikën (5, 4). Duke përdorur këtë funksion si shembull, le të krahasojmë metodat Polak-Reiber dhe Fletcher-Reeves. Përsëritjet në të dyja metodat ndalojnë kur norma në katror e gradientit bëhet më e vogël në hapin aktual. Për përzgjedhje përdoret metoda e raportit të artë

Janë zbatuar dy versione të metodës së gradientit të konjuguar: për minimizimin e një funksioni kuadratik dhe për minimizimin e një funksioni arbitrar. Në rastin e parë, metoda zbatohet nga funksioni vektor Gjeni Zgjidhjen (matricë A, vektor b) Këtu A dhe b janë matrica dhe vektori i përfshirë në përcaktimin e problemit të optimizimit kuadratik. Për të minimizuar funksionalitetin arbitrar, mund të përdorni një nga dy funksionet: vektor FletcherRievesMethod(int spaceSize, Funksioni F, vektori (*GradF) (vektor )) vektor Metoda PolakRibiere(int spaceSize, Funksioni F, vektori (*GradF) (vektor )) Parametrat për të dy funksionet janë të njëjta dhe kanë kuptimin e mëposhtëm: spaceSize - dimensioni i hapësirës (numri i variablave nga i cili varet funksioni i minimizuar) F - një tregues për funksionin që do të minimizohet. Funksioni duhet të jetë i formës double<имя функции>(vektor ) GradF - treguesi i një funksioni që llogarit gradientin e funksionit të minimizuar Të dyja metodat përdorin një funksion ndihmës për të zgjidhur një problem optimizimi njëdimensional. Programi zbaton optimizimin njëdimensional duke përdorur metodën e seksionit të artë.

Metodat e zbritjes së gradientit janë mjete mjaft të fuqishme për zgjidhjen e problemeve të optimizimit. Disavantazhi kryesor i metodave është shtrirja e kufizuar e zbatueshmërisë. Metoda e gradientit të konjuguar përdor informacion vetëm për pjesën lineare të rritjes në një pikë, si në metodat e zbritjes së gradientit. Për më tepër, metoda e gradientit të konjuguar ju lejon të zgjidhni problemet kuadratike në një numër të kufizuar hapash. Në shumë probleme të tjera, metoda e gradientit të konjuguar gjithashtu tejkalon metodën e zbritjes së gradientit. Konvergjenca e metodës së gradientit varet shumë nga sa saktë zgjidhet problemi i optimizimit njëdimensional. Rrjedhat e mundshme të metodave zgjidhen duke përdorur përditësime. Megjithatë, nëse një metodë futet në një minimum lokal të një funksioni, me shumë mundësi nuk do të jetë në gjendje të shpëtojë prej tij.

Metoda më e pjerrët e zbritjes është një metodë gradient me një hap të ndryshueshëm. Në çdo përsëritje, madhësia e hapit k zgjidhet nga kushti i minimumit të funksionit f(x) në drejtim të zbritjes, d.m.th.

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 funksionit

()=f (x (k) -f (x (k)))

Le të përdorim metodën e raportit të artë për këtë.

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

Përcaktohen koordinatat e pikës fillestare x (0).

Në pikën x (k) , k = 0, 1, 2, ..., llogaritet vlera e gradientit f (x (k)).

Madhësia e hapit k përcaktohet nga minimizimi njëdimensional duke përdorur funksionin

()=f (x (k) -f (x (k))).

Përcaktohen koordinatat e pikës x (k):

x i (k+1) = x i (k) - k f i (x (k)), i=1, …, n.

Kontrollohet kushti për ndalimin e procesit përsëritës:

||f (x (k +1))|| .

Nëse plotësohet, atëherë llogaritjet ndalojnë. Përndryshe, ne vazhdojmë me hapin 1. Interpretimi gjeometrik i metodës së zbritjes më të pjerrët është paraqitur në Fig. 1.

Oriz. 2.1. Blloku i metodës së zbritjes më të pjerrët.

Zbatimi i metodës në program:

Metoda e zbritjes më të pjerrët.

Oriz. 2.2. Zbatimi i metodës së zbritjes më të pjerrët.

Përfundim: Në rastin tonë, metoda konvergjoi në 7 përsëritje. Pika A7 (0.6641; -1.3313) është një pikë ekstreme. Metoda e drejtimeve të konjuguara. Për funksionet kuadratike, mund të krijoni një metodë gradienti në të cilën koha e konvergjencës do të jetë e fundme dhe e barabartë me numrin e ndryshoreve n.

Le të quajmë një drejtim të caktuar dhe të konjugojmë në lidhje me një matricë të caktuar pozitive Hess H nëse:

Atëherë, pra, për njësinë H, drejtimi i konjuguar nënkupton pingulën e tyre. Në rastin e përgjithshëm, H është jo i parëndësishëm. Në rastin e përgjithshëm, konjugacioni është aplikimi i matricës Hess në një vektor - do të thotë rrotullimi i këtij vektori me një kënd, shtrirja ose ngjeshja e tij.

Dhe tani vektori është ortogonal, d.m.th. konjugacioni nuk është ortogonaliteti i vektorit, por ortogonaliteti i vektorit të rrotulluar. d.m.th.

Oriz. 2.3. Blloku i metodës së drejtimeve të konjuguara.

Zbatimi i metodës në program: Metoda e drejtimeve të konjuguara.

Oriz. 2.4. Zbatimi i metodës së drejtimeve të konjuguara.

Oriz. 2.5. Grafiku i metodës së drejtimeve të konjuguara.

Përfundim: Pika A3 (0.6666; -1.3333) u gjet në 3 përsëritje dhe është një pikë ekstreme.

3. Analiza e metodave për përcaktimin e vlerës minimale dhe maksimale të një funksioni në prani të kufizimeve

Kujtoni se një problem i përgjithshëm i optimizimit të kufizuar duket kështu:

f(x) ® min, x О W,

ku W është një nëngrup i duhur i R m. Një nënklasë problemesh me kufizime të tipit të barazisë dallohet nga fakti se bashkësia  përcaktohet nga kufizimet e formës

f i (x) = 0, ku f i: R m ®R (i = 1, …, k).

Kështu,W = (x О R m: f i (x) = 0, i = 1, …, k).

Do të jetë e përshtatshme për ne të shkruajmë indeksin "0" për funksionin f. Kështu, problemi i optimizimit me kufizimet e llojit të barazisë shkruhet si

f 0 (x) ® min, (3.1)

f i (x) = 0, i = 1, …, k. (3.2)

Nëse tani shënojmë me f një funksion në Rm me vlera në R k, shënimi koordinativ i të cilit ka formën f(x) = (f 1 (x), ..., f k (x)), atëherë ( 3.1)–(3.2) mund ta shkruajmë edhe në formë

f 0 (x) ® min, f(x) = Q.

Gjeometrikisht, një problem me kufizimet e tipit të barazisë është një problem i gjetjes së pikës më të ulët të grafikut të një funksioni f 0 mbi shumëfishin  (shih Fig. 3.1).

Pikat që plotësojnë të gjitha kufizimet (d.m.th., pikat në grupin ) quhen zakonisht të pranueshme. Një pikë e pranueshme x* quhet një minimum i kushtëzuar i funksionit f 0 nën kufizimet f i (x) = 0, i = 1, ..., k (ose një zgjidhje e problemit (3.1)–(3.2)), nëse për të gjitha pikat e pranueshme x f 0 (x *)  f 0 (x). (3.3)

Nëse (3.3) është i kënaqur vetëm për x të pranueshëm që shtrihet në ndonjë lagje V x * të pikës x*, atëherë flasim për një minimum të kushtëzuar lokal. Konceptet e minimumeve strikte të kushtëzuara lokale dhe globale përcaktohen në mënyrë të natyrshme.

Shënim: Ky leksion mbulon gjerësisht metoda të tilla të optimizimit shumëparametrik si metoda e zbritjes më të pjerrët dhe metoda Davidon-Fletcher-Powell. Përveç kësaj, kryhet një analizë krahasuese e metodave të mësipërme për të përcaktuar më efektiven, për të identifikuar avantazhet dhe disavantazhet e tyre; dhe gjithashtu merr në konsideratë problemet e optimizimit shumëdimensional, të tilla si metoda e përroskës dhe metoda multiekstremale.

1. Metoda e zbritjes më të pjerrët

Thelbi i kësaj metode është se duke përdorur ato të përmendura më parë metoda e zbritjes së koordinatave një kërkim kryhet nga një pikë e caktuar në një drejtim paralel me një nga akset deri në pikën minimale në këtë drejtim. Kërkimi kryhet më pas në drejtim paralel me boshtin tjetër, e kështu me radhë. Udhëzimet janë, natyrisht, fikse. Duket e arsyeshme që të përpiqemi të modifikojmë këtë metodë në mënyrë që në çdo fazë kërkimi për pikën minimale të kryhet përgjatë drejtimit "më të mirë". Nuk dihet se cili drejtim është “më i miri”, por dihet se drejtimi i gradientitështë drejtimi i rritjes më të shpejtë të funksionit. Prandaj, drejtimi i kundërt është drejtimi i rënies më të shpejtë të funksionit. Kjo pronë mund të justifikohet si më poshtë.

Le të supozojmë se po lëvizim nga pika x në pikën tjetër x + hd, ku d është një drejtim i caktuar dhe h është një hap me një gjatësi të caktuar. Rrjedhimisht, lëvizja bëhet nga pika (x 1, x 2, ..., x n) në pikën (x 1 + zx 1, x 2 + zx 2, ..., x n + zx n), Ku

Ndryshimi në vlerat e funksionit përcaktohet nga marrëdhëniet

Deri në renditjen e parë zx i , me derivate të pjesshme që llogariten në pikën x. Si duhet të zgjidhen drejtimet d i që plotësojnë ekuacionin (1.2) për të marrë vlerën më të madhe të ndryshimit në funksionin df? Këtu lind një problem maksimizimi me një kufizim. Le të zbatojmë metodën e shumëzuesve të Lagranzhit, me ndihmën e të cilit përcaktojmë funksionin

Vlera df që plotëson kufizimin (1.2) arrin një maksimum kur funksioni

Arrin maksimumin. Derivati ​​i tij

Prandaj,

(1.6)

Atëherë di ~ df/dx i dhe drejtimi d është paralel me drejtimin V/(x) në pikën x.

Kështu, rritja më e madhe lokale funksioni për një hap të caktuar të vogël h ndodh kur d është drejtimi i Vf(x) ose g(x) . Prandaj, drejtimi i zbritjes më të pjerrët është drejtimi

Në një formë më të thjeshtë, ekuacioni (1.3) mund të shkruhet si më poshtë:

Ku është këndi ndërmjet vektorëve Vf(x) dhe dx. Për një vlerë të caktuar të dx, ne minimizojmë df duke zgjedhur që drejtimi i dx përkon me drejtimin e -Vf(x).

Komentoni. Drejtimi i gradientit pingul me çdo pikë në një vijë të nivelit konstant, pasi përgjatë kësaj linje funksioni është konstant. Kështu, nëse (d 1, d 2, ..., d n) është një hap i vogël përgjatë vijës së nivelit, atëherë

Dhe prandaj

(1.8)

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 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 funksionet

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]= x 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 funksionet? (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]f" (x[k]) = 0.

Oriz. 2.9.

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ë 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ë 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.

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.