شرط اسلیتر در مسائل بهینه‌سازی محدب

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

فاصله دوگانی

اگر پاسخ مسئله اصلی را $d^{*}$ و پاسخ مسئله دوگان را $p^{*}$ بنامیم در آن صورت اختلاف بین آن دو را فاصله دوگانی می‌نامیم.

دوگانی ضعیف و قوی

همیشه برای تمامی مسایل بهینه‌سازی محدب و غیر محدب دوگانی ضعیف برقرار است یعنی $d^{*}=\max _{\lambda \geq 0,\nu }g(\lambda ,\nu )=<\inf f_{0}=p^{*}$ ولی دوگانی قوی تنها زمانی برقرار است که $d^{*}=\max _{\lambda \geq 0,\nu }g(\lambda ,\nu )=\inf f_{0}=p^{*}$ و این در مسایل بهینه‌سازی محدب زمانی اتفاق می‌افتد که شرط اسلیتر برقرار باشد.

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

در مسایل بهینه‌سازی استاندارد که به شکل زیر می‌باشد

${\begin{aligned}{\text{minimize }}&f_{0}(x)\\{\text{subject to }}&f_{i}(x)\leq 0,\ i\in \left\{1,\dots ,m\right\}\\&h_{j}(x)=0,\ j\in \left\{1,\dots ,l\right\}\end{aligned}}$

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

$f_{i}(x^{*})<_{K_{i}}0,i=1,\ldots ,m$

$h_{j}(x^{*})=0,{\text{ for }}j=1,\ldots ,\ell \,\!$

همان‌طور که در شرط بالا دیده می‌شود علامت مساوی از قید نامساوی حذف شده‌است.. به عبارتی دیگر می‌توان گفت اگر حداقل یک نقطه "غیر مرزی " در منطقه شدنی (feasible set) وجود داشته باشد در ان صورت شرط اسلیتر صادق و به تبع آن دوگانی قوی برقرار است.

شرط اسلیتر برای مسایل بهینه‌سازی با قیود نامساوی خطی (افاین)

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

شرط اسلیتر برای مسایل بهینه‌سازی محدب

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