روش تندترین شیب

روش تندترین شیب یک الگوریتم گرادیان است که در آن اندازه گام α_k  به گونه ای انتخاب می شود که میزان کاهش تابع هدف در هر مرحله مجزا حداکثر شود. به طور مشخص، α_k به گونه ای انتخاب شده تا میزان ((⁽ф_k = f( x^(k) – α˅f(x^(k را حداقل نماید، به عبارت دیگر:

روش تندترین شیب

α_k = arg min  f( x^(k) – α˅f(x^(k))) , α≥0

به طور خلاصه، روش تندترین شیب به شرح زیر است: در هر مرحله، با شروع از نقطه ⁽x^(k جستجو خطی در جهت (⁽f(x^(k˅-)  تا زمانی که یک نقطه مینیمم ⁽x^(k+1  یافت شود ادامه می یابد. دنباله معمولی ناشی از روش تندترین شیب در شکل زیر نشان داده شده است.

مشاهده می کنیم که روش از تندترین شیب در گام های متعامد حرکت می کند، همانطور که در گزاره اول بیان شده است.

گزاره اول:

اگر  ⁽X^(k تندترین شیب دنباله برای تابع f:Rⁿ->R باشد پس برای هر K بردار⁽X^(k+1) – X^(k به بردار ⁽X^(k+2) – X^(k+1 متعامد است.

گزاره فوق نشان می دهد که  (⁽f(x^(k˅ با تانژانت در مجموعه سطح {⁽f(x) = f(x ^k+1} در نقطه x^k+1 موازی است. توجه داشته باشید که در هر نقطه جدید بدست آمده توسط روش تندترین شیب، مقدار تابع f کاهش می یابد. ( گزاره دوم)

گزاره دوم:

اگر  ⁽X^(k تندترین شیب دنباله برای تابع f:Rⁿ->R باشد و f(x^(k)))≠0˅باشد، پس مقدار

 f(x ^k+1 )< f(x ^k)

در گزاره دوم، نشان دادیم روش تندترین شیب خاصیت کاهش را اعمال می نماید. اگر برای برخی از k ها، f(x^(k)))=0˅ گردد، پس شرط اول مینیمم بودن نقطه ارضا شده است لذا  ⁽f(x ^k)= f(x ^k+1.حال می توانیم از این قابلیت به عنوان پایه ای برای یک معیار توقف الگوریتم استفاده نماییم.

اگرچه شرط f(x^(k)))=0˅ به طور مستقیم به عنوان یک معیار توقف عملی مناسب نیست، چراکه محاسبات عددی شیب به ندرت عینا برابر با صفر خواهد بود. روش دیگر، ممکن است محاسبه تفاوت مطلق |f(x ^k+1 ) – f(x ^k)| بین مقادیر تابع هدف برای هر دو تکرار پی در پی باشد و اگر تفاوت کمتر از حد آستانه مشخص شده باشد الگوریتم را متوقف خواهیم نمود:

|f(x ^k+1 ) – f(x ^k)| < ϵ

مثال روش تندترین شیب را در این قسمت مطالعه نمایید.