روش شبه-نیوتن (Quasi-Newton Methods for Optimization)، در ریاضیات (Mathematics)
انواع روش های عددی (Numerical Methods) را در آموزش زیر شرح دادیم :
روش شبه-نیوتن (Quasi-Newton Methods for Optimization) :
جایگزینی هسین با یک تقریب به روز شونده
توضیح ساده: روش های شبه-نیوتن خانواده ای از الگوریتم های بهینه سازی هستند که سعی می کنند مزایای روش نیوتن (همگرایی سریع) را بدون نیاز به محاسبه مستقیم ماتریس هسین (مشتقات دوم) داشته باشند. در این روش ها، یک تقریب از هسین (یا معکوس آن) با استفاده از اطلاعات گرادیان در تکرارهای متوالی به روز می شود. این روش ها همگرایی ابرخطی (Superlinear) دارند و برای مسائل با ابعاد متوسط تا بزرگ بسیار کارآمد هستند. معروف ترین آنها BFGS و DFP هستند.
شرح گام به گام: ساختار کلی روش های شبه-نیوتن:
۱. نقطه شروع x₀ و یک تقریب اولیه از هسین (معمولا ماتریس همانی I) انتخاب کنید.
۲. برای k = ۰,۱,۲,... تا همگرایی:
- جهت جستجو را با حل Bₐ dₐ = -gₐ (یا dₐ = -Hₐ gₐ اگر معکوس تقریب زده شود) بدست آورید.
- با جستجوی خطی، اندازه گام αₐ را یافته و xₐ₊₁ = xₐ + αₐ dₐ را به روز کنید.
- گرادیان جدید gₐ₊₁ را محاسبه کنید.
- sₐ = xₐ₊₁ - xₐ و yₐ = gₐ₊₁ - gₐ را محاسبه کنید.
- تقریب هسین (یا معکوس آن) را با فرمول به روزرسانی (مثلا BFGS) تصحیح کنید.
۳. فرمول به روزرسانی BFGS برای معکوس هسین (H ≈ B⁻¹):
\[ H_{k+1} = (I - \frac{s_k y_k^T}{y_k^T s_k}) H_k (I - \frac{y_k s_k^T}{y_k^T s_k}) + \frac{s_k s_k^T}{y_k^T s_k} \]مثال عددی: تابع f(x,y) = 100(y - x²)² + (1-x)² (تابع رزنباک). روش شبه-نیوتن (BFGS) با شروع از (-1,1) به سرعت به سمت دره حرکت می کند و در ۳۰-۴۰ تکرار به جواب (1,1) می رسد. روش گرادیان کاهشی ممکن است صدها تکرار نیاز داشته باشد.
مزایا: همگرایی سریع تر از گرادیان کاهشی، بدون نیاز به هسین تحلیلی، مناسب برای مسائل با ابعاد متوسط.
معایب: نیاز به ذخیره سازی ماتریس n×n (برای n بزرگ مشکل ساز است)، پیاده سازی پیچیده تر از گرادیان کاهشی.
کاربردها: در بهینه سازی مهندسی، در اقتصادسنجی، در یادگیری ماشین (برای مسائل با ابعاد متوسط).
نکته: روش BFGS به افتخار Broyden, Fletcher, Goldfarb, Shanno نامگذاری شده است.
