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čiausio funkcijos padidėjimo tam tikrame taške kryptimi. 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, ...

ir k

Koordinačių forma šis procesas parašytas taip: r+1]=x i [[r] - x if(x f'(x ) a k

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

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

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

+l]

Čia e ir g pateikiami nedideli kiekiai. a k f"(x.

Taip pat galimas kombinuotas kriterijus, kurį sudaro tuo pačiu metu nurodytų sąlygų įvykdymas. 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

užtikrins funkcijos mažėjimą, t.y., nelygybę r+1]) = f(x f(x[ [k] – 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 praktikoje naudojamus tokių 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ę -x[r]) .

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

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

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

5. Patikrinamos sterilizacijos proceso stabdymo 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(a)/da = 0.

Apskaičiavę kompleksinės funkcijos išvestinę, gauname gretimų taškų nusileidimo krypčių vektorių ortogonalumo sąlygą: dj[X[ 1]-x[r]) = 0.

Ryžiai. 2.9. 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) =1, …, n gerai kondicionuotas. Prisiminkite, kad savosios reikšmės l i,

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.Šių funkcijų antigradiento kryptis (žr. 2.10 pav.) ženkliai nukrypsta nuo krypties iki minimalaus taško, todėl sulėtėja konvergencijos greitis.

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ą. X 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 baigtiniu žingsnių skaičiumi p,

lygus funkcijos kintamųjų skaičiui. n 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. X Pagal apibrėžimą, du - matmenų vektorius Ir adresu paskambino konjuguotas matricos atžvilgiu konjuguotas H (arba, -konjugatas), jei skaliarinis sandauga(x Na) = 0.Čia N - simetrinė teigiama apibrėžtoji dydžio matrica n

X p.[r]) 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ą -f(x[r], konjuguotas-konjuguoti su anksčiau rastomis kryptimis Nusileidimo krypties pasirinkimas, Nusileidimo krypties pasirinkimas, ..., Nusileidimo krypties pasirinkimas[r-1].

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

] apskaičiuojamas naudojant formules: r] = --x[r]) p[ -f(x[r+b k-1 r>= 1;

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

f r b vertės -f(x[r], Nusileidimo krypties pasirinkimas[r-1 parinkti taip, kad kryptys konjuguotas-1] buvo :

(-f(x[r], - konjugatas[HP 1])= 0.

k-

,

Dėl to kvadratinei funkcijai

pasikartojantis minimizavimo procesas turi formą r f'(x x[[r]=x[r],

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

užtikrins funkcijos mažėjimą, t.y., nelygybę r] + Autorius[r]) = f(x[r] + judėjimo kryptimi, t. y. išsprendus vienmačio minimizavimo problemą: [r]) .

a k r

ar

Dėl kvadratinės funkcijos X Fletcher-Reeves konjuguoto gradiento metodo algoritmas yra toks. -f(x = --x) .

1. Taške HP apskaičiuotas A 2. Įjungta . m žingsnis, naudojant aukščiau pateiktas formules, žingsnis nustatomas X[X[ 1].

k f(x[r+1]) ir laikotarpis -x[r+1]) .

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

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

pasikartojantis minimizavimo procesas turi formą r f'(x 1) 1-4 procedūrų kartojimas kartojamas cikliškai su pakeitimu[r]=x[r],

] apskaičiuojamas naudojant formules: r] įjungta[r])+ +1] , o skaičiavimai baigiasi , kur yra nurodytas skaičius. Šiuo atveju naudojamas toks metodo modifikavimas: HP 1 -f(x[r+b k-1 r>= 1;

= x k+);

užtikrins funkcijos mažėjimą, t.y., nelygybę r] + = -f’(x[r]) = f(x[r] b[r];

.

p = -f'( a k p+ap a k pČia aš- daug indeksų: N -= (0, n, 2

p, atlyginimas, ...) X, t. y. metodas atnaujinamas kaskart Nusileidimo krypties pasirinkimas = žingsniai. Konjuguoto gradiento metodo geometrinė reikšmė yra tokia (2.11 pav.). Nuo tam tikro pradžios taško X nusileidimas vykdomas kryptimi -f"(x). X Taške Nusileidimo krypties pasirinkimas, nustatomas gradiento vektorius ] antigradientas -) f"(x Nusileidimo krypties pasirinkimas). Kadangi Nusileidimo krypties pasirinkimas , konjuguotas yra mažiausias funkcijos taškas kryptimi Nusileidimo krypties pasirinkimas Tai Nusileidimo krypties pasirinkimas statmena vektoriui

. Toliau randame funkcijos minimumą pagal kryptį N -= (0, n, 2

ir tt Ši paskaita plačiai apima tokius kelių parametrų optimizavimo metodus kaip stačiausio nusileidimo metodas ir Davidon-Fletcher-Powell metodas. Be to, atliekama lyginamoji minėtų metodų analizė, siekiant nustatyti efektyviausią, nustatyti jų privalumus ir trūkumus; taip pat atsižvelgiama į daugiamates optimizavimo problemas, tokias kaip griovelių metodas ir daugiaekstreminis metodas.

1. Stačiausio nusileidimo būdas

Šio metodo esmė ta, kad naudojant anksčiau minėtą koordinačių nusileidimo metodas paieška atliekama nuo nurodyto taško kryptimi, lygiagrečia vienai iš ašių, iki minimalaus taško šia kryptimi. Tada paieška atliekama lygiagrečia kitai ašiai kryptimi ir pan. Nurodymai, žinoma, yra fiksuoti. Atrodo protinga pabandyti modifikuoti šį metodą taip, kad kiekviename etape būtų ieškoma minimalaus taško „geriausia“ kryptimi. Kuri kryptis „geriausia“ neaišku, bet tai žinoma gradiento kryptis yra sparčiausio funkcijos didėjimo kryptis. Todėl priešinga kryptis yra sparčiausio funkcijos mažėjimo kryptis. Šią savybę galima pateisinti taip.

Tarkime, kad judame iš taško x į kitą tašką x + hd, kur d yra tam tikra kryptis, o h yra tam tikro ilgio žingsnis. Vadinasi, judėjimas atliekamas iš taško (x 1, x 2, ..., x n) į tašką (x 1 + zx 1, x 2 + zx 2, ..., x n + zx n), Kur

Funkcijų reikšmių pasikeitimą lemia santykiai

Iki pirmos eilės zx i , o dalinės išvestinės apskaičiuojamos taške x . Kaip reikia pasirinkti kryptis d i, kurios tenkintų (1.2) lygtį, kad būtų gauta didžiausia funkcijos df pokyčio reikšmė? Čia iškyla maksimizavimo problema su apribojimu. Taikykime Lagranžo daugiklių metodą, kurio pagalba nustatome funkciją

Reikšmė df atitinkantis apribojimą (1.2) pasiekia didžiausią, kai funkcija

Pasiekia maksimumą. Jo darinys

Vadinasi,

(1.6)

Tada di ~ df/dx i ir kryptis d yra lygiagreti krypčiai V/(x) taške x.

Taigi, didžiausias vietinis padidėjimas funkcija tam tikram mažam žingsniui h atsiranda, kai d yra Vf(x) arba g(x) kryptis. Todėl stačiausio nusileidimo kryptis yra kryptis

Paprastesne forma (1.3) lygtis gali būti parašyta taip:

Kur yra kampas tarp vektorių Vf(x) ir dx. Esant nurodytai dx reikšmei, sumažiname df, pasirinkdami, kad dx kryptis sutampa su -Vf(x) kryptimi.

komentuoti. Gradiento kryptis statmena bet kuriam pastovaus lygio linijos taškui, nes išilgai šios linijos funkcija yra pastovi. Taigi, jei (d 1, d 2, ..., d n) yra mažas žingsnis išilgai lygio linijos, tada

Ir todėl

(1.8)

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 iteracinis nesuvaržomo 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ą. 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ė retai naudojama, 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: .

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

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žinamos 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 patenka į funkcijos lokalų minimumą, greičiausiai jis negalės nuo jo pabėgti.

Kai kiekvienoje iteracijoje naudojamas stačiausio nusileidimo metodas, žingsnio dydis A r parenkamas iš minimalios funkcijos sąlygos f(x) nusileidimo kryptimi, t.y.

f(x[r] -a r -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 N(x) [X[ 1]1) 1-4 procedūrų kartojimas kartojamas cikliškai su pakeitimu N(x) [r] -A r f" N(x) (X[r]), i = 1,..., p.

5. Patikrinamos sterilizacijos proceso stabdymo 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 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ą:

Būtina sąlyga funkcijos minimumui j (a)/da = -f"(x[X[ 1]-f"(x[r]) = 0.

Ryžiai. 2.9.

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ą Stačiausio nusileidimo metodo geometrinė interpretacija ir mažiausiai M antrųjų išvestinių matricos savosios reikšmės (Heso matrica)

mažai skiriasi viena nuo kitos, t.y. matrica antrųjų išvestinių matricos savosios reikšmės (Heso matrica) gerai kondicionuotas. Prisiminkite, kad savosios reikšmės l i, N(x) =1, …, n, 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.Šių funkcijų antigradiento kryptis (žr. 2.10 pav.) ženkliai nukrypsta nuo krypties iki minimalaus taško, todėl sulėtėja konvergencijos greitis.

Ryžiai. 2.10.

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 X yra toli nuo minimalaus taško, o žingsniai antigradiento kryptimi leidžia pasiekti reikšmingą funkcijos sumažėjimą.

Stačiausio nusileidimo metodas (anglų literatūroje „method of steepest descent“) yra iteracinis skaitinis metodas (pirmos eilės) optimizavimo uždaviniams spręsti, leidžiantis nustatyti tikslo funkcijos ekstremumą (minimumą arba maksimumą):

yra funkcijos argumento reikšmės (valdomi parametrai) realiame domene.

Pagal nagrinėjamą metodą tikslo funkcijos ekstremumas (maksimumas arba minimumas) nustatomas greičiausio funkcijos didėjimo (sumažėjimo) kryptimi, t.y. funkcijos gradiento (antigradiento) kryptimi. Gradiento funkcija taške yra vektorius, kurio projekcijos į koordinačių ašis yra funkcijos dalinės išvestinės koordinačių atžvilgiu:

čia i, j,…, n yra vienetiniai vektoriai, lygiagretūs koordinačių ašims.

Gradientas baziniame taške yra griežtai statmena paviršiui, o jo kryptis rodo sparčiausio funkcijos didėjimo kryptį, o atitinkamai priešinga (antigradientas) – sparčiausio funkcijos mažėjimo kryptį.

Stačiausio nusileidimo metodas yra tolesnė gradiento nusileidimo metodo plėtra. Apskritai funkcijos ekstremumo radimo procesas yra iteracinė procedūra, kuri rašoma taip:

kur „+“ ženklas naudojamas funkcijos maksimumui rasti, o „-“ ženklas – funkcijos minimumui;

Vieneto krypties vektorius, kuris nustatomas pagal formulę:

- gradiento modulis nustato funkcijos padidėjimo arba sumažėjimo greitį gradiento arba antigradiento kryptimi:

Konstanta, kuri nustato žingsnio dydį ir yra vienoda visoms i-osioms kryptims.

Žingsnio dydis parenkamas iš tikslo funkcijos f(x) minimumo sąlygos judėjimo kryptimi, t.y., sprendžiant vienmačio optimizavimo uždavinį gradiento arba antigradiento kryptimi:

Kitaip tariant, žingsnio dydis nustatomas sprendžiant šią lygtį:

Taigi skaičiavimo žingsnis parenkamas toks, kad judesys būtų vykdomas tol, kol funkcija pagerės, tokiu būdu tam tikru momentu pasiekiant ekstremumą. Šiuo metu vėl nustatoma paieškos kryptis (naudojant gradientą) ir ieškoma naujo optimalaus tikslo funkcijos taško ir pan. Taigi šiuo metodu paieška vyksta didesniais žingsniais, o funkcijos gradientas skaičiuojamas esant mažesniam taškų skaičiui.

Dviejų kintamųjų funkcijos atveju šis metodas turi tokią geometrinę interpretaciją: judėjimo kryptis iš taško paliečia lygio liniją taške . Nusileidimo trajektorija yra zigzaginė, o gretimos zigzaginės jungtys yra statmenos viena kitai. Nusileidimo krypčių vektorių gretimuose taškuose ortogonalumo sąlyga užrašoma tokia išraiška:

Judėjimo į ekstremalų tašką trajektorija taikant stačiausio nusileidimo metodą, parodyta funkcijos f(x) vienodo lygio linijos grafike

Optimalaus sprendimo paieška baigiasi, kai iteraciniame skaičiavimo etape (keli kriterijai):

Paieškos trajektorija išlieka nedidelėje dabartinio paieškos taško kaimynystėje:

Tikslo funkcijos padidėjimas nesikeičia:

Tikslinės funkcijos gradientas vietiniame minimaliame taške tampa lygus nuliui:

Pažymėtina, kad gradiento nusileidimo metodas pasirodo labai lėtas judant dauboje, o didėjant tikslo funkcijos kintamųjų skaičiui, toks metodo elgesys tampa tipiškas. Įduba – tai įduba, kurios lygio linijos yra maždaug elipsės su daug kartų besiskiriančiomis pusašėmis. Esant daubai, nusileidimo trajektorija yra zigzago linija su nedideliu žingsniu, dėl to labai sulėtėja susidaręs nusileidimo greitis iki minimumo. Tai paaiškinama tuo, kad šių funkcijų antigradiento kryptis gerokai nukrypsta nuo krypties iki minimalaus taško, todėl skaičiavimas vėluoja papildomai. Dėl to algoritmas praranda skaičiavimo efektyvumą.

Gelbėtojų funkcija

Gradiento metodas kartu su daugybe modifikacijų yra įprastas ir efektyvus metodas ieškant optimalaus tiriamų objektų. Gradientinės paieškos (kaip ir aukščiau aptartų metodų) trūkumas yra tas, kad ją naudojant galima aptikti tik lokalų funkcijos ekstremumą. Norint rasti kitus vietinius kraštutinumus, reikia ieškoti iš kitų atskaitos taškų. Taip pat gradiento metodų konvergencijos greitis taip pat labai priklauso nuo gradiento skaičiavimo tikslumo. Tikslumo praradimas, kuris paprastai atsiranda šalia minimalių taškų arba griovių situacijoje, paprastai gali sutrikdyti gradiento nusileidimo proceso konvergenciją.

Skaičiavimo metodas

1 veiksmas: Analitinių išraiškų (simboline forma) apibrėžimas funkcijos gradientui apskaičiuoti

2 veiksmas: nustatykite pradinį aproksimaciją

3 veiksmas: Nustatomas poreikis iš naujo paleisti algoritminę procedūrą, kad būtų iš naujo nustatyta paskutinė paieškos kryptis. Paleidus iš naujo, paieška vėl atliekama stačiausio nusileidimo kryptimi.