روش شیب دارترین فرود. حداقل عملکرد با شیب ترین روش فرود

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

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

شرح [ | ]

بهبودها[ | ]

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

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

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

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

پیوندها [ | ]

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

ادبیات [ | ]

• آکولیچ آی. ال.برنامه نویسی ریاضی در مثال ها و مسائل. - م.: دانشکده تحصیلات تکمیلی، 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.

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

f(x[ک] -آ ک f" (x[ک])) = f(x[k] -af"(x[ک])) .

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

j (آ) = f(x[ک]-af"(x[ک])) .

الگوریتم روش شیب دارترین فرود به شرح زیر است.

• 1. مختصات نقطه شروع را تنظیم کنید ایکس.
• 2. در نقطه ایکس[ک], k = 0، 1، 2، ... مقدار گرادیان را محاسبه می کند f" (x[ک]) .
• 3. اندازه گام تعیین می شود آ k، با کمینه سازی یک بعدی بیش از آتوابع j (آ) = f(x[ک]-af"(x[ک])).
• 4. مختصات نقطه مشخص می شود ایکس[k+ 1]:

ایکس من [k+ 1]= x من [ک] -آ ک f" من (ایکس[ک])، i = 1،...، ص.

5. شرایط توقف فرآیند استریشن بررسی می شود. اگر آنها برآورده شوند، محاسبات متوقف می شود. در غیر این صورت به مرحله 1 بروید.

در روش مورد بررسی جهت حرکت از نقطه ایکس[ک] خط سطح را در نقطه لمس می کند ایکس[k+ 1] (شکل 2.9). مسیر فرود زیگزاگی است، با پیوندهای زیگزاگ مجاور متعامد به یکدیگر. در واقع یک قدم آ k با کمینه سازی توسط انتخاب می شود آکارکرد؟ (آ) = f(x[k] -af"(x[ک])) . شرط لازم برای حداقل یک تابع د j (a)/da = 0.پس از محاسبه مشتق تابع پیچیده، شرط متعامد بودن بردارهای جهت نزول در نقاط همسایه را به دست می آوریم:

د j (a)/da = -f"(x[k+ 1]f" (x[ک]) = 0.

برنج. 2.9.

روش‌های گرادیان با نرخ بالا به حداقل می‌رسند (با یک نرخ پیشرفت هندسی) برای توابع محدب صاف. چنین توابعی بیشترین میزان را دارند مو حداقل مترمقادیر ویژه ماتریس مشتقات دوم (ماتریس هسی)

تفاوت کمی با یکدیگر دارند، یعنی ماتریس N(x)خوب شرطی شده این را به شما یادآوری کنیم مقادیر ویژهمن، من =1, …, n، ماتریس ها ریشه های معادله مشخصه هستند

با این حال، در عمل، به عنوان یک قاعده، توابعی که به حداقل می رسند، دارای ماتریس های نامشخص مشتقات دوم هستند. (t/m<< 1). مقادیر چنین توابعی در امتداد برخی جهات بسیار سریعتر (گاهی با چندین مرتبه بزرگی) نسبت به سایر جهات تغییر می کند. سطوح تراز آنها در ساده ترین حالت به شدت دراز است (شکل 2.10) و در موارد پیچیده تر خم می شوند و مانند دره ها به نظر می رسند. توابع با چنین ویژگی هایی نامیده می شوند خندقجهت ضد گرادیان این توابع (نگاه کنید به شکل 2.10) به طور قابل توجهی از جهت به نقطه حداقل منحرف می شود، که منجر به کاهش سرعت همگرایی می شود.

برنج. 2.10.

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

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

f(x 1، x 2) =

برای پیدا کردن حداکثر عملکرد، لازم است تابع هدف را در (-1) ضرب کنیم، یعنی. Fmin = -Fmax.
روشی برای یافتن حداقل یک تابعروش شیب دارترین نزول به روش نیوتن
شروع از یک نقطه ( ; ) .
دقت ξ = . تعداد تکرار 1 2 3

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

که در شیب دارترین روش فرودبرداری که جهت آن مخالف جهت بردار گرادیان تابع ▽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 بدست می آوریم

فرمول بندی مسئله

اجازه دهید تابع داده شود f(x) Rn

ضروری f(x) X = Rn

استراتژی جستجو

x k } , k = 0.1،...، به طوری که , k = 0.1، ... . نقاط توالی ( x k ) طبق قاعده محاسبه می شوند

نکته کجاست x 0 تعریف شده توسط کاربر؛ اندازه گام tk برای هر مقدار تعیین می شود ک از شرایط

مشکل (3) را می توان با استفاده از حداقل شرط لازم و سپس بررسی شرط حداقل کافی حل کرد. این مسیر را می توان یا برای یک تابع نسبتاً ساده به حداقل رساندن یا برای تقریب اولیه یک تابع نسبتاً پیچیده استفاده کرد. چند جمله ای P(t k) (معمولاً درجه دوم یا سوم) و سپس شرط با شرط جایگزین می شود و شرط با شرط جایگزین می شود.

ترتیب دهی (xk) به نقطه ختم می شود x k ، برای چه ، کجا ε - یک عدد مثبت کوچک داده شده، یا k ≥ M ، جایی که م - تعداد محدود تکرار، یا با دو اجرای همزمان دو نامساوی , جایی که ε 2 - عدد مثبت کوچک سوال این است که آیا یک نقطه می تواند x k به عنوان تقریب یافت شده از حداقل نقطه محلی مورد نظر در نظر گرفته شود ایکس* ، از طریق تحقیقات تکمیلی حل می شود.

تفسیر هندسی روش برای n=2 در شکل 4.

روش نزول مختصات

فرمول بندی مسئله

اجازه دهید تابع داده شود f(x) ، در زیر مجموعه محدود شده است Rn و داشتن مشتقات جزئی پیوسته در تمام نقاط آن.

f(x) در مجموعه راه حل های عملی X = Rn ، یعنی نقطه ای را پیدا کنید که

استراتژی جستجو

استراتژی برای حل مسئله ساختن دنباله ای از نقاط ( x k } , k = 0.1،...، به طوری که , k = 0.1، ... . نقاط توالی ( x k ) طبق قانون در طول چرخه محاسبه می شوند

(4)

جایی که j - شماره چرخه محاسبه؛ j = 0,1,2,...; ک - عدد تکرار در داخل حلقه، k = 0,1,... ,n - 1; e k +1، k = 0،l،...،n - 1 -بردار واحد، (k+1) -ام طرح ریزی که برابر با 1 است. نقطه x 00 تعریف شده توسط کاربر، اندازه گام tk از شرط انتخاب شده است

یا .

اگر شرایط انتخاب شده در حال حاضر tk انجام نشده است، مرحله نصف شده و دوره می شود دوباره محاسبه می شود. به راحتی می توان مشاهده کرد که برای یک j ثابت، در یک تکرار با عدد ک فقط یک طرح از نقطه تغییر می کند x jk ، داشتن شماره k+1 ، و در طول کل چرخه با شماره j ، یعنی شروع با k = 0 و پایان دادن k = n -1 ، تمام n پیش بینی نقطه تغییر می کند x j0 . بعد از این نقطه x j n شماره اختصاص داده شده است x j + 1.0 ، و به عنوان نقطه شروع برای محاسبات در نظر گرفته می شود j+1 چرخه محاسبه در نقطه پایان می یابد x jk هنگام اجرا بر اساس حداقلیکی از سه معیار پایان شمارش: ، یا ، یا اجرای مضاعف نابرابری ها.

نقاط به دست آمده در نتیجه محاسبات را می توان به عنوان عناصر یک دنباله نوشت (xl) جایی که l=n*j+k - شماره سریال نقطه،

تفسیر هندسی روش برای n = 2 در شکل نشان داده شده است. 5.

4. روش فرانک ولف .

فرض کنید باید حداکثر مقدار یک تابع مقعر را پیدا کنیم

تحت شرایط

ویژگی مشخصه این مسئله این است که سیستم قیود آن فقط شامل نابرابری های خطی است. این ویژگی مبنایی برای جایگزینی تابع هدف غیرخطی با تابع خطی در مجاورت نقطه مورد مطالعه است که به دلیل آن حل مسئله اصلی به حل ترتیبی مسائل برنامه ریزی خطی کاهش می یابد.
فرآیند یافتن راه‌حل برای مشکل با شناسایی نقطه‌ای که متعلق به منطقه راه‌حل‌های امکان‌پذیر برای مشکل است آغاز می‌شود.
270
ویلاها بگذارید این نکته باشد X(k) سپس در این مرحله گرادیان تابع (57) محاسبه می شود

و یک تابع خطی بسازید

سپس حداکثر مقدار این تابع را در محدودیت های (58) و (59) بیابید. بگذارید راه حل این مشکل با نقطه مشخص شود Z(k) . سپس مختصات نقطه به عنوان یک راه حل امکان پذیر جدید برای مسئله اصلی در نظر گرفته می شود X(k+1) :

جایی که λk - عدد معینی به نام مرحله محاسبه و محصور بین صفر و یک (0<λk < 1). Это число λk خودسرانه یا تعیین شده گرفته شده است

به طوری که مقدار تابع در نقطه X (k +1) f(X (k +1)) ، وابسته به λk ، حداکثر بود. برای انجام این کار، باید یک راه حل برای معادله پیدا کنید و کوچکترین ریشه آن را انتخاب کنید. اگر مقدار آن بیشتر از یک باشد، باید قرار دهیم λk=1 . پس از تعیین تعداد λk مختصات یک نقطه را پیدا کنید X(k+1) مقدار تابع هدف را در آن محاسبه کنید و نیاز به حرکت به نقطه جدید را تعیین کنید X(k+2) . اگر چنین نیازی وجود دارد، سپس در نقطه محاسبه کنید X(k+1) گرادیان تابع هدف، به مسئله برنامه ریزی خطی مربوطه بروید و راه حل آن را پیدا کنید. مختصات نقطه را مشخص کنید و X(k+2) و نیاز به محاسبات بیشتر را بررسی کنید. پس از تعداد محدودی از مراحل، راه حلی برای مسئله اصلی با دقت لازم به دست می آید.

بنابراین، فرآیند یافتن راه حل برای مسئله (57) - (59) با استفاده از روش فرانک ولف شامل مراحل زیر است.:

1. راه حل قابل اجرا اولیه برای مشکل را تعیین کنید.
2. گرادیان تابع (57) را در نقطه یک جواب قابل قبول بیابید.
3. تابع (60) را بسازید و حداکثر مقدار آن را در شرایط (58) و (59) بیابید.
4. مرحله محاسبه را تعیین کنید.
5. با استفاده از فرمول (61)، اجزای یک راه حل امکان پذیر جدید پیدا می شود.
6. بررسی کنید که باید به راه حل عملی بعدی بروید. در صورت لزوم به مرحله 2 بروید، در غیر این صورت راه حل قابل قبولی برای مشکل اصلی پیدا می شود.

روش توابع جریمه.

مسئله تعیین حداکثر مقدار تابع مقعر را در نظر بگیرید

f (x 1، x 2، .... x n)تحت شرایط g i (x 1، x 2، .... x n) ≤ b i (i=l، m) , x j ≥ 0 (j=1، n) ، جایی که g i (x 1، x 2، .... x n) - توابع محدب

به جای حل مستقیم این مشکل، حداکثر مقدار تابع را پیدا کنید F(x 1، x 2، ....، x n)= f(x 1، x 2، ....، x n) +H(x 1، x 2، ....، x n) که مجموع تابع هدف مسئله و مقداری تابع است

H(x 1، x 2، ....، x n)، توسط سیستمی از محدودیت ها تعریف شده و نامیده می شود عملکرد پنالتی. تابع پنالتی را می توان به روش های مختلفی ساخت. با این حال، اغلب به نظر می رسد

آ a i > 0 - برخی از اعداد ثابت نشان دهنده ضرایب وزنی.
با استفاده از تابع پنالتی، آنها به صورت متوالی از یک نقطه به نقطه دیگر حرکت می کنند تا زمانی که جواب قابل قبولی به دست آورند. در این حالت با استفاده از فرمول مختصات نقطه بعدی پیدا می شود

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

بنابراین، فرآیند یافتن راه‌حل برای یک مسئله برنامه‌نویسی محدب با استفاده از روش تابع جریمه شامل مراحل زیر است:

1. راه حل قابل اجرا اولیه را تعیین کنید.
2. مرحله محاسبه را انتخاب کنید.
3. برای همه متغیرها، مشتقات جزئی تابع هدف و توابعی را پیدا کنید که محدوده راه حل های امکان پذیر برای مسئله را تعیین می کنند.

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

روش پیکان هورویتز.

هنگام یافتن راه حل برای مسائل برنامه ریزی غیرخطی با استفاده از روش تابع جریمه، مقادیر را انتخاب می کنیم یک من ، به طور خودسرانه، که منجر به نوسانات قابل توجهی در فاصله نقاط تعیین شده از منطقه راه حل های امکان پذیر شد. این اشکال در هنگام حل مسئله با روش پیکان-هورویتز برطرف می شود که طبق آن در مرحله بعد اعداد a i (k) با فرمول محاسبه می شود

به عنوان مقادیر اولیه a i (0) اعداد غیر منفی دلخواه را بگیرید.

راه حل مثال

مثال 1.

حداقل محلی یک تابع را پیدا کنید

تعریف یک نقطه x k

1. بیایید تنظیم کنیم.

2. بگذاریم k = 0 .

سی . بیایید محاسبه کنیم

4 0 . بیایید محاسبه کنیم . بیایید به مرحله 5 برویم.

50 . بیایید شرایط را بررسی کنیم . بیایید به مرحله 6 برویم.

6 0 . بیایید تنظیم کنیم t0 = 0.5 .

7 0 . بیایید محاسبه کنیم

8 0 . بیایید مقایسه کنیم . ما داریم . نتیجه گیری: شرط برای k = 0 اجرا نمی شود. بیایید تنظیم کنیم t0 = 0.25 ، مراحل 7 و 8 را تکرار کنید.

7 01. بیایید محاسبه کنیم.

8 01. بیایید مقایسه کنیم f (x 1) و f (x 0) . نتیجه: f (x 1)< f (x 0) . بیایید به مرحله 9 برویم.

9 0 . بیایید محاسبه کنیم

نتیجه: ما معتقدیم k = 1 و به مرحله 3 بروید.

3 1. بیایید محاسبه کنیم

4 1. بیایید محاسبه کنیم . بیایید به مرحله 5 برویم.

5 1. بیایید شرایط را بررسی کنیم k ≥ M: k = 1< 10 = M . بیایید به مرحله 6 برویم.

6 1. بیایید تنظیم کنیم t 1 = 0.25.

7 1. بیایید محاسبه کنیم

8 1. بیایید مقایسه کنیم f (x 2) با f (x 1) . نتیجه: f (x 2)< f (х 1). بیایید به مرحله 9 برویم.

9 1. بیایید محاسبه کنیم

نتیجه: ما معتقدیم k = 2 و به مرحله 3 بروید.

3 2. بیایید محاسبه کنیم

4 2. بیایید محاسبه کنیم. بیایید به مرحله 5 برویم.

5 2. بیایید شرایط را بررسی کنیم k ≥ M : k = 2< 10 = М ، به مرحله 6 بروید.

6 2. بیایید تنظیم کنیم t 2 =0,25 .

7 2. بیایید محاسبه کنیم

8 2. بیایید مقایسه کنیم f (x 3) و f (x 2) . نتیجه: f (x 3)< f (х 2) به مرحله 9 بروید.

9 2. بیایید محاسبه کنیم

نتیجه: ما معتقدیم k = 3 و به مرحله 3 بروید.

3 3 . بیایید محاسبه کنیم

4 3 . بیایید محاسبه کنیم. بیایید به مرحله 5 برویم.

5 3. بیایید شرایط را بررسی کنیم k ≥ M : k = 3<10 = М ، به مرحله 6 بروید.

6 3. بیایید تنظیم کنیم t 3 = 0.25.

7 3. بیایید محاسبه کنیم

8 3. بیایید مقایسه کنیم f (x 4) و f (x 3): f (x 4)< f (х 3) .

9 3. بیایید محاسبه کنیم

شرایط زمانی برآورده می شود k = 2.3 . محاسبه

تمام شده. نقطه پیدا شد

در شکل 3 نقطه به دست آمده توسط یک خط نقطه به هم متصل می شوند.

II. تحلیل نقطه ای x 4 .

تابع دو برابر قابل تمایز است، بنابراین شرایط کافی برای حداقل را در نقطه بررسی می کنیم x 4 . برای انجام این کار، اجازه دهید ماتریس Hessian را تجزیه و تحلیل کنیم.

ماتریس قطعی ثابت و مثبت است (یعنی . H > 0 ) زیرا هر دو مینور زاویه ای آن مثبت هستند. بنابراین، نکته تقریب یافت شده از حداقل نقطه محلی و مقدار است تقریب یافت شده از مقدار است f (x *) = 0 . توجه داشته باشید که شرط H > 0 ، در عین حال یک شرط برای تحدب شدید تابع وجود دارد . در نتیجه، تقریبی از نقطه حداقل جهانی یافت می شود f(x) و حداقل مقدار آن در R 2 . ■

مثال 2

حداقل محلی یک تابع را پیدا کنید

I. تعریف یک نقطه x k، که در آن حداقل یکی از معیارهای تکمیل محاسبات رعایت شده باشد.

1. بیایید تنظیم کنیم.

بیایید گرادیان تابع را در یک نقطه دلخواه پیدا کنیم

2. بگذاریم k = 0 .

سی . بیایید محاسبه کنیم

4 0 . بیایید محاسبه کنیم . بیایید به مرحله 5 برویم.

50 . بیایید شرایط را بررسی کنیم . بیایید به مرحله 6 برویم.

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

اجازه دهید عبارات به دست آمده را برای مختصات جایگزین کنیم

بیایید حداقل تابع را پیدا کنیم f (t 0) توسط t 0 استفاده از شرایط لازم برای یک افراط گرایی بدون قید و شرط:

از اینجا t 0 = 0.24 . زیرا ، مقدار گام یافت شده حداقل تابع را ارائه می دهد f (t 0) توسط t 0 .

بیایید تعریف کنیم

7 0 . پیدا خواهیم کرد

8 درجه بیایید محاسبه کنیم

نتیجه: ما معتقدیم k = 1 و به مرحله 3 بروید.

3 1. بیایید محاسبه کنیم

4 1. بیایید محاسبه کنیم

5 1. بیایید شرایط را بررسی کنیم k ≥ 1: k = 1< 10 = М.

6 1. بیایید تعریف کنیم

7 1. پیدا خواهیم کرد :

8 1. بیایید محاسبه کنیم

ما معتقدیم k = 2 و به مرحله 3 بروید.

3 2. بیایید محاسبه کنیم

4 2 . بیایید محاسبه کنیم

5 2. بیایید شرایط را بررسی کنیم k ≥ M: k = 2< 10 = M .

6 2. بیایید تعریف کنیم

7 2. پیدا خواهیم کرد

8 2. بیایید محاسبه کنیم

ما معتقدیم k = 3 و به مرحله 3 بروید.

3 3 . بیایید محاسبه کنیم

4 3 . بیایید محاسبه کنیم.

محاسبه تکمیل شده است. نقطه پیدا شد

II. تحلیل نقطه ای x 3 .

در مثال 1.1 (فصل 2 §1) نشان داده شد که تابع f(x) به شدت محدب است و بنابراین، در نقاط 3 تقریب یافت شده از نقطه حداقل جهانی است ایکس* .

مثال 3.

حداقل محلی یک تابع را پیدا کنید

I. تعریف یک نقطه xjk ، که در آن حداقل یکی از معیارهای تکمیل محاسبات رعایت شده باشد.

1. بیایید تنظیم کنیم

بیایید گرادیان تابع را در یک نقطه دلخواه پیدا کنیم

2. بیایید تنظیم کنیم j = 0.

سی . بیایید بررسی کنیم که آیا شرط برقرار است یا خیر

4 0 . بیایید تنظیم کنیم k = 0.

50 . بیایید بررسی کنیم که آیا شرط برقرار است یا خیر

6 0 . بیایید محاسبه کنیم

7 0 . بیایید شرایط را بررسی کنیم

8 0 . تنظیم کنیم

9 0 . بیایید محاسبه کنیم ، جایی که

100 . بیایید شرایط را بررسی کنیم

نتیجه گیری: ما فرض می کنیم و به مرحله 9 می رویم.

9 01. بیایید محاسبه کنیم x 01 به صورت افزایشی

10 01. بیایید شرایط را بررسی کنیم

11 0 . بیایید شرایط را بررسی کنیم

ما معتقدیم k = 1 و به مرحله 5 بروید.

5 1. بیایید شرایط را بررسی کنیم

6 1. بیایید محاسبه کنیم

7 1. بیایید شرایط را بررسی کنیم

8 1. بیایید تنظیم کنیم

9 1. بیایید محاسبه کنیم

10 1. بیایید شرایط را بررسی کنیم :

11 1. بیایید شرایط را بررسی کنیم

ما معتقدیم k = 2 ، به مرحله 5 بروید.

5 2. بیایید شرایط را بررسی کنیم. بیایید تنظیم کنیم، به مرحله 3 بروید.

3 1. بیایید شرایط را بررسی کنیم

4 1. بیایید تنظیم کنیم k = 0.

5 2. بیایید شرایط را بررسی کنیم

6 2. بیایید محاسبه کنیم

7 2. بیایید شرایط را بررسی کنیم

8 2. بیایید تنظیم کنیم

9 2. بیایید محاسبه کنیم

10 2. بیایید شرایط را بررسی کنیم

11 2. بیایید شرایط را بررسی کنیم

ما معتقدیم k = 1 و به مرحله 5 بروید.

5 3. بیایید شرایط را بررسی کنیم

6 3. بیایید محاسبه کنیم

7 3. بیایید شرایط را بررسی کنیم

8 3. تنظیم کنیم

9 3. بیایید محاسبه کنیم

10 3. بیایید شرایط را بررسی کنیم

11 3. بیایید شرایط را بررسی کنیم

تنظیم کنیم k = 2 و به مرحله 5 بروید.

5 4 . بیایید شرایط را بررسی کنیم

ما معتقدیم j = 2، x 20 = x 12 و به مرحله 3 بروید.

3 2. بیایید شرایط را بررسی کنیم

4 2 . تنظیم کنیم k = 0 .

5 4 . بیایید شرایط را بررسی کنیم

6 4. بیایید محاسبه کنیم

7 4. بیایید شرایط را بررسی کنیم

8 4. تنظیم کنیم

9 4. بیایید محاسبه کنیم

10 4. بیایید شرایط را بررسی کنیم و به مرحله 11 برویم.

11 4. بیایید شرایط را بررسی کنیم

شرایط در دو چرخه متوالی با اعداد برآورده می شود j = 2 و j -1= 1 . محاسبه کامل شد، نقطه پیدا شد

در شکل 6 نقطه به دست آمده توسط یک خط نقطه به هم متصل می شوند.

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

II. تجزیه و تحلیل نقطه x21.

در مثال 1.1 نشان داده شد که تابع f(x) به شدت محدب است، دارای حداقل منحصر به فرد و در نتیجه یک نقطه است تقریب یافت شده از نقطه حداقل جهانی است.

در تمام روش های گرادیان مورد بحث در بالا، دنباله نقاط (xk) به نقطه ثابت تابع همگرا می شود f(x) با گزاره های نسبتاً کلی در مورد ویژگی های این تابع. به ویژه، این قضیه صادق است:

قضیه. اگر تابع f(x) در زیر محدود شود، گرادیان آن شرط لیپشیتز () و انتخاب مقدار را برآورده می کند. tn تولید شده توسط یکی از روش های شرح داده شده در بالا، سپس هر نقطه شروع x 0 :

در .

در اجرای عملی طرح

k = 1، 2، ... n.

تکرار متوقف می شود اگر برای همه i، i = 1، 2، ...، n ، شرایطی مانند

,

کجا یک عدد مشخص است که دقت یافتن حداقل را مشخص می کند.

تحت شرایط قضیه، روش گرادیان همگرایی در تابع یا به کران پایینی دقیق را تضمین می کند (اگر تابع f(x) حداقل ندارد؛ برنج. 7) یا به مقدار تابع در یک نقطه ثابت که حد توالی است (x k). زمانی که یک زین در این مرحله محقق می شود، به دست آوردن مثال هایی دشوار نیست، و نه حداقل. در عمل، روش‌های نزول گرادیان با اطمینان نقاط زین را دور می‌زنند و حداقل تابع هدف (در حالت کلی، محلی) را پیدا می‌کنند.

نتیجه

نمونه‌هایی از روش‌های بهینه‌سازی بدون محدودیت گرادیان در بالا مورد بحث قرار گرفت. در نتیجه کار انجام شده می توان به نتایج زیر دست یافت:

1. مشکلات کم و بیش پیچیده یافتن اکستریم در صورت وجود محدودیت، رویکردها و روش های خاصی را می طلبد.

2. بسیاری از الگوریتم‌ها برای حل مسائل محدود شامل حداقل‌سازی بدون محدودیت به عنوان مرحله‌ای هستند.

3. روش های مختلففرودها در نحوه انتخاب جهت فرود و طول پله در این جهت با یکدیگر متفاوت هستند.

4. هنوز هیچ نظریه ای وجود ندارد که ویژگی های توابعی را که فرمول مسئله را توصیف می کند، در نظر بگیرد. اولویت باید به روش هایی داده شود که مدیریت آنها در فرآیند حل مشکل آسان تر باشد.

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

کتابشناسی - فهرست کتب

1. Kosorukov O.A. تحقیق در عملیات: کتاب درسی. 2003

2. Pantleev A.V. روش های بهینه سازی در مثال ها و مسائل: کتاب درسی. سود. 2005

3. Shishkin E.V. تحقیق در عملیات: کتاب درسی. 2006

4. آکولیچ آی.ال. برنامه نویسی ریاضی در مثال ها و مسائل. 1986

5. Ventzel E.S. تحقیق در عملیات. 1980

6. Ventzel E.S., Ovcharov L.A. نظریه احتمال و کاربردهای مهندسی آن 1988

©2015-2019 سایت
تمامی حقوق متعلق به نویسندگان آنها می باشد. این سایت ادعای نویسندگی ندارد، اما استفاده رایگان را فراهم می کند.
تاریخ ایجاد صفحه: 2017-07-02