Raskite funkcijos stacionarųjį tašką naudodami stačiausio nusileidimo metodą. Stačiausio nusileidimo būdas

Paslaugos paskirtis. Rasti naudotas internetinis skaičiuotuvas minimali funkcija stačiausio nusileidimo būdas arba Koši metodas(žr. pavyzdį). Sprendimas parengtas Word formatu.

Funkcijos įvedimo taisyklės

IN stačiausias nusileidimo būdas kaip paieškos kryptis pasirenkamas vektorius, kurio kryptis priešinga funkcijos ▽f(x) gradiento vektoriaus krypčiai. Iš matematinės analizės žinoma, kad vektorius grad f(x)=▽f(x) apibūdina sparčiausio funkcijos didėjimo kryptį (žr. funkcijos gradientą). Todėl vadinamas vektoriumi - grad f (X) = -▽f(X). antigradientas ir yra jo sparčiausio mažėjimo kryptis. Pasikartojimo ryšys, su kuriuo įgyvendintas stačiausio nusileidimo metodas, turi formą X k +1 =X k - λ k ▽f(x k), k = 0,1,...,
kur λ k >0 yra žingsnio dydis. Priklausomai nuo pasirinkto žingsnio dydžio, galite gauti skirtingas gradiento metodo parinktis. Jei optimizavimo proceso metu žingsnio dydis λ yra fiksuotas, tai metodas vadinamas gradiento metodu su diskrečiu žingsniu. Optimizavimo procesas pirmosiose iteracijose gali būti žymiai pagreitintas, jei λ k pasirenkamas iš sąlygos λ k =min f(X k + λS k) .
λ k nustatyti naudojamas bet koks vienmatis optimizavimo metodas. Šiuo atveju metodas vadinamas stačiausio nusileidimo metodu. Paprastai vieno žingsnio nepakanka, kad būtų pasiektas funkcijos minimumas, kol vėlesni skaičiavimai pagerins rezultatą.
Jei kai kuriais kintamaisiais erdvė yra labai pailgėjusi, susidaro „daubė“. Paieška gali sulėtėti ir eiti zigzagu per „daubos“ dugną. Kartais sprendimo nepavyksta rasti per priimtiną laikotarpį.
Kitas metodo trūkumas gali būti stabdymo kriterijus ||▽f(X k)||<ε k , так как этому условию удовлетворяет и седловая точка, а не только оптимум.

Pavyzdys. Pradėdami nuo taško x k =(-2, 3), nustatykite tašką x k +1, naudodami stačiausio nusileidimo metodą, kad sumažintumėte funkciją.
Kaip paieškos kryptį pasirinkite gradiento vektorių dabartiniame taške

Patikrinkime stabdymo kriterijų. Turime
Apskaičiuokime funkcijos reikšmę pradiniame taške f(X 1) = 35. Padarykime
žingsniuokite antigradiento kryptimi

Apskaičiuokime funkcijos reikšmę naujame taške
f(X 2) = 3 (-2 + 19 λ 1) 2 + (3-8 λ 1) 2 - (-2 + 19 λ 1) (3-8 λ 1) - 4 (-2 + 19 λ 1)
Raskime žingsnį, kad tikslo funkcija šia kryptimi pasiektų minimumą. Iš būtinos funkcijos ekstremumo egzistavimo sąlygos
f’(X 2) = 6 (-2 + 19λ 1) 19 + 2 (3-8λ 1) (-8) – (73 - 304 λ 1) – 4*19
arba f’(X 2) = 2598 λ 1 – 425 = 0.
Gauname žingsnį λ 1 = 0,164
Atlikę šį žingsnį, pasieksite tašką

kurioje gradiento reikšmė , funkcijos reikšmė f(X 2) = 0,23. Tikslumas nepasiekiamas, nuo taško žengiame žingsnį antigradiento kryptimi.

f(X 2) = 3(1,116 – 1,008 λ 1) 2 + (1,688-2,26 λ 1) 2 – (1,116 – 1,008 λ 1) (1,688-2,26 λ 1) – 4 (1,116 – 1,0)
f’(X 2) = 11,76 – 6,12λ 1 = 0
Gauname λ 1 = 0,52

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.

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

Ryžiai. 2.8. Gradientas

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

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]

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

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

(a)/da = -f’(x

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, i =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. Gelbėtojų funkcija

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 matricos atžvilgiu H(arba H-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ą -f(x[r]) kryptimi p[r], H-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[ p[r+b k-1 r>= 1;

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

f r b reikšmės p[r], Nusileidimo krypties pasirinkimas[r-1 parinkti taip, kad kryptys H-1] buvo :

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

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)

f(x[ r] + Autorius[r]) = f(x[r] + judėjimo kryptimi, t. y. išsprendus vienmačio minimizavimo problemą: [r]) .

a k r

Dėl kvadratinės funkcijos X Fletcher-Reeves konjuguoto gradiento metodo algoritmas yra toks. p = --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 p[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 p[r+b k-1 r>= 1;

= x k+);

f(x[ 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). Nes Nusileidimo krypties pasirinkimas , H yra mažiausias funkcijos taškas kryptimi Nusileidimo krypties pasirinkimas Tai Nusileidimo krypties pasirinkimas statmena vektoriui

. Tada randamas vektorius . - konjuguoti su

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 n= (0, n, 2

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

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]1) 1-4 procedūrų kartojimas kartojamas cikliškai su pakeitimu i [r] -A r 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 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.

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

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 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 – į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čiavimų 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 greičiausio nusileidimo kryptimi.