روش DFP (انگلیسی : Davidon-Fletcher-Powell Method)، در ریاضیات (Mathematics)
انواع روش های بهینه سازی (Optimization Methods) را در آموزش زیر شرح دادیم :
روش DFP (انگلیسی : Davidon-Fletcher-Powell Method) :
📌 تعریف: روش DFP (Davidon-Fletcher-Powell) اولین روش شبه-نیوتن (Quasi-Newton) است که در سال ۱۹۵۹ توسط دیویدون (Davidon) ابداع و سپس توسط فلچر و پاول (Fletcher & Powell) اصلاح شد. این روش یک تقریب برای معکوس ماتریس هسین (Hessian Inverse) ارائه می دهد و از آن برای تعیین جهت جستجو استفاده می کند.
💡 ایده اصلی
در روش DFP، یک ماتریس
\[ H_k \](تقریب معکوس هسین) به روزرسانی می شود. جهت جستجو به صورت
\[ d_k = -H_k \nabla f(x_k) \]محاسبه می شود. سپس با یک جستجوی خطی، اندازه گام
\[ \alpha_k \]تعیین و نقطه جدید
\[ x_{k+1} = x_k + \alpha_k d_k \]محاسبه می شود. ماتریس
\[ H_k \]با استفاده از اطلاعات تکرار فعلی به روزرسانی می شود.
📐 فرمول به روزرسانی DFP
فرض کنید
\[ s_k = x_{k+1} - x_k \]و
\[ y_k = \nabla f(x_{k+1}) - \nabla f(x_k) \]. فرمول به روزرسانی DFP برای معکوس هسین به صورت زیر است:
\[ H_{k+1}^{DFP} = H_k + \frac{s_k s_k^T}{s_k^T y_k} - \frac{H_k y_k y_k^T H_k}{y_k^T H_k y_k} \]این به روزرسانی تضمین می کند که اگر
\[ H_k \]معین مثبت باشد و
\[ s_k^T y_k > 0 \]، آنگاه
\[ H_{k+1} \]نیز معین مثبت خواهد بود.
🔧 مراحل الگوریتم DFP
یک نقطه شروع
\[ x_0 \]و یک ماتریس اولیه
\[ H_0 \](معمولا ماتریس همانی) انتخاب کن.
جهت جستجو را محاسبه کن:
\[ d_k = -H_k \nabla f(x_k) \].
با جستجوی خطی،
\[ \alpha_k \]را پیدا کن که
\[ f(x_k + \alpha_k d_k) \]را کمینه کند.
نقطه جدید را به روز کن:
\[ x_{k+1} = x_k + \alpha_k d_k \].
\[ s_k \]
و
\[ y_k \]را محاسبه کن.
ماتریس
\[ H_{k+1} \]را با فرمول DFP به روز کن.
اگر شرط توقف برقرار نیست، به گام ۲ برگرد.
📊 ویژگی ها
همگرایی ابرخطی (Superlinear): روش DFP دارای نرخ همگرایی ابرخطی است.
حفظ معین مثبت بودن: با فرض
\[ s_k^T y_k > 0 \]، ماتریس
\[ H_k \]معین مثبت می ماند.
کارایی: برای مسائل با ابعاد متوسط (تا چند صد متغیر) مناسب است.
جایگزینی: امروزه روش BFGS (که بعدا توضیح داده می شود) معمولا بر DFP ترجیح داده می شود زیرا پایداری عددی بهتری دارد.
