Deklarata e problemit

Le të jepet funksioni f(x) Rn

E detyrueshme f(x) X = Rn

Strategjia e kërkimit

x k } , k = 0,1,..., të tilla që , k = 0,1,... . Pikat e renditjes ( x k ) llogariten sipas rregullit

ku eshte thelbi x 0 përcaktuar nga përdoruesi; madhësia e hapit tk përcaktuar për çdo vlerë k nga gjendja

Problemi (3) mund të zgjidhet duke përdorur kushtin minimal të nevojshëm të ndjekur nga kontrollimi i kushtit minimal të mjaftueshëm. Kjo rrugë mund të përdoret ose për një funksion mjaft të thjeshtë për t'u minimizuar, ose për përafrim paraprak të një funksioni mjaft kompleks. polinom P(t k) (zakonisht e shkallës së dytë ose të tretë), dhe më pas gjendja zëvendësohet nga kushti, dhe kushti nga kushti

Sekuenca (xk) përfundon në pikë x k , për të cilën , ku ε - një numër i vogël pozitiv i dhënë, ose k ≥ M , Ku M - numri kufizues i përsëritjeve, ose me dy ekzekutime të njëkohshme të dy pabarazive , Ku ε 2 - numër i vogël pozitiv. Pyetja është nëse një pikë mund x k të konsiderohet si përafrimi i gjetur i pikës minimale lokale të dëshiruar x* , zgjidhet përmes kërkimeve shtesë.

Interpretimi gjeometrik i metodës për n=2 në Fig. 4.

Metoda e zbritjes së koordinatave

Deklarata e problemit

Le të jepet funksioni f(x) , i kufizuar më poshtë në grup Rn dhe që ka derivate të pjesshme të vazhdueshme në të gjitha pikat e tij.

f(x) në grupin e zgjidhjeve të realizueshme X = Rn , d.m.th. gjeni një pikë të tillë që

Strategjia e kërkimit

Strategjia për zgjidhjen e problemit është ndërtimi i një sekuence pikash ( x k } , k = 0,1,..., të tilla që , k = 0,1,... . Pikat e renditjes ( x k ) llogariten me cikle në përputhje me rregullin

(4)

Ku j - numri i ciklit të llogaritjes; j = 0,1,2,...; k - numri i përsëritjes brenda lakut, k = 0,1,... ,n - 1; e k +1, k = 0,l,...,n - 1 - vektori njësi, (k+1) -projeksioni i të cilit është i barabartë me 1; pika x 00 përcaktuar nga përdoruesi, madhësia e hapit tk zgjidhet nga kushti

ose .

Nëse gjendja e zgjedhur në rrymë tk nuk plotësohet, hapi është përgjysmuar dhe periudha llogaritet sërish. Është e lehtë të shihet se për një j fikse, në një përsëritje me numër k ndryshon vetëm një projeksion i pikës x jk , duke pasur një numër k+1 , dhe gjatë gjithë ciklit me numër j , d.m.th. duke filluar nga k = 0 dhe duke përfunduar k = n -1 , të gjitha n projeksionet e pikës ndryshojnë x j0 . Pas kësaj pike x j n është caktuar numri x j + 1.0 , dhe merret si pikënisje për llogaritjet në j+1 ciklit. Llogaritja përfundon në pikën x jk kur të paktën një nga tre kriteret e fundit të numërimit plotësohet: , ose , ose ekzekutimi i dyfishtë i pabarazive.

Pikat e marra si rezultat i llogaritjeve mund të shkruhen si elemente të një sekuence (xl), Ku l=n*j+k - numri serial i pikës,

Interpretimi gjeometrik i metodës për n = 2 është paraqitur në Fig. 5.

4. Metoda Frank-Wolfe .

Supozoni se duhet të gjejmë vlerën maksimale të një funksioni konkav

Në kushte

Një tipar karakteristik i këtij problemi është se sistemi i tij i kufizimeve përmban vetëm pabarazi lineare. Kjo veçori është baza për zëvendësimin e funksionit objektiv jolinear me një funksion linear në afërsi të pikës në studim, për shkak të të cilit zgjidhja e problemit origjinal reduktohet në zgjidhjen sekuenciale të problemeve të programimit linear.
Procesi i gjetjes së një zgjidhjeje për problemin fillon me identifikimin e një pike që i përket rajonit të zgjidhjeve të mundshme të problemit.
270
dacha Le të jetë kjo pika X(k) atëherë në këtë pikë llogaritet gradienti i funksionit (57).

Dhe ndërtoni një funksion linear

Më pas gjeni vlerën maksimale të këtij funksioni nën kufizimet (58) dhe (59). Zgjidhja e këtij problemi le të përcaktohet nga pika Z(k) . Më pas koordinatat e pikës merren si një zgjidhje e re e realizueshme për problemin fillestar X(k+1) :

Ku λ k - një numër i caktuar quhet hapi i llogaritjes dhe i mbyllur midis zeros dhe një (0<λ k < 1). Это число λ k të marra në mënyrë arbitrare ose të përcaktuara

në mënyrë që vlera e funksionit në pikë X (k +1) f(X (k +1)) , në varësi të λ k , ishte maksimumi. Për ta bërë këtë, ju duhet të gjeni një zgjidhje për ekuacionin dhe të zgjidhni rrënjën e tij më të vogël. Nëse vlera e tij është më e madhe se një, atëherë duhet të vendosim λ k=1 . Pas përcaktimit të numrit λ k gjeni koordinatat e një pike X(k+1) llogaritni vlerën e funksionit objektiv në të dhe përcaktoni nevojën për të kaluar në një pikë të re X(k+2) . Nëse ka një nevojë të tillë, atëherë llogarisni në pikën X(k+1) gradienti i funksionit objektiv, shkoni te problemi përkatës i programimit linear dhe gjeni zgjidhjen e tij. Përcaktoni koordinatat e pikës dhe X(k+2) dhe të hetojë nevojën për llogaritje të mëtejshme. Pas një numri të kufizuar hapash, merret një zgjidhje për problemin origjinal me saktësinë e kërkuar.

Pra, procesi i gjetjes së një zgjidhjeje për problemin (57) - (59) duke përdorur metodën Frank-Wolfe përfshin fazat e mëposhtme:

1. Përcaktoni zgjidhjen fillestare të mundshme të problemit.
2. Gjeni gradientin e funksionit (57) në pikën e një zgjidhjeje të pranueshme.
3. Ndërtoni funksionin (60) dhe gjeni vlerën maksimale të tij në kushtet (58) dhe (59).
4. Përcaktoni hapin e llogaritjes.
5. Duke përdorur formulat (61), gjenden përbërësit e një zgjidhjeje të re të realizueshme.
6. Kontrolloni nevojën për të kaluar në zgjidhjen tjetër të mundshme. Nëse është e nevojshme, vazhdoni në fazën 2, përndryshe gjendet një zgjidhje e pranueshme për problemin origjinal.

Mënyra e funksionit të penalltisë.

Shqyrtoni problemin e përcaktimit të vlerës maksimale të funksionit konkav

f (x 1, x 2, .... x n) sipas kushteve g i (x 1, x 2, .... x n) ≤ b i (i=l, m) , x j ≥ 0 (j=1, n) , Ku g i (x 1, x 2, .... x n) - funksionet konvekse.

Në vend që ta zgjidhni këtë problem drejtpërdrejt, gjeni vlerën maksimale të funksionit F(x 1, x 2, ...., x n)= f(x 1, x 2, ...., x n) +H(x 1, x 2, ...., x n) e cila është shuma e funksionit objektiv të problemit dhe disa funksioneve

H(x 1, x 2, ...., x n), i përcaktuar nga një sistem kufizimesh dhe i quajtur funksion penallti. Funksioni i penalltisë mund të ndërtohet në mënyra të ndryshme. Megjithatë, më shpesh duket si

A a i > 0 - disa numra konstante që përfaqësojnë koeficientët e peshimit.
Duke përdorur funksionin e penalltisë, ato lëvizin në mënyrë sekuenciale nga një pikë në tjetrën derisa të marrin një zgjidhje të pranueshme. Në këtë rast, koordinatat e pikës tjetër gjenden duke përdorur formulën

Nga relacioni i fundit rezulton se nëse pika e mëparshme është në rajonin e zgjidhjeve të realizueshme të problemit fillestar, atëherë termi i dytë në kllapa katrore është i barabartë me zero dhe kalimi në pikën tjetër përcaktohet vetëm nga gradienti i objektivit. funksionin. Nëse pika e specifikuar nuk i përket rajonit të zgjidhjeve të pranueshme, atëherë për shkak të këtij termi në përsëritjet pasuese arrihet një kthim në rajonin e zgjidhjeve të pranueshme.
vendimet. Në të njëjtën kohë, aq më pak a i , aq më shpejt gjendet një zgjidhje e pranueshme, por saktësia e përcaktimit të saj zvogëlohet. Prandaj, procesi përsëritës zakonisht fillon me vlera relativisht të vogla a i dhe, duke vazhduar me të, këto vlera rriten gradualisht.

Pra, procesi i gjetjes së një zgjidhjeje për një problem programimi konveks duke përdorur metodën e funksionit të penalitetit përfshin hapat e mëposhtëm:

1. Përcaktoni zgjidhjen fillestare të realizueshme.
2. Zgjidhni hapin e llogaritjes.
3. Gjeni, për të gjitha variablat, derivatet e pjesshme të funksionit objektiv dhe funksionet që përcaktojnë gamën e zgjidhjeve të realizueshme të problemit.

4. Me formulën (72) gjenden koordinatat e pikës që përcakton një zgjidhje të re të mundshme të problemit.
5. Kontrollo nëse koordinatat e pikës së gjetur plotësojnë sistemin e kufizimeve të problemit. Nëse jo, atëherë kaloni në fazën tjetër. Nëse koordinatat e pikës së gjetur përcaktojnë një zgjidhje të pranueshme të problemit, atëherë hetohet nevoja për të kaluar në zgjidhjen tjetër të pranueshme. Nëse është e nevojshme, vazhdoni në fazën 2, përndryshe është gjetur një zgjidhje e pranueshme për problemin origjinal.
6. Vendosni vlerat e koeficientëve të peshimit dhe vazhdoni në hapin 4.

Metoda Arrow-Hurwitz.

Kur gjejmë zgjidhje për problemet e programimit jolinear duke përdorur metodën e funksionit të penalltisë, ne zgjodhëm vlerat a i , në mënyrë arbitrare, gjë që çoi në luhatje të konsiderueshme në distancën e pikave të përcaktuara nga rajoni i zgjidhjeve të realizueshme. Ky pengesë eliminohet kur zgjidhet problemi me metodën Arrow-Hurwitz, sipas së cilës në hapin tjetër numrat a i (k) llogaritur me formulë

Si vlera fillestare a i (0) marrin numra arbitrarë jo negativë.

SHEMBULL ZGJIDHJE

Shembulli 1.

Gjeni minimumin lokal të një funksioni

Përcaktimi i një pike x k

1. Le të vendosim .

2. Le të vëmë k = 0 .

3 0 . Le të llogarisim

4 0 . Le të llogarisim . Le të kalojmë në hapin 5.

5 0 . Le të kontrollojmë gjendjen . Le të kalojmë në hapin 6.

6 0 . Le të vendosim t0 = 0,5 .

7 0 . Le të llogarisim

8 0 . Le të krahasojmë . ne kemi . Përfundim: kusht për k = 0 nuk ekzekutohet. Le të vendosim t0 = 0,25 , vazhdoni me përsëritjen e hapave 7, 8.

7 01. Le të llogarisim.

8 01. Le të krahasojmë f (x 1) dhe f (x 0) . konkluzioni: f (x 1)< f (x 0) . Le të kalojmë në hapin 9.

9 0 . Le të llogarisim

Përfundim: ne besojmë k =1 dhe shkoni në hapin 3.

3 1. Le të llogarisim

4 1. Le të llogarisim . Le të kalojmë në hapin 5.

5 1. Le të kontrollojmë gjendjen k ≥ M: k = 1< 10 = M . Le të kalojmë në hapin 6.

6 1. Le të vendosim t 1 = 0,25.

7 1. Le të llogarisim

8 1. Le të krahasojmë f (x 2) me f (x 1) . konkluzioni: f (x 2)< f (х 1). Le të kalojmë në hapin 9.

9 1. Le të llogarisim

Përfundim: ne besojmë k = 2 dhe shkoni në hapin 3.

3 2. Le të llogarisim

4 2. Le të llogarisim. Le të kalojmë në hapin 5.

5 2. Le të kontrollojmë gjendjen k ≥ M : k = 2< 10 = М , shkoni në hapin 6.

6 2. Le të vendosim t 2 =0,25 .

7 2. Le të llogarisim

8 2. Le të krahasojmë f (x 3) Dhe f (x 2) . konkluzioni: f (x 3)< f (х 2) .Shkoni në hapin 9.

9 2. Le të llogarisim

Përfundim: ne besojmë k = 3 dhe shkoni në hapin 3.

3 3 . Le të llogarisim

4 3 . Le të llogarisim. Le të kalojmë në hapin 5.

5 3. Le të kontrollojmë gjendjen k ≥ M : k = 3<10 = М , shkoni në hapin 6.

6 3. Le të vendosim t 3 = 0,25.

7 3. Le të llogarisim

8 3. Le të krahasojmë f (x 4) Dhe f (x 3) : f (x 4)< f (х 3) .

9 3. Le të llogarisim

Kushtet plotësohen kur k = 2,3 . Llogaritja

përfunduar. Pika e gjetur

Në Fig. 3 pikat që rezultojnë janë të lidhura me një vijë me pika.

II. Analiza e pikave x 4 .

Funksioni është dy herë i diferencueshëm, ndaj do të kontrollojmë kushtet e mjaftueshme për minimumin në pikë x 4 . Për ta bërë këtë, le të analizojmë matricën Hessian.

Matrica është konstante dhe e përcaktuar pozitive (d.m.th. . H > 0 ) meqenëse të dyja minoret këndore të saj janë pozitive. Prandaj, pika është përafrimi i gjetur i pikës minimale lokale, dhe vlerës është përafrimi i gjetur i vlerës f (x *) =0 . Vini re se kushti H > 0 , ekziston në të njëjtën kohë një kusht për konveksitet të rreptë të funksionit . Rrjedhimisht, janë gjetur përafrime të pikës minimale globale f(x) dhe vlera minimale e tij në R 2 . ■

Shembulli 2

Gjeni minimumin lokal të një funksioni

I. Përkufizimi i një pike x k, në të cilën plotësohet të paktën një nga kriteret për plotësimin e llogaritjeve.

1. Le të vendosim .

Le të gjejmë gradientin e funksionit në një pikë arbitrare

2. Le të vëmë k = 0 .

3 0 . Le të llogarisim

4 0 . Le të llogarisim . Le të kalojmë në hapin 5.

5 0 . Le të kontrollojmë gjendjen . Le të kalojmë në hapin 6.

6° Pika tjetër gjendet nga formula

Le të zëvendësojmë shprehjet e marra për koordinatat në

Le të gjejmë minimumin e funksionit f(t 0) Nga t 0 duke përdorur kushtet e nevojshme për një ekstrem të pakushtëzuar:

Nga këtu t 0 =0,24 . Sepse , vlera e gjetur e hapit siguron minimumin e funksionit f(t 0) Nga t 0 .

Le të përcaktojmë

7 0 . Ne do të gjejmë

8°. Le të llogarisim

Përfundim: ne besojmë k = 1 dhe shkoni në hapin 3.

3 1. Le të llogarisim

4 1. Le të llogarisim

5 1. Le të kontrollojmë gjendjen k ≥ 1: k = 1< 10 = М.

6 1. Le të përcaktojmë

7 1. Ne do të gjejmë :

8 1. Le të llogarisim

ne besojmë k = 2 dhe shkoni në hapin 3.

3 2. Le të llogarisim

4 2. Le të llogarisim

5 2. Le të kontrollojmë gjendjen k ≥ M: k = 2< 10 = M .

6 2. Le të përcaktojmë

7 2. Ne do të gjejmë

8 2. Le të llogarisim

ne besojmë k =3 dhe shkoni në hapin 3.

3 3 . Le të llogarisim

4 3 . Le të llogarisim.

Llogaritja është përfunduar. Pika e gjetur

II. Analiza e pikave x 3 .

Në shembullin 1.1 (Kapitulli 2 §1) u tregua se funksioni f(x) është rreptësisht konveks dhe, për rrjedhojë, në pikat 3 është përafrimi i gjetur i pikës minimale globale X* .

Shembulli 3.

Gjeni minimumin lokal të një funksioni

I. Përkufizimi i një pike xjk , në të cilën plotësohet të paktën një nga kriteret për plotësimin e llogaritjeve.

1. Le të vendosim

Le të gjejmë gradientin e funksionit në një pikë arbitrare

2. Le të vendosim j = 0.

3 0 . Le të kontrollojmë nëse kushti është plotësuar

4 0 . Le të vendosim k = 0.

5 0 . Le të kontrollojmë nëse kushti është plotësuar

6 0 . Le të llogarisim

7 0 . Le të kontrollojmë gjendjen

8 0 . Le të vendosim

9 0 . Le të llogarisim , Ku

10 0 . Le të kontrollojmë gjendjen

Përfundim: supozojmë dhe kalojmë në hapin 9.

9 01. Le të llogarisim x 01 në rritje

10 01. Le të kontrollojmë gjendjen

11 0 . Le të kontrollojmë kushtet

ne besojmë k =1 dhe shkoni në hapin 5.

5 1. Le të kontrollojmë gjendjen

6 1. Le të llogarisim

7 1. Le të kontrollojmë gjendjen

8 1. Le të vendosim

9 1. Le të llogarisim

10 1. Le të kontrollojmë gjendjen :

11 1. Le të kontrollojmë kushtet

ne besojmë k = 2 , shkoni në hapin 5.

5 2. Le të kontrollojmë gjendjen. Le të vendosim, shkojmë në hapin 3.

3 1. Le të kontrollojmë gjendjen

4 1. Le të vendosim k = 0.

5 2. Le të kontrollojmë gjendjen

6 2. Le të llogarisim

7 2. Le të kontrollojmë gjendjen

8 2. Le të vendosim

9 2. Le të llogarisim

10 2. Le të kontrollojmë gjendjen

11 2. Le të kontrollojmë kushtet

ne besojmë k =1 dhe shkoni në hapin 5.

5 3. Le të kontrollojmë gjendjen

6 3. Le të llogarisim

7 3. Le të kontrollojmë kushtet

8 3. Le të vendosim

9 3. Le të llogarisim

10 3. Le të kontrollojmë gjendjen

11 3. Le të kontrollojmë kushtet

Le të vendosim k = 2 dhe shkoni në hapin 5.

5 4. Le të kontrollojmë gjendjen

ne besojmë j = 2, x 20 = x 12 dhe shkoni në hapin 3.

3 2. Le të kontrollojmë gjendjen

4 2. Le të vendosim k =0 .

5 4. Le të kontrollojmë gjendjen

6 4. Le të llogarisim

7 4. Le të kontrollojmë gjendjen

8 4 . Le të vendosim

9 4. Le të llogarisim

10 4. Le të kontrollojmë gjendjen dhe të kalojmë në hapin 11.

11 4. Le të kontrollojmë kushtet

Kushtet plotësohen në dy cikle radhazi me numra j=2 Dhe j -1= 1 . Llogaritja ka përfunduar, pika është gjetur

Në Fig. 6 pikat që rezultojnë janë të lidhura me një vijë me pika.

Në metodën e zbritjes së koordinatave, ne zbresim përgjatë një linje të thyer të përbërë nga segmente të drejta paralele me boshtet e koordinatave.

II. Analiza e pikës x21.

Në shembullin 1.1 u tregua se funksioni f(x) është rreptësisht konveks, ka një minimum unik dhe, për rrjedhojë, një pikë është përafrimi i gjetur i pikës minimale globale.

Në të gjitha metodat e gradientit të diskutuar më sipër, sekuenca e pikave (xk) konvergon në pikën e palëvizshme të funksionit f(x) me propozime mjaft të përgjithshme lidhur me vetitë e këtij funksioni. Në veçanti, teorema është e vërtetë:

Teorema. Nëse funksioni f(x) është i kufizuar më poshtë, gradienti i tij plotëson kushtin Lipschitz () dhe zgjedhjen e vlerës tn prodhuar me një nga metodat e përshkruara më sipër, atëherë cilado qoftë pika e fillimit x 0 :

në .

Në zbatimin praktik të skemës

k =1, 2, … n.

përsëritjet ndalojnë nëse për të gjithë i, i = 1, 2, ..., n , kushte si

,

ku është një numër i dhënë që karakterizon saktësinë e gjetjes së minimumit.

Në kushtet e teoremës, metoda e gradientit siguron konvergjencë në funksion ose në kufirin e saktë të poshtëm (nëse funksioni f(x) nuk ka minimum; oriz. 7), ose në vlerën e funksionit në një pikë të palëvizshme, që është kufiri i sekuencës (x k). Nuk është e vështirë të dalësh me shembuj kur një shalë realizohet në këtë pikë, dhe jo një minimum. Në praktikë, metodat e zbritjes me gradient anashkalojnë me siguri pikat e shalës dhe gjejnë minimumin e funksionit objektiv (në rastin e përgjithshëm, ato lokale).

PËRFUNDIM

Shembuj të metodave të optimizimit të pakufizuar të gradientit u diskutuan më lart. Si rezultat i punës së bërë, mund të nxirren përfundimet e mëposhtme:

1. Problemet pak a shumë komplekse të gjetjes së një ekstremi në prani të kufizimeve kërkojnë qasje dhe metoda të veçanta.

2. Shumë algoritme për zgjidhjen e problemeve të kufizuara përfshijnë minimizimin e pakufizuar si disa hapa.

3. Metodat e ndryshme të zbritjes ndryshojnë nga njëra-tjetra në mënyrën se si zgjedhin drejtimin e zbritjes dhe gjatësinë e hapit përgjatë këtij drejtimi.

4. Nuk ka ende një teori që do të merrte parasysh ndonjë veçori të funksioneve që përshkruajnë formulimin e problemit. Preferenca duhet t'u jepet metodave që janë më të lehta për t'u menaxhuar në procesin e zgjidhjes së një problemi.

Problemet reale të optimizimit të aplikuar janë shumë komplekse. Metodat moderne të optimizimit jo gjithmonë përballen me zgjidhjen e problemeve reale pa ndihmën e njeriut.

REFERENCAT

1. Kosorukov O.A. Hulumtimi i Operacioneve: Një Libër mësimi. 2003

2. Pantleev A.V. Metodat e optimizimit në shembuj dhe problema: tekst shkollor. Përfitoni. 2005

3. Shishkin E.V. Hulumtimi i operacioneve: tekst shkollor. 2006

4. Akulich I.L. Programimi matematikor në shembuj dhe problema. 1986

5. Ventzel E.S. Hulumtimi i Operacioneve. 1980

6. Ventzel E.S., Ovcharov L.A. Teoria e probabilitetit dhe aplikimet e saj inxhinierike. 1988

©2015-2019 sajti
Të gjitha të drejtat u përkasin autorëve të tyre. Kjo faqe nuk pretendon autorësinë, por ofron përdorim falas.
Data e krijimit të faqes: 2017-07-02

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

Koment. 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)

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 drejt 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 të gradientit dhe të minimizimit, 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[k r ] anti-gradient - f'(x ) [k] X[k në pikën

], marrim një proces përsëritës të formës X[ 1] = k+[k]-x f'(x ) , a k f"(x > 0; k=0, 1, 2, ...

dhe k

Në formë koordinative, ky proces shkruhet si më poshtë: k+1]=x i [[k] - x if(x f'(x ) një k

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

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

|| - x[k f'(x ) || <= g ,

+l]

Këtu e dhe g janë dhënë sasi të vogla. a k f"(x.

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 a k f"(x 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

do të sigurojë që funksioni të zvogëlohet, d.m.th., pabarazia k+1]) = f(x f(x[ [k] - f'(x )) < f(x f'(x ) .

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 a k f"(x 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 f'(x – 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 - 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[X[ 1]:

x i [ X[ 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ë k+[X[ 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 f'(x -af" (x[k])) . Kusht i domosdoshëm për minimumin e një funksioni j d(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[X[ 1]- x[k]) = 0.

Oriz. 2.9. M Interpretimi gjeometrik i metodës së zbritjes më të pjerrët 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ë 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) =1, …, n i kushtëzuar mirë. Kujtojmë që vlerat e veta l i,

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

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

X fq.[k]) 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], të konjuguara-konjugohet me drejtimet e gjetura më parë Zgjedhja si drejtimi i zbritjes, Zgjedhja si drejtimi i zbritjes, ..., Zgjedhja si drejtimi i zbritjes[k-1].

Le ta shqyrtojmë fillimisht këtë metodë në lidhje me problemin e minimizimit të një funksioni kuadratik. Zgjedhja si drejtimi i zbritjes[k Drejtimet

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

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

f k b vlerat -f(x[k], Zgjedhja si drejtimi i zbritjes[k-1 janë zgjedhur në mënyrë që drejtimet të konjuguara-1] ishin :

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

k-

,

Si rezultat, për funksionin kuadratik

procesi i minimizimit iterativ ka formën k f'(x x[[k]=x[k],

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

do të sigurojë që funksioni të zvogëlohet, d.m.th., pabarazia k] + f(x)[k]) = f(x[k] + në drejtim të lëvizjes, pra si rezultat i zgjidhjes së problemit të minimizimit njëdimensional: [k]) .

a k r

ar

Për një funksion kuadratik X Algoritmi i metodës së gradientit të konjuguar Fletcher-Reeves është si më poshtë. -f(x = -- x) .

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

k f(x[k+1]) dhe periudha - x[k+1]) .

3. Vlerat janë llogaritur - x) Dhe X[k 4. Nëse = 0, pastaj pikë+1] është pika minimale e funksionit -f(x[k f(x).

Përndryshe, përcaktohet një drejtim i ri N -+l] nga relacioni 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. X Kur minimizohen funksionet jo-kuadratike, metoda Fletcher-Reeves bëhet përsëritëse nga e fundme. Në këtë rast, pas X[N -(p+

procesi i minimizimit iterativ ka formën k f'(x 1) përsëritja e procedurës 1-4 përsëriten në mënyrë ciklike me zëvendësim[k]=x[k],

] llogaritet duke përdorur formulat: k] në[k])+ +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: HP 1 -f(x[k+b k-1 k>= 1;

= x k+);

do të sigurojë që funksioni të zvogëlohet, d.m.th., pabarazia k] + = -f'(x[k]) = f(x[k] b[k];

.

p = -f'( a k p+ap a k p Këtu I- shumë indekse: N -= (0, n, 2

p, paga, ...) X, pra metoda përditësohet çdo Zgjedhja si drejtimi i zbritjes = hapat. Kuptimi gjeometrik i metodës së gradientit të konjuguar është si më poshtë (Fig. 2.11). Nga një pikënisje e caktuar X zbritja kryhet në drejtim -f"(x). X Në pikën Zgjedhja si drejtimi i zbritjes, përcaktohet vektori i gradientit ] anti-gradient -) f" (x Zgjedhja si drejtimi i zbritjes). Që nga viti Zgjedhja si drejtimi i zbritjes , të konjuguaraështë pika minimale e funksionit në drejtim Zgjedhja si drejtimi i zbritjes Se Zgjedhja si drejtimi i zbritjes ortogonal në vektor

. Më pas, gjejmë minimumin e funksionit përgjatë drejtimit N -= (0, n, 2

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

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ë për zgjedhjen optimale të parametrave: , megjithëse metoda nuk është shumë e ndjeshme ndaj zgjedhjes së parametrave.

Metoda e zbritjes më të pjerrët

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 ndalues ​​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 optimizimin e pakushtëzuar 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 thjeshtimeve marrim formulat përfundimtare të përdorura gjatë aplikimit 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.