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

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

()=f(x(k)-f(x(k)))

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

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

مختصات نقطه شروع x (0) داده شده است.

در نقطه x (k) ، k = 0، 1، 2، ...، مقدار گرادیان f (x (k)) محاسبه می شود.

اندازه گام k با کمینه سازی یک بعدی با توجه به تابع تعیین می شود

()=f(x(k)-f(x(k))).

مختصات نقطه x (k) تعیین می شود:

x i (k+1) = x i (k) - k f i (x (k))، i=1، …، n.

وضعیت توقف بررسی شد فرآیند تکرار شونده:

||f(x(k+1))|| .

اگر راضی باشد، محاسبات متوقف می شود. در غیر این صورت، انتقال به مرحله 1 انجام می شود. تفسیر هندسی روش شیب دارترین فرود در شکل نشان داده شده است. یکی

برنج. 2.1. بلوک دیاگرام شیب دارترین روش فرود.

پیاده سازی روش در برنامه:

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

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

نتیجه گیری: در مورد ما، روش در 7 تکرار همگرا شد. نقطه A7 (0.6641; -1.3313) یک نقطه افراطی است. روش جهات مزدوج. برای توابع درجه دوم می توانید یک روش گرادیان ایجاد کنید که در آن زمان همگرایی متناهی و برابر با تعداد متغیرهای n خواهد بود.

ما برخی از جهت ها و مزدوج ها را با توجه به ماتریس هس قطعی مثبت H می نامیم اگر:

پس یعنی.. بنابراین، با واحد H، جهت مزدوج به معنای عمود بر آنهاست. در حالت کلی، H غیر پیش پا افتاده است. AT مورد کلی conjugacy - این کاربرد ماتریس هس برای یک بردار است - به معنای چرخش این بردار توسط برخی از زوایای انبساط یا فشرده سازی آن است.

و اکنون یک بردار متعامد بر یک بردار است، یعنی مزدوج، متعامد بودن بردارها نیست، بلکه متعامد بودن یک بردار چرخانده شده است.i.i.

برنج. 2.3. بلوک دیاگرام روش جهات مزدوج.

پیاده سازی روش در برنامه: روش جهت های مزدوج.

برنج. 2.4. اجرای روش جهت های مزدوج.

برنج. 2.5. نمودار روش جهات مزدوج.

نتیجه گیری: نقطه A3 (0.6666; 1.3333-) در 3 تکرار یافت شد و نقطه اکسترموم است.

3. تجزیه و تحلیل روش های تعیین حداقل، حداکثر مقدار تابع در صورت وجود محدودیت

به یاد بیاورید که مشکل کلی بهینه سازی شرطی به این صورت است

f(x) ® min، x О W،

که در آن W یک زیر مجموعه مناسب از Rm است. دسته فرعی از مسائل با محدودیت‌های نوع برابری با این واقعیت متمایز می‌شوند که مجموعه  با محدودیت‌های شکل داده می‌شود.

f i (x) = 0، که در آن f i: R m ®R (i = 1، …، k).

بنابراینW = (x О R m: f i (x) = 0، i = 1، …، k).

نوشتن شاخص "0" برای تابع f برای ما راحت خواهد بود. بنابراین، مسئله بهینه‌سازی با محدودیت‌های نوع برابری به صورت نوشته می‌شود

f 0 (x) ® دقیقه، (3.1)

f i (x) = 0، i = 1، …، k. (3.2)

اگر اکنون تابعی را در Rm با مقادیر Rk با f نشان دهیم که نماد مختصات آن به شکل f(x) = (f 1 (x)، …، f k (x))، سپس (3.1)–( 3.2) را نیز می توان در فرم نوشت

f 0 (x) ® min، f(x) = Q.

از نظر هندسی، مشکل با محدودیت‌های نوع برابری، مسئله یافتن پایین‌ترین نقطه نمودار تابع f 0 بر روی منیفولد  است (شکل 3.1 را ببینید).

نقاطی که همه محدودیت ها را برآورده می کنند (یعنی نقاط مجموعه ) معمولاً قابل قبول نامیده می شوند. یک نقطه مجاز x* حداقل شرطی تابع f 0 تحت قیدهای f i (x) = 0، i = 1، ...، k (یا راه حلی برای مسئله (3.1)–(3.2) نامیده می شود، اگر برای تمام نقاط قابل قبول x f 0 (x *)  f 0 (x). (3.3)

اگر (3.3) فقط برای x قابل قبول واقع در محله ای V x * نقطه x* قانع شود، آنگاه از حداقل شرطی محلی صحبت می شود. مفاهیم حداقل های محلی و جهانی دقیق مشروط به روشی طبیعی تعریف می شوند.

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

اجازه دهید تابع 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 jn یک شماره اختصاص داد 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 می رویم.

9 01. محاسبه کنید 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. Venttsel 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 (х[ک])، 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 p، Zp، ...)، یعنی روش هر بار به روز می شود پمراحل

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

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

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

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

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

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

شیب ترین روش فرود مستلزم حل یک مسئله بهینه سازی تک بعدی در هر مرحله است. تمرین نشان می دهد که این روش اغلب به عملیات کمتری نسبت به روش گرادیان با یک گام ثابت نیاز دارد.

اما در وضعیت کلی، نرخ نظری همگرایی روش شیب دارترین نزول بالاتر از نرخ همگرایی روش گرادیان با گام ثابت (بهینه) نیست.

مثال های عددی

روش نزول گرادیان گام ثابت

برای مطالعه همگرایی روش نزول گرادیان با یک گام ثابت، تابع انتخاب شد:

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

روش گرادیان با تقسیم گام

برای مطالعه همگرایی روش نزول گرادیان با تقسیم گام (2)، تابع زیر انتخاب شد:

تقریب اولیه نقطه (10،10) است.

معیار توقف استفاده شده:

نتایج آزمایش در جدول نشان داده شده است:

معنی پارامتر	مقدار پارامتر	مقدار پارامتر	دقت به دست آورد	تعداد تکرارها

از نتایج به دست آمده می توان نتیجه گرفت که انتخاب بهینهپارامترها: اگرچه روش به انتخاب پارامترها حساسیت چندانی ندارد.

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

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

تقریب اولیه نقطه (10،10) است. معیار توقف استفاده شده:

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

این روش در 9 تکرار دقت 6e-8 را به دست آورد.

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

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

هنگام برنامه نویسی روش های نزولی گرادیان، باید در انتخاب پارامترها، یعنی

• · روش نزول گرادیان با گام ثابت: گام باید کمتر از 0.01 انتخاب شود، در غیر این صورت روش واگرا می شود (روش ممکن است حتی در این مرحله نیز واگرا شود، بسته به تابع مورد مطالعه).
• · روش گرادیان با تقسیم پله ای به انتخاب پارامترها حساسیت چندانی ندارد. یکی از گزینه های انتخاب:
• · شیب ترین روش فرود: به عنوان یک روش بهینه سازی تک بعدی، می توان از روش مقطع طلایی (در صورت امکان) استفاده کرد.

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

بیان مسئله بهینه سازی

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

اگر، پس مسئله بهینه سازی نامحدود نامیده می شود. اگر، پس مسئله بهینه سازی محدود نامیده می شود.

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

بیان روش

مشکل بهینه سازی زیر را در نظر بگیرید:

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

هر تقریب بعدی با فرمول محاسبه می شود:

تعریف. دو بردار و با توجه به یک ماتریس متقارن B مزدوج نامیده می شوند اگر

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

بردارهای پایه با فرمول های زیر محاسبه می شوند:

ضرایب به گونه ای انتخاب می شوند که بردارها و نسبت به A مزدوج باشند.

اگر با علامت گذاری کنیم، پس از چند بار ساده سازی، فرمول های نهایی مورد استفاده در کاربرد روش گرادیان مزدوج را در عمل به دست می آوریم:

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

روش همگرایی

اگر همه محاسبات دقیق و داده های اولیه دقیق باشند، روش به حل سیستم در بیش از تکرارها همگرا می شود، جایی که بعد سیستم است. تجزیه و تحلیل دقیق تر نشان می دهد که تعداد تکرارها تجاوز نمی کند، جایی که تعداد تکرارها متفاوت است مقادیر ویژهماتریس A. برای تخمین نرخ همگرایی، تخمین زیر (نسبتاً تقریبی) معتبر است:

در صورتی که تخمین‌هایی برای حداکثر و حداقل مقادیر ویژه ماتریس مشخص باشد، امکان تخمین نرخ هم‌گرایی را فراهم می‌کند. در عمل، معیار توقف زیر اغلب استفاده می‌شود:

پیچیدگی محاسباتی

عملیات در هر تکرار از روش انجام می شود. این تعداد عملیات برای محاسبه محصول مورد نیاز است - این زمان برترین روش در هر تکرار است. بقیه محاسبات به عملیات O(n) نیاز دارند. پیچیدگی محاسباتی کل روش از آن تجاوز نمی کند - زیرا تعداد تکرارها حداکثر n است.

مثال عددی

برای حل سیستم از روش گرادیان مزدوج استفاده می کنیم که C با استفاده از روش گرادیان مزدوج حل این سیستم در دو تکرار به دست می آید. مقادیر ویژهماتریس - 5، 5، -5 - دو مورد از آنها متفاوت است، بنابراین، طبق برآورد نظری، تعداد تکرارها نمی تواند از دو تجاوز کند.

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

روش گرادیان مزدوج به طور کلی

اجازه دهید اکنون اصلاحی از روش گرادیان مزدوج را برای موردی در نظر بگیریم که تابع کمینه شده درجه دوم نباشد: مشکل را حل خواهیم کرد:

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

را می توان با استفاده از یکی از سه فرمول محاسبه کرد:

1. - روش فلچر-ریوز

• 2. - روش پولاک-ریبیئر

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

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

روش همگرایی

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

مجموعه محدود است

مشتق شرط Lipschitz را با یک ثابت در برخی از محله ها برآورده می کند

مجموعه M: .

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

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

پیچیدگی محاسباتی

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

ما حداقل تابع را با روش گرادیان مزدوج جستجو می کنیم

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

روش فلچر-ریوز	روش پولاک-ریبر
تعداد تکرار	راه حل پیدا شد	مقدار تابع	تعداد تکرار	راه حل پیدا شد	مقدار تابع
		(5.01382198,3.9697932)			(5.03942877,4.00003512)
		(5.01056482,3.99018026)			(4.9915894,3.99999044)
		(4.9979991,4.00186173)			(5.00336181,4.0000018)
		(4.99898277,4.00094645)			(4.99846808,3.99999918)
		(4.99974658,4.0002358)			(4.99955034,3.99999976)

دو نسخه از روش گرادیان مزدوج پیاده سازی شده است: برای کمینه کردن یک تابع درجه دوم، و برای کمینه کردن یک تابع دلخواه. در حالت اول، روش توسط تابع برداری پیاده سازی می شود FindSolution(ماتریس الف، بردار ب) در اینجا A و b یک ماتریس و یک بردار هستند که در تعریف یک مسئله بهینه سازی درجه دوم ظاهر می شوند. برای به حداقل رساندن یک تابع دلخواه، یکی از دو تابع را می توان استفاده کرد: برداری FletcherRievesMethod(int spaceSize، تابع F، برداری (*GradF) (بردار )) بردار روش PolakRibiere(int spaceSize، تابع F، برداری (*GradF) (بردار )) پارامترهای هر دو تابع یکسان هستند و به معنای زیر هستند: spaceSize - بعد فضا (تعداد متغیرهایی که تابع کمینه شده به آنها بستگی دارد) F - اشاره گر به تابع کمینه شده. تابع باید به شکل double باشد<имя функции>(بردار ) GradF - یک اشاره گر به تابعی که گرادیان تابع کمینه شده را محاسبه می کند هر دو روش از یک تابع کمکی برای حل یک مسئله بهینه سازی یک بعدی استفاده می کنند. این برنامه بهینه سازی تک بعدی را با استفاده از روش مقطع طلایی اجرا می کند.

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

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

f(x 1، x 2) =

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

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

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 بدست می آوریم