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

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

اجازه دهید تابع f(x) R n

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

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

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

نقطه کجاست x 0 توسط کاربر تنظیم شده است. اندازه گام t k برای هر مقدار تعریف شده است ک از شرایط

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

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

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

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

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

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

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 تنظیم شده توسط کاربر، اندازه گام t k از شرط انتخاب شده است

یا .

اگر شرایط انتخاب شده در حال حاضر t k اجرا نمی شود، مرحله نصف می شود و نقطه دوباره محاسبه می شود. به راحتی می توان دید که برای یک 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) \u003d 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 .

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

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

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

60 . بیایید تنظیم کنیم t 0 \u003d 0.5 .

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

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

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

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

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

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

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

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

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

6 1 . بیایید تنظیم کنیم t 1 \u003d 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 . بیایید تنظیم کنیم t2 =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 \u003d 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) و کوچکترین مقدار آن در R2 . ■

مثال 2

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

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

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

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

2. قرار دهید k = 0 .

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

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

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

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

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

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

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

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

70. بیایید پیدا کنیم

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. تعیین یک نقطه x jk ، که در آن حداقل یکی از معیارهای فسخ رعایت شده باشد.

1. تنظیم کنید

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

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

سی . بیایید تحقق شرط را بررسی کنیم

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

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

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

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

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

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

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

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

901 . محاسبه کنید x 01 گام به گام

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

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

ما معتقدیم 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 \u003d 2، x 20 \u003d 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) کاملاً محدب است، دارای یک حداقل واحد و از این رو یک نقطه است تقریب یافت شده از نقطه حداقل جهانی است.

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

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

در .

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

k=1، 2، …n.

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

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

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

نتیجه

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

f" (x ) = (df(x)/dx 1 , …, qf(х)/dx n) T .

این بردار عمود بر صفحه عبور از نقطه است ایکس، و مماس بر سطح تراز تابع f(x)عبور از یک نقطه ایکس.در هر نقطه از چنین سطحی، تابع f(x)همان ارزش را به خود می گیرد. با معادل سازی تابع با مقادیر ثابت مختلف C 0 , C 1 , ... , مجموعه ای از سطوح را به دست می آوریم که توپولوژی آن را مشخص می کند (شکل 2.8).

برنج. 2.8. شیب

بردار گرادیان به سمت سریعترین افزایش تابع در یک نقطه معین هدایت می شود. بردار مقابل گرادیان (-f'(x)) ، تماس گرفت ضد گرادیانو در جهت سریعترین کاهش در تابع هدایت می شود. در حداقل نقطه، گرادیان تابع صفر است. روش‌های مرتبه اول که روش‌های گرادیان و کمینه‌سازی نیز نامیده می‌شوند، بر اساس ویژگی‌های گرادیان هستند. استفاده از این روش ها در حالت کلی به فرد اجازه می دهد تا حداقل نقطه محلی تابع را تعیین کند.

بدیهی است که اگر اطلاعات اضافی وجود نداشته باشد، از نقطه شروع ایکسهوشمندانه برای رفتن به نقطه ایکس، دروغ گفتن در جهت ضد گرادیان - سریعترین کاهش عملکرد. انتخاب به عنوان جهت نزول آر[ک] ضد گرادیان - f'(x[k] ) در نقطه ایکس[ک]، یک فرآیند تکراری از فرم به دست می آوریم

ایکس[ k+ 1] = ایکس[ک]-a k f"(x[k] ) , یک ک > 0; ک=0, 1, 2, ...

به صورت مختصات، این فرآیند به صورت زیر نوشته می شود:

x i [ ک+1]=x i[ک] - یک کf(x[k] ) /x i

i = 1، ...، n; ک= 0, 1, 2,...

به عنوان یک معیار توقف فرآیند تکرار شوندهیا از تحقق شرط صغری افزایش برهان استفاده کنید || ایکس[ک+l] -ایکس[ک] || <= e , либо выполнение условия малости градиента

|| f'(x[ک+l] ) || <= g ,

در اینجا e و g مقادیر کمی داده شده است.

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

در روش گام ثابت، مقداری گام ثابت برای همه تکرارها انتخاب می شود. قدم بسیار کوچک یک کتضمین می کند که تابع کاهش می یابد، یعنی تحقق نابرابری

f(x[ ک+1]) = f(x[k]- a k f'(x[k] )) < f(x[k] ) .

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

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

هنگام استفاده از روش تندترین فروددر هر تکرار، اندازه گام یک کاز حداقل شرایط تابع انتخاب می شود f(x)در جهت نزول، یعنی.
f(x[ک]–a k 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]:

x i [ k+ 1]= x i[ک]- a k f' i (x[ک])، i = 1،...، n.

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

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

دی جی (a)/da = -f'(x[k+ 1]f'(x[ک]) = 0.

برنج. 2.9. تفسیر هندسی روش شیب دارترین فرود

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

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

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

برنج. 2.10. عملکرد دره

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

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

f(x) = (x، Hx) + (b، x) + a

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

طبق تعریف، دو n-بردار بعدی ایکسو درتماس گرفت مزدوجبا توجه به ماتریس اچ(یا اچ-ضمیمه) اگر محصول اسکالر (ایکس, خوب) = 0.اینجا H -ماتریس قطعی مثبت متقارن اندازه پایکس پ.

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

جهت ها آر[ک] با فرمول های زیر محاسبه می شود:

پ[ ک] = -f'(x[ک]) +bk-1 پ[ک-l]، ک>= 1;

p=- f’(ایکس) .

ارزش ها ب ک-1 طوری انتخاب می شوند که جهت ها پ[ک], آر[ک-1] بودند اچ- مزدوج :

(پ[ک], HP[k- 1])= 0.

در نتیجه برای تابع درجه دوم

فرآیند کمینه سازی تکراری شکل دارد

ایکس[ ک+l] =x[ک]+a kp[ک],

جایی که آر[ک] - جهت نزول k-گام متر؛ و ک -اندازه گام. مورد دوم از حداقل شرایط تابع انتخاب می شود f(x)بر آدر جهت حرکت، یعنی در نتیجه حل مسئله کمینه سازی یک بعدی:

f(x[ ک] + a k p[ک]) = f(x[ک] + ar [ک]) .

برای تابع درجه دوم

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

1. در نقطه ایکسمحاسبه شد پ = -f'(x) .

2. روشن k-گام متر با توجه به فرمول های بالا مرحله را تعیین می کند آک . و نقطه ایکس[k+ 1].

3. مقادیر محاسبه می شود f(x[ک+1]) و f'(x[ک+1]) .

4. اگر f'(x) = 0، سپس نقطه ایکس[ک+1] حداقل نقطه تابع است f(x).در غیر این صورت مسیر جدیدی مشخص می شود پ[ک+l] از رابطه

و به تکرار بعدی بروید. این روش حداقل یک تابع درجه دوم را در حداکثر می یابد پمراحل هنگام به حداقل رساندن توابع غیر درجه دوم، روش فلچر-ریوز از یک محدود تکرار می شود. در آن صورت، پس از (n+ 1) تکرار روش 1-4 در چرخه هایی با جایگزینی تکرار می شود ایکسبر روی ایکس[پ+1]، و محاسبات زمانی به پایان می‌رسند که در کجا یک عدد داده شده باشد. در این مورد، از اصلاح روش زیر استفاده می شود:

ایکس[ ک+l] = x[ک]+a kp[ک],

پ[ ک] = -f'(x[ک])+ ب k- 1 پ[ک-l]، ک>= 1;

p = -f'( ایکس);

f(x[ ک] + a k p[ک]) = f(x[ک] +ap[ک];

اینجا من- مجموعه ای از شاخص ها: من= (0، n، 2 n، zp، ...)، یعنی روش هر بار به روز می شود پمراحل

حس هندسیروش گرادیان مزدوج به شرح زیر است (شکل 2.11). از نقطه شروع معین ایکسدر جهت پایین آمدن آر = -f"(x). در نقطه ایکسبردار گرادیان تعریف شده است f" (x). از آنجا که ایکسحداقل نقطه تابع در جهت است آر, سپس f'(x) متعامد به برداری آر. سپس بردار پیدا می شود آر , اچ- مزدوج به آر. بعد، حداقل تابع در امتداد جهت پیدا می شود آرو غیره.

برنج. 2.11 . مسیر نزول در روش گرادیان مزدوج

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

مثال 6.8.3-1. حداقل تابع Q(x,y) را با استفاده از روش GDS بیابید.

فرض کنید Q(x,y) = x 2 +2y 2 ; x 0 = 2؛ y 0 = 1.

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

بیایید یک تکرار طبق الگوریتم انجام دهیم.

1. Q(x0,y0) = 6.

2. وقتی x \u003d x 0 و y \u003d y 0،

3. مرحله l k \u003d l 0 \u003d 0.5

پس 4< 8, следовательно, условие сходимости не выполняется и требуется, уменьшив шаг (l=l /2), повторять п.п.3-4 до выполнения условия сходимости. То есть, полученный шаг используется для нахождения следующей точки траектории спуска.

ماهیت روش به شرح زیر است. از نقطه انتخاب شده (x 0 ,y 0) فرود در جهت ضد گرادیان انجام می شود تا به حداقل مقدار تابع هدف Q(x, y) در طول تیر برسد (شکل 6.8.4- 1). در نقطه پیدا شده، پرتو خط تراز را لمس می کند. سپس از این نقطه فرود در جهت ضد گرادیان (عمود بر خط تراز) انجام می شود تا اینکه تیر مربوطه با خط تراز عبوری از آن در نقطه جدید برخورد کند و به همین ترتیب.

بیان تابع هدف Q(x, y) تا مرحله l. در همان زمان، تابع هدف را در یک مرحله خاص به عنوان تابعی از یک متغیر نشان می‌دهیم، یعنی. اندازه گام

اندازه گام در هر تکرار از شرط حداقل تعیین می شود:

Min((l)) l k = l*(xk، y k)، l >0.

بنابراین، در هر تکرار، انتخاب مرحله l k مستلزم حل یک مسئله بهینه سازی یک بعدی است. با توجه به روش حل این مشکل، موارد زیر وجود دارد:

· روش تحلیلی(NSA)؛

· روش عددی (NCh).

در روش NSA، مقدار گام از شرط به دست می‌آید و در روش NSS، با استفاده از یکی از روش‌های بهینه‌سازی یک‌بعدی، مقدار l k بر روی یک قطعه با دقت داده شده به دست می‌آید.

مثال 6.8.4-1. حداقل تابع Q(x,y)=x 2 + 2y 2 را با دقت e=0.1 در شرایط اولیه بیابید: x 0 =2; y 0 = 1.

بیایید یک تکرار با روش انجام دهیم NSA.

=(x-2lx) 2 +2(y-4ly) 2 = x 2 -4lx 2 +4l 2 x 2 +2y 2 -16ly 2 +32l 2 y 2 .

از شرط ¢(l)=0 مقدار l* را پیدا می کنیم:

تابع به دست آمده l=l(x,y) به شما امکان می دهد مقدار l را پیدا کنید. برای x=2 و y=1 l=0.3333 داریم.

مقادیر مختصات نقطه بعدی را محاسبه کنید:

بیایید برآورده شدن معیار خاتمه تکرار را برای k=1 بررسی کنیم:

از آنجایی که |2*0.6666|>0.1 و |-0.3333*4|>0.1، شرایط خاتمه دادن به فرآیند تکرار وجود ندارد، یعنی. حداقل پیدا نشد بنابراین باید مقدار جدید l را در x=x 1 و y=y 1 محاسبه کنید و مختصات نقطه نزول بعدی را بدست آورید. محاسبات تا زمانی که شرایط پایان فرود برآورده شود ادامه دارد.

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

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

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

AT شیب دارترین روش فرودیک بردار به عنوان جهت جستجو انتخاب می شود که جهت آن خلاف جهت بردار گرادیان تابع ▽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) \u003d 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) \u003d 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)
f'(X 2) \u003d 11.76 - 6.12λ 1 \u003d 0
λ 1 = 0.52 بدست می آوریم

در این نوع از روش گرادیان، دنباله کمینه سازی (X k ) نیز طبق قانون (2.22) ساخته شده است. با این حال، اندازه گام a k در نتیجه حل مسئله کمینه سازی یک بعدی کمکی یافت می شود.

min(j k (a) | a>0)، (2.27)

جایی که j k (a)=f(X k - a· (X k)). بنابراین، در هر تکرار در جهت ضد گرادیان فرود جامع انجام می شود. برای حل مسئله (2.27)، می توان از یکی از روش های جستجوی تک بعدی که در بخش 1 توضیح داده شده است استفاده کرد، به عنوان مثال، روش جستجوی بیتی یا روش مقطع طلایی.

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

مرحله 0پارامتر دقت e>0 را تنظیم کنید، X 0 нE n را انتخاب کنید، k=0 را قرار دهید.

مرحله 1.(X k) را پیدا کرده و شرط دستیابی به دقت داده شده || را بررسی کنید (x k) ||£ e. اگر اینطور است، به مرحله 3 و در غیر این صورت به مرحله 2 بروید.

گام 2حل مسئله (2.27)، یعنی. یک k پیدا کن نقطه بعدی را پیدا کنید، k=k+1 را قرار دهید و به مرحله 1 بروید.

مرحله 3محاسبه را با قرار دادن X * = X k , f * = f(X k) خاتمه دهید.

مثال معمولی

به حداقل رساندن عملکرد

f(x)=x 1 2 +4x 2 2 -6x 1 -8x 2 +13; (2.28)

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

با حل آن یک نقطه ثابت X*=(3;1) بدست می آوریم. در مرحله بعد، تحقق شرط کافی را بررسی می کنیم که برای آن ماتریس مشتقات دوم را پیدا می کنیم

از آنجایی که طبق معیار سیلوستر، این ماتریس به صورت مثبت در " تعریف می شود، پس نقطه X* حداقل نقطه تابع f(X) است. حداقل مقدار f *=f(X*)=0 این راه حل دقیق مشکل است (11).

بیایید یک تکرار از روش را اجرا کنیم شیب نزولبرای (2.28). نقطه شروع X 0 =(1;0) را انتخاب می کنیم، مرحله اولیه a=1 و پارامتر l=0.5 را تنظیم می کنیم. بیایید f(X 0)=8 را محاسبه کنیم.

گرادیان تابع f(X) را در نقطه X 0 پیدا کنید

(X 0) = = (2.29)

یک نقطه جدید X=X 0 -a (X 0) را با محاسبه مختصات آن تعریف کنید

x 1 =

x 2 = (2.30)

f(X)= f(X 0 -a (X 0))=200 را محاسبه کنید. از آنجایی که f(X)>f(X 0)، پس تقسیم مرحله را انجام می دهیم و a=a·l=1·0.5=0.5 را تنظیم می کنیم. دوباره با فرمول های (2.30) x 1 =1+4a=3 را محاسبه می کنیم. x 2 =8a=4 و مقدار f(X)=39 را پیدا کنید. از آنجایی که دوباره f(X)>f(X 0) اندازه گام را نیز کاهش می دهیم و a=a·l=0.5·0.5=0.25 را تنظیم می کنیم. یک نقطه جدید را با مختصات x 1 =1+4 0.25=2 محاسبه می کنیم. x 2 \u003d 8 0.25 \u003d 2 و مقدار تابع در این نقطه f (X) \u003d 5. از آنجایی که شرط کاهش f(X)

بیایید یک تکرار روی متد اجرا کنیم تندترین فرودبرای (2.28) با همان نقطه اولیه X 0 = (1; 0). با استفاده از گرادیان از قبل یافت شده (2.29)، پیدا می کنیم

X \u003d X 0 -a (X 0)

و تابع j 0 (a)=f(X 0 -a· (X 0))=(4a-2) 2 +4(8a-1) 2 را بسازید. به حداقل رساندن آن با شرط لازم

j 0 ¢(a)=8 (4a - 2)+64 (8a - 1)=0

مقدار بهینه مرحله a 0 =5/34 را پیدا می کنیم.

نقطه توالی کمینه سازی را تعیین کنید

X 1 \u003d X 0 -a 0 (X 0) .