روش Conjugate Gradients برای بهینه سازی

فرض کنیم F تابعی هموار ازRª→R باشد.  یک روش معمول برای پیدا کردن مینیمم این تابع این است که با شروع از نقطه ی خاصی، در جهت های انتخاب شده ای حرکت کنیم و در هر مرحله، گامی چنان برداریم که به مقدار کمینه تابع روی آن راستا برسیم. یک روش ابتدایی این است که این جهت ها را در راستای منفی گرادیان F انتخاب کنیم که منجر به روشی موسوم به "Steepest Descent Method" میشود. اما این روش معمولا کارآیی بالایی ندارد، چرا که سریعا در دام مینیمم های موضعی می افتد و خیلی کند پیش می رود. استفاده از روش ارتقا یافته ای به نام "Conjugate Gradients Method" راه بهتری است. در این روش جهت هایی را پیش میگیریم که در آن ماندهها متعامد باشند (هر کدام از این دو واﮋه تعریف دقیق و مشخصی دارند.) هر تابع هموار در نزدیکی نقاط مینیمم موضعی، شبیه یک تابع quadratic با ماتریس هسیان (Hessian Matrix) مثبت معیین رفتار می کند. این بدان معنی است که اگرA وb- ضرایب مورد نیاز برای تعریف یک تابع quadratic- را می داشتیم می توانستیم از روش CG برای بهینه سازی استفاده کنیم. در نگاه اول به نظر می رسد که بدون داشتن ماتریس هسیان-  که نقش A را بازی میکند- نمی توان CG را به کار برد. اما این مشکل رفع شدنی است. بررسی الگوریتم CG نشان می دهد که A در دو جا استفاده می شود. یکی در محاسبه ی گرادیان F و دیگری برای محاسبه ی گام حرکت در هر مرحله. مورد اول با به کارگیری روش خاصی حل شدنی است. برای دومی هم از روش های عددی برای مینیمم کردن مقدار F روی راستای خاص استفاده می کنیم. روش CG با این دو تغییرموسوم به روش Fletcher- Reeves می باشد.

مزایا و معایب

در این روشو تنها عملیاتی که با A انجام می گیرد ضرب آن در یک بردار است. اگر ماتریس A بزرگ و sparse باشد، این موضوع می تواند مفید باشد، چرا که شاید هیچوقت لازم نشود که A را در یک ماتریس m*m ذخیره کنیم. در عوض A را می توان به صورت ذخیره شده نگه داشت یا فورا محاسبه کرد. در این صورت تنها لازم است یک تابع مخصوص برای ضرب A در یک بردار نوشته شود.

CG یک روش تکراری است. به طور تئوری، تعداد تکرار های لازم برابر تعداد مقادیر وﯿﮋه متفاوت A است، یعنی m. در عمل معمولا خیلی زودتر به یک تقریب خوب می رسیم، که این عامل کارایی CG در مسایل بزرگ را توجیه می کند.

در مقایسه با روش های دیگر مرتبط با گرادیان، در CG جهت های متعامد همواره غیر صفرند و از بردار های جهت های قبلی به طور خطی مستقل هستند.

جهت بعدی از فرمول ساده ای به دست می آید، فقط کمی مشکلتر از روش steepest descent.

در مقایسه با Newton Method، که از CG کارایی بیشتری دارد، روش CG به حافظه ی کمتری احتیاج دارد. با توجه به اینکه جهت جستجو اطلاعات تمام جهت های قبلی را در خود دارد، تنها باید آخرین جهت، جهت فعلی و نقطه ی فعلی ذخیره شوند.

در حقیقت برای اطمینان از A- متعامد بودن جهت های جدید جستجو لازم نیست که نمام جهت های قبلی را داشته باشیم. این باعث می شود زمان عملیات از O(n²) به O(m) کاهش یابد (m تعداد درایه های غیر صفر A است.)

این روش توسط نرم افزار متلب قابل پیاده سازی است

• افزودن جدید
• جستجو

نظر ها (1)

• |78.39.165.xxx |2012-03-05 05:59:15 فرهاد یولداشی  - تشکر
  سلام. مهندس واقعاً لذت بردم.مطالب خیلی جالبی تو سایتتون هست. با آرزوی موفقیت
  • 0
  • 0

  پاسخبازگو

نوشتن نظر

Your Contact Details:

نام:

ایمیل: اعلام نکردناعلام کردن

آدرس سایت:

نظر:

عنوان:

قالب نوشته:         -رنگ-آبی کمرنگسیاهآبیبنفشخاکستریسبزلیموییقرمز آلبالوییسرمه ایزیتونیزرشکیقرمزنقره ایآبی سیرسفیدزرد -اندازه-ریزکوچکمعمولیبزرگبسیار بزرگ

Message:

Security

کد آنتی اسپم نمایش داده شده در عکس را وارد کنید.

Powered by !JoomlaComment 4.0 beta2