Amaliy vazifalar

4.5.3. SHARTSIZ OPTIMALLASHTIRISH USULLARI

Yuqorida ko'rib chiqilgan barcha shakllarda ekstremumga erishish uchun zarur shart-sharoitlar chiziqli bo'lmagan tenglamalar tizimini echishga olib keladi - juda murakkab va ko'p vaqt talab qiladigan vazifa (hatto hisoblash matematikasida ham chiziqli bo'lmagan tenglamalarni hal qilish ko'pincha qandaydir turdagi tenglamalarga qisqartiriladi). optimallashtirish muammosi). Shuning uchun amalda funktsiyalarni optimallashtirishning boshqa yondashuvlari qo'llaniladi, ularni ko'rib chiqish to'g'ridan-to'g'ri usullar deb ataladigan usullardan boshlanadi. Kelajakda biz bu erda minimallashtirish haqida gapiramiz, shuning uchun ekstremum minimaldir.
Hozirgi vaqtda ham shartsiz, ham shartli optimallashtirish masalalari uchun ko'plab sonli usullar ishlab chiqilgan. Raqamli usulning sifati ko'pgina omillar bilan tavsiflanadi: yaqinlashish tezligi, bir iteratsiyaning bajarilish vaqti, usulni amalga oshirish uchun zarur bo'lgan kompyuter xotirasi hajmi, echilishi kerak bo'lgan masalalar sinfi va boshqalar. ham juda xilma-xildir: ular yuqori va past o'lchamlarga ega bo'lishi mumkin, unimodal va multiekstremal bo'lishi mumkin va hokazo. Bir turdagi muammolarni hal qilish uchun samarali bo'lgan bir xil usul boshqa turdagi masalalar uchun mutlaqo nomaqbul bo'lishi mumkin.
Quyida nochiziqli dasturlash masalalarini yechishning asosiy usullari haqida umumiy ma’lumot berilgan. Shuni yodda tutish kerakki, bunday usullarning butun ro'yxati juda keng va ochiq qolmoqda. Bundan tashqari, ko'rib chiqilgan bir qator usullar uchun turli xil modifikatsiyalar ma'lum. Batafsil ma'lumotni quyidagi manzildan olishingiz mumkin -
РЕКЛАМА•18+
misol, ichida.
Cheklovlar mavjud bo'lmaganda, cheklanmagan optimallashtirishning bevosita usullarini ko'rib chiqishdan boshlaylik.
Shartsiz optimallashtirishning to'g'ridan-to'g'ri usullarining ma'nosi X, X, ..., X nuqtalar ketma-ketligini qurishdir.
f (X )>f (X )>… …>f (X ). X ning boshlang'ich nuqtasi sifatida ixtiyoriy nuqta tanlanishi mumkin, ammo uni minimal nuqtaga iloji boricha yaqinroq tanlashga intiladi. X nuqtadan X nuqtaga o'tish (iteratsiya) , k =0,1,2,... ikki bosqichdan iborat:
– nuqtadan harakat yo'nalishini tanlash X;
– bu yo'nalish bo'yicha qadamni belgilash.
Bunday ketma-ketlikni yaratish usullari ko'pincha tushish usullari deb ataladi, chunki funktsiyaning katta qiymatlaridan kichikroq qiymatlarga o'tish amalga oshiriladi.
Matematik jihatdan tushish usullari munosabat bilan tavsiflanadi
X =X + a k p , k =0,1,2,...,
bu erda p - tushish yo'nalishini belgilovchi birlik vektor;
a k - qadam uzunligi.
Turli xil tushish usullari bir-biridan p va a k ni tanlash usuli bilan farqlanadi. Amalda faqat konvergentsiyaga ega usullar qo'llaniladi. Ular minimal nuqtani olish yoki unga etarlicha yaqinlashish uchun cheklangan miqdordagi qadamlarni bajarishga imkon beradi. Konvergent iterativ usullarning sifati yaqinlashish tezligi bilan baholanadi.
Nazariy jihatdan, tushish usullarida muammo cheksiz ko'p takrorlashda hal qilinadi. Amalda, iteratsiya jarayonini to'xtatishning muayyan mezonlari (shartlari) bajarilganda hisob-kitoblar to'xtatiladi. Misol uchun, bu kichik tabiatning holati bo'lishi mumkin

	dalil		X[ k] − X[ k − 1 ]

f(X[k]) − f(X[k−1])< γ
Minimal nuqtani topish usullari, agar X dan X ga o'tishning ikkala parametri (harakat yo'nalishi va qadam o'lchami) X nuqtada mavjud bo'lgan ma'lumotlarga ko'ra yagona tanlangan bo'lsa, deterministik deb ataladi. Agar o'tish jarayonida biron bir tasodifiy mexanizm qo'llanilsa, u holda qidiruv algoritmi tasodifiy minimal qidiruv deb ataladi.
Deterministik cheklanmagan minimallashtirish algoritmlari ishlatiladigan axborot turiga qarab sinflarga bo'linadi. Agar har bir iteratsiyada faqat minimallashtirilgan funksiyalarning qiymatlari ishlatilsa, u holda usul nol tartibli usul deb ataladi. Agar qo'shimcha ravishda minimallashtirilayotgan funktsiyaning birinchi hosilalarini hisoblash kerak bo'lsa, unda birinchi tartibli usullar mavjud,
agar kerak bo'lsa, ikkinchi hosilalarni qo'shimcha hisoblash - ikkinchi tartibli usullar.
Shuni ta'kidlash kerakki, cheksiz minimallashtirish masalalarini hal qilishda birinchi va ikkinchi tartibli usullar odatda nol tartibli usullarga qaraganda yuqoriroq yaqinlashish tezligiga ega. Biroq, amalda ko'p sonli o'zgaruvchilar funktsiyasining birinchi va ikkinchi hosilalarini hisoblash juda mashaqqatli. Ayrim hollarda ularni analitik funksiyalar shaklida olish mumkin emas. Hosilalar turli xil sonli usullar bilan aniqlanadi, bunday usullardan foydalanishni cheklashi mumkin bo'lgan xatolar. Bundan tashqari, optimallik mezonini aniq emas, balki tenglamalar tizimi bilan belgilash mumkin. Bunday holda, hosilalarni analitik yoki son yo'l bilan topish juda qiyin, ba'zan esa imkonsiz bo'ladi. Shuning uchun bu erda nol tartibli usullar eng batafsil ko'rib chiqiladi.
Bir o'lchovli qidiruv usullari. Bir o'lchovli qidiruv usullari ro'yxati - bitta argument funktsiyasining ekstremumini raqamli qidirish f(x ) ancha keng va adabiyotda yaxshi yoritilgan. Shuning uchun, biz bu erda faqat bitta usulni ko'rib chiqish bilan cheklanamiz, mualliflarning tajribasiga ko'ra, eng samarali usullardan biri, "oltin qism" usuli.
Usulning g'oyasi noaniqlik oralig'ini - kerakli minimal nuqtani o'z ichiga olgan x argumentining qiymatlari oralig'ini - dan oshmaydigan uzunlikka doimiy ravishda kamaytirishdir.
ruxsat etilgan natija xatosi e. Boshlang'ich interval sifatida, muammoning shartlari bilan belgilanadigan argument qiymatlarining ruxsat etilgan diapazoni yoki agar chap va (yoki) o'ng chegaralar bo'lmasa, ruxsat etilgan chegara ichidagi ba'zi bir maydon. kerakli minimum dastlabki tahlil bilan ko'rsatiladi, ko'rib chiqilishi mumkin.
Har qanday oraliq ichida ikkita teng bo'lmagan ikki qismga bo'linadigan x = y 0 va x = z 0 nuqtalari mavjud bo'lib, uning "oltin qismi" ni bajaradi, shunda katta qismning butun oraliq uzunligiga nisbati nisbati bilan mos keladi. kichikroq qismdan kattasiga. Shubhasiz, bu nuqtalar intervalning markaziga nisbatan simmetrik joylashgan (26-rasm). "Oltin qism" nuqtalarining koordinatalarini tegishli nisbatlardan topish mumkin:

b − y0		y0 − a	= δ ,	z0 − a		b − z0	= δ,

bu yerdan d = (1–d)/d ni olish oson va tenglamaga keling: d 2 + d –1=0. Natijada, biz intervalning "oltin qismi" ni aniqlaydigan nisbiy ulushlarni olamiz: d = 0,618, 1-d = 0,382. “Oltin kesim” muhim xususiyatga ega: y 0 nuqtasi intervalning “oltin kesimi” nuqtalaridan biri, z 0 nuqtasi intervalning “oltin kesimi” nuqtalaridan biridir. Bu o'ldirishda
Oddiy hisob-kitob kutmoqda: 0,382 / 0,618 = 0,618 va (0,618-0,382) / 0,618 = = 0,382.
"Oltin qism" usuli asosida qurilgan minimal qidiruv algoritmi har bir iteratsiyada "oltin qism" ning chap yoki o'ng nuqtasini qisqartirilgan intervalning chegaralaridan biri sifatida tanlashni ta'minlaydi. uning ichida kerakli minimal saqlanadi:
1. k =0 o'rnating, dastlabki noaniqlik oralig'i , ruxsat etilgan natija xatosi e .
2. "Oltin qism" nuqtalarining koordinatalarini hisoblang:
y k \u003d a k +0,382 (b k - a k), z k \u003d a k +0,618 (b k - a k).
3. Topilgan nuqtalarda maqsad funksiyasining qiymatlarini hisoblang
f (y k ) va f (z k ).
4. Agar f (yk) ≤ f (zk) bo‘lsa (26-rasm, lekin), ak + 1 =ak, bk + 1 =zk, zk + 1 =yk, yk + 1 =ak +zk –yk, k ni belgilang. =k+1. Aks holda (26-rasm, b) a k + 1 =y k, b k + 1 = b k, y k + 1 = z k, z k + 1 = y k + b k –z k, k = k +1.
5. Qidiruvni yakunlash shartining bajarilishini tekshiring
b k + 1 - a k + 1 ≤ e. Agar u bajarilsa, yechim sifatida x = (y k + 1 + z k + 1 ) 2 nuqta tanlanadi. Aks holda, 2-bosqichga o'ting.
"Oltin kesim" usulining hisoblash samaradorligi shundan iboratki, bu erda har bir iteratsiyada faqat bitta maqsad funktsiyasi qiymatini hisoblash talab qilinadi.
To'g'ridan-to'g'ri qidirish usuli (Huk-Jeves usuli). Biroz
ikkinchi boshlanish nuqtasi X. X vektorining komponentlarini muqobil ravishda o'zgartirib, ular ushbu nuqtaning qo'shniligini tekshiradilar, natijada ular minimallashtirilgan f (X) funktsiyaning kamayish yo'nalishini aniqlaydigan nuqtani (yangi asos) topadilar. Tushilish funksiya qiymatining kamayishiga ishonch hosil qilib, tanlangan yo'nalishda amalga oshiriladi. Qabul qilingan to'xtash holatini hisobga olgan holda, tushish yo'nalishini topish mumkin bo'lgunga qadar protsedura tsiklik takrorlanadi.
РЕКЛАМА
To'g'ridan-to'g'ri qidirish usulining algoritmi eng umumiy shaklda quyidagicha ifodalanishi mumkin:
1. X i , i= 1,2,…n koordinatalarining qiymatlari, boshlang'ich nuqtasi (k = 0), koordinatalarning dastlabki o'sish vektori bo'yicha o'rnatiladi.
∆ X = (∆ x 1 , ∆ x 2 ,…, ∆ xn ) mahallani oʻrganish jarayonida e komponentining ruxsat etilgan eng kichik qiymati ∆ X , tushish tezligini belgilovchi tezlashtiruvchi omil l ≥ 1, masshtab koeffitsienti d>1.
2. "Eski asos" uchun X ni oling: X b \u003d X. Hisoblash
f (X b) qiymati.
3. Har bir koordinatani navbat bilan o'zgartiring x b i, i = 1,2, ... n,
X b nuqtalarini ∆ x i qiymati bo'yicha, ya'ni x i \u003d x b i + ∆ x i ni oling, keyin
x i \u003d x b i -∆ x i. Olingan test nuqtalarida f (X ) qiymatlarini hisoblang va ularni f (X b ) qiymati bilan solishtiring. Agar f(X)< < f (X б ), то соответствующая координата х i приобретает новое значение, вычисленное по одному из приведенных выражений. В противном случае значение этой координаты остается неизменным. Если после изменения последней n -й координаты f (X )<="" p="" >
4. Ular ikkinchisi orqali "eski" dan "yangi" asosga yo'nalishda tushadilar, ya'ni yangi nuqtaning koordinatalarini hisoblashadi.
X: x i \u003d x i + l (x i - x bi), i \u003d 1,2, ... n. f(X) ning qiymatini hisoblang. Agar f (X ) sharti<="" p="" >
"Yangi" asos "eski" sifatida qabul qilinadi (X b \u003d X, f (X b) \u003d f (X)) va 5-bosqichga o'ting. Aks holda, ular xi \u003d xi, i \u003d ni oladi. 1.2, ... n.

5. 3-bandda bo'lgani kabi, nuqtaning har bir koordinatasini navbat bilan o'zgartiring f (X) funktsiyasining mos qiymatlarini 4-bosqichda olingan f (X) qiymati bilan solishtirish orqali X. Oxirgi koordinatani o'zgartirgandan so'ng, mos keladigan qiymatni solishtiring.
4-bosqichda olingan f (X b ) qiymatiga ega f (X ) funksiyalari. Agar f (X )<="" p="" >
6. Agar hamma uchun i ∆ x i<ε , вычисления прекращаются. В противном случае уменьшают значения ∆ х i в d раз и переходят к п. 3.
Algoritmning ishlashi rasmda ko'rsatilgan. 27. Chiziqlar ko'rsatilgan
minimallashtirilgan f (x 1 ,x 2 ) funksiya darajasi, ya’ni f (x 1 ,x 2 )=f 1 =const, f (x 1 ,x 2 )=f 2 =const va shartlardan olingan chiziqlar. shuning uchun Keyinchalik. Bu yerda f 1 >f 2 >f 3 . Qattiq chiziqlar - qadamlarning bir marta bajarilishining natijalari. 3...5 (funktsiyani pasaytirish yo'nalishini qidiring va pastga tushing), nuqta chiziq keyingi pasayishdir.
To'g'ridan-to'g'ri qidirish usulining afzalligi - uni kompyuterda dasturlashning soddaligi. Bu maqsad funktsiyasini aniq bilishni talab qilmaydi, shuningdek, alohida o'zgaruvchilar bo'yicha cheklovlarni, shuningdek, qidiruv doirasidagi murakkab cheklovlarni osongina hisobga oladi.

To'g'ridan-to'g'ri qidirish usulining kamchiligi shundaki, juda cho'zilgan, egri yoki o'tkir burchakli maqsad funksiyasi darajasidagi chiziqlarda tahlil qilinadigan yo'nalishlarning cheklangan soni tufayli minimal nuqtaga progressni ta'minlay olmaydi.
Deformatsiyalanadigan ko'pburchak usuli (Nelder-Mead usuli) Bu funktsiyani minimallashtirish uchun n o‘lchamli f(X) o‘zgaruvchilari makon, o'z ichiga olgan ko'pburchak qurilgan n +1 yuqori. Shubhasiz, har bir cho'qqi qandaydir vektorga mos keladi Xi . Maqsad funksiyasi qiymatlarini hisoblang f(Xi ), i=1,2,…, n +1, ko'pburchakning har bir cho'qqisida ushbu qiymatlarning maksimalini va mos keladigan cho'qqini aniqlang xh . Ushbu cho'qqi va qolgan cho'qqilarning og'irlik markazi orqali nuqta joylashgan proyeksiya chizig'i o'tkaziladi. xq maqsad funktsiyasining yuqori qismiga qaraganda kichikroq qiymati bilan Xh (28-rasm, a ). Keyin tepalikni olib tashlang xh . Qolgan cho'qqilar va nuqtalardan xq tasvirlangan protsedura takrorlanadigan yangi ko'pburchakni qurish. Bunday operatsiyalarni bajarish jarayonida poliedr o'zining o'lchamlarini o'zgartiradi, bu esa usulning nomiga olib keldi.
Quyidagi yozuvni kiritamiz: X - ko'pburchakning i-cho'qqisining k-qidiruv bosqichidagi koordinata vektori, i= 1,2,…n +1, k= 1,2,…; h - maqsadning qiymati bo'lgan tepaning soni
X dan tashqari shinalar. Og'irlik markazining koordinatalari hisoblanadi

	xj[n + 2, k] =		n+1
formula			∑ xj[i, k] − xj[h, k]		J= 1,2,…n.

РЕКЛАМА
Deformatsiyalanuvchi ko‘pburchak usulining namunaviy algoritmi quyidagicha:
1. Ko'zgu koeffitsientlari bilan belgilanadi a , kuchlanishlar g >1, siqilishlar b<1 , допустимой погрешностью определения координат
minimal e ball. Dastlabki ko‘pburchak X , i= 1,2,…n +1, k= 1 cho‘qqilarining koordinatalarini tanlang.
2. Maqsad funktsiyasi qiymatlarini barcha cho'qqilarda hisoblang f (X ), i = 1,2,…n +1 va X , X nuqtalarni toping (28-rasmda b, mos ravishda X 2 va X 1 nuqtalari), shuningdek X .
3. Nuqtani loyihalash markazi orqali X
qalay: X \u003d X + a (X -X).
4. Agar f (X) ≤ X bo'lsa, cho'zish operatsiyasini bajaring
ion: X \u003d X + g (X -X). Aks holda, 6-bosqichga o'ting.
5. Yangi ko'pburchak yarating: agar f(X)<="" p="" >
X ni X bilan almashtirish orqali, aks holda X ni X bilan almashtirish orqali. k =k +1 uchun 2-band bilan hisob-kitoblarni davom ettiring.
6. Barcha i uchun X >f (X )>X h ga teng bo‘lmasa,
siqish amalini bajaring: X =X +b (X – X). X ni X bilan almashtirib, yangi ko'pburchak tuzing va k =k +1 uchun 2-bosqichdan boshlab hisoblarni davom ettiring.
7. Agar f (X)>X bo'lsa, X cho'qqisini saqlab, barcha qirralarning uzunligini yarmiga qisqartirish orqali hozirgiga o'xshash yangi ko'pburchak quring: X \u003d X +0,5 (X -X) va k=k+1 uchun 2-bosqichdan boshlab hisoblarni davom ettiring.
pp.da. 6, 7, 2-bosqichga o'tishdan oldin, minimal qidiruvni yakunlash shartining bajarilishini tekshirish kerak, masalan, shartga muvofiq

max n ∑ + 1 (x j [ i ,k ] − x j [ n + 2,k ] ) 2< ε 2 .
i j = 1
BILAN Cho`zish va kichraytirish amallari yordamida deformatsiyalanuvchi ko`pburchakning o`lchamlari va shakli maqsad funksiya topografiyasiga moslashtiriladi. Natijada, ko'pburchak uzun qiya yuzalar bo'ylab cho'ziladi, egri chuqurliklarda yo'nalishini o'zgartiradi va minimal yaqinida qisqaradi, bu ko'rib chiqilayotgan usulning samaradorligini belgilaydi.
a =1, 2≤ g ≤3, 0,4≤b ≤0,6.
Koordinatalarni aylantirish usuli (Rozenbrok usuli). Uning mohiyati maqsad funktsiyasining eng tez kamayish yo'nalishining o'zgarishiga muvofiq koordinata tizimining ketma-ket aylanishidan iborat (29-rasm). Boshlanish nuqtasidan X nuqtaga tushish X koordinata o'qlariga parallel yo'nalishlarda. Keyingi iteratsiyada o'qlardan biri yo'nalishda o'tishi kerak x'1 = X–X, qolganlari perpendikulyar yo'nalishlarda x'1 . Ushbu o'qlar bo'ylab tushish nuqtaga olib keladi X , bu yangi vektorni qurish imkonini beradi x''1 = X–X va uning asosida yangi tizim yo'nalishlarni qidirish