Ishonch zonasi

Ishonch zonasi – bu ishonch oraligʻi tushunchasini raqamli funktsiya yordamida yaqinlashuvchi maqsad funktsiyasining koʻp oʻzgaruvchan parametri. Holatiga umumlashtirish koʻpincha kvadratik boʻladi: agar ishonch mintaqasi ichidagi maqsadli funktsiyalarning aniqligiga mos keladigan raqamli funktsiya topilsa, u holda mintaqa kengayadi. Agar yaqinlashish aniqligi past boʻlsa, mintaqa aksincha torayadi. Aniqlik odatda ishonch mintaqasining kengligi sifatida tushuntiriladi.

Ishonch sohasi usuli bir bosqichli usul sifatida ham tanilgan. Qaysidir maʼnoda, bu chiziqli qidirish usuli bilan ikki tomonlama – ishonch maydoni usulida avval qadam oʻlchamini (ishonch maydoni oʻlchamini), soʻngra uning yoʻnalishini, chiziqli qidirish usulida birinchi qadam yoʻnalishini, soʻngra uning hajmini tanlang.

Tegishli oʻlcham raqamli funktsiyadan kutilgan yaxshilanish nisbati va maqsad funktsiyasini hisoblash natijasida olingan haqiqiy yaxshilanish nisbatini taqqoslagandan soʻng hisoblanadi;

Kengayish yoki qisqarish mezoni sifatida oddiy printsip qoʻllanadi, bunda raqamli funktsiya faqat maqbul yaqinlikni taʼminlaydigan mintaqada gina ishonchli boʻla oladi.

Misol

Kontseptual ravishda, Levenberg – Markvardt algoritmida maqsad funktsiyasi ikkinchi darajali sirt bilan iterativ ravishda yaqinlashadi, soʻngra tegishli chiziqli tenglamalar tizimi echiladi va baholash yangilanadi, shundan soʻng tsikl kerakli taxminiy aniqlikka erishilgunga qadar takrorlanadi. Agar siz faqat ushbu algoritmdan foydalansangiz va dastlabki taxmin optimal echimdan „juda uzoq“ boʻlsa, unda usul kerakli taxminiy aniqlikka yaqinlashmasligi mumkin. Shu sababli, algoritm har bir qadamni cheklaydi va juda „uzoq“ yaqinlashishni oldini oladi. Algoritm „juda uzoq“ ni quyidagicha belgilaydi. Yechim oʻrniga $A\,\Delta x=b$ ga nisbatan $\Delta x$ usul hal qilishni taklif qiladi. ${\big (}A+\lambda \operatorname {diag} (A){\big )}\,\Delta x=b$, Qayerda $\operatorname {diag} (A)$ A matritsasi bilan bir xil diagonali diagonal matritsa va $\lambda$ ishonch mintaqasi hajmini nazorat qiluvchi parametr hioblanadi. Geometrik tarafdan, usul markazlashtirilgan paraboloidni qoʻshadi $\Delta x=0$, bu har bir iteratsiya uchun kichikroq qadam hajmiga olib kelishi mumkin.

Buning maʼnosi ishonch maydonining hajmini oʻzgartirish hisoblanadi ($\lambda$). Har bir iteratsiyada kvadratik yaqinlashish maqsad funksiyasining pasayishini bashorat qiladi $\Delta f_{p}$ (bu yerda va pastda $f_{p}$ yaqinlashtirish orqali olingan qiymatni bildiradi va $f_{a}$ funktsiyaning haqiqiy qiymatini ifodalaydi), bu haqiqiy pasayishdan kamroq boʻlishi mumkin. Agar bizga $\Delta x$ maʼnosi berilsa buni hisoblashimiz mumkin

$\Delta f_{a}=f(x)-f(x+\Delta x).$

Nisbatni hisoblagandan soʻngra biz $\Delta f_{p}/\Delta f_{a}$ ishonch mintaqasining hajmini oʻzgartirishimiz mumkin. Umuman olganda,$\Delta f_{a}$, $\Delta f_{p}$ dan biroz kamroq boʻlishi mumkin, shuning uchun ham nisbat 0,25 dan 0,5 gacha boʻladi. Agar nisbat 0,5 dan katta boʻlsa, unda qilingan qadam juda katta, shuning uchun ishonch mintaqasini kengaytirish kerak (kamaytirish 𝜆) va takrorlashni davom ettiring. Agar nisbat 0,25 dan kam boʻlsa, u holatda haqiqiy funktsiya ishonch mintaqasidagi yaqinlashuvdan „juda koʻp“ farq qiladi, yaʼni ishonch mintaqasini kamaytirish kerak (oʻsish 𝜆) va takrorlashni davom ettiring.

Adabiyot

• . 
• Byrd R. H, Schnabel R. B., Schultz G. A. A trust region algorithm for nonlinearly constrained optimization // SIAM J. Numer. Anal.,. — 1987. — Т. 24. — С. 1152–1170.
• Sorensen D. C. Newton’s Method with a Model Trust Region Modification // SIAM J. Numer. Anal.. — 1982. — Т. 19, № 2.
• . 
• Yuan Y. Recent Advances in Trust Region Algorithms // Math. Program.. — 2015.