Vietinio ekstremumo radimas naudojant konjuguoto gradiento metodą. Retas matricos daugyba

Gradiento metodai, pagrįsti tik gradiento skaičiavimu R(x), yra pirmosios eilės metodai, nes žingsnio intervale jie pakeičia netiesinę funkciją R(x) linijinis.

Antros eilės metodai, naudojantys ne tik pirmąjį, bet ir antrąjį išvestinius R(x) dabartiniame taške. Tačiau šie metodai turi savo sunkiai išsprendžiamas problemas – skaičiuojant antrąsias išvestines taške, be to, toli nuo optimalaus, antrųjų išvestinių matrica gali būti blogai sąlygota.

Konjuguoto gradiento metodas yra bandymas sujungti pirmos ir antros eilės metodų privalumus, pašalinant jų trūkumus. Įjungta pradiniai etapai(toli nuo optimalaus) metodas veikia kaip pirmos eilės metodas, o šalia optimalaus priartėja prie antros eilės metodų.

Pirmasis žingsnis yra panašus į pirmąjį stačiausio nusileidimo metodo žingsnį, antrasis ir sekantys žingsniai pasirenkami kiekvieną kartą ta kryptimi, kuri suformuota kaip tiesinis gradiento vektorių derinys tam tikrame taške ir ankstesnėje kryptyje.

Metodo algoritmą galima parašyti taip (vektorine forma):

x 1 = x 0 – h grad R(x 0),

x i+1 = x i – h .

Reikšmę α galima apytiksliai rasti iš išraiškos

Algoritmas veikia taip. Nuo pradinio taško X 0 ieško min R(x) gradiento kryptimi (pagal metodą greitas nusileidimas), tada, pradedant nuo rasto taško ir toliau, paieškos kryptis min nustatoma pagal antrąją išraišką. Minimalio paieška kryptimi gali būti atliekama bet kokiu būdu: galite naudoti nuoseklųjį nuskaitymo metodą, nereguliuodami nuskaitymo žingsnio, kai pravažiuojate minimumą, todėl minimumo pasiekimo kryptimi tikslumas priklauso nuo žingsnio dydžio. h.

Dėl kvadratinės funkcijos R(x) sprendimą galima rasti nžingsniai (p– problemos dimensija). Kitoms funkcijoms paieška bus lėtesnė, o kai kuriais atvejais dėl to gali ir nepasiekti optimalaus stiprią įtaką skaičiavimo klaidų.

Viena iš galimų dvimatės funkcijos minimumo paieškos trajektorijų naudojant konjuguoto gradiento metodą parodyta Fig. 1.

Konjuguoto gradiento metodo algoritmas minimumui rasti.

Pradinis etapas. Gradiento metodo vykdymas.

Nustatykite pradinį aproksimaciją x 1 0 ,X 2 0 . Kriterijaus reikšmės nustatymas R(x 1 0 ,X 2 0). Nustatykite k = 0 ir pereikite prie pradinio etapo 1 veiksmo.

1 veiksmas. Ir
.

2 veiksmas. Jei gradiento modulis

3 veiksmas.

x k+1 = x k – h grad R(x k)).

4 veiksmas. R(x 1k +1, X 2 k +1). Jeigu R(x 1k +1, X 2k +1)< R(x 1k, X 2 k), tada nustatykite k = k+1 ir pereikite prie 3 veiksmo. Jei R(x 1k +1, X 2 k +1) ≥ R(x 1k, X 2 k), tada eikite į pagrindinę sceną.

Pagrindinė scena.

1 veiksmas. Apskaičiuokite R(x 1 k + g, x 2 k), R(x 1 k – g, x 2 k), R(x 1 k , x 2 k + g), R(x 1 k , x 2 k) . Pagal algoritmą, iš centrinės arba porinės imties, apskaičiuokite dalinių išvestinių verčių vertę Ir . Apskaičiuokite gradiento modulio reikšmę
.

2 veiksmas. Jei gradiento modulis
, tada sustabdykite skaičiavimą ir laikykite tašką (x 1 k, x 2 k) optimaliu tašku. Kitu atveju pereikite prie 3 veiksmo.

3 veiksmas. Apskaičiuokite koeficientą α pagal formulę:

4 veiksmas. Atlikite darbo žingsnį apskaičiuodami pagal formulę

x k+1 = x k – h .

5 veiksmas. Nustatykite kriterijaus reikšmę R(x 1k +1, X 2 k +1). Nustatykite k = k+1 ir pereikite prie 1 veiksmo.

Pavyzdys.

Palyginimui apsvarstykite ankstesnio pavyzdžio sprendimą. Pirmąjį žingsnį žengiame naudodami stačiausio nusileidimo metodą (5 lentelė).

5 lentelė

Geriausias taškas rastas. Šioje vietoje apskaičiuojame išvestines: dR/ dx 1 = –2.908; dR/ dx 2 =1 600; Apskaičiuojame koeficientą α, kuriame atsižvelgiama į gradiento įtaką ankstesniame taške: α = 3,31920 ∙ 3,3192/8,3104 2 =0,160. Mes atliekame darbo žingsnį pagal metodo algoritmą, gauname X 1 = 0,502, X 2 = 1.368. Tada viskas kartojama taip pat. Žemiau, lentelėje. 6 rodo esamas tolesnių veiksmų paieškos koordinates.

6 lentelė

Sąvoka „konjuguoto gradiento metodas“ yra vienas iš pavyzdžių, kaip beprasmės frazės, jau susipažinusios, yra savaime suprantamos ir nesukelia painiavos. Faktas yra tas, kad gradientai nėra konjuguoti, išskyrus konkretų atvejį, kuris praktiškai neįdomus, o konjuguotos kryptys neturi nieko bendra su gradientais. Metodo pavadinimas atspindi tai, kad šis metodas besąlyginio ekstremumo radimas sujungia gradiento sąvokas objektyvią funkciją ir susijusias kryptis.

Keletas žodžių apie toliau naudojamą žymėjimą.

Dviejų vektorių skaliarinė sandauga užrašoma $x^Ty$ ir reiškia skaliarų sumą: $\sum_(i=1)^n\, x_i\,y_i$. Atminkite, kad $x^Ty = y^Tx$. Jei x ir y yra stačiakampiai, tai $x^Ty = 0$. Paprastai išraiškos, transformuojančios į 1x1 matricą, pvz., $x^Ty$ ir $x^TA_x$, yra traktuojamos kaip skaliarai.

Konjuguoto gradiento metodas iš pradžių buvo sukurtas linijinėms sistemoms išspręsti algebrines lygtis tipas:

kur x nėra garsus vektorius, b yra žinomas vektorius, o A yra žinoma kvadratinė, simetriška, teigiama apibrėžtoji matrica. Šios sistemos sprendimas yra tolygus atitinkamos kvadratinės formos minimumo suradimui.
Kvadratinė forma yra tiesiog skaliarinė kvadratinė kai kurių šios formos vektoriaus x funkcija:

$f\,(x) = (\frac(1)(2))\,x^TA_x\,-\,b^Tx\,+\,c$, (2)

Tokio ryšio tarp matricos buvimas tiesinė transformacija A ir skaliarinė funkcija f(x) leidžia iliustruoti kai kurias formules tiesinė algebra intuityvūs piešiniai. Pavyzdžiui, matrica A laikoma teigiama apibrėžta, jei bet kuriam nuliui skirtingam vektoriui x yra teisinga:

$x^TA_x\,>\,0$, (3)

1 paveiksle parodyta, kaip jie atrodo kvadratinės formos atitinkamai teigiamai apibrėžtai matricai (a), neigiamai apibrėžtai matricai (b), teigiamai neapibrėžtai matricai (c), neapibrėžtai matricai (d).

Tai yra, jei matrica A yra teigiama apibrėžtoji, tai vietoj 1 lygčių sistemos sprendimo galite rasti jos kvadratinės funkcijos minimumą. Be to, konjuguoto gradiento metodas tai padarys n ar mažiau žingsnių, kur n yra nežinomo vektoriaus x matmuo. Kadangi bet koks sklandi funkcijašalia minimalaus taško yra gerai apytikslis kvadratiniu, tą patį metodą galima naudoti siekiant sumažinti, o ne kvadratines funkcijas. Šiuo atveju metodas nustoja būti baigtinis, bet tampa iteracinis.

Patartina pradėti svarstyti konjuguoto gradiento metodą svarstant daugiau paprastas metodas ieškant funkcijos ekstremumo – stačiausio nusileidimo metodo. 2 paveiksle parodyta judėjimo trajektorija iki mažiausio taško naudojant stačiausio nusileidimo metodą. Šio metodo esmė:

• pradiniame taške x(0) apskaičiuojamas gradientas ir vykdomas judėjimas antigradiento kryptimi, kol tikslo funkcija mažėja;
• taške, kur funkcija nustoja mažėti, gradientas vėl apskaičiuojamas ir nusileidimas tęsiamas nauja kryptimi;
• procesas kartojamas tol, kol pasiekiamas minimalus taškas.

IN šiuo atveju kiekviena nauja judėjimo kryptis yra statmena ankstesnei. Ar nėra protingesnio būdo pasirinkti naują kryptį? Yra ir jis vadinamas konjuguotų krypčių metodu. O konjuguoto gradiento metodas kaip tik priklauso konjuguotų krypties metodų grupei. 3 paveiksle parodyta judėjimo trajektorija iki mažiausio taško, naudojant konjuguoto gradiento metodą.

Konjugacijos apibrėžimas formuluojamas taip: du vektoriai x ir y vadinami A konjugatais (arba konjugatais matricos A atžvilgiu) arba A-stačiakampiais, jei taškinis produktas x ir Ay yra lygūs nuliui, tai yra:

$x^TA_y\,=\,0$, (4)

Konjugaciją galima laikyti ortogonalumo sampratos apibendrinimu. Iš tiesų, kai matrica A yra tapatumo matrica, pagal lygybę 4, vektoriai x ir y yra stačiakampiai. Yra dar vienas būdas parodyti ryšį tarp ortogonalumo ir konjugacijos sąvokų: mintyse ištempkite 3 paveikslą taip, kad vienodo lygio linijos iš elipsių virstų apskritimais, o konjuguotos kryptys taptų tiesiog stačiakampės.

Belieka išsiaiškinti, kaip apskaičiuoti konjugavimo kryptis. Vienas iš galimi būdai– naudoti tiesinės algebros metodus, ypač Gramo-Schmidto ortogonalizacijos procesą. Tačiau tam reikia žinoti matricą A, todėl daugumai užduočių (pavyzdžiui, mokant daugiasluoksnius neuroninius tinklus) šis metodas netinka. Laimei, yra ir kitų kartotinių būdų konjugato krypčiai apskaičiuoti, žinomiausia yra Fletcher-Reeves formulė:

$d_((i+1)) = d_((i+1))\,+\,\beta_((i+1))\,d_i$ , (5)

$\beta_((i+1)) = \frac(r_((i+1))^T)(r_(i)^T)\,\frac(r_((i+1)))(r_( (i)))$, (6)

5 formulė reiškia, kad nauja konjugavimo kryptis gaunama pridedant antigradientą posūkio taške ir ankstesnę judėjimo kryptį, padaugintą iš koeficiento, apskaičiuoto pagal 6 formulę. Kryptys, apskaičiuotos pagal 5 formulę, yra konjuguotos, jei sumažinta funkcija yra pateikta forma 2. Tai yra kvadratiniam Konjuguoto gradiento metodas randa funkcijas bent n žingsnių (n yra paieškos erdvės matmuo). Dėl funkcijų bendras vaizdas algoritmas nustoja būti baigtinis ir tampa kartotinis. Tuo pačiu metu Fletcheris ir Reevesas siūlo atnaujinti algoritminę procedūrą kas n + 1 žingsnių.

Galite pateikti kitą formulę konjugato krypčiai nustatyti, Polak-Ribiere formulę:

$\beta_((i+1)) = \frac(r_((i+1))^T\,(r_((i+1))\,-\,r_((i))))(r_ (i)^T\,r_((i)))$, (7)

Fletcher-Reeves metodas susilieja, jei pradžios taškas yra gana artimas reikalaujamam minimumui, o Polako-Reiber metodas retais atvejais gali veikti neribotą laiką. Tačiau pastarieji dažnai susilieja greičiau nei pirmasis metodas. Laimei, Polak-Reiber metodo konvergenciją galima užtikrinti pasirinkus $\beta = \max \(\beta;\,0\)$. Tai prilygsta algoritmo paleidimui iš naujo su sąlyga $\beta \leq 0$. Iš naujo paleisti algoritminę procedūrą būtina norint pamiršti paskutinę paieškos kryptį ir vėl pradėti algoritmą stačiausio nusileidimo kryptimi.

1. Antigradientas apskaičiuojamas savavališkas taškas x(0) .
   

   $d_((0)) = r_((0)) = -\,f"(x_((0)))$

2. Jis nusileidžia apskaičiuota kryptimi, kai funkcija mažėja, kitaip tariant, ieško (i), kuris sumažina
   

   $f\,(x_((i))\,+\,a_((i))\,d_((i)))$

3. Eikite į ankstesnėje pastraipoje rastą tašką
   

   $x_((i+1)) = x_((i))\,+\,a_((i))\,d_((i))$

4. Antigradiento apskaičiavimas šiuo metu
   

   $r_((i+1)) = -\,f"(x_((i+1)))$

5. Skaičiavimai naudojant 6 arba 7 formulę. Norėdami paleisti algoritmą iš naujo, ty pamiršti paskutinę paieškos kryptį ir vėl pradėti algoritmą stačiausio nusileidimo kryptimi, Fletcher-Reeves formulei 0 priskiriama kas n + 1 žingsnių, Polakui -Reiber formulė – $\beta_ ((i+1)) = \max \(\beta_((i+1)),\,0\)$
6. Apskaičiuokite naują konjugavimo kryptį
   

   $d_((i+1)) = r_((i+1))\,+\,\beta_((i+1))\,d_((i))$

7. Eikite į 2 punktą.

Iš aukščiau pateikto algoritmo išplaukia, kad 2 žingsnyje atliekamas vienmatis funkcijos sumažinimas. Norėdami tai padaryti, visų pirma galite naudoti Fibonačio metodą, aukso pjūvio metodą arba padalijimo metodą. Niutono – Rafsono metodas užtikrina greitesnę konvergenciją, tačiau tam būtina mokėti apskaičiuoti Heseno matricą. IN pastarasis atvejis, optimizavimui naudojamas kintamasis apskaičiuojamas kiekviename iteracijos etape naudojant formulę:

$$a = -\,\frac((f")^T\,(x)\,d)(d^T\,f""(x)\,d)$$

$f""(x)\,= \begin(pmatrix) \frac(\partial^2\,f)(\partial x_1\,\partial x_1)&\frac(\partial^2\,f)(\ dalinis x_1\,\partial x_2)&\cdots&\frac(\partial^2\,f)(\partial x_1\,\partial x_n)& \\ \frac(\partial^2\,f)(\partial x_2 \,\partial x_1)&\frac(\partial^2\,f)(\partial x_2\,\partial x_2)& \cdots&\frac(\partial^2\,f)(\partial x_2\,\partial x_n)& \\ \vtaškai&\vtaškai&\dtaškai&\vtaškai &\\ \frac(\partial^2\,f)(\partial x_n\,\partial x_1)& \frac(\partial^2\,f)( \partial x_n\,\partial x_2)&\cdots&\frac(\partial^2\,f)(\partial x_n\,\partial x_n) \end(pmatrix)$
Heseno matrica

Keletas žodžių apie konjuguotų krypčių metodo naudojimą mokyme neuroniniai tinklai. Šiuo atveju naudojamas epocha grįstas mokymasis, tai yra, skaičiuojant tikslo funkciją, pateikiami visi mokymo aibės šablonai ir apskaičiuojamas paklaidos funkcijos (ar tam tikros jos modifikacijos) vidutinis kvadratas. Tas pats pasakytina ir skaičiuojant gradientą, tai yra, naudojamas visas gradientas per visą treniruočių rinkinį. Kiekvieno pavyzdžio gradientas apskaičiuojamas naudojant algoritmą dauginimas atgal(BackProp).

Pabaigoje pateikiame vieną iš galimų konjuguoto gradiento metodo programinės įrangos įgyvendinimo algoritmų. Šiuo atveju konjugacija apskaičiuojama naudojant Fletcher-Reeves formulę, o vienmačiui optimizavimui naudojamas vienas iš aukščiau pateiktų metodų. Kai kurių autoritetingų ekspertų nuomone, algoritmo konvergencijos greitis mažai priklauso nuo optimizavimo formulės, naudojamos 2-ame aukščiau nurodyto algoritmo žingsnyje, todėl galime rekomenduoti, pavyzdžiui, aukso pjūvio metodą, kuriam nereikia skaičiuoti išvestinių.

Konjuguotų krypčių metodo variantas, kuriame konjugavimo kryptims apskaičiuoti naudojama Fletcher-Reeves formulė.

r:= -f"(x) // tikslo funkcijos antigradientas

d:= r // pradinė kryptis nusileidimas sutampa su antigradientu

Sigma new: = r T * r // antigradiento modulio kvadratas

Sigma 0: = Sigma nauja

// Paieškos ciklas (išėjimas ant skaitiklio arba klaida)
o aš< i max and Sigma new >Eps 2 * Sigma 0
pradėti
j:=0
Sigma d: = d T * d

// Vienmatis sumažinimo ciklas (nusileidimas d kryptimi)
kartoti
a: =
x: = x + a
j: = j + 1
iki (j >= j max) arba (a 2 * Sigma d<= Eps 2)

R: = -f"(x) // tikslo funkcijos antigradientas naujame taške
Sigma old: = Sigma new
Sigma new: = r T * r
beta: = Sigma new / Sigma old
d: = r + beta * d // Apskaičiuokite konjugacijos kryptį
k: = k + 1

Jei (k = n) arba (r T * d<= 0) then // Рестарт алгоритма
pradėti
d:=r
k:=0
pabaiga

Aš: = i + 1
pabaiga

Konjuguoto gradiento metodas yra pirmos eilės metodas, o tuo pačiu jo konvergencijos greitis yra kvadratinis. Tai geriau palyginti su įprastais gradiento metodais. Pavyzdžiui, stačiausio nusileidimo metodas ir koordinačių nusileidimo metodas kvadratinei funkcijai susilieja tik į ribą, o konjuguoto gradiento metodas optimizuoja kvadratinę funkciją esant baigtiniam iteracijų skaičiui. Optimizuojant bendrąsias funkcijas, konjuguotos krypties metodas suartėja 4-5 kartus greičiau nei stačiausio nusileidimo metodas. Šiuo atveju, skirtingai nuo antros eilės metodų, daug darbo reikalaujančių antrųjų dalinių išvestinių skaičiavimų nereikia.

Literatūra

• N.N.Moisejevas, Yu.P.Ivanilovas, E.M.Stolyarova „Optimizacijos metodai“, M. Nauka, 1978 m.
• A. Fiacco, G. McCormick „Netiesinis programavimas“, M. Mir, 1972 m.
• W.I.Zangwill „Netiesinis programavimas“, M. Sovietų radijas, 1973 m
• Jonathan Richard Shewchuk "Antros eilės gradientų metodai", Kompiuterių mokslų mokykla Carnegie Mellon universitetas Pitsburgas, 1994 m.

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 H baigtiniame žingsnių n skaičiuje, lygiame 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.

Pagal apibrėžimą du n matmenų vektoriai x ir y vadinami konjuguotais su matrica H (arba H konjugatu), jei skaliarinė sandauga (x, H) = 0. Čia H yra simetrinė teigiama apibrėžtoji matrica, kurios dydis yra nxn.

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[k]) į p[k] kryptį, H-konjugatą su anksčiau rastomis kryptimis p, p, ..., p. Pirmiausia panagrinėkime šį metodą, susijusį su kvadratinės funkcijos sumažinimo problema.

Kryptys p[k] apskaičiuojamos naudojant formules:

p[k] = -f’(x[k])+k-1p, k >= 1; p = -f’(x).

k-1 reikšmės parenkamos taip, kad kryptys p[k], p būtų konjuguotos H:

(p[k], Hp) = 0.

Dėl to kvadratinei funkcijai

pasikartojantis minimizavimo procesas turi formą

x =x[k] +akp[k],

čia p[k] – nusileidimo kryptis k-tame žingsnyje; ak yra žingsnio dydis. Pastarasis parenkamas iš funkcijos f(x) minimumo sąlygos a judėjimo kryptimi, t.y., sprendžiant vienmačio minimizavimo uždavinį:

f(х[k] + акр[k]) = f(x[k] + ар [k]).

Dėl kvadratinės funkcijos

Fletcher-Reeves konjuguoto gradiento metodo algoritmas yra toks.

1. Taške x apskaičiuojamas p = -f’(x).

2. K-ajame žingsnyje žingsnis ak nustatomas naudojant aukščiau pateiktas formules. ir taškas x.

3. Apskaičiuojamos reikšmės f(x) ir f’(x).

4. Jei f’(x) = 0, tai taškas x yra mažiausias funkcijos f(x) taškas. Kitu atveju nauja kryptis p nustatoma iš santykio

ir atliekamas perėjimas prie kitos iteracijos. Ši procedūra aptiks kvadratinės funkcijos minimumą ne daugiau kaip n žingsnių. Sumažinant ne kvadratines funkcijas, Fletcher-Reeves metodas tampa iteracinis iš baigtinio. Šiuo atveju po (n+1) kartojimo procedūros 1-4 kartojamos cikliškai, x pakeičiant x[n+1], o skaičiavimai baigiasi , kur yra duotas skaičius. Šiuo atveju naudojamas toks metodo modifikavimas:

x = x[k] +akp[k],

p[k] = -f’(x[k])+k-1p, k >= 1;

f(x[k] + akp[k]) = f(x[k] + ap[k];

Čia I yra indeksų rinkinys: I = (0, n, 2n, 3n, ...), ty metodas atnaujinamas kas n žingsnių.

Konjuguoto gradiento metodo geometrinė reikšmė yra tokia (1.19 pav.). Iš nurodyto pradžios taško x nusileidžiama kryptimi p = -f"(x). Taške x nustatomas gradiento vektorius f"(x). Kadangi x yra mažiausias funkcijos taškas p kryptimi, tai f’(x) yra statmenas vektoriui p. Tada randamas vektorius p, H-konjugatas su p. Toliau randamas funkcijos minimumas išilgai p krypties ir kt.

Ryžiai. 1.19. Nusileidimo trajektorija konjuguoto gradiento metodu

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, tai yra, jai skirtas procesas ne visada telpa į n žingsnių.

Skaitiniai antros eilės nesuvaržomo optimizavimo metodai, Niutono metodo algoritmų variantai

Antrosios eilės metodų ypatybės. Antrosios eilės nesuvaržytos optimizacijos metodai naudoja antrąsias dalines minimalizuotos funkcijos f(x) išvestines. Šių metodų esmė yra tokia.

Būtina daugelio kintamųjų funkcijos f(x) ekstremumo taške x* sąlyga, kad jos gradientas šiame taške būtų lygus nuliui:

F'(x) išplėtimas šalia taško x[k] į Taylor seriją iki pirmos eilės terminų, leidžia perrašyti ankstesnę lygtį į formą

f"(x) f'(x[k]) + f"(x[k]) (x - x[k]) 0.

Čia f"(x[k]) Н(х[k]) yra minimizuojamos funkcijos antrųjų išvestinių (Heso matricos) matrica. Vadinasi, iteracinis procesas, skirtas nuoseklių aproksimacijų konstravimui, siekiant išspręsti funkcijos f minimizavimo problemą. (x) apibūdinamas išraiška

x x[k] – H-1(x[k]) f’(x[k]) ,

čia H-1(x[k]) yra atvirkštinė Heseno matricos matrica, o H-1(x[k])f'(x[k]) р[k] yra nusileidimo kryptis.

Gautas sumažinimo metodas vadinamas Niutono metodu. Akivaizdu, kad pagal šį metodą žingsnio dydis p[k] kryptimi yra lygus vienetui. Taškų seka (x[k]), gauta taikant iteracinį procesą, esant tam tikroms prielaidoms, konverguoja į kokį nors stacionarų funkcijos f(x) tašką x*. Jei Heseno matrica H(x*) yra teigiama apibrėžtoji, taškas x* bus funkcijos f(x) griežto lokalaus minimumo taškas. Seka x[k] konverguoja į tašką x* tik tuo atveju, jei tikslo funkcijos Heso matrica yra teigiama apibrėžtoji kiekvienoje iteracijoje.

Jei funkcija f(x) yra kvadratinė, tai, nepaisant pradinio aproksimacijos x ir griovelio laipsnio, naudojant Niutono metodą, jos minimumas randamas vienu žingsniu. Tai paaiškinama tuo, kad nusileidimo kryptis р[k] H-1(x[k])f’(x[k]) bet kuriuose taškuose x visada sutampa su kryptimi į mažiausią tašką x*. Jei funkcija f(x) yra ne kvadratinė, o išgaubta, Niutono metodas garantuoja jos monotonišką mažėjimą nuo iteracijos iki iteracijos. Sumažinant daubų funkcijas, Niutono metodo konvergencijos greitis yra didesnis, palyginti su gradiento metodais. Šiuo atveju vektorius p[k] nenurodo krypties į funkcijos f(x) mažiausią tašką, tačiau jis turi didelę dedamąją išilgai vagos ašies ir yra daug arčiau minimumo krypties nei antigradientas.

Reikšmingas Niutono metodo trūkumas yra neišgaubtų funkcijų konvergencijos priklausomybė nuo pradinės aproksimacijos x. Jei x yra pakankamai toli nuo minimalaus taško, tada metodas gali skirtis, ty iteracijos metu kiekvienas paskesnis taškas bus toliau nuo minimalaus taško nei ankstesnis. Metodo konvergencija, nepriklausomai nuo pradinės aproksimacijos, užtikrinama pasirinkus ne tik nusileidimo kryptį p[k] H-1(x[k])f'(x[k]), bet ir žingsnio dydį a. šia kryptimi. Atitinkamas algoritmas vadinamas Niutono metodu su žingsnių valdymu. Iteracinį procesą šiuo atveju lemia išraiška

x x[k] - akH-1(x[k])f’(x[k]).

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

f(x[k] – ak H-1(x[k])f'(x[k]) (f(x[k] - aH-1(x[k])f'(x[k]) ).

Ši algoritmo versija dar vadinama Niutono-Rafsono metodu. Grafinis šios Niutono metodo versijos aiškinimas pateiktas fig. 1.20. Paveikslo išnašos elementai rodo vienmačių funkcijų, kurios turi būti optimizuojamos, siekiant nustatyti žingsnį, grafikus.

Ryžiai. 1.20. Geometrinė Niutono-Rafsono metodo interpretacija

Niutono-Rafsono metodo algoritmas yra toks. Kai kurie veiksmai atliekami prieš pradedant iteracijos procesą. Būtent, reikia gauti vektorių formulių, kurios sudaro gradientą f'([x]) (t. y. pirmųjų dalinių išvestinių vektorių) ir formulių, sudarančių Heseno matricą H(x) (t.y. , antrųjų dalinių išvestinių matrica). Toliau iteracinėje kilpoje vektoriaus x komponentų reikšmės pakeičiamos į šias formules ir šios masyvai tampa skaičių masyvais.

1. Pradiniame taške x apskaičiuojamas vektorius, kuris nustato nusileidimo kryptį p - H-1(x)f’(). Taigi daugiamatė problema redukuojama į vienmatę optimizavimo problemą.

2. K-oje iteracijoje nustatomas žingsnis ak (pagal schemą, parodytą 1.20 pav.; tam išsprendžiama vienmačio optimizavimo užduotis) ir taškas x.

3. Apskaičiuojama reikšmė f(x).

4. Patikrinamos sąlygos išeiti iš paprogramės, kuri įgyvendina šį algoritmą. Šios sąlygos yra panašios į išėjimo iš paprogramės sąlygas naudojant stačiausio nusileidimo metodą. Jei šios sąlygos įvykdomos, skaičiavimai nutraukiami. Priešingu atveju apskaičiuojama nauja kryptis

р –H-1(x[k])f’([k])

ir pereinama prie kitos iteracijos, ty į 2 veiksmą.

Skaičiavimų skaičius per iteraciją pagal Niutono metodą, kaip taisyklė, yra daug didesnis nei naudojant gradiento metodus. Tai paaiškinama tuo, kad reikia apskaičiuoti ir apversti tikslo funkcijos antrųjų išvestinių matricą (arba išspręsti lygčių sistemą, kuriai reikia mažiau darbo). Tačiau norint gauti pakankamai aukšto tikslumo sprendimą naudojant Niutono metodą, paprastai reikia daug mažiau iteracijų nei naudojant gradiento metodus. Dėl šios priežasties Niutono metodas yra žymiai efektyvesnis. Jis turi supertiesinį arba kvadratinį konvergencijos greitį, priklausomai nuo reikalavimų, kuriuos tenkina funkcija f(x), kuri yra sumažinta iki minimumo. Tačiau kai kuriose problemose iteracijos, naudojant Niutono metodą, sudėtingumas gali būti labai didelis, nes reikia apskaičiuoti minimizuojamos funkcijos antrųjų išvestinių matricą, o tai pareikalaus daug kompiuterio laiko.

Kai kuriais atvejais patartina derinti gradiento metodus ir Niutono metodą. Minimalizacijos proceso pradžioje, kai taškas x yra toli nuo ekstremalaus taško x*, gali būti naudojamas koks nors gradiento metodų variantas. Tada, kai gradiento metodo konvergencijos greitis sumažėja, galite pereiti prie Niutono metodo. Arba dėl klaidų kaupimosi skaičiavimo proceso metu Heseno matrica tam tikroje iteracijoje gali pasirodyti neigiama apibrėžta arba negali būti apversta. Tokiais atvejais optimizavimo rutina remiasi H-1(x[k]) E, kur E yra tapatybės matrica. Iteracija atliekama naudojant stačiausio nusileidimo metodą.

Kitoje Niutono metodo modifikacijoje, vadinamoje Levenbergo-Marquardt metodu (Niutono metodas su matricos koregavimu), šios matricos reguliavimas naudojamas siekiant užtikrinti teigiamą Heseno matricos apibrėžtumą sekos taškuose. Levenbergo-Marquardto metodu taškai konstruojami pagal dėsnį: , kur yra teigiamų skaičių seka, užtikrinanti teigiamą matricos apibrėžtumą. Paprastai reikšmė imama didesne tvarka nei didžiausias matricos elementas. Taip yra daugelyje standartinių programų. Jei, tada , kitaip Akivaizdu, kad jei , tai Levenbergo-Marquardto metodas yra Niutono metodas, o jei yra didelis, tai kadangi dideliems Levenbergo-Marquardto metodas yra artimas gradiento metodui. Todėl, pasirinkus parametro reikšmes, galima užtikrinti, kad Levenbergo-Marquardto metodas konverguotų

Ankstesniuose poskyriuose buvo aptariami Koši ir Niutono metodai. Pastebėta, kad Koši metodas yra efektyvus ieškant dideliais atstumais nuo minimalaus taško X* ir „veikia“ prastai šalia šio taško, o Niutono metodas nėra labai patikimas ieškant X* tačiau iš tolimo taško jis pasirodo esąs labai veiksmingas tais atvejais, kai x(k) yra arti mažiausio taško. Šiame ir tolesniuose poskyriuose aptariami metodai, turintys teigiamų Koši ir Niutono metodų savybių ir pagrįsti tik pirmųjų darinių verčių apskaičiavimu. Taigi šie metodai, viena vertus, yra labai patikimi ieškant X* iš atokios vietos X* ir, kita vertus, greitai susilieja arti minimalaus taško.

Metodai, leidžiantys apytiksliai gauti problemų, susijusių su kvadratinėmis tikslo funkcijomis, sprendimus Nžingsnius, naudojant ne dešimtaines trupmenas, iškviesime kvadratiškai susiliejanti. Tarp tokių metodų galime išskirti algoritmų klasę, pagrįstą konstrukcija konjuguotos kryptys. Aukščiau buvo suformuluota krypčių sistemos konjugacijos sąlyga s(k) , k = 1, 2, 3,…, r ≤ N, ir simetrinė matrica SU tvarka N N. Taip pat buvo nustatytas ryšys tarp nurodytų krypčių konstravimo ir savavališkos kvadratinės funkcijos pavertimo sumos sumos forma.

1) Tokio tipo problemos kyla, pavyzdžiui, atliekant regresinę analizę - Pastaba vertimas

kvadratai; buvo padaryta išvada, kad nuosekli paieška išilgai kiekvieno N nuorodas, turinčias nuosavybę SU-konjugacija, leidžia rasti mažiausią kvadratinės funkcijos tašką N kintamieji. Nagrinėjama konjuguotų krypčių sistemos nustatymo procedūra naudojant tik tikslo funkcijos reikšmes. Žemiau kvadratinė aproksimacija naudojama konjugavimo kryptims gauti f(x) ir gradiento komponentų reikšmės. Be to, mes reikalaujame, kad nagrinėjami metodai užtikrintų, jog tikslo funkcija mažėtų, kai pereinama nuo iteracijos prie iteracijos.

Tegu pateikiami du savavališki divergentiniai taškai valdomų kintamųjų erdvėje x(0) ir x(1) . Kvadratinės funkcijos gradientas yra

f(x) = q(x) =Cx + b = g(x) (3.60)

Formulės rašymo patogumui čia įvedamas žymėjimas g(x). Taigi,

g(x (0)) = Cx (0) + b,

g(x (1)) = Cx (1) + b.

Užrašykime gradiento pokytį judant iš taško X(0) iki taško X (1) :

g(x) = g(x (1)) -g(x (0)) = C(x (1) - x (0)), (3.61)

g(x) = C x

Lygybė (3.61) išreiškia kvadratinių funkcijų savybę, kuri bus naudojama toliau.

1952 m. Estensas ir Stiefelis pasiūlė veiksmingą iteracinį tiesinių lygčių sistemų sprendimo algoritmą, kuris iš esmės buvo konjuguoto gradiento metodas. Jie laikė kairiąsias tiesinių lygčių puses kvadratinės funkcijos gradiento komponentais ir išsprendė šios funkcijos sumažinimo problemą. Vėliau Fletcheris ir Reevesas pagrindė kvadratinę metodo konvergenciją ir apibendrino nekvadratinių funkcijų atveju. Friedas ir Metzleris pademonstravo (tačiau su tam tikrais netikslumais) galimybę naudoti metodą tiesinėms sistemoms su reta koeficientų matrica spręsti. (Žr. A priedą, kad apibrėžtumėte retą matricą.) Jie pabrėžė metodo įgyvendinimo paprastumą, palyginti su kitais, bendresniais algoritmais, o tai yra ypač svarbi charakteristika mūsų pristatymo požiūriu.

Metodą nagrinėsime darydami prielaidą, kad tikslo funkcija yra kvadratinė:

f(x) = q(x) = a + b T x + ½ x TCx,

iteracijos atliekamos pagal (3.42) formulę, t.y.

x = x +α s(x).

Kiekvienos iteracijos paieškos kryptys nustatomos naudojant šias formules:

s(k) = -g(k) + (3,62)

s (0) = –g (0) , (3.63)

Kur g(k) = f(x). Kadangi nustačius krypčių sistemą, nuosekli paieška atliekama pagal kiekvieną iš krypčių, naudinga prisiminti, kad sąlyga dažniausiai naudojama kaip kriterijus baigiant vienmatę paiešką.

f (x)T s(k) = 0 (3,64)

Vertybės ,i= 1, 2, 3,...,k - 1, parenkami taip, kad kryptis s(k) buvo SU-susijęs su visomis anksčiau sukurtomis paieškos kryptimis. Panagrinėkime pirmąją kryptį

s (1) = –g(1) + γ (0) s (0) = –g(1) –γ (0) g (0)

ir nustatyti jos konjugacijos sąlygą su s (0)

s (1)T C s(0) = 0,

kur TC s(0) = 0.

Pradinėje iteracijoje

s (0) = ;

vadinasi,

TC = 0

Pasinaudoję kvadratinių funkcijų savybe (3.61), gauname

T g = 0, (3.65)

γ (0) = – ( g T g (1)/( g T g(0)). (3,66)

Iš (3.65) lygties išplaukia, kad

g (1) T g (1) + γ (0) g (0) T g (1) – g (1) T g(0) – γ (0) g (0) T g(0) = 0.

Tinkamai pasirinkę α (0) ir atsižvelgdami į formulę (3.64), turime

g (1) T g(0) = 0.

Taigi,

s (2) = –g(2) + γ (0) s(0) + γ (1) s (1) .

ir pasirinkite γ (0) γ (1), kad sąlygos būtų tenkinamos

s(2) TC s(0) = 0 ir s(2) C s(1) = 0,

y. sąlygos SU-krypties s (2) konjugacija su kryptimis s (0) ir s (1). Naudojant formules (3.61) ir (3.64), galima parodyti (tai paliekama kaip pratimas skaitytojui), kad čia γ (0) = 0, o bendruoju atveju γ ( i) = 0, i = 0, 1, 2,...,k-2, bet kokia verte k. Iš to išplaukia, kad bendrąją paieškos krypčių formulę galima parašyti Fletcherio ir Reeveso pasiūlyta forma:

s ( k) = –g (k) + s (3,68)

Jeigu f(x)- kvadratinė funkcija, norint rasti mažiausią tašką, kurį reikia nustatyti N-1 tokias kryptis ir vykdyti N ieško tiesia linija (jei nėra apvalinimo klaidų). Jei funkcija f(x) nėra kvadratinis, krypčių ir atitinkamų paieškų skaičius didėja.

Kai kurie tyrėjai, remdamiesi skaičiavimo eksperimentų atlikimo patirtimi, teigia, kad po kiekvienos serijos įgyvendinimo N arba N+ 1 žingsnis grįžta į pradinę algoritmo iteraciją, įdėjimą s(x) = -g(x).Šis pasiūlymas tebėra tyrimo objektas, nes bendrosios formos funkcijų sumažinimas kai kuriais atvejais reiškia konvergencijos sulėtėjimą. Kita vertus, cikliniai perėjimai į pradinę iteraciją padidina algoritmo patikimumą, nes sumažėja tiesiškai priklausomų krypčių konstravimo tikimybė. Jei gauta kryptis yra tiesinis vienos ar kelių anksčiau gautų krypčių derinys, tai metodas gali neprivesti prie sprendimo, nes ieškoma atitinkamoje poerdvėje R N jau buvo atliktas. Tačiau reikia pažymėti, kad praktikoje tokios situacijos yra gana retos. Metodas pasirodo esąs labai efektyvus sprendžiant praktines problemas, jam būdingas vieno parametro skaičiavimo schemos paprastumas ir paieškai reikalingas nedidelis kompiuterio atminties kiekis. Dėl santykinai žemų reikalavimų kompiuterio atminčiai Fletcher-Reeves (FR) metodas ir jo modifikacijos yra ypač naudingi sprendžiant didelio masto problemas.

3.9 pavyzdys. Fletcher-Reeves metodas

Raskite funkcijos mažiausią tašką

f(x) = 4x+ 3x – 4x x + x

Jeigu x = T.

1 veiksmas. f(x) =T,

s (0) = – f(x (0)) = – T.

2 veiksmas. Ieškokite tiesia linija:

x = x –α f(x (0)) → α = ⅛,

x =T – ⅛ T = [– ⅛, 0]T

3 veiksmas. k = 1.

s (1) = – T –[¼, 1] T = [– ¼, ½] T.

4 veiksmas. Ieškokite tiesia linija:

x = x+ α s(1) → α = ¼,

x =[– ⅛, 0]T – ¼ [¼, ½] T = [– , ]T,

f(x (2)) = T.

Taigi, x = x*. Sprendimas gautas atlikus dvi vienmates paieškų, nes tikslo funkcija yra kvadratinė ir nėra apvalinimo klaidų.

Milas ir Cantrellas apibendrino Fletcherio ir Reeveso požiūrį, pasiūlydami formulę

x = x +α {– f(x (k)) + γ s(x)} (3.69)

kur α ir γ - parametrai, kurių reikšmės nustatomos kiekvienoje iteracijoje. Šis metodas, žinomas kaip gradiento metodas su atmintimi, yra labai efektyvus iteracijų, reikalingų problemai išspręsti, skaičiumi, tačiau reikalauja daugiau funkcijų reikšmių ir gradiento komponentų skaičiavimų nei Fletcher-Reeves metodas. Todėl Mil ir Cantrell algoritmas yra naudingas tik tais atvejais, kai tikslo funkcijos ir gradiento komponentų reikšmių įvertinimas nėra susijęs su jokiais sunkumais.

Prisiminkime, kad Fletcher-Reeves metodo svarstymas buvo atliktas darant prielaidą, kad tikslo funkcija yra kvadratinė ir ieškant išilgai tiesės nėra apvalinimo klaidų. Tačiau įgyvendinant daugybę metodų, konjugavimo kryptys nustatomos neatsižvelgiant į vieną iš šių prielaidų (ar net į abi prielaidas). Tarp šių metodų turbūt daugiausiai dėmesio nusipelno Polzko ir Ribière 1969 m. sukurtas metodas. Metodas pagrįstas tikslia paieškos procedūra išilgai linijos ir bendresne tikslo funkcijos aproksimacijos prielaida. Tuo pačiu metu

γ = , (3.70)

kur, kaip ir anksčiau,

g(x)= g(x) -g(x). (3.71)

Jei α - parametras, kurio reikšmė nustatoma atlikus paiešką išilgai tiesės, o γ yra parametras, kurio reikšmė apskaičiuojama pagal (3.70) formulę, tada Polak-Ribiera konjugato gradiento metodas yra įgyvendinamas naudojant šiuos ryšius:

x = x +α s(x),

s(x) = – f (x) + γ s(x). (3.72)

Nesunku pastebėti, kad vienintelis skirtumas tarp Polak-Ribier ir Fletcher-Reeves metodų slypi parametro γ pasirinkimo metoduose.

Taip pat žinomi kiti panašūs metodai, kurie taip pat yra pagrįsti tikslių skaičiavimų atlikimu vienmatės paieškos metu ir bendresniu (ne kvadratiniu) tikslo funkcijos aproksimavimu (žr., pavyzdžiui,). Crowderis ir Wolfas 1972 m., o paskui Powellas, įrodė, kad konjuguotų gradientų metodai turi tiesinį konvergencijos greitį, kai nėra periodinio grįžimo prie pradinės iteracijos. Šie grąžinimai atliekami pagal specialią procedūrą, kuri nutraukia paieškos krypties vektorių konstravimo procesą, o tada skaičiavimai tęsiami pagal analogiją su konstravimu. s(x(0)). Aukščiau buvo pažymėta, kad dėl daugelio priežasčių grįžimo į pradinę iteraciją procedūros buvimas padidina algoritmo stabilumą, nes tai leidžia išvengti tiesiškai priklausomų paieškos krypčių vektorių konstravimo. Powellas įrodė, kad Polako-Ribière metodui taip pat būdingas tiesinis konvergencijos greitis, kai nėra grįžimo į pradinę iteraciją, tačiau jis turi neabejotiną pranašumą prieš Fletcher-Reeves metodą sprendžiant problemas su bendromis tikslinėmis funkcijomis ir yra mažiau jautrus. apvalinimo paklaidoms atliekant vienmates paieškas.

Veiksmingų procedūrų ir metodų, užtikrinančių grįžimą į pradinę iteraciją ir tuo pačiu mažą jautrumą apvalinimo klaidoms, sukūrimas išlieka aktyvių tyrimų objektu. Bealas pasiūlė konjuguotų gradientų metodą, panašų į standartinę Fletcher-Reeves procedūrą, tačiau tuo pat metu nenaudoja krypties palei gradientą, kai grįžtama prie pradinės iteracijos. Jis parodė, kaip remiantis prieš pat grįžimą į pradinę iteraciją gautos krypties analize, sprendžiant daugkartinio grąžinimo reikalaujančias problemas, galima sumažinti reikalingų skaičiavimų kiekį. Powellas išnagrinėjo Bealo strategiją, taip pat kitas strategijas, skirtas grįžti prie pradinės iteracijos, ir pasiūlė naudoti grįžimo procedūrą po kiekvienos serijos. Nžingsnių, arba kai tenkinama nelygybė

| g(x)T g(x) | ≥ 0.2 ||g(x)|| . (3.73)

Jis parodė, kad Beale strategija, papildyta sąlyga (3,73), gali būti sėkmingai taikoma tiek su Fletcher-Reeves formule, tiek su Polak-Ribière formule, ir atliko daugybę skaičiavimo eksperimentų, kurių rezultatai patvirtina Polak-Ribière metodas (su reversija) . Shannault ištyrė apvalinimo klaidų eilučių paieškose ir įvairių grįžimo strategijų poveikį konjuguoto gradiento metodų veikimui. Jis parodė, kad Beale strategija (naudojant atitinkamą dviejų parametrų formulę), papildyta Powello grįžimo sąlyga, žymiai sumažina reikiamą vienos dimensijos paieškos tikslumą ir todėl žymiai padidina visos paieškos efektyvumą. konjuguoto gradiento metodo skaičiavimo schema. Shannault taip pat pateikė skaitinius rezultatus, rodančius Polak-Ribière metodo pranašumą, naudojant atgalinio sekimo ir apvalinimo procedūras ieškant išilgai linijos. Darbas parodo pagrindinį konjuguotų gradientų metodų vaidmenį sprendžiant aukštos dimensijos netiesinio programavimo problemas.

Kvazi-niutono metodai

Šie metodai yra panašūs į metodus, aptartus poskyryje. 3.3.5, nes jie taip pat pagrįsti kvadratinių funkcijų savybėmis. Vadovaujantis aukščiau aprašytais metodais, sprendimo paieška vykdoma pagal konjuguotų krypčių sistemą, tuo tarpu kvaziniutono metodai turi teigiamų Niutono metodo bruožų, tačiau naudoja tik pirmuosius išvestinius. Visuose šios klasės metoduose paieškos krypties vektorių konstravimas atliekamas naudojant formulę (3.42), kurioje s(x(k)) rašoma kaip

s(x) = –A f (x), (3.74)

Kur A- užsakymo matrica N N, kuris vadinamas metrikos. Paieškos metodai pagal šios formulės nustatytas kryptis vadinami metodais kintamoji metrika, nes matrica A kinta kiekvienos iteracijos metu. Tiksliau, kintamos metrinis metodas yra kvazi-niutono metodas, jei pagal jį bandymo taško judėjimas atitinka šią sąlygą:

x =C g. (3.75)

Deja, specializuotoje literatūroje nėra parengtos vienodos ir tvirtos minėtų terminų vartojimo rekomendacijos; laikysime juos pakeičiamais, nes jie turi vienodai svarbią informaciją apie nagrinėjamų metodų kūrimo ir įgyvendinimo ypatybes.

Norėdami aproksimuoti matricą, atvirkštinę Heseno matricai, naudojame šį pasikartojimo ryšį:

A = A+ A(3.76)

Kur A- korekcijos matrica. Matrica A bus naudojami (3.74) ir (3.42) formulėse. Užduotis yra sudaryti matricą A kad seka A (0) , A (1) , A (2) ,...,A(k +1) davė aproksimaciją N -1 = f (x*) -1 ; kad gautų sprendimą X* reikia vienos papildomos paieškos tiesioje linijoje, jei f(x)- kvadratinė funkcija. Kaip jau ne kartą buvo pabrėžta aukščiau, yra tam tikrų priežasčių manyti, kad metodas, užtikrinantis kvadratinių funkcijų optimalų radimą, gali lemti sėkmę sprendžiant uždavinius su bendros formos netiesinėmis objektyviomis funkcijomis.

Grįžkime prie svarbios kvadratinių funkcijų savybės (3.75) ir tarkime, kad matrica SU-1 yra apytikslis pagal formulę

SU-1 = β A, (3.77)

kur p yra skaliarinis dydis. Labiausiai pageidaujama aproksimacija yra tokia, kuri tenkina (3,75), t.y.

x= A g. (3.78)

Tačiau aišku, kad tokio aproksimavimo sukurti neįmanoma, nes norint rasti g, jūs turite žinoti matricą A. Čia naudojami šie užrašai:

x= x– x, (3.79)

g= g(x) – g(x). (3.80)

Kita vertus, galima reikalauti, kad naujasis aproksimavimas atitiktų (3.75) formulę:

x= β A g. (3.81)

Pakeitę išraišką (3.76) į (3.81), gauname

A g= x– A g. (3.82)

Naudodami tiesioginį pakeitimą galite patikrinti, ar matrica

A = – (3.83)

yra šios lygties sprendimas. Čia adresu Ir z- savavališki vektoriai, ty formulė (3.83) apibrėžia tam tikrą sprendinių šeimą. Jei įdėsite

y = x Ir z =A g, (3.84)

tada gauname formulę, kuri įgyvendina gerai žinomą ir plačiai naudojamą Davidono metodas- Fletcheris- Powell(DFP):

A= A + – . (3.85)

Galima parodyti, kad ši pasikartojanti formulė išsaugo simetrijos ir teigiamo matricų apibrėžtumo savybes. Todėl jei A(0) yra simetriška teigiama apibrėžtoji matrica, tada matricos A (1) , A(2) , ... taip pat yra simetriški ir teigiamai apibrėžti, jei nėra apvalinimo klaidų; dažniausiai patogu rinktis A (0) = aš.

Pirma variacija f(x) lygus

f(x) = f (x) x. (3.86)

Naudodami (3.42) ir (3.74) formules gauname

f(x) = f (x) α A f (x), (3.87)

f(x) = – α f (x) A f (x), (3.88)

ir nelygybė f (x(k+1)) < f(x k) yra patenkintas bet kokioms α > 0 reikšmėms, jei A yra teigiama apibrėžtoji matrica. Taigi, algoritmas užtikrina, kad tikslo funkcija mažėtų, kai pereinama nuo iteracijos prie iteracijos. Davidon-Fletcher-Powell metodas daugelį metų išliko plačiausiai naudojamas gradiento metodas. Jis yra stabilus ir sėkmingai naudojamas sprendžiant įvairias praktikoje iškylančias problemas. Pagrindinis šio tipo metodų trūkumas yra būtinybė saugoti matricą kompiuterio atmintyje A tvarka N N.

Metodas skirtas (5.1) uždaviniui spręsti ir priklauso pirmos eilės metodų klasei. Metodas yra stačiausio nusileidimo (pakilimo) metodo modifikacija ir automatiškai atsižvelgia į tikslo funkcijos ypatybes, greitinančius konvergenciją.

Algoritmo aprašymas

0 veiksmas. Pasirinktas pradinis artėjimo taškas, žingsnio ilgio parametras , sprendimo tikslumas ir apskaičiuojama pradinė paieškos kryptis.

K žingsnis. Įjungta k-tas žingsnis, tikslo funkcijos minimumas (maksimumas) randamas tiesėje, nubrėžtoje iš taško kryptimi . Rastas minimumas (maksimalus) taškas lemia kitą k aproksimacija, po kurios nustatoma paieškos kryptis

Formulė (5.4) gali būti perrašyta lygiaverte forma

.

Algoritmas baigia savo darbą, kai tik įvykdoma sąlyga; sprendiniu imama paskutinės gautos aproksimacijos reikšmė.

Niutono metodas

Metodas skirtas (5.1) uždaviniui spręsti ir priklauso antros eilės metodų klasei. Metodas pagrįstas tikslinės funkcijos Teiloro išplėtimu ir tuo, kad ekstremaliame taške funkcijos gradientas yra lygus nuliui, tai yra.

Iš tiesų, tegul kuris nors taškas yra pakankamai arti norimo ekstremumo taško. Pasvarstykime i Tikslinės funkcijos gradiento komponentą ir išplėskite jį taške, naudodami Teiloro formulę iki pirmos eilės išvestinių:

. (5.5)

Formulę (5.5) perrašome matricine forma, atsižvelgdami į tai :

kur yra tikslo funkcijos Heso matrica taške .

Tarkime, kad Heseno matrica yra ne vienaskaita. Tada ji turi atvirkštinę matricą. Padauginę abi (5.6) lygties puses iš kairės, gauname , Iš kurių

. (5.7)

Formulė (5.7) apibrėžia Niutono metodo algoritmą: aproksimacijų perskaičiavimas pagal k

Algoritmas baigia savo darbą, kai tik įvykdoma sąlyga

,

kur nurodytas sprendimo tikslumas; sprendiniu imama paskutinės gautos aproksimacijos reikšmė.

Niutono-Rafsono metodas

Metodas yra pirmos eilės metodas ir skirtas sistemoms spręsti n netiesinės lygtys c n nežinomas:

Ypač šis metodas gali būti taikomas ieškant uždavinio (5.1) tikslo funkcijos stacionarių taškų, kai reikia išspręsti lygčių sistemą iš sąlygos .

Tegul taškas yra sistemos (5.9) sprendimas, o taškas yra šalia . Išplėsdami funkciją taške, naudodami Teiloro formulę, turime

iš kur (pagal sąlygą) išplaukia

, (5.11)

kur yra vektorinės funkcijos Jakobijos matrica. Tarkime, kad Jakobijos matrica yra ne vienaskaita. Tada ji turi atvirkštinę matricą. Abi lygties (5.11) puses padauginę iš kairės, gauname , kur

. (5.12)

Formulė (5.12) apibrėžia Niutono-Rafsono metodo algoritmą: aproksimacijų perskaičiavimas į k iteracija atliekama pagal formulę

Vieno kintamojo atveju, kai sistema (5.9) išsigimsta į vieną lygtį, formulė (5.13) įgauna formą

, (5.14)

kur yra funkcijos išvestinės reikšmė taške .

Fig. 5.2 paveiksle pavaizduota Niutono-Rafsono metodo įgyvendinimo schema ieškant lygties sprendimo.

Pastaba 5.1. Skaitinių metodų konvergencija, kaip taisyklė, labai priklauso nuo pradinio aproksimavimo.

Pastaba 5.2. Niutono ir Niutono-Rafsono metodai reikalauja daug skaičiavimų (kiekviename žingsnyje būtina apskaičiuoti ir apversti Heso ir Jacobi matricas).

Pastaba 5.3. Taikant metodus, būtina atsižvelgti į tai, kad tikslo funkcijoje (savybėje) gali būti daug ekstremalių multimodalumas).

LITERATŪRA

1. Afanasjevas M. Yu., Suvorovas B.P. Operacijų tyrimas ekonomikoje: vadovėlis. – M.: Maskvos valstybinio universiteto Ekonomikos fakultetas, TEIS, 2003 – 312 p.

2. Bazara M, Shetty K. Netiesinis programavimas. Teorija ir algoritmai: Trans. iš anglų kalbos – M.: Mir, 1982 – 583 p.

3. Bermanas G.N. Matematinės analizės kurso uždavinių rinkinys: Vadovėlis universitetams. – Sankt Peterburgas: „Specialioji literatūra“, 1998. – 446 p.

4. Vagneris G. Operacijų tyrimo pagrindai: 3 tomai. Per. iš anglų kalbos – M.: Mir, 1972. – 336 p.

5. Ventzelis E. C. Operacijų tyrimas. Tikslai, principai, metodika - M.: Nauka, 1988. - 208 p.

6. Demidovičius B.P. Matematinės analizės uždavinių ir pratimų rinkinys . – M.: Nauka, 1977. – 528 p.

7. Degtyarev Yu.I. Operacijų tyrimas. – M.: Aukštesnis. mokykla, 1986. – 320 p.

8. Nurejevas R.M. Mikroekonomikos problemų rinkinys. – M.: NORMA, 2006. – 432 p.

9. Solodovnikovas A. SU., Babaicevas V.A., Brailovas A.V. Matematika ekonomikoje: Vadovėlis: 2 dalyse - M.: Finansai ir statistika, 1999. - 224 p.

10. Taha H.Įvadas į operacijų tyrimą, 6 leidimas: Trans. iš anglų kalbos – M.: Williams Publishing House, 2001. – 912 p.

11. Himmelblau D. Taikomas netiesinis programavimas: Vertimas. iš anglų kalbos – M.: Mir, 1975 – 534 p.

12. Šikinas E. IN., Shikina G.E. Operacijų tyrimas: Vadovėlis - M.: TK Welby, Prospekt leidykla, 2006. - 280 p.

13. Operacijų tyrimas ekonomikoje: Vadovėlis. vadovas universitetams / N.Sh.Kremer, B.A.Putko, I.M.Trishin, M.N. Red. prof. N. Š. Kremeris. – M.: Bankai ir biržos, VIENYBĖ, 1997. – 407 p.

14. Matricos ir vektoriai: Vadovėlis. pašalpa / Ryumkin V.I. – Tomskas: TSU, 1999. – 40 p.

15. Tiesinių lygčių sistemos: Vadovėlis. pašalpa / Ryumkin V.I. – Tomskas: TSU, 2000. – 45 p.

Tiesinių ir netiesinių funkcijų apibrėžimus rasite 1.2 skyriuje