روش گرادیان

به یاد آورید که مجموعه سطح از تابع f: Rn -> R برابر است با مجموعه ای از نقاط X که تابع f(x) =c  را به ازای مقادیر ثابت c  راضی نماید. بنابراین، x0 ϵ Rn یکی از مجموعه سطح ها مرتبط به سطح c خواهد بود اگر f (X0) = C باشد. در مورد توابع با دو متغیر واقعی      f: R2 -> R مفهوم مجموعه سطح در شکل زیر نشان داده شده است.

روش گرادیان

گرادیان f در نقطه x0، که به صورت f(x0)Ʌ نشان داده می شود، اگر یک بردار صفر نباشد، متعامد به بردار مماس بر منحنی صاف دلخواه عبور کننده از  نقطه x0  در سطح مجموعه تابع f (x) = C خواهد بود. بنابراین، جهت حداکثر نرخ افزایش یک تابع مشتق پذیر حقیقی در یک نقطه متعامد به مجموعه سطح عملکرد از طریق آن نقطه بیان می شود.

به عبارت دیگر، گرادیان در جهتی عمل می نماید که با یک جابجایی کوچک، تابع f افزایش بیشتری در جهت گرادیان از هر جهت دیگر داشته باشد. برای اثبات این بیانیه، به یاد آورید (˅f(x0),d) ، به عبارتی ||d||=1، میزان افزایش f در جهت d در نقطه x می باشد. با استفاده از  نابرابری کوشی-شوارتز،

(˅f(x0), d)) ≤ || ˅f(x0) ||

چون ||d||=1. اما اگر ||(d=˅f(x) / ||˅f(x باشد، انگاه

[˅f(x0), (f(x) / ||˅f(x) ||)]=||˅f(x) ||

بنابراین، جهتی که در آن نقاط ((f(x˅) وجود دارد، جهت حداکثر نرخ افزایش f در x است. جهتی که در آن نقاط -˅f(x) وجود دارد، جهت حداکثر نرخ کاهش f در x است. از این رو، جهت شیب گرادیان یک جهت خوب برای جستجو است اگر ما بخواهیم یک مینیمم برای تابع بدست آوریم.

به صورت زیر ادامه می دهیم. فرض کنید  x0 یک نقطه شروع باشد و (x0 – α ˅ f(x0 را در نظر بگیریم. سپس با قضیه تیلور، خواهیم داشت:

F(x0 – α ˅ f(x0)) = f(x0) – α ||˅ f(x0)||2 + oα

بنابراین، اگر    f(x0) ≠0˅، سپس برای مقدار به اندازه کافی کوچک α>0 خواهیم داشت:

F(x0 – α ˅ f(x0)) < f(x0)

این به این معنی است که نقطه (x0 – α ˅ f(x0 ، اگر بخواهیم نقطه مینیمم را جستجو نماییم بهبودی بر روی x0 خواهد بود.

به منظور تدوین و فرموله نمودن یک الگوریتم جهت پیاده سازی این ایده، فرض کنید که نقطه xk  داده شده است. برای پیدا کردن نقطه بعدی xk+1 ، از نقطه xk شروع نموده و به میزان  (α ˅ f(x0)-حرکت می نماییم، که در آن αk یک اسکالر مثبت است که به آن” طول گام” گفته می شود. این روند منجر به الگوریتم تکرار شونده زیر خواهد شد:

xk+1 = xk – α ˅ f(xk)

ما به این الگوریتم، “ الگوریتم گرادیان نزولی” (و یا به طور ساده الگوریتم گرادیان) می گوییم. نتایج گرادیان به عنوان ابزار جستجو متفاوت است و رویکرد ما به جهت یافتن نقطه مینیمم آن را به سمت صفر هدایت می نماییم. این قابلیت وجود دارد که گام های بسیار کوچک برداشته و گرادیان را در هر مرحله ارزیابی مجدد نماییم یا اینکه گام های بزرگتری هر زمان برداریم.

روش اول روشی پر زحمت جهت رسیدن به نقطه مینیمم می باشد در حالی که روش دوم ممکن است مسیر کج و معوج بیشتری را در جهت رسیدن به مینیمم طی نماید.

مزیت استفاده از روش دوم احتمالا ارزیابی کمتر گرادیان خواهد بود. در میان بسیاری از روش های مختلف که از این الگوریتم استفاده می نمایند، یکی از محبوب ترین آن ها روش “تندترین شیب”  است که در ادامه به آن خواهیم پرداخت.

روش گرادیان روشی ساده برای پیاده سازی است و اغلب به خوبی انجام می شود. به همین دلیل به طور گسترده در کاربردهای عملی از آن استفاده می شود.

روش تندترین شیب را اینجا بخوانید.

X
سوالی دارین؟