دوگانگی (بهینه‌سازی)

تاریخچه

به گفتهٔ George Dantzig نظریهٔ دوگانگی برای بهینه‌سازی خطی بلافاصله پس از آنکه Dantzing مسئلهٔ برنامه‌ریزی خطی را ارائه داد، توسط جان فون نویمان، پیش‌بینی شده بود. Von Neumann اشاره کرد که از اطلاعات نظریه بازی‌های خودش استفاده کرده‌است و پیش‌بینی کرده که ماتریس مجموع صفر دو نفره معادل با برنامه‌ریزی خطی است. ابتدا در سال ۱۹۴۸ اثبات‌های پیچیده‌ای توسط Albert W. Tucker و گروهش منتشر شد.

مسئلهٔ دوگانگی Dual Problem

معمولاً مسئلهٔ دوگانگی اشاره با مسئلهٔ دو گانگی لاگرانژی دارد؛ ولی مسائل دوگانگی دیگری نیز، مانند مسئلهٔ دوگانگی Wolfe و مسئله ی دوگانگی Fenchel، مورد استفاده قرار می‌گیرند. مسئلهٔ دوگانگی لاگرانژی با تشکیل لاگرانژین (Lagrangian)، با استفاده از ضرایب نامنفی لاگرانژی، به منظور افزودن قیدها به تابع هدف و سپس حل کردن آن برای برخی مقادیر متغیر اصلی که لاگرانژین را کمینه می‌کند، به دست می‌آید. این راه حل متغیرهای اصلی (the primal variables) را به عنوان تابعی از ضرایب لاگرانژ ارائه می‌دهد که به آن‌ها متغیرهای دوگان (dual varibales) می‌گویند؛ بنابراین مسئلهٔ جدید این است که تابع هدف را نسبت به متغیرهای دوگان در شرایط حاصل از متغیزهای دوگان (مثلاً حداقل نامنفی بودن آنها) بیشینه کنیم.
معمولاً با داشتن دو زوج دوگانه (dual pairs) از فضاهای محدب محلی مجزا (separated locally convex spaces)  و  و تابع  می‌توانیم مسئلهٔ اصلی (primal problem) را به صورت یافتن  به‌طوری‌که  برابر ، تعریف کنیم.
اگر constraint conditions وجود داشته باشد، امکان اعمال آن‌ها به تابع  به واسطهٔ قرار دادن  که در آن  تابع مشخصه (indicator function) است وجود دارد. آنگاه  را به عنوان یک تابع اغتشاش (perturbation function) به صورتی که در آن  است، در نظر گرفت.
شکاف دوگانگی عبارت از اختلاف سمت راست و چپ نامعادلهٔ  است که در آن مزدوج محدب (convex conjugate) در هر دو متغیر و  نشانگر سوپریمم (کوچکترین کران بالا) است.

شکاف دوگانگی (duality gap)

شکاف دوگانگی عبارت از تفاوت بین متغیرهای هر راه حل اصلی و هر راه حل دوگان است. اگر  مقدار دوگان ی بهینه و  مقداراصلی ی بهینه باشد، آنگاه شکاف دوگانگی برابر  است. این مقدار همیشه بزرگتر با مساوی صفر است. شکاف دوگانگی صفر است اگر و تنها اگر دوگانگی قوی (Strong duality) وجود داشته باشد. در غیر اینصورت شکاف اکیداً مثبت است و دوگانگی ضعیف (weak duality) وجود دارد.
در بهینه‌سازی رایانشی (computational) یک شکاف دوگانگی دیگر نیز معمولاً مطرح است که برابر اختلاف مقدار بین هر راه حل دوگان و مقدار یک تکرار (iterate) امکان‌پذیر ولی زیر بهینه (suboptimal) برای مسئلهٔ اصلی می‌باشد. این شکاف دوگانهٔ جایگزین اختلاف بین مقدار یک تکرار امکان‌پذیر، ولی زیر بهینهٔ فعلی برای مسئلهٔ اصلی و مقدار مسئلهٔ دوگان، را محدود می‌کند؛ مقدار مسئلهٔ دوگان، در شرایطregularity conditions برابر با مقدارconvex relaxation مسئلهٔ اصلی است: Convex relaxation موجب مطرح شدن مطلب ذیل می‌شود: جایگزین کردن یک مجموعهٔ امکان‌پذیر غیر محدب (a non-convex feasible set) با پوش محدب بستهٔ (closed convex hull) آن، و با جایگزین کردن یک تابع غیر محدب با Convex closure آن که تابعی است که این سرلوحه (epigraph) را دارد که عبارت از پوش محدب بستهٔ تابع اصلی هدف اصلی است.

مورد خطی the linear case

مسائل برنامه‌ریزی خطی، مسائل بهینه‌سازی هستند که در آن‌ها تابع هدف و محدودیت‌ها همگی خطی‌اند. در مسائل اصلی تابع هدف یک ترکیب خطی از n متغیر است. در چنین مسائلی m محدودیت وجود دارد که هر کدام یک کران بالا بر ترکیب خطی n متغیر اعمال می‌کند. مقصود بیشینه کردن مقدار تابع هدف مربوط به محدودیت هاست. یک راه حل عبارت است از برداری (یک لیست) از n مقدار که مقدار بیشینه برای تابع هدف را حاصل می‌کند.
در مسئلهٔ دوگان، تابع هدف یک ترکیب خطی از m مقدار است که مشخص‌کنندهٔ محدودهٔ m محدودیت مسئلهٔ اصلی است. n محدودیت دوگان وجود دارند که هر کدام یک کران پایین بر ترکیب خطی m متغیر دوگان اعمال می‌کند.

رابطهٔ بین مسئلهٔ اصلی و مسئلهٔ دوگان

در حالت خطی در مسئلهٔ اصلی از هر نقطهٔ زیر بهینهٔ که تمام محدودیت‌ها را فراهم می‌کند یک جهت یا زیر فضایی از جهت‌ها برای حرکت وجود دارد که تابع هدف را افزایش می‌دهد. آنچنان که بیان شده‌است حرکت کردن در هر چنین جهتی، تفاوت بین راه حل پیشنهادی و یک یا چند محدودیت را حذف می‌کند. یک امکان‌ناپذیر از راه حل پیشنهادی همانی است که از یک یا چند محدودیت فراتر می‌رود.
در مسئلهٔ دوگان، بردار دوگان ضرب می‌کند ثابت‌هایی را که موقعیت محدودیت‌ها را در مسئلهٔ اصلی مشخص می‌کنند. تغییر دادن تابع دوگان در مسئلهٔ دوگان معادل با بازبینی کران‌های بالا در مسئلهٔ اصلی است. به این ترتیب کوچکترین کران بالا یافت می‌شود. به این معنا که بردار دوگان کمینه شده تا تفاوت بین مکان پیشنهادی محدودیت‌ها و موقعیت بهینهٔ واقعی از میان بردارد. یک مقدار امکان‌ناپذیر از بردار دوگان آنی است که خیلی کم است. چنین مقداری موقعیت‌های پیشنهادی یک یا تعداد بیشتری از محدودیت‌ها را در جاهایی که موقعیت بهینهٔ واقعی را در بر نمی‌گیرد، تعیین می‌کند.
این شهود به وسیلهٔ معادلات برنامه‌ریزی خطی: دوگانگی (Linear programming: Duality) به صورت فرمال درآمده‌است.

تفسیر اقتصادی

اگر مسئلهٔ اصلی برنامه‌ریزی خطی را به عنوان مسئلهٔ تخصیص منابع کلاسیک در نظر بگیریم، دوگان آن را می‌توان به عنوان مسئلهٔ ارزش‌گذاری منابع در نظر گرفت.

حالت غیر خطی

در برنامه‌ریزی غیر خطی محدودیت‌ها الزاماً خطی نیستند. با این حال، بسیاری از همان اصول صدق می‌کنند. به منظور کسب اطمینان از اینکه مقدار بیشینهٔ سراسری یک مسئلهٔ غیر خطی می‌تواند به آسانی یافت شود، فرمولاسیون مسئله معمولاً به این نیاز دارد که تابع محدب بوده و مجموعه‌های سطح پایین فشرده داشته باشد.
این اهمیت شرایط Karush–Kuhn–Tucker را نشان می‌دهد. این شرایط، شرط‌های ضروری برای یافتن بهینه‌های محلی برای مسائل برنامه‌ریزی غیر خطی را ارائه می‌دهد. همچنین شرایط اضافه‌ای وجود دارند (constraint qualification) که به منظور امکان‌پذیر شدن تعریف جهتی به سوی راه حل بهینه، ضروری‌اند. یک راه حل بهینه آنی است که یک بهینهٔ محلی است ولی احتمالاً یک بهینهٔ سراسری نیست.

حل مسئله بهینه‌سازی از طریق دوگان

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

مسئله اصلی

فرم استاندارد یک مسئله بهینه‌سازی به صورت زیر می‌باشد:
به این مسئله، مسئله اصلی می‌گویند. متغیر بهینه‌سازی ، را پارامتر اولیه گویند.  قیود نامساوی می‌باشند.

تابع لاگرانژی

تابع لاگرانژی که یک مجموعه وزن دار از تابع هدف و قیود است را بفرم زیر نمایش می‌دهند:
لاگرانژی تابعی از پارامتر اولیه و یک متغیر اضافه  می‌باشد که به آن متغیر دوگان گویند.

تابع دوگان

با کمک تابع لاگرانژی می‌توان یک تابع جدید (تنها از متغیر دوگان) بنام تابع دوگان ساخت. این تابع را می‌توان بفرم زیر نمایش داد:
g به صورت حداقل نقطه‌ای تعریف می‌شود پس مقعر است.
به ازای هر داریم: . تابع  کران پایینی از تابع هدف در ناحیه شدنی ارائه می‌دهد را ارائه می‌دهد.
در این حالت می‌توان مسئله دوگان را به صورت ضمنی حل کرد. در واقع مسئله فوق نامقید، با تابع هدف محدب (از متغیر) است، بنابراین بهینهٔ سراسری را می‌توان با برابر صفر قرار دادن مشتق تابع هدف نسبت به   به دست آورد.

مسئله دوگان

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

مسائل با قیود تساوی

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