Shuningdek, siz gradient yo'nalishi bo'yicha eng yaxshi nuqtani emas, balki hozirgisidan yaxshiroq nuqtani qidirishingiz mumkin.
Barcha mahalliy optimallashtirish usullarini amalga oshirishning eng oson usuli. Juda bor zaif sharoitlar konvergentsiya, lekin yaqinlashish tezligi ancha past (chiziqli). Gradient usuli bosqichi ko'pincha Fletcher-Rives usuli kabi boshqa optimallashtirish usullarining bir qismi sifatida ishlatiladi.
Tavsif [ | ]
Yaxshilanishlar[ | ]
Gradient tushish usuli jar bo'ylab harakatlanayotganda va o'zgaruvchilar sonining ko'payishi bilan juda sekin bo'lib chiqadi. maqsad funktsiyasi Usulning bunday xatti-harakati odatiy holga aylanadi. Ushbu hodisaga qarshi kurashish uchun u ishlatiladi, uning mohiyati juda oddiy. Gradient tushishning ikki bosqichini amalga oshirib, uchta nuqtani qo'lga kiritgandan so'ng, uchinchi qadamni birinchi va uchinchi nuqtalarni bog'laydigan vektor yo'nalishi bo'yicha, jarlikning tubi bo'ylab qilish kerak.
Kvadratga yaqin funksiyalar uchun konjugat gradient usuli samarali hisoblanadi.
Sun'iy neyron tarmoqlarda qo'llanilishi[ | ]
Gradient descent usuli, ba'zi bir modifikatsiyalari bilan, perseptronlarni tayyorlash uchun keng qo'llaniladi va sun'iy neyron tarmoqlar nazariyasida teskari tarqalish usuli sifatida ma'lum. Perseptron tipidagi neyron tarmog'ini o'rgatishda tarmoqning og'irlik koeffitsientlarini minimallashtirish uchun o'zgartirish kerak. o'rtacha xato neyron tarmog'ining chiqishida o'quv kiritish ma'lumotlarining ketma-ketligi kirishga etkazib berilganda. Rasmiy ravishda, gradient tushish usulidan foydalangan holda bir qadam tashlash uchun (tarmoq parametrlarini faqat bitta o'zgartirish), tarmoq kiritishiga o'quv ma'lumotlarining to'liq to'plamini ketma-ket ravishda topshirish, har bir ob'ekt uchun xatoni hisoblash kerak. o'quv ma'lumotlarini o'rganing va tarmoq koeffitsientlarini kerakli tuzatishni hisoblang (lekin bunday tuzatishni qilmang) va barcha ma'lumotlarni taqdim etgandan so'ng, har bir tarmoq koeffitsientini (gradientlar yig'indisi) tuzatish miqdorini hisoblang va "bir qadam" koeffitsientlarini to'g'rilang. . Shubhasiz, o'quv ma'lumotlarining katta to'plami bilan algoritm juda sekin ishlaydi, shuning uchun amalda tarmoq koeffitsientlari ko'pincha har bir o'quv elementidan keyin o'rnatiladi, bu erda gradient qiymati faqat bitta treningda hisoblangan xarajat funktsiyasi gradienti bilan yaqinlashadi. element. Bu usul deyiladi stokastik gradient tushishi yoki operatsion gradient tushishi . Stokastik gradient tushishi stokastik yaqinlashishning bir shaklidir. Stokastik yaqinlashishlar nazariyasi stokastik gradient tushish usulining yaqinlashuvi uchun shart-sharoitlarni ta'minlaydi.
Havolalar [ | ]
- J. Metyus. Eng tik tushish yoki gradient usuli uchun modul. (mavjud havola)
Adabiyot [ | ]
- Akulich I. L. Misollar va masalalarda matematik dasturlash. - M.: Oliy maktab, 1986. - B. 298-310.
- Gill F., Myurrey V., Rayt M. Amaliy optimallashtirish = Amaliy optimallashtirish. - M.: Mir, 1985 yil.
- Korshunov M., Korshunov M. Kibernetikaning matematik asoslari. - M.: Energoatomizdat, 1972 yil.
- Maksimov Yu., Fillipovskaya E. A. Nochiziqli dasturlash masalalarini yechish algoritmlari. - M.: MEPhI, 1982 yil.
- Maksimov A. Chiziqli va diskret dasturlash algoritmlari. - M.: MEPhI, 1980 yil.
- Korn G., Korn T. Olimlar va muhandislar uchun matematika bo'yicha qo'llanma. - M.: Nauka, 1970. - B. 575-576.
- S. Yu Gorodetskiy, V. A. Grishagin. Nochiziqli dasturlash va multiekstremal optimallashtirish. - Nijniy Novgorod: Nijniy Novgorod universiteti nashriyoti, 2007. - 357-363-betlar.
Eng tik tushish usuli - bu o'zgaruvchan bosqichli gradient usuli. Har bir iteratsiyada f(x) funksiyaning tushish yo‘nalishi bo‘yicha minimumi shartidan qadam o‘lchami k tanlanadi, ya’ni.
Bu holat antigradient bo‘ylab harakatlanish f (x) funksiyaning qiymati kamayguncha sodir bo‘lishini bildiradi. Matematik nuqtai nazardan, har bir iteratsiyada funktsiya bo'yicha bir o'lchovli minimallashtirish masalasini hal qilish kerak.
()=f (x (k) -f (x (k))))
Buning uchun oltin nisbat usulidan foydalanamiz.
Eng tik tushish usulining algoritmi quyidagicha.
X (0) boshlang'ich nuqtasining koordinatalari ko'rsatilgan.
x (k) , k = 0, 1, 2, ... nuqtada f (x (k)) gradient qiymati hisoblanadi.
Qadam o'lchami k funksiya yordamida bir o'lchovli minimallashtirish orqali aniqlanadi
()=f (x (k) -f (x (k)))).
x (k) nuqtaning koordinatalari aniqlanadi:
x i (k+1) = x i (k) - k f i (x (k)), i=1, …, n.
Takroriy jarayonni to'xtatish sharti tekshiriladi:
||f (x (k +1))|| .
Agar u bajarilsa, hisob-kitoblar to'xtaydi. Aks holda, biz 1-bosqichga o'tamiz. Eng tik tushish usulining geometrik talqini rasmda keltirilgan. 1.
Guruch. 2.1. Eng tik tushish usulining blok diagrammasi.
Usulni dasturda amalga oshirish:
Eng keskin tushish usuli.
Guruch. 2.2. Eng tik tushish usulini amalga oshirish.
Xulosa: Bizning holatlarimizda usul 7 ta iteratsiyada birlashtirildi. A7 nuqtasi (0,6641; -1,3313) ekstremum nuqtadir. Konjugatsiya yo'nalishlari usuli. Kvadrat funksiyalar uchun gradient usulini yaratishingiz mumkin, bunda yaqinlashish vaqti chekli va o'zgaruvchilar soni n ga teng bo'ladi.
Keling, ma'lum bir yo'nalishni chaqiramiz va H musbat aniq Hess matritsasiga nisbatan konjugat qilamiz, agar:
Keyin, ya'ni H birligi uchun konjugat yo'nalishi ularning perpendikulyarligini anglatadi. Umumiy holda, H ahamiyatsiz emas. IN umumiy holat konjugatsiya Gess matritsasining vektorga qo'llanilishi - bu vektorni qandaydir burchak bilan aylantirish, uni cho'zish yoki siqish demakdir.
Va endi vektor ortogonal, ya'ni konjugatsiya vektorning ortogonalligi emas, balki aylantirilgan vektorning ortogonalligi.e.i.
Guruch. 2.3. Konjugat yo'nalishlari usulining blok diagrammasi.
Usulning dasturda amalga oshirilishi: Konjugatsiya yo'nalishlari usuli.
Guruch. 2.4. Konjugat yo'nalishlari usulini amalga oshirish.
Guruch. 2.5. Konjugat yo'nalishlar usulining grafigi.
Xulosa: A3 nuqtasi (0,6666; -1,3333) 3 ta takrorda topilgan va ekstremum nuqta hisoblanadi.
3. Cheklovlar mavjudligida funksiyaning minimal va maksimal qiymatini aniqlash usullarini tahlil qilish
Shuni eslatib o'tamiz umumiy vazifa shartli optimallashtirish shunday ko'rinadi
f(x) ® min, x O Vt,
Bu erda W - R m ning to'g'ri kichik to'plami. Tenglik tipidagi cheklovlarga ega bo'lgan masalalarning kichik sinfi to'plamning shakl cheklovlari bilan aniqlanishi bilan ajralib turadi.
f i (x) = 0, bu erda f i: R m ®R (i = 1, …, k).
Shunday qilib,W = (x O R m: f i (x) = 0, i = 1, …, k).
Bizga f funksiyasi uchun "0" indeksini yozish qulay bo'ladi. Shunday qilib, tenglik tipidagi cheklovlar bilan optimallashtirish masalasi quyidagicha yoziladi
f 0 (x) ® min, (3.1)
f i (x) = 0, i = 1, …, k. (3.2)
Agar biz R m ustidagi funktsiyani R k qiymatlari bilan f bilan belgilasak, uning koordinata yozuvi f(x) = (f 1 (x), ..., f k (x)), keyin ( 3.1)–(3.2) shaklida ham yozishimiz mumkin
f 0 (x) ® min, f(x) = Q.
Geometrik jihatdan tenglik tipidagi cheklovlar bilan bog‘liq masala f 0 funksiya grafigining manifold ustidagi eng past nuqtasini topish masalasidir (3.1-rasmga qarang).
Barcha cheklovlarni qondiradigan nuqtalar (ya'ni, to'plamdagi nuqtalar ) odatda ruxsat etilgan deb ataladi. Ruxsat etilgan x* nuqta f i (x) = 0, i = 1, ..., k (yoki (3.1)–(3.2) masala yechimi) cheklovlari ostida f 0 funksiyaning shartli minimumi deyiladi, agar barcha ruxsat etilgan nuqtalar uchun x f 0 (x *) f 0 (x). (3.3)
Agar (3.3) faqat x* nuqtaning V x * mahallasida yotadigan ruxsat etilgan x uchun qanoatlansa, u holda biz mahalliy shartli minimum haqida gapiramiz. Shartli qat'iy mahalliy va global minimal tushunchalar tabiiy tarzda aniqlanadi.
Gradient usulining ushbu variantida minimallashtirish ketma-ketligi (X k) ham qoida (2.22) bo'yicha tuzilgan. Biroq, a k qadam o'lchami yordamchi bir o'lchovli minimallashtirish masalasini echish natijasida topiladi.
min(j k (a) | a>0 ), (2.27)
bu yerda j k (a)=f(X k - a· (X k)). Shunday qilib, antigradient yo'nalishi bo'yicha har bir iteratsiyada 
to'liq tushish amalga oshiriladi. Muammoni (2.27) hal qilish uchun siz 1-bo'limda tasvirlangan bir o'lchovli qidirish usullaridan birini qo'llashingiz mumkin, masalan, bit bo'yicha qidirish usuli yoki oltin qism usuli.
Keling, eng tik tushish usulining algoritmini tasvirlaylik.
0-qadam. Aniqlik parametrini e>0 o'rnating, X 0 OE n ni tanlang, k=0 ni o'rnating.
1-qadam.(X k) ni toping va belgilangan aniqlikka erishish shartini tekshiring || (x k) ||£ e. Agar u bajarilgan bo'lsa, 3-bosqichga, aks holda - 2-bosqichga o'ting.
2-qadam. Muammoni yechish (2.27), ya'ni. k toping. Keyingi nuqtani toping, k=k+1 qo'ying va 1-bosqichga o'ting.
3-qadam X * = X k, f * = f (X k) qo'yish orqali hisob-kitoblarni yakunlang.
Funktsiyani minimallashtirish
f(x)=x 1 2 +4x 2 2 -6x 1 -8x 2 +13; (2,28)
Avval muammoni hal qilaylik klassik usul. ifodalovchi tenglamalar tizimini yozamiz zarur shart-sharoitlar shartsiz ekstremum
Uni yechib, statsionar X*=(3;1) nuqtani olamiz. Keyinchalik, bajarilishni tekshiramiz etarli holat, buning uchun biz ikkinchi hosilalarning matritsasini topamiz
Silvester mezoniga ko'ra, bu matritsa " uchun musbat aniqlanganligi sababli, topilgan X * nuqtasi f(X) funktsiyasining minimal nuqtasidir. Minimal qiymati f *=f(X*)=0. Bu (11) muammoning aniq yechimi.
Keling, usulning bir iteratsiyasini bajaramiz gradient tushishi uchun (2.28). X 0 =(1;0) boshlang'ich nuqtasini tanlaymiz, boshlang'ich qadam a=1 va l=0,5 parametrini o'rnatamiz. f(X 0)=8 ni hisoblab chiqamiz.
f(X) funksiyaning X 0 nuqtadagi gradientini topamiz
(X 0)= = (2,29)
Yangi X=X 0 -a· (X 0) nuqtani uning koordinatalarini hisoblab aniqlaymiz.
x 1 = 
x 2 = 
(2.30)
f(X)= f(X 0 -a· (X 0))=200 ni hisoblaymiz. f(X)>f(X 0) bo’lgani uchun a=a·l=1·0,5=0,5 deb, qadamni ajratamiz. (2.30) x 1 =1+4a=3 formulalar yordamida yana hisoblaymiz; x 2 =8a=4 va f(X)=39 qiymatini toping. Yana f(X)>f(X 0) bo'lgani uchun qadam o'lchamini yanada kamaytiramiz, a=a·l=0,5·0,5=0,25 o'rnatamiz. Koordinatalari x 1 =1+4·0,25=2 bo'lgan yangi nuqtani hisoblaymiz; x 2 =8·0,25=2 va funksiyaning bu nuqtadagi qiymati f(X)=5. f(X) ni kamaytirish sharti tufayli Usul yordamida bir iteratsiyani bajaramiz eng keskin tushish uchun (2.28) bir xil boshlang'ich nuqta bilan X 0 =(1;0). Topilgan gradientdan (2.29) foydalanib, biz topamiz X= X 0 -a· (X 0) va j 0 (a)=f(X 0 -a· (X 0))=(4a-2) 2 +4(8a-1) 2 funksiyani tuzing. Kerakli shart yordamida uni minimallashtirish orqali j 0 ¢(a)=8·(4a - 2)+64·(8a - 1)=0 qadam kattaligining optimal qiymatini topamiz a 0 =5/34. Minimallashtirish ketma-ketligining nuqtasini aniqlash X 1 = X 0 -a 0 · (X 0) f(x) differensiallanuvchi funksiyaning nuqtadagi gradienti X chaqirdi n-o'lchovli vektor f(x)
, uning komponentlari funksiyaning qisman hosilalari f(x), nuqtada hisoblangan X, ya'ni. f"(x ) = (df(x)/dh 1 , …, df(x)/dx n) T. Bu vektor nuqta orqali tekislikka perpendikulyar X, va funksiyaning tekis yuzasiga teginish f(x), nuqtadan o'tish X.Bunday sirtning har bir nuqtasida funksiya f(x) bir xil qiymatni oladi. Funktsiyani C 0, C 1, ... har xil doimiy qiymatlarga tenglashtirib, biz uning topologiyasini tavsiflovchi bir qator sirtlarni olamiz (2.8-rasm). Gradient vektori berilgan nuqtada funktsiyaning eng tez o'sish yo'nalishiga yo'naltiriladi. Gradientga qarama-qarshi vektor (-f'(x))
, chaqirildi gradientga qarshi va funksiyaning eng tez kamayishiga qaratilgan. Minimal nuqtada funksiyaning gradienti nolga teng. Gradient va minimallashtirish usullari deb ham ataladigan birinchi tartibli usullar gradientlarning xususiyatlariga asoslanadi. Ushbu usullardan umumiy holatda foydalanish funksiyaning mahalliy minimal nuqtasini aniqlash imkonini beradi. Shubhasiz, agar qo'shimcha ma'lumot bo'lmasa, unda boshlang'ich nuqtadan X nuqtaga o'tish maqsadga muvofiqdir X, antigradient yo'nalishida yotish - funktsiyaning eng tez pasayishi. Pastga tushish yo'nalishi sifatida tanlash R[k] anti-gradient - f'(x[k] )
nuqtada X[k], biz shaklning iterativ jarayonini olamiz X[ k+ 1] = x[k]-a k f"(x[k] )
,
va k > 0; k=0, 1, 2, ... Koordinata shaklida bu jarayon quyidagicha yoziladi: x i [ k+1]=x i[k] - a kf(x[k] )
/x i i = 1, ..., n; k= 0, 1, 2,... Takrorlanish jarayonini to'xtatish mezoni sifatida yoki argumentning kichik o'sishi shartining bajarilishi || x[k+l] - x[k] || <= e
,
либо выполнение условия малости градиента || f'(x[k+l] )
|| <= g
, Bu yerda e va g kichik miqdorlar berilgan. Belgilangan shartlarni bir vaqtning o'zida bajarishdan iborat bo'lgan birlashtirilgan mezon ham mumkin. Gradient usullari qadam o'lchamini tanlashda bir-biridan farq qiladi va k. Doimiy qadamli usulda barcha iteratsiyalar uchun ma'lum bir doimiy qadam qiymati tanlanadi. Juda kichik qadam va k funksiyaning, ya'ni tengsizlikning kamayishini ta'minlaydi f(x[ k+1])
= f(x[k] - a k f’(x[k] ))
< f(x[k] )
. Biroq, bu minimal nuqtaga erishish uchun qabul qilib bo'lmaydigan darajada ko'p takrorlashni amalga oshirish zarurligiga olib kelishi mumkin. Boshqa tomondan, juda katta qadam funktsiyaning kutilmagan o'sishiga olib kelishi yoki minimal nuqta (velosiped) atrofida tebranishlarga olib kelishi mumkin. Qadam o'lchamini tanlash uchun kerakli ma'lumotlarni olish qiyinligi sababli, amalda doimiy qadamlarga ega bo'lgan usullar kamdan-kam qo'llaniladi. Gradientlilar iteratsiyalar soni va ishonchliligi jihatidan ancha tejamkor o'zgaruvchan qadam usullari, qachon, hisob-kitoblar natijalariga qarab, qadam o'lchami qandaydir tarzda o'zgaradi. Keling, amaliyotda qo'llaniladigan bunday usullarning variantlarini ko'rib chiqaylik. Har bir iteratsiyada eng tik tushish usulidan foydalanilganda, qadam o'lchami va k funksiyaning minimal shartidan tanlanadi f(x) tushish yo'nalishi bo'yicha, ya'ni. Bu holat antigradient bo'ylab harakatlanish funktsiya qiymatiga qadar sodir bo'lishini anglatadi f(x) kamayadi. Matematik nuqtai nazardan, har bir iteratsiyada quyidagiga muvofiq bir o'lchovli minimallashtirish masalasini hal qilish kerak. A funktsiyalari Eng tik tushish usulining algoritmi quyidagicha. 1. Boshlanish nuqtasining koordinatalarini o'rnating X.
2. Nuqtada X[k],
k = 0, 1, 2, ... gradient qiymatini hisoblaydi f'(x[k])
. 3. Qadam hajmi aniqlanadi a k, bir o'lchovli minimallashtirish orqali A funktsiyalari j (a) = f(x[k]-af"(x[k])).
4. Nuqtaning koordinatalari aniqlanadi X[k+ 1]: x i [ k+ 1]= xi[k]– a k f’ i (x[k]), i = 1,..., p. 5.Steratsiya jarayonini to'xtatish shartlari tekshiriladi. Agar ular bajarilsa, hisob-kitoblar to'xtaydi. Aks holda, 1-bosqichga o'ting. Ko'rib chiqilayotgan usulda nuqtadan harakat yo'nalishi X[k] nuqtadagi daraja chizig'iga tegadi x[k+ 1] (2.9-rasm). Tushilish traektoriyasi zigzag bo'lib, qo'shni zigzag aloqalari bir-biriga ortogonal bo'ladi. Haqiqatan ham, bir qadam a k tomonidan minimallashtirish orqali tanlanadi A funktsiyalari? (a) = f(x[k] -af"(x[k]))
. Funksiyaning minimumi uchun zaruriy shart d j (a)/da = 0. Murakkab funktsiyaning hosilasini hisoblab, biz qo'shni nuqtalarda tushish yo'nalishlari vektorlarining ortogonalligi shartini olamiz: dj (a)/da = -f’(x[k+ 1]f'(x[k])
= 0.
Gradient usullari silliq konveks funktsiyalari uchun yuqori tezlikda (geometrik progressiya tezligi) minimal darajaga yaqinlashadi. Bunday funktsiyalar eng katta xususiyatlarga ega M va eng kam m Ikkinchi hosilalar matritsasining xos qiymatlari (Gessian matritsasi) bir-biridan kam farq qiladi, ya'ni matritsa N(x) yaxshi shartlangan. Eslatib o'tamiz, xususiy qiymatlar l i, i
=1, …, n, matritsalar xarakteristik tenglamaning ildizlari hisoblanadi Biroq, amalda, qoida tariqasida, minimallashtiriladigan funktsiyalar ikkinchi hosilalarning noto'g'ri matritsalariga ega. (t/m<<
1). Ba'zi yo'nalishlar bo'yicha bunday funktsiyalarning qiymatlari boshqa yo'nalishlarga qaraganda ancha tezroq (ba'zan bir necha darajalar bilan) o'zgaradi. Ularning tekis sirtlari eng oddiy holatda kuchli cho'zilgan (2.10-rasm), murakkabroq hollarda esa ular egilib, jarlarga o'xshaydi. Bunday xususiyatlarga ega funksiyalar deyiladi jar. Ushbu funktsiyalarning antigradientining yo'nalishi (2.10-rasmga qarang) yo'nalishdan minimal nuqtaga sezilarli darajada og'adi, bu esa konvergentsiya tezligining sekinlashishiga olib keladi. Gradient usullarining yaqinlashuv tezligi ham sezilarli darajada gradient hisob-kitoblarining to'g'riligiga bog'liq. Odatda minimal nuqtalar yaqinida yoki chuqurlikdagi vaziyatda sodir bo'ladigan aniqlikni yo'qotish, odatda, gradient tushish jarayonining yaqinlashishini buzishi mumkin. Yuqoridagi sabablarga ko'ra, muammoni hal qilishning dastlabki bosqichida gradient usullari ko'pincha boshqa, samaraliroq usullar bilan birgalikda qo'llaniladi. Bu holda, nuqta X minimal nuqtadan uzoqda va antigradient yo'nalishidagi qadamlar funktsiyaning sezilarli pasayishiga erishishga imkon beradi. Yuqorida ko'rib chiqilgan gradient usullari umumiy holatda funktsiyaning minimal nuqtasini faqat cheksiz miqdordagi iteratsiyalarda topadi. Konjugat gradient usuli minimallashtirilayotgan funksiya geometriyasiga ko'proq mos keladigan qidiruv yo'nalishlarini yaratadi. Bu ularning yaqinlashish tezligini sezilarli darajada oshiradi va, masalan, kvadratik funktsiyani minimallashtirishga imkon beradi. f(x) = (x, Hx) + (b, x) + a simmetrik musbat aniq matritsa bilan N cheklangan miqdordagi qadamlarda P, funksiya o'zgaruvchilari soniga teng. Minimal nuqtaga yaqin joylashgan har qanday silliq funksiya kvadrat funktsiya bilan yaxshi yaqinlashishi mumkin, shuning uchun kvadratik bo'lmagan funktsiyalarni minimallashtirish uchun konjugat gradient usullari muvaffaqiyatli qo'llaniladi. Bunday holda, ular chekli bo'lishni to'xtatadi va iterativ bo'ladi. Ta'rifga ko'ra, ikkita n-o'lchovli vektor X Va da chaqirdi konjugatsiyalangan matritsaga nisbatan H(yoki H-konjugat), agar skalyar ko'paytma bo'lsa (x, Xo'sh) = 0. Bu yerga N - kattalikning simmetrik musbat aniq matritsasi P X P. Konjugat gradient usullarining eng muhim muammolaridan biri bu yo'nalishlarni samarali qurish muammosidir. Fletcher-Rives usuli bu muammoni har bir bosqichda antigradientni o'zgartirish orqali hal qiladi -f(x[k])
yo'nalishda p[k],
H-oldindan topilgan yo'nalishlar bilan konjugatsiya R, R, ..., R[k-1]. Keling, avval ushbu usulni minimallashtirish muammosi bilan bog'liq holda ko'rib chiqaylik. kvadratik funktsiya R[k Yo'nalishlar ] formulalar yordamida hisoblanadi: k] = -f'(x[k])
p[ p[k+b k-1 k>= 1; -l], p = -’(x)
. f k Qadriyatlar b p[k], R[k-1 yo'nalishlari shunday tanlangan H-1] edi :
(p[k], - konjugat[HP 1])= 0.
k- Natijada, kvadratik funktsiya uchun takroriy minimallashtirish jarayoni shaklga ega k+l] x[[k]=x[k], +a k p R[k] -
Qayerda HP ga tushish yo'nalishi m qadam; va k - qadam hajmi. Ikkinchisi funksiyaning minimal shartidan tanlanadi f(x) A tomonidan f(x[ k] + harakat yo'nalishi bo'yicha, ya'ni bir o'lchovli minimallashtirish masalasini hal qilish natijasida:[k])
= f(x[k] + a k r [k])
. ar Kvadrat funksiya uchun Fletcher-Rives konjugat gradient usulining algoritmi quyidagicha. X 1. Nuqtada p = -f'(x)
. hisoblangan HP 2. Yoqilgan A m qadam, yuqoridagi formulalar yordamida qadam aniqlanadi .
k X[k+ 1]. va davr f(x[k+1])
3. Qiymatlar hisoblab chiqiladi f'(x[k+1])
. Va f'(x)
4. Agar X[k= 0, keyin nuqta +1] funksiyaning minimal nuqtasi f(x). p[k Aks holda, yangi yo'nalish belgilanadi +l] munosabatdan P va keyingi iteratsiyaga o'tish amalga oshiriladi. Ushbu protsedura kvadratik funktsiyaning minimalini ko'pi bilan topmaydi qadamlar. Kvadrat bo'lmagan funktsiyalarni minimallashtirishda Fletcher-Rives usuli cheklidan iterativga o'tadi. Bunday holda, keyin(p+ X 1) 1-4-protseduralarning ikkinchi takrori almashtirish bilan tsiklik ravishda takrorlanadi X[P yoqilgan takroriy minimallashtirish jarayoni shaklga ega k+l] +1] va hisoblar bilan tugaydi, bu erda berilgan raqam. Bunday holda, usulning quyidagi modifikatsiyasi qo'llaniladi:[k]=x[k],
] formulalar yordamida hisoblanadi: k] = x[k])+
= -f'(x HP 1 p[k+b k-1 k>= 1; b x); f(x[ k] + p = -f’([k])
= f(x[k] a k p[k];
+ap Bu yerga I Bu yerga- ko'plab indekslar: = (0, n, 2 p, ish haqi, ...) P, ya'ni usul har yili yangilanadi qadamlar. Geometrik ma'no X Konjugat gradient usuli quyidagicha (2.11-rasm). Berilgan boshlang'ich nuqtadan R = yo'nalishi bo'yicha tushish amalga oshiriladi-f"(x X). Shu nuqtada gradient vektori aniqlanadi f"(x X yo'nalishdagi funktsiyaning minimal nuqtasidir R,
Bu f'(x)
vektorga ortogonal R. Keyin vektor topiladi R , H-ga birikadi R. Keyinchalik, yo'nalish bo'yicha funktsiyaning minimalini topamiz R va hokazo. Konjugat yo'nalishi usullari minimallashtirish muammolarini hal qilishda eng samarali hisoblanadi. Ammo shuni ta'kidlash kerakki, ular hisoblash jarayonida yuzaga keladigan xatolarga sezgir. Ko'p sonli o'zgaruvchilar bilan xato shunchalik ko'payishi mumkinki, jarayon hatto kvadratik funktsiya uchun ham takrorlanishi kerak bo'ladi, ya'ni uning jarayoni har doim ham mos kelmaydi. P, ya'ni usul har yili yangilanadi Eng tik tushish usuli (ingliz adabiyotida "eng tik tushish usuli") optimallashtirish masalalarini hal qilish uchun takrorlanuvchi raqamli usul (birinchi tartib) bo'lib, bu sizga maqsad funktsiyasining ekstremumini (minimal yoki maksimal) aniqlash imkonini beradi: Ko'rib chiqilayotgan usulga muvofiq, maqsad funktsiyasining ekstremum (maksimal yoki minimal) funktsiyaning eng tez o'sishi (kamayishi) yo'nalishi bo'yicha aniqlanadi, ya'ni. funktsiyaning gradienti (anti-gradient) yo'nalishi bo'yicha. Bir nuqtada gradient funktsiyasi bu yerda i, j,…, n koordinata o‘qlariga parallel bo‘lgan birlik vektorlar. Asosiy nuqtada gradient Eng keskin tushish usuli yanada rivojlantirish gradient tushish usuli. Umuman olganda, funktsiyaning ekstremumini topish jarayoni iterativ protsedura bo'lib, u quyidagicha yoziladi: bu yerda “+” belgisi funksiyaning maksimalini, “-” belgisi esa funksiyaning minimalini topish uchun ishlatiladi; Formula bilan aniqlanadigan birlik yo'nalishi vektori: Qadam hajmini aniqlaydigan va barcha i-yo'nalishlar uchun bir xil bo'lgan doimiy. Qadam o'lchami f(x) maqsad funktsiyasining harakat yo'nalishi bo'yicha minimal shartidan, ya'ni gradient yoki antigradient yo'nalishi bo'yicha bir o'lchovli optimallashtirish masalasini hal qilish natijasida tanlanadi: Boshqacha qilib aytganda, qadam hajmi ushbu tenglamani yechish orqali aniqlanadi: Shunday qilib, hisoblash bosqichi shunday tanlanadiki, harakat funktsiya yaxshilanmaguncha amalga oshiriladi va shu bilan bir nuqtada ekstremumga etadi. Bu vaqtda qidiruv yo`nalishi yana aniqlanadi (gradient yordamida) va maqsad funksiyasining yangi optimal nuqtasi izlanadi va hokazo. Shunday qilib, bu usulda qidiruv kattaroq bosqichlarda sodir bo'ladi va funksiyaning gradienti kichikroq nuqtalarda hisoblanadi. Ikki o'zgaruvchining funksiyasi holatida bu usul quyidagi geometrik talqinga ega: nuqtadan harakat yo'nalishi nuqtadagi sath chizig'iga tegadi. Tushilish traektoriyasi zigzag bo'lib, qo'shni zigzag rishtalari bir-biriga ortogonal bo'ladi. Qo'shni nuqtalarda tushish yo'nalishlari vektorlarining ortogonalligi sharti quyidagi ifoda bilan yoziladi: f(x) funksiyaning teng darajali chizig'i grafigida ko'rsatilgan eng keskin pasayish usuli yordamida ekstremum nuqtagacha bo'lgan harakat traektoriyasi. Optimal yechimni izlash iterativ hisoblash bosqichida (bir nechta mezonlarga muvofiq) tugaydi: Qidiruv traektoriyasi joriy qidiruv nuqtasining kichik hududida qolmoqda: Maqsad funktsiyasining o'sishi o'zgarmaydi: Mahalliy minimal nuqtada maqsad funktsiyasining gradienti nolga aylanadi: Shuni ta'kidlash kerakki, gradient tushish usuli jar bo'ylab harakatlanayotganda juda sekin bo'lib chiqadi va maqsad funktsiyasidagi o'zgaruvchilar soni ortib borishi bilan usulning bunday xatti-harakati odatiy holga keladi. Dara - bu chuqurlik bo'lib, uning tekislik chiziqlari taxminan bir necha marta farq qiladigan yarim o'qli ellips shakliga ega. Jarlik mavjud bo'lganda, tushish traektoriyasi kichik qadam bilan zigzag chizig'i shaklini oladi, buning natijasida minimal darajaga tushish tezligi juda sekinlashadi. Bu, ushbu funktsiyalarning antigradientining yo'nalishi yo'nalishdan minimal nuqtaga sezilarli darajada og'ishi bilan izohlanadi, bu esa hisoblashda qo'shimcha kechikishga olib keladi. Natijada, algoritm hisoblash samaradorligini yo'qotadi. Gully funktsiyasi Gradient usuli ko'plab modifikatsiyalari bilan birga keng tarqalgan va samarali usul o'rganilayotgan ob'ektlarning optimalini izlash. Gradientli qidiruvning kamchiliklari (shuningdek, yuqorida muhokama qilingan usullar) uni ishlatishda faqat funktsiyaning mahalliy ekstremumini aniqlash mumkin. Boshqalarni topish uchun mahalliy ekstremallar boshqa boshlang'ich nuqtalardan qidirish kerak. Shuningdek, konvergentsiya tezligi gradient usullari gradient hisob-kitoblarining to'g'riligiga ham sezilarli darajada bog'liq. Odatda minimal nuqtalar yaqinida yoki chuqurlikdagi vaziyatda sodir bo'ladigan aniqlikni yo'qotish, odatda, gradient tushish jarayonining yaqinlashishini buzishi mumkin. Hisoblash usuli 1-qadam: Funksiya gradientini hisoblash uchun analitik ifodalarning ta’rifi (ramzli shaklda) 2-qadam: Dastlabki taxminiylikni o'rnating 3-qadam: Oxirgi qidiruv yo'nalishini tiklash uchun algoritmik protsedurani qayta boshlash zarurati aniqlanadi. Qayta ishga tushirish natijasida qidiruv yana eng tez tushish yo'nalishi bo'yicha amalga oshiriladi.
.
f(x[k]–a k f’(x[k]))
= f(x[k] – af"(x[k]))
.
j (a) = f(x[k]-af"(x[k]))
.
,
.
haqiqiy domendagi funktsiya argumentining qiymatlari (boshqariladigan parametrlar).koordinata o'qlariga proyeksiyalari funktsiyaning koordinatalarga nisbatan qisman hosilalari bo'lgan vektor:
sirtga qat’iy ortogonal bo’lib, uning yo’nalishi funksiyaning eng tez ortish yo’nalishini, teskari yo’nalishi (antigradient) esa mos ravishda funksiyaning eng tez kamayish yo’nalishini ko’rsatadi.
- gradient moduli funktsiyaning gradient yoki antigradient yo'nalishi bo'yicha o'sish yoki pasayish tezligini aniqlaydi:
