Usul eng keskin tushish(ingliz adabiyotida "eng tik tushish usuli") - bu optimallashtirish muammolarini hal qilish uchun takrorlanuvchi raqamli usul (birinchi tartib), bu sizga maqsad funktsiyasining ekstremumini (minimal yoki maksimal) aniqlash imkonini beradi:
haqiqiy domendagi funktsiya argumentining qiymatlari (boshqariladigan parametrlar).
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 koordinata o'qlariga proyeksiyalari funktsiyaning koordinatalarga nisbatan qisman hosilalari bo'lgan vektor:
bu yerda i, j,…, n koordinata o‘qlariga parallel bo‘lgan birlik vektorlar.
Asosiy nuqtada gradient 
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.
Eng keskin tushish usuli yanada rivojlantirish gradient tushish usuli. IN umumiy holat 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:
- gradient moduli funktsiyaning gradient yoki antigradient yo'nalishi bo'yicha o'sish yoki pasayish tezligini aniqlaydi:
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 depressiya 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 sezilarli darajada 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, uning ko'plab modifikatsiyalari bilan birga, keng tarqalgan va samarali usul o'rganilayotgan ob'ektlarning optimalini izlash. Gradient qidiruvining kamchiliklari (shuningdek, yuqorida muhokama qilingan usullar) uni ishlatishda faqat funktsiyaning mahalliy ekstremumini aniqlash mumkin. Boshqalarni topish uchun mahalliy ekstremallar boshqa boshlang'ich nuqtalardan izlash kerak. Shuningdek, gradient usullarining yaqinlashuv tezligi ham gradient hisoblarining to'g'riligiga 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.
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). Qadam gradient usuli ko'pincha boshqa optimallashtirish usullarining bir qismi sifatida ishlatiladi, masalan, Fletcher-Reeves usuli.
Tavsif [ | ]
Yaxshilanishlar[ | ]
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. 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.
Funksiyani kiritish qoidalari
IN eng keskin tushish usuli▽f(x) funksiyaning gradient vektorining yo‘nalishiga qarama-qarshi bo‘lgan vektor qidiruv yo‘nalishi sifatida tanlanadi. Kimdan matematik tahlil ma'lumki, grad f(x)=▽f(x) vektori funksiyaning eng tez o'sish yo'nalishini xarakterlaydi (funksiya gradientiga qarang). Shuning uchun vektor - grad f (X) = -▽f(X) deyiladi gradientga qarshi va uning eng tez pasayish yo'nalishi. Eng keskin pasayish usuli amalga oshiriladigan takrorlanish munosabati X k +1 =X k - l k ▽f(x k), k = 0,1,..., ko'rinishga ega.
bu yerda l k >0 - qadam kattaligi. Qadam o'lchamini tanlashga qarab, siz olishingiz mumkin turli xil variantlar gradient usuli. Agar optimallashtirish jarayonida qadam o'lchami l aniqlangan bo'lsa, u holda usul diskret qadamli gradient usuli deb ataladi. Agar l k =min f(X k + lS k) shartidan l k tanlansa, birinchi iteratsiyalarda optimallashtirish jarayoni sezilarli darajada tezlashishi mumkin.
l k ni aniqlash uchun har qanday bir o'lchovli optimallashtirish usuli qo'llaniladi. Bunday holda, usul eng tik tushish usuli deb ataladi. Qoida tariqasida, umumiy holatda, funktsiyaning minimaliga erishish uchun bir qadam etarli emas, jarayon keyingi hisob-kitoblar natijani yaxshilamaguncha takrorlanadi;
Agar ba'zi o'zgaruvchilarda bo'shliq juda cho'zilgan bo'lsa, unda "jarlik" hosil bo'ladi. Qidiruv sekinlashishi va "jarlik" tubida zigzag bo'lishi mumkin. Ba'zida maqbul vaqt oralig'ida yechim olinmaydi.
Usulning yana bir kamchiligi to'xtash mezoni bo'lishi mumkin ||▽f(X k)||<ε k , так как этому условию удовлетворяет и седловая точка, а не только оптимум.
Misol. X k =(-2, 3) nuqtadan boshlab, funktsiyani minimallashtirish uchun eng tik tushish usuli yordamida x k +1 nuqtasini aniqlang.
Qidiruv yo'nalishi sifatida joriy nuqtada gradient vektorini tanlang 
Keling, to'xtash mezonini tekshiramiz. Bizda ... bor 
Funksiyaning f(X 1) = 35 boshlang‘ich nuqtasidagi qiymatini hisoblab chiqamiz.
antigradient yo'nalishi bo'ylab qadam tashlang
Funksiya qiymatini yangi nuqtada hisoblaymiz
f(X 2) = 3(-2 + 19l 1) 2 + (3-8l 1) 2 - (-2 + 19l 1)(3-8l 1) - 4(-2 + 19l 1)
Maqsad funksiyasi shu yo'nalish bo'ylab minimal darajaga yetadigan qadam topamiz. Funksiya ekstremumining mavjudligi uchun zaruriy shartdan
f’(X 2) = 6(-2 + 19l 1) 19 + 2(3-8l 1)(-8) – (73 - 304 l 1) – 4*19
yoki f’(X 2) = 2598 l 1 – 425 = 0.
Biz l 1 = 0,164 qadamni olamiz
Ushbu bosqichni bajarish nuqtaga olib keladi 
unda gradient qiymati 
, funktsiya qiymati f(X 2) = 0,23. Biz antigradient yo'nalishi bo'ylab qadam tashlaganimizdan boshlab, aniqlikka erishilmaydi.
f(X 2) = 3(1,116 – 1,008l 1) 2 + (1,688-2,26l 1) 2 - (1,116 – 1,008l 1)(1,688-2,26l 1) - 4(1,118 – 1,010)
f’(X 2) = 11,76 – 6,12l 1 = 0
Biz l 1 = 0,52 ni olamiz 
Izoh: Ushbu ma'ruza eng tik tushish usuli va Devidon-Fletcher-Pauell usuli kabi ko'p parametrli optimallashtirish usullarini keng qamrab oladi. Bundan tashqari, eng samaralisini aniqlash uchun yuqoridagi usullarning qiyosiy tahlili o'tkaziladi, ularning afzalliklari va kamchiliklari aniqlanadi; va shuningdek, jar usuli va multiekstremal usul kabi ko'p o'lchovli optimallashtirish muammolarini ko'rib chiqadi.
1. Eng tik tushish usuli
Ushbu usulning mohiyati yuqorida aytib o'tilganlardan foydalanishdir koordinatali tushish usuli ma'lum bir nuqtadan eksalardan biriga parallel yo'nalishda ushbu yo'nalishdagi minimal nuqtagacha qidiruv amalga oshiriladi. Keyin qidiruv boshqa o'qga parallel yo'nalishda amalga oshiriladi va hokazo. Yo'nalishlar, albatta, belgilangan. Har bir bosqichda minimal nuqtani qidirish "eng yaxshi" yo'nalish bo'ylab amalga oshirilishi uchun ushbu usulni o'zgartirishga harakat qilish oqilona ko'rinadi. Qaysi yo'nalish "eng yaxshi" ekanligi aniq emas, lekin bu ma'lum gradient yo'nalishi funktsiyaning eng tez o'sish yo'nalishi. Shuning uchun teskari yo'nalish funktsiyaning eng tez kamayishi yo'nalishidir. Bu xususiyatni quyidagicha asoslash mumkin.
Faraz qilaylik, biz x nuqtadan keyingi x + hd nuqtaga o'tmoqdamiz, bu erda d - ma'lum bir yo'nalish va h - ma'lum uzunlikdagi qadam. Binobarin, harakat (x 1, x 2, ..., x n) nuqtadan nuqtagacha amalga oshiriladi. (x 1 + zx 1, x 2 + zx 2, ..., x n + zx n), Qayerda
Funktsiya qiymatlarining o'zgarishi munosabatlar bilan belgilanadi
| (1.3) |
Birinchi darajali zx i gacha, qisman hosilalar x nuqtada hisoblanadi. df funktsiyasi o'zgarishining eng katta qiymatini olish uchun (1.2) tenglamani qanoatlantiradigan d i yo'nalishlarini qanday tanlash kerak? Bu erda cheklov bilan maksimallashtirish muammosi paydo bo'ladi. Keling, Lagrange ko'paytmalari usulini qo'llaymiz, uning yordamida biz funktsiyani aniqlaymiz
Cheklovni (1.2) qoniqtiruvchi df qiymati funksiya bajarilganda maksimal darajaga etadi
Maksimal darajaga etadi. Uning hosilasi
Demak,
 |
(1.6) |
Keyin di ~ df/dx i va d yo'nalishi x nuqtada V/(x) yo'nalishiga parallel bo'ladi.
Shunday qilib, eng katta mahalliy o'sish berilgan kichik qadam uchun h funksiyasi d Vf(x) yoki g(x) ning yo nalishi bo lganda sodir bo ladi. Shuning uchun, eng tik tushish yo'nalishi - bu yo'nalish
Oddiyroq shaklda (1.3) tenglamani quyidagicha yozish mumkin:
Vf(x) va dx vektorlari orasidagi burchak qayerda. dx ning berilgan qiymati uchun dx ning yo'nalishi -Vf(x) yo'nalishiga to'g'ri kelishini tanlab, df ni minimallashtiramiz.
Izoh. Gradient yo'nalishi doimiy darajadagi chiziqning istalgan nuqtasiga perpendikulyar, chunki bu chiziq bo'ylab funktsiya doimiydir. Shunday qilib, agar (d 1, d 2, ..., d n) daraja chizig'i bo'ylab kichik qadam bo'lsa, u holda
Va shuning uchun
 |
(1.8) |
