در مسایل بهینه سازی ریاضی یکی از روش های حل، استفاده از دوگان مسئله می باشد یعنی حل مسئله بهینه سازی از طریق دوگان. یعنی ابتدا لاگرانژی مسئله اصلی را می نویسیم و سپس تابع دوگان مسئله را با کمک لاگرانژی می نویسیم و سپس مسئله دوگان را با کمک تابع دوگان تعریف می کنیم و در نهایت با حل مسئله دوگان می توانیم به حل مسئله اصلی برسیم. در این مبحث سعی می کنیم توضیح دهیم در صورتی که شرط اسلیتر در مسئله اصلی برقرار باشد آنگاه پاسخ مسئله دوگان قطعاً پاسخ مسئله اصلی است و به اصطلاح دوگانی قوی برقرار می باشد. [ ۱]
اگر پاسخ مسئله اصلی را d ∗ و پاسخ مسئله دوگان را p ∗ بنامیم در آن صورت اختلاف بین آن دو را فاصله دوگانی می نامیم.
همیشه برای تمامی مسایل بهینه سازی محدب و غیر محدب دوگانی ضعیف برقرار است یعنی d ∗ = max λ ≥ 0 , ν g ( λ , ν ) =< inf f 0 = p ∗ ولی دوگانی قوی تنها زمانی برقرار است که d ∗ = max λ ≥ 0 , ν g ( λ , ν ) = inf f 0 = p ∗ و این در مسایل بهینه سازی محدب زمانی اتفاق می افتد که شرط اسلیتر برقرار باشد.
در مسایل بهینه سازی استاندارد که به شکل زیر می باشد
طبق شرط اسلیتر اگر در مسئله فوق حداقل یک نقط شدنی وجود داشته باشد که در دامنه تابع هدف صدق کند و علاوه بر این در قیود نامساوی و مساوی به صوت زیر هم صدق کند لذا می توان گفت شرط اسلیتر برای مسئله فوق صادق است و دوگانی قوی برقرار می باشد. [ ۲]
همان طور که در شرط بالا دیده می شود علامت مساوی از قید نامساوی حذف شده است. . به عبارتی دیگر می توان گفت اگر حداقل یک نقطه "غیر مرزی " در منطقه شدنی ( feasible set ) وجود داشته باشد در ان صورت شرط اسلیتر صادق و به تبع آن دوگانی قوی برقرار است.
در مورد قیود نامساوی های خطی یا افاین شرط اسلیتر همان شرط شدنی ( feasibility ) می باشد. یعنی نیاز به برداشتن علامت تساوی از قید نامساوی نیست. به عبارت دیگر می توان گفت که در مسایل بهینه سازی محدب با قیود نامساوی خطی و موجود بودن ناحیه شدنی حتماً شرایط اسلیتر برقرار است.
ازآنجایی که در مسایل بهینه سازی محدب که دارای ناحیه شدنی می باشند حتماً شرط دوگانی قوی برقرار است پس شرط اسلیتر برای تمامی مسایل بهینه سازی محدب صادق است. تنها برای مسایل بهینه سازی غیر محدب برای آنکه بدانیم پاسخ مسئله بهینه سازی با پاسخ مسئله دوگان یکی هست یا نه از شرط اسلیتر می توان کمک گرفت.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفاگر پاسخ مسئله اصلی را d ∗ و پاسخ مسئله دوگان را p ∗ بنامیم در آن صورت اختلاف بین آن دو را فاصله دوگانی می نامیم.
همیشه برای تمامی مسایل بهینه سازی محدب و غیر محدب دوگانی ضعیف برقرار است یعنی d ∗ = max λ ≥ 0 , ν g ( λ , ν ) =< inf f 0 = p ∗ ولی دوگانی قوی تنها زمانی برقرار است که d ∗ = max λ ≥ 0 , ν g ( λ , ν ) = inf f 0 = p ∗ و این در مسایل بهینه سازی محدب زمانی اتفاق می افتد که شرط اسلیتر برقرار باشد.
در مسایل بهینه سازی استاندارد که به شکل زیر می باشد
طبق شرط اسلیتر اگر در مسئله فوق حداقل یک نقط شدنی وجود داشته باشد که در دامنه تابع هدف صدق کند و علاوه بر این در قیود نامساوی و مساوی به صوت زیر هم صدق کند لذا می توان گفت شرط اسلیتر برای مسئله فوق صادق است و دوگانی قوی برقرار می باشد. [ ۲]
همان طور که در شرط بالا دیده می شود علامت مساوی از قید نامساوی حذف شده است. . به عبارتی دیگر می توان گفت اگر حداقل یک نقطه "غیر مرزی " در منطقه شدنی ( feasible set ) وجود داشته باشد در ان صورت شرط اسلیتر صادق و به تبع آن دوگانی قوی برقرار است.
در مورد قیود نامساوی های خطی یا افاین شرط اسلیتر همان شرط شدنی ( feasibility ) می باشد. یعنی نیاز به برداشتن علامت تساوی از قید نامساوی نیست. به عبارت دیگر می توان گفت که در مسایل بهینه سازی محدب با قیود نامساوی خطی و موجود بودن ناحیه شدنی حتماً شرایط اسلیتر برقرار است.
ازآنجایی که در مسایل بهینه سازی محدب که دارای ناحیه شدنی می باشند حتماً شرط دوگانی قوی برقرار است پس شرط اسلیتر برای تمامی مسایل بهینه سازی محدب صادق است. تنها برای مسایل بهینه سازی غیر محدب برای آنکه بدانیم پاسخ مسئله بهینه سازی با پاسخ مسئله دوگان یکی هست یا نه از شرط اسلیتر می توان کمک گرفت.
