Taip pat galite ieškoti ne geriausio taško gradiento kryptimi, o geresnio už dabartinį.

Lengviausiai įgyvendinamas iš visų vietinio optimizavimo metodų. Jis turi gana silpnas konvergencijos sąlygas, tačiau konvergencijos greitis yra gana mažas (tiesinis). Gradiento metodo žingsnis dažnai naudojamas kaip kitų optimizavimo metodų, tokių kaip Fletcher-Reeves metodas, dalis.

Aprašymas [ | ]

Patobulinimai[ | ]

Gradiento nusileidimo metodas pasirodo labai lėtas judant dauboje, o didėjant tikslo funkcijos kintamųjų skaičiui, toks metodo elgesys tampa tipiškas. Kovai su šiuo reiškiniu naudojamas jis, kurio esmė labai paprasta. Atlikus du gradiento nusileidimo žingsnius ir gavus tris taškus, trečią žingsnį reikia žengti vektoriaus, jungiančio pirmąjį ir trečiąjį taškus, kryptimi, palei daubos dugną.

Funkcijoms, artimoms kvadratinėms, konjuguoto gradiento metodas yra veiksmingas.

Taikymas dirbtiniuose neuroniniuose tinkluose[ | ]

Gradiento nusileidimo metodas su tam tikrais pakeitimais yra plačiai naudojamas perceptronų mokymui ir yra žinomas dirbtinių neuroninių tinklų teorijoje kaip atgalinio sklaidos metodas. Treniruojant perceptrono tipo neuroninį tinklą, reikia keisti tinklo svorinius koeficientus taip, kad būtų sumažinta vidutinė neuroninio tinklo išvesties paklaida, kai į įvestį tiekiama mokymo įvesties duomenų seka. Formaliai, norint žengti tik vieną žingsnį naudojant gradiento nusileidimo metodą (padaryti tik vieną tinklo parametrų pakeitimą), į tinklo įvestį reikia nuosekliai pateikti absoliučiai visą mokymo duomenų rinkinį, apskaičiuoti kiekvieno objekto paklaidą. mokymo duomenis ir apskaičiuoti reikiamą tinklo koeficientų pataisą (bet nedaryti šios korekcijos), o pateikus visus duomenis, apskaičiuoti kiekvieno tinklo koeficiento pataisos sumą (gredientų sumą) ir pakoreguoti koeficientus „vienu žingsniu“ . Akivaizdu, kad esant dideliam mokymo duomenų rinkiniui, algoritmas veiks itin lėtai, todėl praktikoje tinklo koeficientai dažnai koreguojami po kiekvieno mokymo elemento, kur gradiento reikšmė apytiksliai apskaičiuojama pagal kaštų funkcijos gradientą, skaičiuojamą tik vienam mokymui. elementas. Šis metodas vadinamas stochastinis gradiento nusileidimas arba operatyvinis gradiento nusileidimas . Stochastinis gradiento nusileidimas yra stochastinės aproksimacijos forma. Stochastinių aproksimacijų teorija suteikia sąlygas stochastinio gradiento nusileidimo metodo konvergencijai.

Nuorodos [ | ]

• J. Mathewsas. Stačiausio nusileidimo arba gradiento metodo modulis. (nuoroda nepasiekiama)

Literatūra [ | ]

• Akulichas I. L. Matematinis programavimas pavyzdžiuose ir uždaviniuose. - M.: Aukštoji mokykla, 1986. - P. 298-310.
• Gill F., Murray W., Wright M. Praktinis optimizavimas = Praktinis optimizavimas. - M.: Mir, 1985 m.
• Koršunovas M., Koršunovas M. Kibernetikos matematiniai pagrindai. - M.: Energoatomizdat, 1972 m.
• Maksimovas Yu A., Fillipovskaja E. A. Netiesinio programavimo uždavinių sprendimo algoritmai. - M.: MEPhI, 1982 m.
• Maksimovas A. Linijinio ir diskretinio programavimo algoritmai. - M.: MEPhI, 1980 m.
• Kornas G., Kornas T. Matematikos vadovas mokslininkams ir inžinieriams. - M.: Nauka, 1970. - P. 575-576.
• S. Yu Gorodetskis, V. A. Grišaginas. Netiesinis programavimas ir multiekstremalus optimizavimas. - Nižnij Novgorodas: Nižnij Novgorodo universiteto leidykla, 2007. - P. 357-363.

Diferenciuojamosios funkcijos f(x) gradientas taške X paskambino n- matmenų vektorius f(x) , kurio komponentai yra funkcijos dalinės išvestinės f(x), skaičiuojamas taške X, t.y.

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

Šis vektorius yra statmenas plokštumai per tašką X, ir funkcijos lygaus paviršiaus liestinė f(x), einantis per tašką X.Kiekviename tokio paviršiaus taške funkcija f(x)įgauna tą pačią vertę. Funkciją prilyginus įvairioms pastovioms reikšmėms C 0, C 1, ..., gauname jos topologiją apibūdinančių paviršių eilę (2.8 pav.).

Gradiento vektorius nukreiptas į greičiausią funkcijos padidėjimą tam tikrame taške. Vektorius priešingas gradientui (-f'(x)) , paskambino antigradientas ir yra nukreiptas į greičiausią funkcijos sumažėjimą. Mažiausiame taške funkcijos gradientas lygus nuliui. Pirmosios eilės metodai, dar vadinami gradiento ir minimizavimo metodais, yra pagrįsti gradientų savybėmis. Šių metodų naudojimas bendruoju atveju leidžia nustatyti vietos minimalų funkcijos tašką.

Akivaizdu, kad jei nėra papildomos informacijos, tada nuo pradžios taško X protinga eiti prie reikalo X, gulint antigradiento kryptimi – greičiausias funkcijos mažėjimas. Nusileidimo krypties pasirinkimas[r k ] antigradientas - f'(x ) [k] X[r taške

], gauname kartotinį formos procesą X[ 1] = k+[r]-x f'(x ) , a k f"(x > 0; r=0, 1, 2, ...

Koordinačių forma šis procesas parašytas taip:

x i [ r+1]=x i[r] - a kf(x f'(x ) /x i

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

Kaip iteracinio proceso stabdymo kriterijus, arba nedidelio argumento prieaugio sąlygos įvykdymas || k+[r+l] -x[r] || <= e , либо выполнение условия малости градиента

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

Čia e ir g pateikiami nedideli kiekiai.

Taip pat galimas kombinuotas kriterijus, kurį sudaro tuo pačiu metu įvykdytos nurodytos sąlygos. Gradiento metodai skiriasi vienas nuo kito tuo, kaip pasirenka žingsnio dydį a k f"(x.

Metodu su pastoviu žingsniu visoms iteracijoms parenkama tam tikra pastovaus žingsnio reikšmė. Visai mažas žingsnelis a k f"(x užtikrins funkcijos mažėjimą, t.y., nelygybę

f(x[ r+1]) = f(x[k] – a k f’(x f'(x )) < f(x f'(x ) .

Tačiau dėl to gali prireikti atlikti nepriimtinai daug iteracijų, kad būtų pasiektas minimalus taškas. Kita vertus, per didelis žingsnis gali sukelti netikėtą funkcijos padidėjimą arba sukelti svyravimus aplink minimalų tašką (važiavimas dviračiu). Kadangi sunku gauti reikiamą informaciją žingsnio dydžiui parinkti, metodai su pastoviais žingsniais praktiškai naudojami retai.

Gradientiniai yra ekonomiškesni iteracijų skaičiaus ir patikimumo požiūriu kintamų žingsnių metodai, kai, priklausomai nuo skaičiavimų rezultatų, žingsnio dydis kažkaip pasikeičia. Panagrinėkime tokių praktikoje naudojamų metodų variantus.

Kai kiekvienoje iteracijoje naudojamas stačiausio nusileidimo metodas, žingsnio dydis a k f"(x parenkamas iš minimalios funkcijos sąlygos f(x) nusileidimo kryptimi, t.y.
f(x[r]–a k f’(x[r])) = f(x f'(x – af"(x[r])) .

Ši sąlyga reiškia, kad judėjimas išilgai antigradiento vyksta tol, kol funkcijos reikšmė f(x) mažėja. Matematiniu požiūriu kiekvienoje iteracijoje būtina išspręsti vienmačio minimizavimo problemą pagal A funkcijas
j a) = f(x[r]-af"(x[r])) .

Stačiausio nusileidimo metodo algoritmas yra toks.

1. Nustatykite pradžios taško koordinates X.

2. Taške X[r], k = 0, 1, 2, ... apskaičiuoja gradiento reikšmę f'(x[r]) .

3. Nustatomas žingsnio dydis a k, vienmatis sumažinimas per A funkcijos j a) = f(x[r]-af"(x[r])).

4. Nustatomos taško koordinatės X[X[ 1]:

x i [ X[ 1]= x i[r]– a k f’i (x[r]), i = 1,..., p.

5. Patikrinamos sterilizacijos proceso sustabdymo sąlygos. Jei jie įvykdomi, skaičiavimai sustoja. Kitu atveju pereikite prie 1 veiksmo.

Nagrinėjamu metodu judėjimo kryptis iš taško X[r] paliečia lygio liniją taške k+[X[ 1] (2.9 pav.). Nusileidimo trajektorija yra zigzaginė, o gretimos zigzaginės jungtys yra statmenos viena kitai. Tikrai, žingsnis a k pasirenkamas sumažinant pagal A funkcijos? a) = f(x f'(x -af"(x[r])) . Būtina sąlyga funkcijos minimumui j d Apskaičiavę kompleksinės funkcijos išvestinę, gauname gretimų taškų nusileidimo krypčių vektorių ortogonalumo sąlygą:

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

Stačiausio nusileidimo metodo geometrinė interpretacija Gradiento metodai susilieja iki minimumo esant dideliam greičiui (geometrinės progresijos greičiui), kad būtų užtikrintos sklandžiai išgaubtos funkcijos. Tokios funkcijos turi didžiausią M ir mažiausiai m

antrųjų išvestinių matricos savosios reikšmės (Heso matrica) mažai skiriasi viena nuo kitos, t.y. matrica N(x) gerai kondicionuotas. Prisiminkite, kad savosios reikšmės l i, =1, …, n i

, matricos yra charakteristikų lygties šaknys Tačiau praktiškai, kaip taisyklė, minimuojamos funkcijos turi blogai sąlygotas antrųjų išvestinių matricas<< (t/m 1). Tokių funkcijų reikšmės kai kuriomis kryptimis kinta daug greičiau (kartais keliomis eilėmis) nei kitomis kryptimis. Jų lygūs paviršiai paprasčiausiu atveju yra stipriai ištįsę (2.10 pav.), o sudėtingesniais – išlinksta ir atrodo kaip daubos. Funkcijos su tokiomis savybėmis vadinamos griovys.

Ryžiai. 2.10. Gelbėtojų funkcija X Gradiento metodų konvergencijos greitis taip pat labai priklauso nuo gradiento skaičiavimų tikslumo. Tikslumo praradimas, kuris paprastai atsiranda šalia minimalių taškų arba griovių situacijoje, paprastai gali sutrikdyti gradiento nusileidimo proceso konvergenciją.

Dėl minėtų priežasčių gradiento metodai dažnai naudojami kartu su kitais efektyvesniais metodais pradiniame problemos sprendimo etape. Šiuo atveju taškas

yra toli nuo minimalaus taško, o žingsniai antigradiento kryptimi leidžia pasiekti reikšmingą funkcijos sumažėjimą.

Aukščiau aptarti gradiento metodai randa minimalų funkcijos tašką bendruoju atveju tik begaliniu iteracijų skaičiumi. Konjuguoto gradiento metodas generuoja paieškos kryptis, kurios labiau atitinka sumažinamos funkcijos geometriją. Tai žymiai padidina jų konvergencijos greitį ir leidžia, pavyzdžiui, sumažinti kvadratinę funkciją f(x) = (x, Hx) + (b, x) + a su simetrine teigiama apibrėžtine matrica N lygus funkcijos kintamųjų skaičiui.

Bet kuri sklandi funkcija, esanti šalia minimalaus taško, gali būti gerai aproksimuota kvadratine funkcija, todėl konjuguoto gradiento metodai sėkmingai naudojami siekiant sumažinti ne kvadratines funkcijas. Tokiu atveju jie nustoja būti baigtiniai ir pasikartojantys. n Pagal apibrėžimą, du X- matmenų vektorius Ir adresu paskambino konjuguotas matricos atžvilgiu H matricos atžvilgiu(arba -konjugatas), jei skaliarinis sandauga, (x Na) = 0. Čia N - simetrinė teigiama apibrėžtoji dydžio matrica n X

p. Viena iš svarbiausių konjuguotų gradientų metodų problemų yra efektyvaus krypčių konstravimo problema. Fletcher-Reeves metodas išsprendžia šią problemą, kiekviename žingsnyje transformuodamas antigradientą[r]) -f(x kryptimi[r], matricos atžvilgiu p Nusileidimo krypties pasirinkimas, Nusileidimo krypties pasirinkimas, ..., Nusileidimo krypties pasirinkimas[r-konjuguoti su anksčiau rastomis kryptimis

-1]. Nusileidimo krypties pasirinkimas[r Pirmiausia panagrinėkime šį metodą, susijusį su kvadratinės funkcijos sumažinimo problema.

Kryptys r] = -f'(x[r]) ] apskaičiuojamas naudojant formules: kryptimi[r p[ r>= 1;

+b k-1 -l],’-konjugatas), jei skaliarinis sandauga) .

p = - r f kryptimi[r], Nusileidimo krypties pasirinkimas[r b reikšmės matricos atžvilgiu-1 parinkti taip, kad kryptys :

(kryptimi[r], -1] buvo[- konjugatas 1])= 0.

HP

,

k-

Dėl to kvadratinei funkcijai r+l] pasikartojantis minimizavimo procesas turi formą[r]x[[r],

=x Nusileidimo krypties pasirinkimas[r] - +a k p - konjugatas Kur nusileidimo kryptis į m žingsnis; ir k -žingsnio dydis. A Pastaroji parenkama iš minimalios funkcijos sąlygos

f(x[ r] + f(x)[r]) = f(x[r] + Autorius [r]) .

judėjimo kryptimi, t. y. išsprendus vienmačio minimizavimo problemą:

a k r

ar X Dėl kvadratinės funkcijos kryptimi = -f'(x) .

Fletcher-Reeves konjuguoto gradiento metodo algoritmas yra toks. - konjugatas 1. Taške A apskaičiuotas . 2. Įjungta X[X[ 1].

m žingsnis, naudojant aukščiau pateiktas formules, žingsnis nustatomas f(x[r+1]) k f'(x[r+1]) .

ir laikotarpis f'(x) 3. Skaičiuojamos reikšmės X[r Ir 4. Jei= 0, tada taškas kryptimi[r+1] yra mažiausias funkcijos taškas

f(x). simetrinė teigiama apibrėžtoji dydžio matrica Priešingu atveju nustatoma nauja kryptis +l] iš santykio ir atliekamas perėjimas prie kitos iteracijos. Ši procedūra aptiks kvadratinės funkcijos minimumą ne daugiau kaip Xžingsniai. X[simetrinė teigiama apibrėžtoji dydžio matrica Sumažinant ne kvadratines funkcijas, Fletcher-Reeves metodas tampa iteracinis iš baigtinio. Šiuo atveju po

Dėl to kvadratinei funkcijai r+l] (p+[r]x[[r],

Kryptys r] 1) 1-4 procedūrų kartojimas kartojamas cikliškai su pakeitimu[r])+ įjungta - konjugatas 1 kryptimi[r p[ r>= 1;

+1] , o skaičiavimai baigiasi , kur yra nurodytas skaičius. Šiuo atveju naudojamas toks metodo modifikavimas: k+);

f(x[ r] + = x[r]) = f(x[r] = -f’(x[r];

.

b p = -f'( a k p p = -f'(+ap Čia aš simetrinė teigiama apibrėžtoji dydžio matrica- daug indeksų:

= (0, n, 2 X p, atlyginimas,...) Nusileidimo krypties pasirinkimas = , t. y. metodas atnaujinamas kaskartžingsniai. X Konjuguoto gradiento metodo geometrinė reikšmė yra tokia (2.11 pav.). Nuo tam tikro pradžios taško nusileidimas vykdomas kryptimi-f"(x X yra mažiausias funkcijos taškas kryptimi Nusileidimo krypties pasirinkimas, Tai ] antigradientas -) statmena vektoriui Nusileidimo krypties pasirinkimas. Tada randamas vektorius Nusileidimo krypties pasirinkimas , matricos atžvilgiu- konjuguoti su Nusileidimo krypties pasirinkimas. Toliau randame funkcijos minimumą pagal kryptį Nusileidimo krypties pasirinkimas ir tt

Konjuguotos krypties metodai yra vieni efektyviausių sprendžiant mažinimo problemas. Tačiau reikia pažymėti, kad jie yra jautrūs klaidoms, atsirandančioms skaičiavimo proceso metu. Esant dideliam kintamųjų skaičiui, paklaida gali padidėti tiek, kad procesas turės būti kartojamas net ir kvadratinei funkcijai, t.y. jai skirtas procesas ne visada tinka simetrinė teigiama apibrėžtoji dydžio matrica- daug indeksų:

Stačiausias nusileidimo metodas yra gradiento metodas su kintamu žingsniu. Kiekvienoje iteracijoje žingsnio dydis k pasirenkamas iš funkcijos f(x) minimumo sąlygos nusileidimo kryptimi, t.y.

Ši sąlyga reiškia, kad judėjimas išilgai antigradiento vyksta tol, kol funkcijos f (x) reikšmė mažėja. Matematiniu požiūriu kiekvienoje iteracijoje būtina išspręsti vienmačio sumažinimo pagal funkciją problemą

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

Tam naudokime aukso pjūvio metodą.

Stačiausio nusileidimo metodo algoritmas yra toks.

Nurodomos pradžios taško x (0) koordinatės.

Taške x (k) , k = 0, 1, 2, ... apskaičiuojama gradiento reikšmė f (x (k)).

Žingsnio dydis k nustatomas naudojant vienmatį sumažinimą naudojant funkciją

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

Nustatomos taško x (k) koordinatės:

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

Patikrinama iteracinio proceso sustabdymo sąlyga:

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

Jei jis įvykdomas, skaičiavimai sustoja. Kitu atveju pereiname prie 1 žingsnio. Stačiausio nusileidimo metodo geometrinė interpretacija pateikta Fig. 1.

Ryžiai. 2.1. Stačiausio nusileidimo metodo blokinė schema.

Metodo diegimas programoje:

Stačiausio nusileidimo būdas.

Ryžiai. 2.2. Stačiausio nusileidimo metodo įgyvendinimas.

Išvada: mūsų atveju metodas susiliejo per 7 iteracijas. Taškas A7 (0,6641; -1,3313) yra ekstremumo taškas. Konjuguotų krypčių metodas. Kvadratinėms funkcijoms galite sukurti gradiento metodą, kuriame konvergencijos laikas bus baigtinis ir lygus kintamųjų skaičiui n.

Pavadinkime tam tikrą kryptį ir konjuguokime tam tikros teigiamos apibrėžtosios Heso matricos H atžvilgiu, jei:

Tada, ty vienetui H, konjugavimo kryptis reiškia jų statmeną. Bendru atveju H nėra trivialus. Bendru atveju konjugacija yra Heso matricos pritaikymas vektoriui – tai reiškia šio vektoriaus pasukimą kokiu nors kampu, jo ištempimą ar suspaudimą.

Ir dabar vektorius yra stačiakampis, ty konjugacija yra ne vektoriaus stačiakampis, o pasukto vektoriaus ortogonalumas.t.y.

Ryžiai. 2.3. Konjuguotų krypčių metodo blokinė diagrama.

Metodo įgyvendinimas programoje: Konjuguotų krypčių metodas.

Ryžiai. 2.4. Konjuguotų krypčių metodo įgyvendinimas.

Ryžiai. 2.5. Konjuguotų krypčių metodo grafikas.

Išvada: taškas A3 (0,6666; -1,3333) buvo rastas per 3 iteracijas ir yra ekstremumo taškas.

3. Funkcijos mažiausios ir didžiausios reikšmės nustatymo metodų analizė esant apribojimams

Prisiminkite, kad bendra riboto optimizavimo problema atrodo taip:

f(x) ® min, x О W,

kur W yra tinkamas R m poaibis. Problemų su lygybės tipo apribojimais poklasis išsiskiria tuo, kad aibė  apibrėžiama formos apribojimais

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

Taigi, W = (x О R m: f i (x) = 0, i = 1, …, k).

Mums bus patogu funkcijai f parašyti indeksą „0“. Taigi optimizavimo problema su lygybės tipo apribojimais parašyta kaip

f 0 (x) ® min, (3.1)

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

Jei dabar žymime f funkciją R m su reikšmėmis R k, kurios koordinačių žymėjimas yra f(x) = (f 1 (x), ..., f k (x)), tada ( 3.1)–(3.2) galime parašyti ir formoje

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

Geometriškai lygybės tipo apribojimų problema yra funkcijos f 0 grafiko žemiausio taško, esančio virš kolektoriaus , radimo (žr. 3.1 pav.).

Taškai, kurie atitinka visus apribojimus (t. y. aibės  taškai), paprastai vadinami leistinais. Leistinas taškas x* vadinamas funkcijos f 0 sąlyginiu minimumu, esant apribojimams f i (x) = 0, i = 1, ..., k (arba uždavinio (3.1)–(3.2) sprendimu, jei visiems leistiniems balams x f 0 (x *)  f 0 (x). (3.3)

Jei (3.3) tenkinama tik leistinam x, esančiam kokioje nors taško x* kaimynystėje V x *, tai kalbame apie vietinį sąlyginį minimumą. Sąlyginių griežtų lokalinių ir globalių minimumų sąvokos apibrėžiamos natūraliai.

6.8.3-1 pavyzdys. Raskite funkcijos Q(x,y) minimumą naudodami GDS metodą.

Tegu Q(x,y) = x 2 +2y 2 ; x 0 = 2;y 0 = 1.

Patikrinkime pakankamas sąlygas minimumo egzistavimui:

Atlikime vieną iteraciją pagal algoritmą.

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

2. Jei x = x 0 ir y = y 0,

3. Žingsnis l k = l 0 = 0,5

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

Metodo esmė yra tokia. Nuo pasirinkto taško (x 0 ,y 0) nuleidžiama antigradiento kryptimi, kol pasiekiama minimali tikslinės funkcijos Q(x, y) reikšmė išilgai spindulio (6.8.4-1 pav.) . Rastame taške spindulys paliečia lygio liniją. Tada nuo šio taško nusileidžiama antigradiento kryptimi (statmenai lygio linijai), kol atitinkamas spindulys paliečia per jį einantį lygio liniją naujame taške ir pan.

Tikslinę funkciją Q(x, y) išreikškime žingsnio l terminais. Šiuo atveju tikslinę funkciją pateikiame tam tikrame žingsnyje kaip vieno kintamojo funkciją, t.y. žingsnio dydis

Žingsnio dydis kiekvienoje iteracijoje nustatomas pagal minimalią sąlygą:

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

Taigi kiekvienoje iteracijoje pasirenkant žingsnį l k reikia išspręsti vienmačio optimizavimo problemą. Pagal šios problemos sprendimo būdą jie išskiriami:

· analitinis metodas (NAA);

· skaitmeninis metodas (NMS).

NSA metodu žingsnio reikšmė gaunama iš sąlygos, o NSF metodu l k reikšmė randama atkarpoje duotu tikslumu, naudojant vieną iš vienmačio optimizavimo metodų.

6.8.4-1 pavyzdys. Raskite funkcijos Q(x,y)=x 2 + 2y 2 minimumą e=0,1 tikslumu, esant pradinėms sąlygoms: x 0 =2; y 0 =1.

Atlikime vieną iteraciją naudodami metodą NSA.

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

Iš sąlygos ¢(l)=0 randame l* reikšmę:

Gauta funkcija l=l(x,y) leidžia rasti l reikšmę. Jei x = 2 ir y = 1, turime l = 0,3333.

Apskaičiuokime kito taško koordinates:

Patikrinkime iteracijų pabaigos kriterijaus įvykdymą esant k=1:

Kadangi |2*0.6666|>0.1 ir |-0.3333*4|>0.1, tai sąlygos iteracijos procesui užbaigti netenkinamos, t.y. minimumas nerastas. Todėl turėtumėte apskaičiuoti naują l reikšmę x=x 1 ir y=y 1 ir gauti kito nusileidimo taško koordinates. Skaičiavimai tęsiami tol, kol bus įvykdytos nusileidimo nutraukimo sąlygos.

Skirtumas tarp skaitinio NN metodo ir analitinio yra tas, kad l reikšmės kiekvienoje iteracijoje ieškoma naudojant vieną iš skaitinių vienmačio optimizavimo metodų (pavyzdžiui, dichotomijos metodą arba aukso pjūvio metodą). Šiuo atveju leistinų verčių diapazonas l - tarnauja kaip neapibrėžties intervalas.

3 pav. Stačiausio nusileidimo metodo geometrinė interpretacija. Kiekviename žingsnyje jis parenkamas taip, kad kita iteracija būtų mažiausias funkcijos taškas ant spindulio L.

Ši gradiento metodo versija pagrįsta žingsnio pasirinkimu iš toliau pateiktų svarstymų. Nuo taško judėsime antigradiento kryptimi, kol pasieksime funkcijos f minimumą šia kryptimi, t.y. ant spindulio:

Kitaip tariant, jis pasirenkamas taip, kad sekanti iteracija būtų mažiausias funkcijos f taškas ant spindulio L (žr. 3 pav.). Ši gradiento metodo versija vadinama stačiausio nusileidimo metodu. Beje, atkreipkite dėmesį, kad šiuo metodu gretimų žingsnių kryptys yra statmenos.

Taikant stačiausią nusileidimo metodą, kiekviename žingsnyje reikia išspręsti vienmačio optimizavimo problemą. Praktika rodo, kad šis metodas dažnai reikalauja mažiau operacijų nei gradiento metodas su pastoviu žingsniu.

Tačiau bendroje situacijoje teorinis stačiausio nusileidimo metodo konvergencijos greitis yra ne didesnis nei gradiento metodo konvergencijos greitis su pastoviu (optimaliu) žingsniu.

Skaitiniai pavyzdžiai

Gradiento nusileidimo metodas su pastoviu žingsniu

Norint ištirti gradiento nusileidimo metodo konvergenciją su pastoviu žingsniu, pasirinkta funkcija:

Iš gautų rezultatų galime daryti išvadą, kad jei tarpas yra per didelis, metodas skiriasi, jei tarpas yra per mažas, jis konverguoja lėtai ir tikslumas yra prastesnis. Būtina pasirinkti didžiausią žingsnį iš tų, kuriuose metodas susilieja.

Gradiento metodas su žingsnių padalijimu

Gradiento nusileidimo metodo su pakopų padalijimu (2) konvergencijai ištirti pasirinkta funkcija:

Pradinė aproksimacija yra taškas (10,10).

Naudojamas sustabdymo kriterijus:

Eksperimento rezultatai pateikti lentelėje:

Iš gautų rezultatų galime daryti išvadą apie optimalų parametrų pasirinkimą: , nors metodas nėra labai jautrus parametrų pasirinkimui.

Stačiausio nusileidimo būdas

Stačiausio nusileidimo metodo konvergencijai ištirti buvo pasirinkta ši funkcija:

Pradinė aproksimacija yra taškas (10,10). Naudojamas sustabdymo kriterijus:

Vienmačio optimizavimo uždaviniams spręsti buvo naudojamas aukso pjūvio metodas.

Metodas pasiekė 6e-8 tikslumą per 9 iteracijas.

Iš to galime daryti išvadą, kad stačiausio nusileidimo metodas suartėja greičiau nei laiptelių padalijimo gradiento metodas ir pastovaus žingsnio gradiento nusileidimo metodas.

Stačiausio nusileidimo metodo trūkumas yra tas, kad reikia išspręsti vienmačio optimizavimo problemą.

Programuodami gradiento nusileidimo metodus, turėtumėte būti atsargūs renkantis parametrus, būtent

• · Gradiento nusileidimo metodas su pastoviu žingsniu: žingsnis turi būti pasirinktas mažesnis nei 0,01, kitaip metodas skiriasi (metodas gali skirtis net ir tokiu žingsniu, priklausomai nuo tiriamos funkcijos).
• · Gradiento metodas su pakopų padalijimu nėra labai jautrus parametrų pasirinkimui. Viena iš parametrų pasirinkimo parinkčių:
• · Stačiausio nusileidimo metodas: aukso pjūvio metodas (kai taikomas) gali būti naudojamas kaip vienmatis optimizavimo metodas.

Konjuguoto gradiento metodas yra pasikartojantis besąlyginio optimizavimo daugiamatėje erdvėje metodas. Pagrindinis metodo privalumas yra tas, kad jis išsprendžia kvadratinio optimizavimo uždavinį baigtiniu žingsnių skaičiumi. Todėl pirmiausia aprašomas konjuguoto gradiento metodas kvadratinei funkcijai optimizuoti, išvedamos iteracinės formulės ir pateikiami konvergencijos greičio įverčiai. Po to parodoma, kaip apibendrinamas adjungtinis metodas, siekiant optimizuoti savavališką funkciją, nagrinėjami įvairūs metodo variantai, aptariama konvergencija.

Optimizavimo problemos teiginys

Tegu aibė duota ir šioje aibėje apibrėžta tikslo funkcija. Optimizavimo uždavinys susideda iš tikslios viršutinės arba tikslios apatinės tikslinės funkcijos ribos aibėje radimo. Nurodoma taškų, kuriuose pasiekiama apatinė tikslo funkcijos riba, rinkinys.

Jei, tada optimizavimo problema vadinama nesuvaržyta. Jei, tada optimizavimo problema vadinama suvaržyta.

Konjuguoto gradiento metodas kvadratinei funkcijai

Metodo teiginys

Apsvarstykite šią optimizavimo problemą:

Čia yra simetriška teigiamo apibrėžto dydžio matrica. Ši optimizavimo problema vadinama kvadratine. Atkreipkite dėmesį, kad. Funkcijos ekstremumo sąlyga yra lygiavertė sistemai Funkcija pasiekia apatinę ribą viename lygties apibrėžtame taške. Taigi ši optimizavimo problema sumažinama iki tiesinių lygčių sistemos sprendimo. Konjuguoto gradiento metodo idėja yra tokia: Tegul yra pagrindas. Tada bet kurio taško vektorius išplečiamas į pagrindą. Taigi jis gali būti pavaizduotas formoje

Kiekvienas paskesnis aproksimavimas apskaičiuojamas pagal formulę:

Apibrėžimas. Sakoma, kad du vektoriai ir yra konjuguoti simetrinės matricos B atžvilgiu, jei

Apibūdinkime pagrindo konjuguoto gradiento metodą. Kaip pradinį aproksimaciją pasirenkame savavališką vektorių. Kiekvienoje iteracijoje pasirenkamos šios taisyklės:

Baziniai vektoriai apskaičiuojami naudojant formules:

Koeficientai parenkami taip, kad vektoriai ir būtų konjuguoti A atžvilgiu.

Jei pažymime , tada po kelių supaprastinimų gauname galutines formules, naudojamas praktikoje taikant konjuguoto gradiento metodą:

Konjuguoto gradiento metodui galioja ši teorema: Teorema Tegu, kur yra simetrinė teigiama apibrėžtoji dydžio matrica. Tada konjuguoto gradiento metodas susilieja ne daugiau kaip žingsniais ir galioja šie santykiai:

Metodo konvergencija

Jei visi skaičiavimai yra tikslūs ir pradiniai duomenys tikslūs, tai metodas suartėja su sistemos sprendimu ne daugiau kaip iteracijomis, kur yra sistemos matmuo. Išsamesnė analizė rodo, kad iteracijų skaičius neviršija, kur yra skirtingų matricos A savųjų reikšmių skaičius. Norint įvertinti konvergencijos greitį, teisingas yra šis (gana grubus) įvertinimas:

Tai leidžia įvertinti konvergencijos greitį, jei žinomi didžiausių ir mažiausiųjų matricos savųjų verčių įverčiai Praktikoje dažniausiai naudojamas šis stabdymo kriterijus:

Skaičiavimo sudėtingumas

Kiekvienos metodo iteracijos metu atliekamos operacijos. Šis operacijų skaičius reikalingas norint apskaičiuoti produktą – tai daugiausiai laiko reikalaujanti procedūra kiekvienoje iteracijoje. Kiti skaičiavimai reikalauja O(n) operacijų. Bendras metodo skaičiavimo sudėtingumas neviršija - nes iteracijų skaičius yra ne didesnis kaip n.

Skaitinis pavyzdys

Taikykime konjuguoto gradiento metodą, kad išspręstume sistemą, kurioje, naudojant konjuguoto gradiento metodą, šios sistemos sprendimas gaunamas dviem iteracijomis. Matricos savosios reikšmės yra 5, 5, -5 - tarp jų yra dvi skirtingos, todėl, remiantis teoriniu įvertinimu, iteracijų skaičius negali viršyti dviejų

Konjuguoto gradiento metodas yra vienas iš efektyviausių metodų sprendžiant SLAE su teigiama apibrėžta matrica. Metodas garantuoja konvergenciją baigtiniu žingsnių skaičiumi, o reikiamą tikslumą galima pasiekti daug anksčiau. Pagrindinė problema yra ta, kad dėl klaidų kaupimosi gali būti pažeistas bazinių vektorių ortogonalumas, o tai pablogina konvergenciją

Konjuguoto gradiento metodas apskritai

Dabar panagrinėkime konjuguoto gradiento metodo modifikaciją tuo atveju, kai sumažintas funkcionalumas nėra kvadratinis: Išspręsime problemą:

Nuolat diferencijuojama funkcija. Norėdami pakeisti konjuguoto gradiento metodą, kad išspręstumėte šią problemą, formulėms, kuriose nėra A matricos, reikia gauti:

galima apskaičiuoti naudojant vieną iš trijų formulių:

1. – Fletcher-Reeves metodas

• 2. - Polak-Ribi`ere metodas

Jei funkcija kvadratinė ir griežtai išgaubta, tai visos trys formulės duoda tą patį rezultatą. Jei yra savavališka funkcija, tada kiekviena formulė atitinka savo konjuguoto gradiento metodo modifikaciją. Trečioji formulė naudojama retai, nes jai reikia funkcijos ir funkcijos Heseno skaičiavimo kiekviename metodo žingsnyje.

Jei funkcija nėra kvadratinė, konjuguoto gradiento metodas gali nesutapti per baigtinį žingsnių skaičių. Be to, tiksliai apskaičiuoti kiekviename žingsnyje įmanoma tik retais atvejais. Todėl klaidų kaupimasis lemia tai, kad vektoriai neberodo funkcijos mažėjimo krypties. Tada tam tikru žingsniu jie patiki. Visų skaičių rinkinys, kuriuo jis priimtas, bus pažymėtas. Skaičiai vadinami metodo atnaujinimo momentais. Praktikoje dažnai pasirenkama, kur yra erdvės matmuo.

Metodo konvergencija

Fletcher-Reeves metodui yra konvergencijos teorema, kuri minimalizuojamai funkcijai nustato ne per griežtas sąlygas: teorema. Tegul tenkinamos šios sąlygos:

Įvairovė ribota

Darinys tenkina Lipšico sąlygą su konstanta tam tikroje kaimynystėje

rinkiniai M: .

Naudojant Polak-Reiber metodą, konvergencija įrodoma darant prielaidą, kad tai yra griežtai išgaubta funkcija. Bendruoju atveju Polako-Reiberio metodo konvergencijos įrodyti neįmanoma. Priešingai, teisinga tokia teorema: Teorema. Tarkime, kad taikant Polak-Reiber metodą vertės kiekviename žingsnyje apskaičiuojamos tiksliai. Tada yra funkcija ir pradinis spėjimas, toks, kad.

Tačiau praktiškai Polak-Reiber metodas veikia geriau. Praktikoje dažniausiai pasitaikantys stabdymo kriterijai: gradiento norma tampa mažesnė už tam tikrą ribą Funkcijos reikšmė išliko beveik nepakitusi m iteracijų iš eilės

Skaičiavimo sudėtingumas

Kiekvienoje Polak-Reiber arba Fletcher-Reeves metodų iteracijoje funkcija ir jos gradientas apskaičiuojami vieną kartą ir išsprendžiama vienmačio optimizavimo problema. Taigi, vieno konjuguoto gradiento metodo žingsnio sudėtingumas yra tokio paties dydžio kaip ir vieno stačiausio nusileidimo metodo žingsnio sudėtingumas. Praktikoje konjuguoto gradiento metodas parodo geriausią konvergencijos greitį.

Funkcijos minimumo ieškosime konjuguoto gradiento metodu

Šios funkcijos minimumas yra 1 ir pasiekiamas taške (5, 4). Naudodami šią funkciją kaip pavyzdį, palyginkime Polak-Reiber ir Fletcher-Reeves metodus. Abiejų metodų iteracijos sustoja, kai dabartiniame žingsnyje gradiento norma kvadratu tampa mažesnė. Atrankai naudojamas aukso pjūvio metodas

Buvo įgyvendintos dvi konjuguoto gradiento metodo versijos: kvadratinei funkcijai sumažinti ir savavališkai funkcijai sumažinti. Pirmuoju atveju metodas įgyvendinamas vektorine funkcija FindSolution(matrica A, vektorius b) Čia A ir b yra matrica ir vektorius, dalyvaujantys kvadratinio optimizavimo uždavinyje. Norėdami sumažinti savavališkas funkcijas, galite naudoti vieną iš dviejų funkcijų: vektoriaus FletcherRievesMethod(int spaceSize, Funkcija F, vektorius (*GradF) (vektorius )) vektorius PolakRibiereMethod(int erdvės dydis, funkcija F, vektorius (*GradF) (vektorius )) Abiejų funkcijų parametrai yra vienodi ir turi tokią reikšmę: spaceSize - erdvės matmuo (kintamųjų skaičius, nuo kurio priklauso minimizuota funkcija) F - rodyklė į funkciją, kurią reikia sumažinti. Funkcija turi būti dvigubos formos<имя функции>(vektorius ) GradF – rodyklė į funkciją, kuri apskaičiuoja sumažintos funkcijos gradientą Abu metodai naudoja pagalbinę funkciją, kad išspręstų vienmačio optimizavimo problemą. Programa įgyvendina vienmatį optimizavimą aukso pjūvio metodu.

Gradiento nusileidimo metodai yra gana galingi įrankiai optimizavimo problemoms spręsti. Pagrindinis metodų trūkumas yra ribotas pritaikymo diapazonas. Konjuguoto gradiento metodas naudoja informaciją tik apie tiesinę prieaugio dalį taške, kaip ir gradiento nusileidimo metoduose. Be to, konjuguoto gradiento metodas leidžia išspręsti kvadratines problemas per ribotą skaičių žingsnių. Dėl daugelio kitų problemų konjuguoto gradiento metodas taip pat lenkia gradiento nusileidimo metodą. Gradiento metodo konvergencija labai priklauso nuo to, kaip tiksliai išspręsta vienmačio optimizavimo problema. Galimos metodų kilpos išsprendžiamos naudojant naujinimus. Tačiau jei metodas pateks į funkcijos lokalų minimumą, greičiausiai jis negalės nuo jo pabėgti.