روش شبه-نیوتن (Quasi-Newton Methods)، در ریاضیات (Mathematics)
انواع روش های عددی (Numerical Methods) را در آموزش زیر شرح دادیم :
روش شبه-نیوتن (Quasi-Newton Methods) :
توضیح ساده: روش های شبه-نیوتن خانواده ای از روش ها هستند که برای حل دستگاه های غیرخطی و مسائل بهینه سازی طراحی شده اند. ایده اصلی این است که به جای محاسبه دقیق ماتریس ژاکوبی (یا ماتریس هسین در بهینه سازی) در هر تکرار، یک تقریب از آن را نگه می داریم و با استفاده از اطلاعات تکرارها، آن را به روز می کنیم. این کار هزینه محاسباتی را کاهش می دهد، در حالی که سرعت همگرایی هنوز خوب است (ابرخطی).
شرح گام به گام: در بهینه سازی، به دنبال کمینه تابع f(x) هستیم. روش نیوتن نیاز به ماتریس هسین ∇²f دارد. در روش های شبه-نیوتن، یک ماتریس Bₖ (تقریب هسین) را به روز می کنیم. معروف ترین فرمول های به روزرسانی عبارتند از:
- DFP (Davidon-Fletcher-Powell)
- BFGS (Broyden-Fletcher-Goldfarb-Shanno) که محبوب ترین است.
- SR1 (Symmetric Rank-One)
در هر تکرار، با حل Bₖ pₖ = -∇f(xₖ)، جهت جستجو pₖ را پیدا می کنیم. سپس با یک جستجوی خطی، گام αₖ را تعیین کرده و xₖ₊₁ = xₖ + αₖ pₖ را به روز می کنیم. سپس با استفاده از تغییرات x و گرادیان، ماتریس Bₖ₊₁ را به روز می کنیم به طوری که شرط سکانت (Secant Equation) را ارضا کند.
مثال (روش BFGS): فرمول به روزرسانی BFGS:
\[ B_{k+1} = B_k - \frac{B_k s_k s_k^T B_k}{s_k^T B_k s_k} + \frac{y_k y_k^T}{y_k^T s_k} \]که در آن sₖ = xₖ₊₁ - xₖ و yₖ = ∇f(xₖ₊₁) - ∇f(xₖ). این فرمول تضمین می کند که اگر Bₖ متقارن و مثبت معین باشد، Bₖ₊₁ نیز همین خاصیت را داشته باشد.
مزایا: هزینه کمتر از نیوتن (بدون نیاز به محاسبه مشتقات دوم)، همگرایی ابرخطی، مناسب برای مسائل بزرگ.
معایب: کندتر از نیوتن در نزدیکی جواب، نیاز به حافظه برای ذخیره ماتریس (برای مسائل بسیار بزرگ، نسخه محدودشده L-BFGS استفاده می شود).
کاربردها: استانداردترین روش ها در بهینه سازی غیرخطی، در یادگیری ماشین، در آموزش شبکه های عصبی، در مسائل مهندسی.
نکته: روش BFGS یکی از موفق ترین الگوریتم های بهینه سازی است و در اکثر کتابخانه های بهینه سازی پیاده سازی شده است.
