موضوع مقاله: دوگانگی (بهینه‌سازی) | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # دوگانگی (بهینه‌سازی) | مقدمه: Von Neumann اشاره کرد که از اطلاعات نظریه بازی‌های خودش استفاده کرده‌است و پیش‌بینی کرده که ماتریس مجموع صفر دو نفره معادل با برنامه‌ریزی خطی است. | ## بخش 1: دوگانگی (بهینه‌سازی) | مسئلهٔ دوگانگی لاگرانژی با تشکیل لاگرانژین (Lagrangian)، با استفاده از ضرایب نامنفی لاگرانژی، به منظور افزودن قیدها به تابع هدف و سپس حل کردن آن برای برخی مقادیر متغیر اصلی که لاگرانژین را کمینه می‌کند، به دست می‌آید. در چنین مسائلی m محدودیت وجود دارد که هر کدام یک کران بالا بر ترکیب خطی n متغیر اعمال می‌کند. یک راه حل عبارت است از برداری (یک لیست) از n مقدار که مقدار بیشینه برای تابع هدف را حاصل می‌کند. در مسئلهٔ دوگان، تابع هدف یک ترکیب خطی از m مقدار است که مشخص‌کنندهٔ محدودهٔ m محدودیت مسئلهٔ اصلی است. n محدودیت دوگان وجود دارند که هر کدام یک کران پایین بر ترکیب خطی m متغیر دوگان اعمال می‌کند. رابطهٔ بین مسئلهٔ اصلی و مسئلهٔ دوگان در حالت خطی در مسئلهٔ اصلی از هر نقطهٔ زیر بهینهٔ که تمام محدودیت‌ها را فراهم می‌کند یک جهت یا زیر فضایی از جهت‌ها برای حرکت وجود دارد که تابع هدف را افزایش می‌دهد. آنچنان که بیان شده‌است حرکت کردن در هر چنین جهتی، تفاوت بین راه حل پیشنهادی و یک یا چند محدودیت را حذف می‌کند. یک امکان‌ناپذیر از راه حل پیشنهادی همانی است که از یک یا چند محدودیت فراتر می‌رود. در مسئلهٔ دوگان، بردار دوگان ضرب می‌کند ثابت‌هایی را که موقعیت محدودیت‌ها را در مسئلهٔ اصلی مشخص می‌کنند. تغییر دادن تابع دوگان در مسئلهٔ دوگان معادل با بازبینی کران‌های بالا در مسئلهٔ اصلی است. به این معنا که بردار دوگان کمینه شده تا تفاوت بین مکان پیشنهادی محدودیت‌ها و موقعیت بهینهٔ واقعی از میان بردارد. | ## بخش 2: دوگانگی (بهینه‌سازی) | چنین مقداری موقعیت‌های پیشنهادی یک یا تعداد بیشتری از محدودیت‌ها را در جاهایی که موقعیت بهینهٔ واقعی را در بر نمی‌گیرد، تعیین می‌کند. به منظور کسب اطمینان از اینکه مقدار بیشینهٔ سراسری یک مسئلهٔ غیر خطی می‌تواند به آسانی یافت شود، فرمولاسیون مسئله معمولاً به این نیاز دارد که تابع محدب بوده و مجموعه‌های سطح پایین فشرده داشته باشد. این شرایط، شرط‌های ضروری برای یافتن بهینه‌های محلی برای مسائل برنامه‌ریزی غیر خطی را ارائه می‌دهد. یک راه حل بهینه آنی است که یک بهینهٔ محلی است ولی احتمالاً یک بهینهٔ سراسری نیست. اصل قوی لاگرانژی: دوگانگی لاگرانژی برای یک مسئلهٔ برنامه‌ریزی غیر خطی داده شده با فرم استاندارد با دامنهٔ که Interior غیر تهی، دارد، تابع لاگرانژین به صورت تعریف می‌شود. مسائل محدب برای یک مسئلهٔ کمینه‌سازی محدب با شرایط نامعادلهٔ مسئلهٔ دوگان لاگرانژی است که تابع هدف تابع دوگان لاگرانژ است. به شرط این که توابع و به صورت پیوسته مشتق پذیر باشند، اینفیمم هنگامی که گرادیان برابر صفر باشد رخ می‌دهد. شاید حل این مسئله با کامپیوتر دشوار باشد، زیرا تابع هدف در متغیرهای مشترک مقعر نیست. همچنین شرط تساوی معمولاً غیر خطی است، بنابراین مسئلهٔ دوگان Wolfe به‌طور معمول یک مسئلهٔ بهینه‌سازی غیر مقعر است. حل مسئله بهینه‌سازی از طریق دوگان در حل مسئله بهینه‌سازی به روش معادل سازی، یک مسئله معادل برای مسئله استاندارد تعریف می‌کنیم که پاسخ آن بسیار راحت‌تر از مسئله اولیه به دست می‌آید؛ برای به دست آوردن مسئله معادل روند مشخصی وجود ندارد اما برای برخلاف آن در حل مسئله بهینه‌سازی از طریق دوگان یک روند مشخص برای به دست آوردن مسئله دوگان وجود دارد. پاسخ این مسئله یک کران پایین روی مسئله اصلی ارائه می‌دهد و در حالت محدب دقیقاً همان جواب است. | ## بخش 3: دوگانگی (بهینه‌سازی) | مسئله اصلی فرم استاندارد یک مسئله بهینه‌سازی به صورت زیر می‌باشد:به این مسئله، مسئله اصلی می‌گویند. تابع لاگرانژی تابع لاگرانژی که یک مجموعه وزن دار از تابع هدف و قیود است را بفرم زیر نمایش می‌دهند:لاگرانژی تابعی از پارامتر اولیه و یک متغیر اضافه می‌باشد که به آن متغیر دوگان گویند. تابع دوگان با کمک تابع لاگرانژی می‌توان یک تابع جدید (تنها از متغیر دوگان) بنام تابع دوگان ساخت. این تابع را می‌توان بفرم زیر نمایش داد:g به صورت حداقل نقطه‌ای تعریف می‌شود پس مقعر است. در واقع مسئله فوق نامقید، با تابع هدف محدب (از متغیر) است، بنابراین بهینهٔ سراسری را می‌توان با برابر صفر قرار دادن مشتق تابع هدف نسبت به به دست آورد. مسئله دوگان از آنجا که کران پایین برای هر صادق است، باید به دنبال بهترین آن بود، که آن بزرگترین کران پایین است:به دست آوردن کران پایین از طریق مسئله دوگان ساده‌تر است زیرا محاسبه با قیود کمتری همراه است. مسئله پیدا کردن بهترین کران پایین به صورت زیر تعریف می‌شود:این مسئله، مسئله دوگان نامیده می‌شود. این به آن معنی است که مسئله دوگان، که شامل حداکثرسازی ، یک مسئله بهینه‌سازی محدب می‌باشد. مسائل با قیود تساوی در این حالت یک قید دیگر به صورت به مسئله اصلی افزوده می‌شود. | ## جمع‌بندی | برای حل آن به روش دوگان، متغیر دوگان را تعریف می‌کنند و باکمک آن تابع دوگان را تشکیل می‌دهیم؛ یعنی در تابع دوگان جمله افزوده می‌شود.