Si të gjeni normalen në një vijë në hapësirë. Si të gjejmë ekuacionet e rrafshit tangjent dhe sipërfaqes normale në një pikë të caktuar? Lloji i ekuacionit të planit sipas koordinatave të dy pikave dhe një vektori kolinear me rrafshin

Le të shqyrtojmë problemin e minimizimit të pakushtëzuar të një funksioni të diferencueshëm të shumë ndryshoreve, le t'i afrohemi vlerës së gradientit në pikën minimale funksioni jepet nga antigradienti Kjo veti përdoret në mënyrë të konsiderueshme në një sërë metodash minimizimi. Në metodën e gradientit të konsideruar më poshtë, drejtimi i zbritjes nga pika zgjidhet drejtpërdrejt, kështu, sipas metodës së gradientit

Ka mënyra të ndryshme përzgjedhja e hapave, secila prej të cilave specifikon një opsion specifik metoda e gradientit.

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

Le të shqyrtojmë një funksion të një ndryshoreje skalare dhe të zgjedhim si vlerën për të cilën vlen barazia

Kjo metodë, e propozuar në 1845 nga O. Cauchy, tani quhet zakonisht metoda e zbritjes më të pjerrët.

Në Fig. Figura 10.5 tregon një ilustrim gjeometrik të kësaj metode për minimizimin e një funksioni të dy variablave. Nga pika e fillimit pingul me vijën e nivelit në drejtim të zbritjes, zbritja vazhdon derisa të arrihet vlera minimale e funksionit përgjatë rrezes. Në pikën e gjetur, kjo rreze prek vijën e nivelit Më pas, nga pika, kryhet një zbritje në pingul me vijën drejtimi i nivelit derisa rrezja përkatëse të prekë në një pikë vijën e nivelit që kalon në këtë pikë, etj.

Vini re se në çdo përsëritje, zgjedhja e hapit përfshin zgjidhjen e problemit të minimizimit njëdimensional (10.23). Ndonjëherë ky operacion mund të kryhet në mënyrë analitike, për shembull për funksion kuadratik.

Le të përdorim metodën e zbritjes më të pjerrët për të minimizuar funksionin kuadratik

me një matricë të caktuar simetrike pozitive A.

Sipas formulës (10.8), në këtë rast, formula (10.22) duket kështu:

Vini re se

Ky funksion është një funksion kuadratik i parametrit a dhe arrin një minimum në një vlerë për të cilën

Kështu, në lidhje me minimizimin e kuadratit

funksioni (10.24), metoda e zbritjes më të pjerrët është ekuivalente me llogaritjen duke përdorur formulën (10.25), ku

Vërejtje 1. Meqenëse pika minimale e funksionit (10.24) përkon me zgjidhjen e sistemit, metoda e zbritjes më të pjerrët (10.25), (10.26) mund të përdoret gjithashtu si metodë përsëritëse për zgjidhjen e sistemeve lineare. ekuacionet algjebrike me matrica të përcaktuara pozitive simetrike.

Vërejtje 2. Vini re se ku është raporti Rayleigh (shih § 8.1).

Shembulli 10.1. Le të përdorim metodën e zbritjes më të pjerrët për të minimizuar funksionin kuadratik

Vini re se Prandaj vlerën e saktë ne e dimë pikën minimale paraprakisht. Le ta shkruajmë këtë funksion në formën (10.24), ku matrica dhe vektori As është i lehtë për t'u parë,

Le të marrim përafrimin fillestar dhe të bëjmë llogaritjet duke përdorur formulat (10.25), (10.26).

I përsëritje.

përsëritje II.

Mund të tregohet se për të gjitha përsëritjet do të merren vlerat

Vini re se për Kështu,

sekuenca e marrë me metodën e zbritjes më të pjerrët konvergon me shpejtësinë progresion gjeometrik, emëruesi i të cilit

Në Fig. Figura 10.5 tregon saktësisht trajektoren e zbritjes që është marrë në këtë shembull.

Për rastin e minimizimit të një funksioni kuadratik, vlen sa vijon: rezultat i përgjithshëm.

Teorema 10.1. Le të jetë A një matricë e caktuar simetrike pozitive dhe funksioni kuadratik (10.24) minimizohet. Pastaj, për çdo zgjedhje të përafrimit fillestar, metoda e zbritjes më të pjerrët (10.25), (10.26) konvergjon dhe vlerësimi i mëposhtëm i gabimit është i saktë:

Këtu dhe Lado - minimale dhe maksimale eigenvlerat matricat A.

Vini re se kjo metodë konvergon me shpejtësinë e një progresion gjeometrik, emëruesi i të cilit, nëse janë afër, është i vogël dhe metoda konvergjon mjaft shpejt. Për shembull, në shembullin 10.1 kemi dhe për këtë arsye If Aschach, atëherë 1 dhe duhet të presim konvergjencë të ngadaltë të metodës së zbritjes më të pjerrët.

Shembulli 10.2. Zbatimi i metodës së zbritjes më të pjerrët për të minimizuar funksionin kuadratik gjatë përafrimit fillestar jep një sekuencë përafrimesh ku trajektorja e zbritjes është paraqitur në Fig. 10.6.

Sekuenca konvergjon këtu me shpejtësinë e një progresion gjeometrik, emëruesi i të cilit është i barabartë me, d.m.th., dukshëm më i ngadalshëm,

Do ta provoj se në atë të mëparshmen. Meqenëse këtu rezultati i marrë është mjaft në përputhje me vlerësimin (10.27).

Vërejtje 1. Formuluam një teoremë mbi konvergjencën e metodës së zbritjes më të pjerrët në rastin kur funksioni objektiv është kuadratik. NË rast i përgjithshëm, nëse funksioni që do të minimizohet është rreptësisht konveks dhe ka një pikë minimale x, atëherë gjithashtu, pavarësisht nga zgjedhja përafrimi fillestar Sekuenca e përftuar me këtë metodë konvergon në x si . Në këtë rast, pasi futet një lagje mjaft e vogël e pikës minimale, konvergjenca bëhet lineare dhe emëruesi i progresionit gjeometrik përkatës vlerësohet nga lart me vlerën dhe ku si minimumi ashtu edhe maksimumi eigenvlerat Matricat Hessian

Vërejtje 2. Për kuadratik funksion objektiv(10.24) zgjidhja e problemit të minimizimit njëdimensional (10.23) mund të gjendet në formën e një formulë eksplicite(10.26). Megjithatë, për shumicën e funksioneve të tjera jolineare kjo nuk mund të bëhet dhe për të llogaritur metodën e zbritjes më të pjerrët duhet të përdoret metodat numerike minimizimi njëdimensional i tipit të diskutuar në kapitullin e mëparshëm.

2. Problemi i “përrenjve”.

Nga diskutimi i mësipërm rezulton se metoda e gradientit konvergon mjaft shpejt nëse, për funksionin që minimizohet, sipërfaqet e nivelit janë afër sferave (nëse vijat e nivelit janë afër rrathëve). Për funksione të tilla dhe 1. Teorema 10.1, Vërejtje 1, si dhe rezultati i Shembullit 10.2 tregojnë se shkalla e konvergjencës bie ndjeshëm me rritjen e vlerës Në të vërtetë, dihet se metoda e gradientit konvergon shumë ngadalë nëse sipërfaqet e nivelit të funksioni që minimizohet janë shumë të zgjatur në disa drejtime. Në rastin dydimensional, relievi i sipërfaqes përkatëse i ngjan terrenit me përroskë (Fig. 10.7). Prandaj, funksione të tilla zakonisht quhen funksione grykë. Përgjatë drejtimeve që karakterizojnë "fundin e përroskës", funksioni i grykës ndryshon pak, por në drejtime të tjera që karakterizojnë "pjerrësinë e përroskës", ndodh një ndryshim i mprehtë në funksion.

Nëse pika e fillimit bie në "shpatin e përroskës", atëherë drejtimi i zbritjes së gradientit rezulton të jetë pothuajse pingul me "fundin e përroskës" dhe afrimi tjetër bie në "pjerrësinë e përroskës" të kundërt. Hapi tjetër drejt “fundit të përroskës” e kthen afrimin në “shpatin e përroskës” origjinale. Si rezultat, në vend që të lëvizë përgjatë "fundit të përroskës" drejt pikës minimale, trajektorja e zbritjes bën kërcime zigzag përgjatë "gropës", pothuajse asnjëherë duke mos iu afruar qëllimit (Fig. 10.7).

Për të përshpejtuar konvergjencën e metodës së gradientit duke minimizuar funksionet e grykës, janë zhvilluar një sërë metodash speciale "gulle". Le të japim një ide për një nga teknikat më të thjeshta. Nga dy pikënisje të afërta ata bëjnë një zbritje gradient deri në "fundin e përroskës". Nëpër pikat e gjetura vizatohet një vijë e drejtë, përgjatë së cilës hidhet një hap i madh “gulle” (Fig. 10.8). Nga pika e gjetur në këtë mënyrë, një hap i zbritjes së gradientit merret përsëri në pikën Më pas një hap i dytë "gulle" ndërmerret përgjatë vijës së drejtë që kalon nëpër pika. Si rezultat, lëvizja përgjatë "fundit të përroskës" deri në pikën minimale është përshpejtuar ndjeshëm.

Më shumë informacion të detajuar në lidhje me problemin e metodave "graka" dhe "gulle" mund të gjenden, për shembull, në,.

3. Qasje të tjera për përcaktimin e hapit të zbritjes.

Siç është e lehtë për t'u kuptuar, në çdo përsëritje do të ishte e dëshirueshme të zgjidhni një drejtim zbritjeje afër drejtimit përgjatë të cilit lëviz lëvizja nga pika në pikën x. Fatkeqësisht, antigradienti (është, si rregull, një drejtim i pasuksesshëm i zbritjes. Kjo është veçanërisht e theksuar për funksionet e grykës. Prandaj, lind dyshimi për këshillueshmërinë e një kërkimi të plotë për një zgjidhje për problemin e minimizimit njëdimensional (10.23) dhe ekziston dëshira për të ndërmarrë vetëm një hap të tillë në drejtimin që do të siguronte "ulje të ndjeshme" të funksionit Për më tepër, në praktikë, ndonjëherë ata mjaftohen me përcaktimin e një vlere që thjesht siguron një ulje të vlerës së funksionit objektiv.

Metodat e gradientit për kërkimin e optimumit të funksionit objektiv bazohen në përdorimin e dy vetitë themelore funksioni i gradientit.

1. Gradienti i një funksioni është një vektor që në çdo pikë të fushës së përcaktimit të funksionit
drejtuar normalisht në sipërfaqen e nivelit të tërhequr përmes kësaj pike.

Projeksionet e gradientit
në boshtin koordinativ janë të barabartë me derivatet e pjesshme të funksionit
sipas variablave përkatës, d.m.th.

. (2.4)

Metodat e gradientit përfshijnë: metodën e relaksimit, metodën e gradientit, metodën e zbritjes më të pjerrët dhe një sërë të tjerash.

Le të shohim disa nga metodat e gradientit.

Metoda e gradientit

Në këtë metodë, zbritja kryhet në drejtim të ndryshimit më të shpejtë të funksionit objektiv, i cili natyrisht përshpejton procesin e gjetjes së optimumit.

Kërkimi për optimumin kryhet në dy faza. Në fazën e parë, gjenden vlerat e derivateve të pjesshme në lidhje me të gjitha variablat e pavarur, të cilat përcaktojnë drejtimin e gradientit në pikën në fjalë. Në fazën e dytë, bëhet një hap në drejtim të kundërt me drejtimin e gradientit (kur kërkohet minimumi i funksionit objektiv).

Kur ekzekutohet një hap, vlerat e të gjitha variablave të pavarur ndryshojnë njëkohësisht. Secili prej tyre merr një rritje në përpjesëtim me komponentin përkatës të gradientit përgjatë një boshti të caktuar.

Shënimi formulaik i algoritmit mund të duket si ky:

,
. (2.5)

Në këtë rast, madhësia e hapit
në vlerë konstante parametri h ndryshon automatikisht me ndryshimet në vlerën e gradientit dhe zvogëlohet kur i afrohet optimumit.

Një formulë tjetër për algoritmin është:

,
. (2.6)

Ky algoritëm përdor një vektor të gradientit të normalizuar që tregon vetëm drejtimin e ndryshimit më të shpejtë në funksionin objektiv, por nuk tregon shkallën e ndryshimit në këtë drejtim.

Në strategjinë e ndryshimit të hapit
në këtë rast përdoret që gradientët
Dhe
ndryshojnë në drejtim. Hapi i kërkimit ndryshohet në përputhje me rregullin:

(2.7)

Ku
– këndi i rrotullimit të gradientit në hapin k-të, i përcaktuar nga shprehja

,

,
– kufijtë e lejuar të këndit të rrotullimit të gradientit.

Natyra e kërkimit për optimumin në metodën e gradientit është paraqitur në Fig. 2.1.

Momenti i përfundimit të kërkimit mund të gjendet duke kontrolluar në çdo hap të lidhjes

,

Ku – gabimi i specifikuar i llogaritjes.

Oriz. 2.1. Natyra e lëvizjes drejt optimumit në metodën e gradientit me një madhësi të madhe hapi

Disavantazhi i metodës së gradientit është se kur përdoret, mund të zbulohet vetëm minimumi lokal i funksionit objektiv. Për të gjetur minimume të tjera lokale për një funksion, është e nevojshme të kërkoni nga pika të tjera fillestare.

Një tjetër disavantazh i kësaj metode është sasia e konsiderueshme e llogaritjeve, sepse në çdo hap, përcaktohen vlerat e të gjithë derivateve të pjesshëm të funksionit të optimizuar në lidhje me të gjitha variablat e pavarur.

Metoda e zbritjes më të pjerrët

Kur aplikoni metodën e gradientit, në çdo hap është e nevojshme të përcaktohen vlerat e derivateve të pjesshme të funksionit që optimizohet në lidhje me të gjitha variablat e pavarur. Nëse numri i variablave të pavarur është i rëndësishëm, atëherë vëllimi i llogaritjeve rritet ndjeshëm dhe koha e nevojshme për të gjetur optimumin rritet.

Zvogëlimi i sasisë së llogaritjes mund të arrihet duke përdorur metodën e zbritjes më të pjerrët.

Thelbi i metodës është si më poshtë. Pas në pikënisje do të gjendet gradienti i funksionit të optimizuar dhe në këtë mënyrë do të përcaktohet drejtimi i uljes më të shpejtë të tij në pikën e specifikuar, në në këtë drejtim bëhet një hap zbritjeje (Fig. 2.2).

Nëse vlera e funksionit zvogëlohet si rezultat i këtij hapi, një hap tjetër ndërmerret në të njëjtin drejtim dhe kështu me radhë derisa të gjendet një minimum në këtë drejtim, pas së cilës llogaritet gradienti dhe një drejtim i ri i uljes më të shpejtë të përcaktohet funksioni objektiv.

Oriz. 2.2. Natyra e lëvizjes drejt optimumit në metodën e zbritjes më të pjerrët (–) dhe metodën e gradientit (∙∙∙∙)

Krahasuar me metodën e gradientit, metoda e zbritjes më të pjerrët është më e favorshme për shkak të zvogëlimit të sasisë së llogaritjeve.

Karakteristikë e rëndësishme Metoda më e pjerrët e zbritjes është se kur zbatohet, çdo drejtim i ri i lëvizjes drejt optimumit është ortogonal me atë të mëparshëm. Kjo shpjegohet me faktin se lëvizja në një drejtim kryhet derisa drejtimi i lëvizjes të jetë tangjent me çdo vijë të një niveli konstant.

I njëjti kusht si në metodën e diskutuar më sipër mund të përdoret si kriter për përfundimin e kërkimit.

Përveç kësaj, ju gjithashtu mund të merrni kushtin e përfundimit të kërkimit në formën e lidhjes

,

Ku
Dhe
– koordinatat e pikave të fillimit dhe mbarimit të segmentit të fundit të zbritjes. I njëjti kriter mund të përdoret në kombinim me monitorimin e vlerave të funksionit objektiv në pika
Dhe

.

Zbatimi i përbashkët i kushteve të përfundimit të kërkimit justifikohet në rastet kur funksioni që optimizohet ka një minimum të përcaktuar qartë.

Oriz. 2.3. Për të përcaktuar përfundimin e kërkimit në metodën e zbritjes më të pjerrët

Si një strategji për ndryshimin e hapit të zbritjes, mund të përdorni metodat e përshkruara më sipër (2.7).

Metoda bazohet në modifikimin e mëposhtëm përsëritës të formulës

x k +1 = x k + a k s(x k),

x k+1 = x k - a k Ñ f(x k), ku

a është një koeficient pozitiv i dhënë;

Ñ f(x k) është gradienti i funksionit objektiv të rendit të parë.

Të metat:

nevoja për të zgjedhur një vlerë të përshtatshme ;

konvergjenca e ngadaltë në pikën minimale për shkak të vogëlsisë së f(x k) në afërsi të kësaj pike.

Metoda e zbritjes më të pjerrët

I lirë nga pengesa e parë e metodës më të thjeshtë të gradientit, sepse a k llogaritet duke zgjidhur problemin e minimizimit të Ñ f(x k) përgjatë drejtimit Ñ f(x k) duke përdorur një nga metodat e optimizimit njëdimensional x k+1 = x k - a k Ñ f(x k).

Kjo metodë nganjëherë quhet metoda Cauchy.

Algoritmi karakterizohet nga një shkallë e ulët konvergjence gjatë zgjidhjes së problemeve praktike. Kjo shpjegohet me faktin se ndryshimet në variabla varen drejtpërdrejt nga vlera e gradientit, e cila tenton në zero në afërsi të pikës minimale dhe nuk ka mekanizëm nxitimi në përsëritjet e fundit. Prandaj, duke marrë parasysh stabilitetin e algoritmit, metoda e zbritjes më të pjerrët shpesh përdoret si procedurë fillestare për gjetjen e një zgjidhjeje (nga pikat e vendosura në distanca të konsiderueshme nga pika minimale).

Metoda e drejtimeve të konjuguara

Problemi i përgjithshëm i programimit jolinear të pakufizuar zbret në sa vijon: minimizoni f(x), x E n, ku f(x) është funksioni objektiv. Gjatë zgjidhjes së këtij problemi, ne përdorim metoda minimizimi që çojnë në një pikë stacionare f(x), të përcaktuar nga ekuacioni f(x *)=0. Metoda e drejtimit të konjuguar i referohet metodave të minimizimit të pakufizuara që përdorin derivate. Problemi: minimizoni f(x), x E n, ku f(x) është funksioni objektiv i n variablave të pavarur. Një tipar i rëndësishëm është konvergjenca e shpejtë për faktin se kur zgjedh një drejtim, përdoret matrica Hessian, e cila përshkruan rajonin e topologjisë së sipërfaqes së përgjigjes. Në veçanti, nëse funksioni objektiv është kuadratik, atëherë pika minimale mund të merret në jo më shumë se një numër hapash të barabartë me dimensionin e problemit.

Për të zbatuar metodën në praktikë, ajo duhet të plotësohet me procedura për kontrollin e konvergjencës dhe pavarësisë lineare të sistemit të drejtimit. Metodat e rendit të dytë

Metoda e Njutonit

Zbatimi i vazhdueshëm i skemës së përafrimit kuadratik çon në zbatimin e metodës së optimizimit të Njutonit sipas formulës

x k +1 = x k - Ñ 2 f(x k -1) Ñ f(x k).

Disavantazhi i metodës së Njutonit është besueshmëria e saj e pamjaftueshme kur optimizohen funksionet objektive jo-kuadratike. Prandaj, shpesh modifikohet:

x k +1 = x k - a k Ñ 2 f(x k -1) Ñ f(x k), ku

a k është një parametër i zgjedhur në mënyrë që f(x k+1) min.

2. Gjetja e ekstremumit të një funksioni pa kufizim

Jepet një funksion i caktuar f(x) në një interval të hapur (a, b) të ndryshimeve në argumentin x. Supozojmë se exst ekziston brenda këtij intervali (duhet thënë se në rastin e përgjithshëm kjo nuk mund të thuhet matematikisht paraprakisht; megjithatë, në aplikimet teknike, shumë shpesh prania e exst brenda një intervali të caktuar ndryshimi në intervalin e ndryshimit të argumenti mund të parashikohet nga konsideratat fizike).

Përkufizim exst. Funksioni f(x) i dhënë në intervalin (a, b) ka në pikën x * max(min), nëse kjo pikë mund të rrethohet nga një interval i tillë (x * -ε, x * +ε) që përmbahet në intervali (a, b) , që për të gjitha pikat e tij x që i përkasin intervalit (x * -ε, x * +ε), vlen pabarazia e mëposhtme:

f(x) ≤ f(x *) → për max

f(x) ≥ f(x *) → për min

Ky përkufizim nuk vendos asnjë kufizim në klasën e funksioneve f(x), e cila, natyrisht, është shumë e vlefshme.

Nëse kufizohemi për funksionet f(x), në një klasë mjaft të zakonshme, por ende më të ngushtë funksionesh të lëmuara (me funksione të lëmuara nënkuptojmë ato funksione që janë të vazhdueshme së bashku me derivatet e tyre në intervalin e variacionit të argumentit), atëherë ne mund të përdorë teoremën e Fermatit, e cila jep kushtet e nevojshme për ekzistencën e exst.

Teorema e Fermatit. Le të përcaktohet funksioni f(x) në një interval të caktuar (a, b) dhe në pikën “c” të këtij intervali të marrë vlerën më të madhe (më të vogël). Nëse një derivat i fundëm i dyanshëm ekziston në këtë pikë, atëherë ekzistenca e exst është e nevojshme.

Shënim. Derivati ​​i dyanshëm karakterizohet nga vetia, me fjalë të tjera, po flasim për se në pikën "c" derivati ​​në kufi është i njëjtë kur i afrohemi pikës "c" nga e majta dhe nga e djathta, d.m.th f(x) - funksion të qetë.

* Në rastin e min, dhe në → max. Së fundi, nëse në x=x 0, atëherë përdorimi i derivatit të 2-të nuk ndihmon dhe ju duhet të përdorni, për shembull, përkufizimin e exst.

Gjatë zgjidhjes së problemit I, kushtet e nevojshme ekzistuese (d.m.th. teorema e Fermatit) përdoren shumë shpesh.

Nëse ekuacioni exst ka rrënjë reale, atëherë pikat që u korrespondojnë këtyre rrënjëve janë të dyshimta në exst (por jo domosdoshmërisht vetë ekstremet, pasi kemi të bëjmë me kushte të nevojshme, dhe jo të nevojshme dhe të mjaftueshme). Kështu, për shembull, në pikën e lakimit ndodh X p, megjithatë, siç dihet, ky nuk është një ekstrem.

Le të theksojmë gjithashtu se:

nga kushtet e nevojshmeështë e pamundur të thuhet se çfarë lloji i ekstremit është gjetur, max apo min: nevojiten kërkime shtesë për të përcaktuar këtë;

Nga kushtet e nevojshme është e pamundur të përcaktohet nëse ky ekstrem është global apo lokal.

Prandaj, kur gjenden pika të dyshimta për exst, ato shqyrtohen më tej, për shembull, bazuar në përkufizimin e exst ose derivatit të 2-të.