ساده‌سازی لاگرانژی

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

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

مسئلهٔ بیشینه کردن تابع لاگرانژی از متغیرهای دوگانه (ضریب‌های لاگرانژی) مسئله دوگانه لاگرانژی است.

توضیحات ریاضی

فرض کنید به ما یک مسئلهٔ برنامه‌نویسی خطی داده شده به شکل زیر داده شده است که $x\in {ℝ}^n$$x\in {ℝ}^n$و $A\in {ℝ}^{m,n}$:

مقدار $c^{T}x$را بیشینه کنید

با فرض این محدودیت که:

$Ax\le b$

اگر محدودیت‌های موجود در A را به دو دسته‌ی زیر تقسیم کنیم:

• $A_1\in {ℝ}^{m_1,n}$
• $A_2\in {ℝ}^{m_2,n}$

و با فرض اینکه می‌دانیم $m_1+m_2=m$است، می‌توان معادله را به صورت زیر نوشت:

مقدار $c^{T}x$را بیشینه کنید

با فرض این محدودیت‌ها که:

1. $A_{1}x\le b_1$
2. $A_{2}x\le b_2$

می‌توانیم محدودیت شماره‌ی ۲ را در صورت مسئله اعمال کنیم و مسئله را به این صورت تغییر دهیم:

مقدار $c^{T}x+{\lambda }^T(b_2-A_{2}x)$را بیشینه کنید

با فرض این محدودیت که:

1. $A_{1}x\le b_1$

اگر لاندا $\lambda =({\lambda }_1,\dots ,{\lambda }_{m_2})$ را به صورت وزن‌های نامنفی فرض کنیم، اگر محدودیت شماره‌ی ۲ را نقض کنیم جریمه خواهیم خورد و اگر محدودیت مورد نظر را ارضا کنیم شامل پاداش خواهیم شد.

این روش ساده‌سازی لاگرانژی از مشکل اصلی ما نامیده می‌شود.

محدودیت‌های راه حل ساده‌سازی لاگرانژ

یکی از ویژگی‌های کاربردی این راه‌حل آن است که برای هر مجموعه‌ی ثابت از مقادیر $\tilde{\lambda }$نتیجه‌ی بهینه‌ی ساده‌سازی لاگرانژی، از نتیجه‌ی بهینه‌ی مسئله‌ی اصلی کوچکتر نخواهد بود. برای آن‌که این موضوع اثبات شود، $\hat{x}$را راه حل بهینه‌ی مسئله‌ی اصلی در نظر بگیرید و $\overline{x}$را راه حل بهینه‌ی ساده‌سازی لاگرانژی در نظر بگیرید. در ادامه خواهیم داشت:

• $c^T\hat{x}\le c^T\hat{x}+{\tilde{\lambda }}^T(b_2-A_2\hat{x})\le c^T\overline{x}+{\tilde{\lambda }}^T(b_2-A_2\overline{x})$

نامعادله‌ی اول درست است زیرا $\hat{x}$در مسئله‌ی اصلی قابل قبول است و نامعادله‌ی دوم صحیح است زیرا $\overline{x}$اه حل بهینه برای آساده‌سازی اگرانژی است.

حرکت به سوی حل مسئله اصلی

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

$P(\lambda )$را کمینه کنید

با در نظر گرفتن محدودیت:

• $\lambda \ge 0$

در حالی که $P(\lambda )$را به صورت زیر تعریف می‌کنیم:

$c^{T}x+{\lambda }^T(b_2-A_{2}x)$را بیشینه کنید

با در نظر گرفتن نامعادله‌ی:

$A_{1}x\le b_1$

در نتیجه یک الگوریتم ساده‌سازی لاگرانژی به این صورت کار می‌کند که بازه‌ای از مقادیر $\lambda$قابل قبول را جستجو می‌کند تا نتیجه‌ی تولید شده توسط مسئله‌ی درونی $P$را کمینه کند. هر مقدار بازگشتی توسط $P$یک کاندیدا برای حد بالای مسئله است، که کوچکترین مقدار آن به عنوان بهترین حد بالا در نظر گرفته می‌شود. اگر افزون بر این، از یک تابع اکتشافی هیوریستیک (که با استفاده از مقدار $\overline{x}$که از $P$برگشته‌اند، دسته‌بندی شده‌اند.) استفاده کنیم، می‌توانیم روی مسئله تکرار انجام دهیم تا بهترین حد بالا و هزینه‌ی بهترین راه‌حل قابل قبول به اندازه‌ای که می‌خواهیم به جواب اصلی نزدیک شوند.

روش‌های مرتبط

روش تقویت‌شده لاگرانژی از نظر ساختاری کاملاً شبیه به روش ساده‌سازی لاگرانژی است، اما یک جمله به آن اضافه می‌کند و پارامترهای دوگانه $\lambda$را با روشی اصولی‌تر به روز می کند. این روش در دهه 1970 معرفی شد و از آن موقع به صورت گسترده مورد استفاده قرار گرفته است.

روش مجازات از متغیرهای دوگانه استفاده نمی‌کند. بلکه محدودیت ها را حذف می‌کند و در عوض انحراف از محدودیت مجازات می‌کند. این روش از نظر مفهومی ساده است اما معمولاً روشهای تقویت‌شده لاگرانژی در عمل ترجیح داده می شوند زیرا روش مجازات در وضعیت‌های بدتنظیم‌شده به خوبی کار نمی‌کند.

منابع

کتاب‌ها

Bertsekas, Dimitri P. (1999). Nonlinear Programming: 2nd Edition. Athena Scientific. الگو:IsbnISBN 1-886529-00-0.