|
Muhammad al‑xorazmiy nomidagi toshkent axborot texnologiyalari universiteti
|
| bet | 4/11 | | Sana | 05.06.2024 | | Hajmi | 249,42 Kb. | | #260638 |
Bog'liq pbcTjQw8uRMUDHAn PArOWXTeagvh3-g fmincon Faol to'plam algoritmi Kirish
Cheklangan optimallashtirishda umumiy maqsad muammoni keyinchalik hal qilinishi va iterativ jarayonning asosi sifatida ishlatilishi mumkin bo'lgan osonroq kichik muammoga aylantirishdir. Dastlabki usullarning katta sinfiga xos xususiyat cheklash chegarasiga yaqin yoki undan tashqarida bo'lgan cheklovlar uchun jarima funksiyasidan foydalanib, cheklangan muammoni asosiy cheklanmagan masalaga tarjima qilishdir. Shu tarzda chegaralangan masala chegaralangan (ketma-ketlik) chegaralangan masalaga yaqinlashuvchi parametrlangan cheklanmagan optimallashtirishlar ketma-ketligi yordamida hal qilinadi. Ushbu usullar endi nisbatan samarasiz deb hisoblanadi va ularning o'rnini muammoni hal qilishga qaratilgan usullar egalladiKarush-Kun-Taker (KKT) tenglamalari. KKT tenglamalari cheklangan optimallashtirish muammosi uchun optimallik uchun zarur shartlardir. Muammo deb ataladigan bo'lsaqavariq dasturlash masalasi, ya'ni f ( x ) va G i ( x ), i = 1,..., m , qavariq funksiyalar bo'lsa, KKT tenglamalari global yechim nuqtasi uchun ham zarur, ham etarli.
GP ( 1-tenglama ) ga ishora qilib , Kuhn-Tucker tenglamalari quyidagicha ifodalanishi mumkin.
∇ f(x∗)+m∑i = 1li⋅ ∇Gi(x∗)li⋅Gi(x∗)li= 0= 0 , i = 1 , ... , mBu≥ 0 , i = mBu+ 1 , ... , m ,
|
(12)
|
1-tenglamadagi dastlabki cheklovlarga qo'shimcha ravishda .
Birinchi tenglama maqsad funktsiyasi va yechim nuqtasidagi faol cheklovlar o'rtasidagi gradientlarning bekor qilinishini tavsiflaydi. Bekor qilinadigan gradientlar uchun Lagrange ko'paytmalari ( l i , i = 1,..., m ) maqsad funktsiyasi va cheklash gradientlari kattaligidagi og'ishlarni muvozanatlash uchun zarur. Ushbu bekor qilish operatsiyasiga faqat faol cheklovlar kiritilganligi sababli, faol bo'lmagan cheklovlar ushbu operatsiyaga kiritilmasligi kerak va shuning uchun 0 ga teng Lagrange ko'paytmalari beriladi. Bu oxirgi ikki Kuhn-Tucker tenglamalarida aniq ko'rsatilgan.
KKT tenglamalarini echish ko'plab chiziqli bo'lmagan dasturlash algoritmlariga asos bo'ladi. Ushbu algoritmlar to'g'ridan-to'g'ri Lagrange multiplikatorlarini hisoblashga harakat qiladi. Cheklangan kvazi-Nyuton usullari kvazi-Nyuton yangilash protsedurasidan foydalangan holda KKT tenglamalari bo'yicha ikkinchi darajali ma'lumotlarni to'plash orqali superchiziqli yaqinlashuvni kafolatlaydi. Ushbu usullar odatda ketma-ket kvadratik dasturlash (SQP) usullari deb ataladi, chunki QP kichik muammosi har bir asosiy iteratsiyada hal qilinadi (shuningdek, iterativ kvadratik dasturlash, rekursiv kvadratik dasturlash va cheklangan o'zgaruvchan metrik usullar sifatida ham tanilgan).
Algoritm 'active-set'katta hajmli algoritm emas; Katta o'lchamli va o'rta miqyosli algoritmlarga qarang .
|
| |
