صفحه اصلی لثه روش تندترین شیب فرود. روش شیب دارترین فرود

لثه

روش تندترین شیب فرود. روش شیب دارترین فرود

روش تندترین فرود(در ادبیات انگلیسی "روش شیب دارترین نزول") یک روش عددی تکرار شونده ( مرتبه اول) برای حل مسائل بهینه سازی است که به شما امکان می دهد حداکثر (حداقل یا حداکثر) تابع هدف را تعیین کنید:

مقادیر آرگومان تابع (پارامترهای کنترل شده) در دامنه واقعی هستند.

مطابق با روش مورد بررسی، حداکثر (حداکثر یا حداقل) تابع هدف در جهت سریعترین افزایش (کاهش) تابع تعیین می شود. در جهت گرادیان (ضد گرادیان) تابع. تابع گرادیان در یک نقطه برداری است که پیش بینی های آن بر روی محورهای مختصات مشتقات جزئی تابع نسبت به مختصات است:

که در آن i، j،…، n بردارهای واحد موازی با محورهای مختصات هستند.

گرادیان در نقطه پایه کاملاً متعامد به سطح است و جهت آن جهت سریعترین افزایش تابع را نشان می دهد و جهت مخالف (ضد گرادیان) به ترتیب جهت سریعترین کاهش تابع را نشان می دهد.

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

که در آن علامت "+" برای یافتن حداکثر یک تابع و علامت "-" برای یافتن حداقل یک تابع استفاده می شود.

بردار جهت واحد که با فرمول تعیین می شود:

- ماژول گرادیان میزان افزایش یا کاهش تابع را در جهت گرادیان یا ضد گرادیان تعیین می کند:

ثابتی که اندازه گام را تعیین می کند و برای تمام جهات i-ام یکسان است.

اندازه گام از شرط حداقل تابع هدف f(x) در جهت حرکت انتخاب می شود، یعنی در نتیجه حل مسئله بهینه سازی یک بعدی در جهت گرادیان یا ضد گرادیان:

به عبارت دیگر، اندازه گام با حل این معادله تعیین می شود:

بنابراین، مرحله محاسبه به گونه‌ای انتخاب می‌شود که حرکت تا زمانی انجام شود که عملکرد بهبود یابد، بنابراین در نقطه‌ای به حداکثر می‌رسد. در این مرحله، جهت جستجو مجدداً تعیین می شود (با استفاده از گرادیان) و یک نقطه بهینه جدید از تابع هدف و غیره جستجو می شود. بنابراین در این روش جستجو در مراحل بزرگتر انجام می شود و گرادیان تابع در تعداد نقاط کمتری محاسبه می شود.

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

مسیر حرکت به سمت نقطه منتهی با استفاده از روش شیب دارترین فرود، نشان داده شده در نمودار خط مساوی از تابع f(x)

جستجوی یک راه حل بهینه زمانی به پایان می رسد که در مرحله محاسبه تکراری (چند معیار):

مسیر جستجو در یک محله کوچک از نقطه جستجوی فعلی باقی می ماند:

افزایش تابع هدف تغییر نمی کند:

گرادیان تابع هدف در نقطه حداقل محلی صفر می شود:

لازم به ذکر است که روش شیب نزولی هنگام حرکت در امتداد یک دره بسیار کند می شود و با افزایش تعداد متغیرها در تابع هدف، این رفتار روش معمولی می شود. دره یک فرورفتگی است که خطوط تراز آن تقریباً به شکل بیضی با نیم محورهای چندین برابر متفاوت است. در حضور دره، مسیر فرود به شکل یک خط زیگزاگ با یک پله کوچک به خود می گیرد که در نتیجه سرعت فرود حاصله به حداقل ممکن کاهش می یابد. این با این واقعیت توضیح داده می شود که جهت ضد گرادیان این توابع به طور قابل توجهی از جهت به نقطه حداقل منحرف می شود که منجر به تاخیر اضافی در محاسبه می شود. در نتیجه، الگوریتم کارایی محاسباتی را از دست می دهد.

عملکرد آبکند

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

روش محاسبه

مرحله 1:تعریف عبارات تحلیلی (به صورت نمادین) برای محاسبه گرادیان یک تابع

مرحله 2: تقریب اولیه را تنظیم کنید

مرحله 3:نیاز به راه اندازی مجدد روش الگوریتمی برای تنظیم مجدد آخرین جهت جستجو مشخص می شود. در نتیجه شروع مجدد، جستجو دوباره در جهت سریعترین فرود انجام می شود.

همچنین می توانید نه برای بهترین نقطه در جهت گرادیان، بلکه برای نقطه ای بهتر از نقطه فعلی جستجو کنید.

ساده ترین روش برای پیاده سازی تمام روش های بهینه سازی محلی. کاملا دارد شرایط ضعیفهمگرایی، اما میزان همگرایی بسیار کم (خطی) است. مرحله روش گرادیاناغلب به عنوان بخشی از سایر روش های بهینه سازی، مانند روش فلچر-ریوز استفاده می شود.

توضیحات [ | ]

بهبودها[ | ]

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

برای توابع نزدیک به درجه دوم، روش گرادیان مزدوج موثر است.

کاربرد در شبکه های عصبی مصنوعی[ | ]

روش نزول گرادیان، با مقداری اصلاح، به طور گسترده ای برای آموزش پرسپترون استفاده می شود و در تئوری شبکه های عصبی مصنوعی به عنوان روش پس انتشار شناخته می شود. هنگام آموزش یک شبکه عصبی از نوع پرسپترون، لازم است ضرایب وزن شبکه را طوری تغییر دهید که به حداقل برسد. خطای متوسطدر خروجی شبکه عصبی زمانی که دنباله ای از داده های ورودی آموزشی به ورودی ارائه می شود. به طور رسمی، برای برداشتن تنها یک مرحله با استفاده از روش نزول گرادیان (فقط یک تغییر در پارامترهای شبکه)، لازم است که به طور متوالی تمام مجموعه داده های آموزشی به ورودی شبکه ارسال شود، خطا برای هر شیء محاسبه شود. داده های آموزشی را محاسبه کرده و تصحیح لازم ضرایب شبکه را محاسبه کرده (اما این اصلاح را انجام ندهید) و پس از ارسال کلیه داده ها، مقدار در تنظیم هر ضریب شبکه (مجموع شیب ها) را محاسبه کرده و ضرایب را "یک مرحله ای" تصحیح کنید. . بدیهی است که با مجموعه بزرگی از داده های آموزشی، الگوریتم بسیار کند کار می کند، بنابراین در عمل، ضرایب شبکه اغلب پس از هر عنصر آموزشی تنظیم می شود، جایی که مقدار گرادیان با گرادیان تابع هزینه تقریبی می شود، که تنها بر روی یک آموزش محاسبه می شود. عنصر این روش نامیده می شود نزول گرادیان تصادفی یا نزول شیب عملیاتی . نزول گرادیان تصادفی شکلی از تقریب تصادفی است. تئوری تقریب های تصادفی شرایطی را برای همگرایی روش نزول گرادیان تصادفی فراهم می کند.

پیوندها [ | ]

جی. ماتیوس.ماژول برای شیب ترین نزول یا روش گرادیان. (لینک در دسترس نیست)

ادبیات [ | ]

آکولیچ آی. ال.برنامه نویسی ریاضی در مثال ها و مسائل. - م.: دبیرستان، 1986. - ص 298-310.
گیل اف.، موری دبلیو.، رایت ام.بهینه سازی عملی = بهینه سازی عملی. - م.: میر، 1364.
کورشونوف یو.مبانی ریاضی سایبرنتیک - M.: Energoatomizdat، 1972.
ماکسیموف یو.، فیلیپوفسکایا ای.الگوریتم های حل مسائل برنامه ریزی غیرخطی - M.: MEPhI، 1982.
ماکسیموف یو.الگوریتم های برنامه ریزی خطی و گسسته - M.: MEPhI، 1980.
کورن جی.، کورن تی.کتاب ریاضیات برای دانشمندان و مهندسان. - M.: Nauka، 1970. - P. 575-576.
S. Yu. Gorodetsky، V. A. Grishagin.برنامه نویسی غیرخطی و بهینه سازی چند جانبی - نیژنی نووگورود: انتشارات دانشگاه نیژنی نووگورود، 2007. - صص 357-363.

هدف از خدمات. ماشین حساب آنلاین مورد استفاده برای پیدا کردن حداقل عملکردشیب دارترین روش فرود یا روش کوشی(نمونه را ببینید). راه حل با فرمت Word طراحی شده است.

قوانین برای وارد کردن یک تابع

در شیب دارترین روش فرودبرداری که جهت آن مخالف جهت بردار گرادیان تابع ▽f(x) است به عنوان جهت جستجو انتخاب می شود. از تجزیه و تحلیل ریاضیمشخص است که بردار درجه f(x)=▽f(x) جهت سریعترین افزایش در تابع را مشخص می کند (به گرادیان تابع مراجعه کنید). بنابراین، بردار - grad f (X) = -▽f(X) نامیده می شود ضد گرادیانو جهت سریعترین کاهش آن است. رابطه بازگشتی که شیب‌دارترین روش فرود با آن اجرا می‌شود، به شکل X k +1 =X k - λ k ▽f(x k)، k = 0،1،...،
که در آن λ k>0 اندازه گام است. بسته به انتخاب اندازه گام، می توانید دریافت کنید گزینه های مختلفروش گرادیان اگر در طول فرآیند بهینه‌سازی، اندازه گام λ ثابت باشد، روش را روش گرادیان با یک گام گسسته می‌نامند. اگر λk از شرط λk =min f(Xk + λS k) انتخاب شود، فرآیند بهینه‌سازی در اولین تکرارها می‌تواند به طور قابل توجهی تسریع شود.
برای تعیین λ k از هر روش بهینه سازی تک بعدی استفاده می شود. در این حالت روش شیب دارترین روش فرود نامیده می شود. به عنوان یک قاعده، در حالت کلی، یک مرحله برای دستیابی به حداقل تابع کافی نیست تا زمانی که محاسبات بعدی امکان بهبود نتیجه را فراهم کند.
اگر فضا در برخی از متغیرها بسیار کشیده باشد، "دره" تشکیل می شود. جستجو ممکن است کند شود و در پایین "دره" به صورت زیگزاگ حرکت کند. گاهی اوقات نمی توان راه حلی را در یک بازه زمانی قابل قبول به دست آورد.
یکی دیگر از معایب روش ممکن است معیار توقف ||▽f(X k)||<ε k , так как этому условию удовлетворяет и седловая точка, а не только оптимум.

مثال. با شروع از نقطه x k =(-2، 3)، نقطه x k +1 را با استفاده از شیب‌دارترین روش فرود تعیین کنید تا تابع را به حداقل برسانید.
به عنوان جهت جستجو، بردار گرادیان را در نقطه فعلی انتخاب کنید

بیایید معیار توقف را بررسی کنیم. ما داریم
بیایید مقدار تابع را در نقطه اولیه f(X 1) = 35 محاسبه کنیم.
در جهت ضد گرادیان قدم بردارید

بیایید مقدار تابع را در یک نقطه جدید محاسبه کنیم
f(X 2) = 3 (-2 + 19λ 1) 2 + (3-8λ 1) 2 - (-2 + 19λ 1) (3-8λ 1) - 4 (-2 + 19λ 1)
اجازه دهید مرحله ای را پیدا کنیم که تابع هدف در این جهت به حداقل برسد. از شرط لازم برای وجود افراطی تابع
f’(X 2) = 6(-2 + 19λ 1) 19 + 2(3-8λ 1)(-8) - (73 - 304 λ 1) - 4*19
یا f'(X 2) = 2598 λ 1 - 425 = 0.
مرحله λ 1 = 0.164 را دریافت می کنیم
تکمیل این مرحله به نقطه منتهی می شود

که در آن مقدار گرادیان ، مقدار تابع f(X 2) = 0.23. دقت به دست نمی آید، از نقطه ای که ما در جهت ضد گرادیان یک گام برداریم.

f(X 2) = 3 (1.116 - 1.008 λ 1) 2 + (1.688-2.26 λ 1) 2 - (1.116 - 1.008 λ 1) (1.688-2.26 λ 1) - 4 (1.116 - 1.008λ)
f'(X 2) = 11.76 - 6.12λ 1 = 0
λ 1 = 0.52 بدست می آوریم

حاشیه نویسی: این سخنرانی به طور گسترده ای روش های بهینه سازی چند پارامتری مانند شیب دارترین روش فرود و روش دیویدون-فلچر-پاول را پوشش می دهد. علاوه بر این، تجزیه و تحلیل مقایسه ای از روش های فوق به منظور تعیین موثرترین، مزایا و معایب آنها انجام می شود. و همچنین مسائل بهینه سازی چند بعدی مانند روش دره و روش چند اکسترمال را در نظر می گیرد.

1. روش شیب دارترین فرود

ماهیت این روش این است که با استفاده از مواردی که قبلا ذکر شد روش نزول مختصاتجستجو از یک نقطه معین در جهت موازی با یکی از محورها تا حداقل نقطه در این جهت انجام می شود. سپس جستجو در جهتی موازی با محور دیگر و غیره انجام می شود. البته مسیرها ثابت هستند. منطقی به نظر می رسد تلاش برای اصلاح این روش به طوری که در هر مرحله جستجو برای حداقل نقطه در امتداد "بهترین" جهت انجام شود. مشخص نیست که کدام جهت "بهترین" است، اما معلوم است که جهت گرادیانجهت سریعترین افزایش در تابع است. بنابراین جهت مخالف جهت سریعترین کاهش تابع است. این ویژگی را می توان به شرح زیر توجیه کرد.

فرض کنید از نقطه x به نقطه بعدی x + hd حرکت می کنیم، جایی که d یک جهت معین و h یک پله با طول معین است. در نتیجه، حرکت از نقطه (x 1، x 2، ...، x n) به نقطه انجام می شود. (x 1 + zx 1، x 2 + zx 2، ...، x n + zx n)، کجا

تغییر در مقادیر تابع توسط روابط تعیین می شود

(1.3)

تا مرتبه اول zx i، با مشتقات جزئی که در نقطه x محاسبه می شوند. برای به دست آوردن بیشترین مقدار تغییر در تابع df، چگونه باید جهاتی d i انتخاب شود که معادله (1.2) را برآورده کند؟ اینجاست که یک مشکل حداکثر سازی با یک محدودیت ایجاد می شود. اجازه دهید روش ضریب های لاگرانژ را اعمال کنیم که با کمک آن تابع را تعیین می کنیم

مقدار df ارضا کننده محدودیت (1.2) زمانی که تابع به حداکثر می رسد

به حداکثر می رسد. مشتق آن

از این رو،

(1.6)

سپس di ~ df/dx i و جهت d با جهت V/(x) در نقطه x موازی است.

بنابراین، بزرگترین افزایش محلیتابع برای یک گام کوچک معین h زمانی رخ می دهد که d جهت Vf(x) یا g(x) باشد. بنابراین، جهت تندترین نزول، جهت است

به شکل ساده تر، معادله (1.3) را می توان به صورت زیر نوشت:

زاویه بین بردارهای Vf(x) و dx کجاست. برای مقدار معین dx، df را با انتخاب اینکه جهت dx با جهت -Vf(x) منطبق است، به حداقل می‌رسانیم.

نظر دهید. جهت گرادیانعمود بر هر نقطه از خطی با سطح ثابت، زیرا در طول این خط تابع ثابت است. بنابراین، اگر (d 1, d 2, ..., d n) یک پله کوچک در امتداد خط تراز باشد، پس

و بنابراین