روش گرادیان مزدوج (Conjugate Gradient Method for Optimization)، در ریاضیات (Mathematics)
انواع روش های عددی (Numerical Methods) را در آموزش زیر شرح دادیم :
روش گرادیان مزدوج (Conjugate Gradient Method for Optimization) :
روشی برای بهینه سازی با استفاده از جهت های مزدوج
توضیح ساده: روش گرادیان مزدوج (CG) برای بهینه سازی، یک روش تکراری قدرتمند برای حل مسائل بهینه سازی، به ویژه برای توابع درجه دوم محدب است. این روش بین روش گرادیان کاهشی (که کند است) و روش نیوتن (که پرهزینه است) قرار می گیرد. ایده اصلی این است که جهت های جستجو به گونه ای انتخاب شوند که نسبت به ماتریس هسین (مشتقات دوم) مزدوج باشند. این خاصیت باعث می شود که برای توابع درجه دوم با n متغیر، روش در حداکثر n تکرار به جواب دقیق برسد. برای توابع غیرخطی، با بازنشانی (Restart) دوره ای استفاده می شود.
شرح گام به گام: الگوریتم گرادیان مزدوج برای بهینه سازی (نسخه فلچر-ریوز):
۱. نقطه شروع x₀ را انتخاب کنید. g₀ = ∇f(x₀)، d₀ = -g₀.
۲. برای k = ۰,۱,۲,... تا همگرایی:
- اندازه گام αₐ را با جستجوی خطی پیدا کنید (برای توابع درجه دوم، فرمول بسته دارد).
- xₐ₊₁ = xₐ + αₐ dₐ.
- gₐ₊₁ = ∇f(xₐ₊₁) را محاسبه کنید.
- βₐ₊₁ = (gₐ₊₁ᵀ gₐ₊₁) / (gₐᵀ gₐ) (فرمول فلچر-ریوز).
- dₐ₊₁ = -gₐ₊₁ + βₐ₊₁ dₐ.
۳. اگر k مضربی از n بود (مثلا هر n تکرار)، با d = -g بازنشانی کنید.
۴. معیار توقف: ||gₐ|| کوچک.
مثال عددی: تابع درجه دوم f(x) = ½ xᵀA x با A = [[3,1],[1,2]] و b = [5,5]ᵀ (که قبلا در روش CG برای حل دستگاه خطی دیدیم). از x₀=[0,0] شروع می کنیم. پس از ۲ تکرار (چون n=2)، به جواب دقیق [1,2] می رسیم. این نشان دهنده قدرت روش CG برای توابع درجه دوم است.
مزایا: حافظه کم (فقط چند بردار)، همگرایی سریع تر از گرادیان کاهشی، بدون نیاز به هسین.
معایب: برای توابع غیرخطی، نیاز به بازنشانی دارد و ممکن است کارایی کاهش یابد. جستجوی خطی باید دقیق باشد.
کاربردها: در بهینه سازی مهندسی، در یادگیری ماشین (نسخه های غیرخطی)، در حل دستگاه های خطی بزرگ.
نکته: روش CG برای بهینه سازی معادل روش CG برای حل دستگاه های خطی با A مثبت معین است.
