Chiziqsiz programmalashtirish masalalarini taqribiy yechish usullari

Chiziqsiz programmalashtirish masalalarini taqribiy yechish usullari Reja: Chiziqsiz programmalashtirish masalasining qo'yilishi Chiziqsiz tenglamalarni yechish uchun Nyuton usuli. Chiziqsiz tenglamalar sistemasini yechish uchun Nyuton usuli Chiziqsiz tenglamalar sistemasini yechish uchun iteratsiya usuli. Chiziqsiz tenglamalar sistemasini yechish uchun gradient usuli. Chiziqsiz tenglamalar sistemasini yechish uchun jarima funksiya usuli. Chiziqsiz tenglamalar sistemasini yechish uchun tasodifiy izlash usuli. Masalaning qo'yilishi. Chiziqsiz programmalashtirish masalalarining maqsad funksiyalari va cheklanish shartlarida qatnashadigan funksiyalar izlanayotgan nomalumlarning chiziqsiz funksiyalaridan iborat bo'ladi. Agar p o'zgaruvchiga bog'liq bo'lgan birorta funksiyaning cheklanish tenglamalari yokitengsizliklari sistemasini qanoatlantiradigan minimumni topish talab qilingan bo'lsa, bu shartli minimallash masalasi Lagranjning aniqmas ko'paytuvchilar usuli yordamida shartsiz minimallash masalasiga keltiriladi. Bu funksiyaning minimumi mavjudligining 1-tartibli zaruriy (statsionarlik) sharti quyidagicha bo'ladi: (1) Berilgan funksiyaga minimum beruvchi statsionar (kritik) nuqtalar (1) tenglamaning yechimlaridan iborat bo'ladi. funksiya p o'zgaruvchiga bog'liq chiziqsiz funksiya bo'lganligidan (1) tenglamaning yechimlarini topish ancha murakkab masalalardan biri bo'lib, uni yechish uchun hozirgacha yagona usul mavjud emas. Bu tenglamalarning ko'rinishiga qarab, uni yechish uchun har xil taqribiy usullar qo'llaniladi. Masalan, funksiyaning aniqlanish sohasidan nuqta tanlab olinib, bu nuqtada funksiyaning qiymati hisoblanadi. nuqta funksiyaga minimum beruvchi nuqtaning nolinchi qadami deyiladi. nuqta funksiyaga minimum beruvchi nuqta uchun dastlabki taqribiy nuqta bo'lib, nuqtaga yaqinroq bo'lgan taqribiy nuqtaga, yani 1-qadamga o'tish zarur. Bu o'tish ikki bosqichdan iborat bo'ladi: 1). nuqtaning nuqtaga o'tishdagi harakatyo'nalishi tanalanadi. 2). Shu yo'nalish bo'yicha qanday qadam bilan borish aniqlanadi. nuqtani tanlash umumiy holda quyidagi shartga bo'ysunishi kerak: 1-ta'rif. Funksiyaning minimumini yoki maksimumini topish algortmi, agar ga o'tish malum bir qoida (biror tasodifiy mexanizm) asosida amalga oshirilsa, determinallashgan (tasodifiy) algoritm deyiladi. Agar har bir ketma-ket yaqinlashishda faqat funksiyaning o'zi qatnashadigan bo'lsa, bunday determinallashgan algoritm - nolinchi, 1-tartibli hosila qatnashadigan bo'lsa - birinchi va … deyiladi. Agar birorta chiziqsiz programmalashtirish masalasi va uning biror taqribiy yechish usuli berilgan bo'lsa, «bu taqribiy yechish usulining aniq yechimga yaqinlashish tezligi qanday?» - degan savol tug'iladi. Bunga quyidagicha javob berish mumkin: Agar tengsizlikda bo'lsa, bu taqribiy yechish usulining yaqinlashish tezligi chiziqli, bo'lsa, kvadratik, bo'lsa, geometrik deyiladi. Nyuton usuli. nuqta funksiyaga minimum beruvchi nuqta bo'lishi uchun shu nuqtada berilgan funksiyaning gradienti nolga teng bo'lishi kerak, yani . Shunday qilib, funksiyaga minimum beruvchi nuqta mavjud bo'lsa, u nuqta tenglmalar ichidan topilar ekan.Faraz qilaylik, nuqta tenglamaning taqribiy yechimi bo'lsin. funksiyani nuqta atrofida Teylor qatoriga yoyamiz: (1) Bu yoyilmada 1-ikkita qushiluvchi bilan chegaralanib, quyidagi tenglamani hosil qilamiz Bundan quyidagi munosabatni hosil qilamiz: (2) Nyuton usuli (2) dan foydalanib, quyidagi rekurrent formula orqali (3) ketma-ketliklarni aniqlashdan iboratdir: bo'lgani uchun ...