روش نیوتن (Newton's Method for Optimization)، در ریاضیات (Mathematics)
انواع روش های عددی (Numerical Methods) را در آموزش زیر شرح دادیم :
روش نیوتن (Newton's Method for Optimization) :
\[ x_{k+1} = x_k - [\nabla^2 f(x_k)]^{-1} \nabla f(x_k) \]توضیح ساده: روش نیوتن برای بهینه سازی، تعمیم روش نیوتن برای ریشه یابی به مسائل بهینه سازی است. ایده اصلی این است که در هر گام، تابع هدف را با یک تقریب درجه دوم (با استفاده از بسط تیلور تا مرتبه دوم) جایگزین کنیم و کمینه این تقریب را به عنوان نقطه بعدی انتخاب کنیم. این روش همگرایی بسیار سریعی (درجه دوم) در نزدیکی جواب دارد، اما نیاز به محاسبه ماتریس هسین (مشتقات دوم) و حل یک دستگاه خطی در هر گام دارد.
شرح گام به گام: الگوریتم نیوتن برای بهینه سازی نامقید:
۱. نقطه شروع x₀ را انتخاب کنید.
۲. برای k = ۰,۱,۲,... تا همگرایی:
- گرادیان gₐ = ∇f(xₐ) و هسین Hₐ = ∇²f(xₐ) را محاسبه کنید.
- جهت نیوتن را با حل دستگاه خطی Hₐ dₐ = -gₐ بدست آورید.
- xₐ₊₁ = xₐ + dₐ را به روز کنید (یا با جستجوی خطی، xₐ₊₁ = xₐ + αₐ dₐ).
۳. اگر f به شدت محدب و نزدیک جواب باشد، همگرایی درجه دوم است.
۴. برای مسائل بزرگ، محاسبه هسین و حل دستگاه پرهزینه است. روش های شبه-نیوتن این مشکل را کاهش می دهند.
مثال عددی: تابع f(x) = x⁴ - 3x². مشتق اول: 4x³ - 6x، مشتق دوم: 12x² - 6. از نقطه x₀=2: g=4*8-12=32-12=20، H=48-6=42، d = -20/42 ≈ -0.476، x₁=1.524. از x₁: g=4*3.54-9.14=14.16-9.14=5.02، H=12*2.32-6=27.84-6=21.84، d=-5.02/21.84=-0.23، x₂=1.294. نزدیک به جواب x=1.225 (که از 4x²-6=0 می آید).
مزایا: همگرایی بسیار سریع (درجه دوم) در نزدیکی جواب.
معایب: نیاز به محاسبه هسین (پرهزینه)، ممکن است به نقاط زینی همگرا شود اگر هسین مثبت معین نباشد، برای مسائل بزرگ غیرعملی است.
کاربردها: در مسائل با ابعاد کوچک تا متوسط، در روش های درونیابی، در آمار (حداکثر درستنمایی).
نکته: روش نیوتن برای بهینه سازی معادل روش نیوتن برای یافتن ریشه گرادیان است.
