دوگانگی (بهینه‌سازی)
در نظریه بهینه‌سازی ریاضیاتی، دوگانگی بدین معنی است که مسائل بهینه‌سازی را می‌توان از هر یک از دو دیدگاه مسئلهٔ اصلی (the primal problem) و مسئلهٔ دوگان (the dual problem) نگریست (اصل دوگانگی). راه حل مسئله ی دوگان کران پایینی برای راه حل مسئلهٔ اصلی (minimization) ارائه می‌کند. هرچند به‌طور معمول دلیلی ندارد که مقادیر بهینهٔ مسائل اصلی و دوگان برابر باشند. به اختلاف این دو شکاف دوگانگی (duality gap) گویند. البته در مسائل بهینه‌سازی محدب (convex optimization problems)، شکاف دوگانگی تحت یک شرط می‌تواند صفر باشد؛ بنابراین راه حل مسئلهٔ دوگان کرانی برای مقدار راه حل مسئلهٔ اصلی است؛ وقتی مسئله محدب (convex) است و یک constraint qualification را تأمین می‌کند در این صورت مقدار یک راه حل بهینهٔ مسئلهٔ اصلی توسط مسئلهٔ دوگان داده می‌شود.
به گفتهٔ George Dantzig نظریهٔ دوگانگی برای بهینه‌سازی خطی بلافاصله پس از آنکه Dantzing مسئلهٔ برنامه‌ریزی خطی را ارائه داد، توسط جان فون نویمان، پیش‌بینی شده بود. Von Neumann اشاره کرد که از اطلاعات نظریه بازی‌های خودش استفاده کرده‌است و پیش‌بینی کرده که ماتریس مجموع صفر دو نفره معادل با برنامه‌ریزی خطی است. ابتدا در سال ۱۹۴۸ اثبات‌های پیچیده‌ای توسط Albert W. Tucker و گروهش منتشر شد.
معمولاً مسئلهٔ دوگانگی اشاره با مسئلهٔ دو گانگی لاگرانژی دارد؛ ولی مسائل دوگانگی دیگری نیز، مانند و مسئله ی دوگانگی Fenchel، مورد استفاده قرار می‌گیرند. مسئلهٔ دوگانگی لاگرانژی با تشکیل لاگرانژین (Lagrangian)، با استفاده از ضرایب نامنفی لاگرانژی، به منظور افزودن قیدها به تابع هدف و سپس حل کردن آن برای برخی مقادیر متغیر اصلی که لاگرانژین را کمینه می‌کند، به دست می‌آید. این راه حل متغیرهای اصلی (the primal variables) را به عنوان تابعی از ضرایب لاگرانژ ارائه می‌دهد که به آن‌ها متغیرهای دوگان (dual varibales) می‌گویند؛ بنابراین مسئلهٔ جدید این است که تابع هدف را نسبت به متغیرهای دوگان در شرایط حاصل از متغیزهای دوگان (مثلاً حداقل نامنفی بودن آنها) بیشینه کنیم. معمولاً با داشتن دو زوج دوگانه (dual pairs) از فضاهای محدب محلی مجزا (separated locally convex spaces) formula_1 و formula_2 و تابع formula_3 می‌توانیم مسئلهٔ اصلی (primal problem) را به صورت یافتن formula_4 به‌طوری‌که formula_4 برابر formula_6، تعریف کنیم.
اگر constraint conditions وجود داشته باشد، امکان اعمال آن‌ها به تابع formula_7 به واسطهٔ قرار دادن formula_8 که در آن formula_9 تابع مشخصه (indicator function) است وجود دارد. آنگاه formula_10 را به عنوان یک تابع اغتشاش (perturbation function) به صورتی که در آن formula_11 است، در نظر گرفت.
شکاف دوگانگی عبارت از اختلاف سمت راست و چپ نامعادلهٔ formula_12 است که در آن مزدوج محدب (convex conjugate) در هر دو متغیر و formula_13 نشانگر سوپریمم (کوچکترین کران بالا) است.
شکاف دوگانگی عبارت از تفاوت بین متغیرهای هر راه حل اصلی و هر راه حل دوگان است. اگر formula_14 مقدار دوگان ی بهینه و formula_15 مقداراصلی ی بهینه باشد، آنگاه شکاف دوگانگی برابر formula_16 است. این مقدار همیشه بزرگتر با مساوی صفر است. شکاف دوگانگی صفر است اگر و تنها اگر دوگانگی قوی (Strong duality) وجود داشته باشد. در غیر اینصورت شکاف اکیداً مثبت است و دوگانگی ضعیف (weak duality) وجود دارد. در بهینه‌سازی رایانشی (computational) یک شکاف دوگانگی دیگر نیز معمولاً مطرح است که برابر اختلاف مقدار بین هر راه حل دوگان و مقدار یک تکرار (iterate) امکان‌پذیر ولی زیر بهینه (suboptimal) برای مسئلهٔ اصلی می‌باشد. این شکاف دوگانهٔ جایگزین اختلاف بین مقدار یک تکرار امکان‌پذیر، ولی زیر بهینهٔ فعلی برای مسئلهٔ اصلی و مقدار مسئلهٔ دوگان، را محدود می‌کند؛ مقدار مسئلهٔ دوگان، در شرایطregularity conditions برابر با مقدارconvex relaxation مسئلهٔ اصلی است: Convex relaxation موجب مطرح شدن مطلب ذیل می‌شود: جایگزین کردن یک مجموعهٔ امکان‌پذیر غیر محدب (a non-convex feasible set) با پوش محدب بستهٔ (closed convex hull) آن، و با جایگزین کردن یک تابع غیر محدب با Convex closure آن که تابعی است که این سرلوحه (epigraph) را دارد که عبارت از پوش محدب بستهٔ تابع اصلی هدف اصلی است.
مسائل برنامه‌ریزی خطی، مسائل بهینه‌سازی هستند که در آن‌ها تابع هدف و محدودیت‌ها همگی خطی‌اند. در مسائل اصلی تابع هدف یک ترکیب خطی از "n" متغیر است. در چنین مسائلی "m" محدودیت وجود دارد که هر کدام یک کران بالا بر ترکیب خطی "n" متغیر اعمال می‌کند. مقصود بیشینه کردن مقدار تابع هدف مربوط به محدودیت هاست. یک "راه حل" عبارت است از برداری (یک لیست) از "n" مقدار که مقدار بیشینه برای تابع هدف را حاصل می‌کند. در مسئلهٔ دوگان، تابع هدف یک ترکیب خطی از "m" مقدار است که مشخص‌کنندهٔ محدودهٔ "m" محدودیت مسئلهٔ اصلی است. "n" محدودیت دوگان وجود دارند که هر کدام یک کران پایین بر ترکیب خطی "m" متغیر دوگان اعمال می‌کند.
در حالت خطی در مسئلهٔ اصلی از هر نقطهٔ زیر بهینهٔ که تمام محدودیت‌ها را فراهم می‌کند یک جهت یا زیر فضایی از جهت‌ها برای حرکت وجود دارد که تابع هدف را افزایش می‌دهد. آنچنان که بیان شده‌است حرکت کردن در هر چنین جهتی، تفاوت بین راه حل پیشنهادی و یک یا چند محدودیت را حذف می‌کند. یک "امکان‌ناپذیر" از راه حل پیشنهادی همانی است که از یک یا چند محدودیت فراتر می‌رود. در مسئلهٔ دوگان، بردار دوگان ضرب می‌کند ثابت‌هایی را که موقعیت محدودیت‌ها را در مسئلهٔ اصلی مشخص می‌کنند. تغییر دادن تابع دوگان در مسئلهٔ دوگان معادل با بازبینی کران‌های بالا در مسئلهٔ اصلی است. به این ترتیب کوچکترین کران بالا یافت می‌شود. به این معنا که بردار دوگان کمینه شده تا تفاوت بین مکان پیشنهادی محدودیت‌ها و موقعیت بهینهٔ واقعی از میان بردارد. یک مقدار امکان‌ناپذیر از بردار دوگان آنی است که خیلی کم است. چنین مقداری موقعیت‌های پیشنهادی یک یا تعداد بیشتری از محدودیت‌ها را در جاهایی که موقعیت بهینهٔ واقعی را در بر نمی‌گیرد، تعیین می‌کند.
این شهود به وسیلهٔ معادلات برنامه‌ریزی خطی: دوگانگی (Linear programming: Duality) به صورت فرمال درآمده‌است.
اگر مسئلهٔ اصلی برنامه‌ریزی خطی را به عنوان مسئلهٔ تخصیص منابع کلاسیک در نظر بگیریم، دوگان آن را می‌توان به عنوان مسئلهٔ ارزش‌گذاری منابع در نظر گرفت.
در برنامه‌ریزی غیر خطی محدودیت‌ها الزاماً خطی نیستند. با این حال، بسیاری از همان اصول صدق می‌کنند. به منظور کسب اطمینان از اینکه مقدار بیشینهٔ سراسری یک مسئلهٔ غیر خطی می‌تواند به آسانی یافت شود، فرمولاسیون مسئله معمولاً به این نیاز دارد که تابع محدب بوده و مجموعه‌های سطح پایین فشرده داشته باشد.
این اهمیت شرایط Karush–Kuhn–Tucker را نشان می‌دهد. این شرایط، شرط‌های ضروری برای یافتن بهینه‌های محلی برای مسائل برنامه‌ریزی غیر خطی را ارائه می‌دهد. همچنین شرایط اضافه‌ای وجود دارند (constraint qualification) که به منظور امکان‌پذیر شدن تعریف جهتی به سوی راه حل بهینه، ضروری‌اند. یک راه حل بهینه آنی است که یک بهینهٔ محلی است ولی احتمالاً یک بهینهٔ سراسری نیست.
برای یک مسئلهٔ برنامه‌ریزی غیر خطی داده شده با فرم استاندارد با دامنهٔ formula_18 که Interior غیر تهی، دارد، "تابع لاگرانژین" formula_19 به صورت formula_20 تعریف می‌شود.
بردارهای formula_21 و formula_22 را "متغیرهای دوگان" یا "بردارهای ضرایب لاگرانژ" مرتبط با مسئله می‌نامند. "تابع دوگان لاگرانژ" formula_23 به صورت formula_24 زیر تعریف می‌شود.
تابع دوگان "g" مقعر است حتی هنگامی که مسئلهٔ آغازین محدب نیست. تابع دوگان کرانهای پایین مقدار بهینهٔ formula_15 مسئلهٔ آغازین را می‌دهد؛ برای formula_26 هر و هر formula_22 داریم: formula_28
اگر یک constraint qualification مثل شرط Slater برقرار باشد و مسئلهٔ اصلی مقعر باشد آنگاه دوگانگی قوی داریم، یعنی formula_29.
برای یک مسئلهٔ کمینه‌سازی محدب با شرایط نامعادلهٔ مسئلهٔ دوگان لاگرانژیformula_31 است که تابع هدف تابع دوگان لاگرانژ است. به شرط این که توابع formula_7 و formula_33 به صورت پیوسته مشتق پذیر باشند، اینفیمم هنگامی که گرادیان برابر صفر باشد رخ می‌دهد. مسئلهٔ formula_34 مسئلهٔ دوگان Wolfe نامیده می‌شود. شاید حل این مسئله با کامپیوتر دشوار باشد، زیرا تابع هدف در متغیرهای مشترک formula_35 مقعر نیست. همچنین شرط تساوی formula_36 معمولاً غیر خطی است، بنابراین مسئلهٔ دوگان Wolfe به‌طور معمول یک مسئلهٔ بهینه‌سازی غیر مقعر است. در هر صورت دوگانگی ضعیف برقرار است.
در حل مسئله بهینه‌سازی به روش معادل سازی، یک مسئله معادل برای مسئله استاندارد تعریف می‌کنیم که پاسخ آن بسیار راحت‌تر از مسئله اولیه به دست می‌آید؛ برای به دست آوردن مسئله معادل روند مشخصی وجود ندارد اما برای برخلاف آن در حل مسئله بهینه‌سازی از طریق دوگان یک روند مشخص برای به دست آوردن مسئله دوگان وجود دارد. برای هر مسئله بهینه‌سازی می‌توان یک معادل محدب تعریف کرد. . پاسخ این مسئله یک کران پایین روی مسئله اصلی ارائه می‌دهد و در حالت محدب دقیقاً همان جواب است.
فرم استاندارد یک مسئله بهینه‌سازی به صورت زیر می‌باشد:formula_37formula_38به این مسئله، مسئله اصلی می‌گویند. متغیر بهینه‌سازی formula_4، را پارامتر اولیه گویند. formula_40 قیود نامساوی می‌باشند.
تابع لاگرانژی که یک مجموعه وزن دار از تابع هدف و قیود است را بفرم زیر نمایش می‌دهند:formula_41لاگرانژی تابعی از پارامتر اولیه و یک متغیر اضافه formula_42 می‌باشد که به آن متغیر دوگان گویند.
با کمک تابع لاگرانژی می‌توان یک تابع جدید (تنها از متغیر دوگان) بنام تابع دوگان ساخت. این تابع را می‌توان بفرم زیر نمایش داد:formula_43g به صورت حداقل نقطه‌ای تعریف می‌شود پس مقعر است.
به ازای هرformula_44 داریم:formula_45 . تابع formula_46 کران پایینی از تابع هدف در ناحیه شدنی ارائه می‌دهد را ارائه می‌دهد.
در این حالت می‌توان مسئله دوگان را به صورت ضمنی حل کرد. در واقع مسئله فوق نامقید، با تابع هدف محدب (از متغیرformula_4) است، بنابراین بهینهٔ سراسری را می‌توان با برابر صفر قرار دادن مشتق تابع هدف نسبت به formula_4 به دست آورد.
از آنجا که کران پایین برای هر formula_49 صادق است، باید به دنبال بهترین آن بود، که آن بزرگترین کران پایین است:formula_50به دست آوردن کران پایین از طریق مسئله دوگان ساده‌تر است زیرا محاسبه formula_51 با قیود کمتری همراه است. مسئله پیدا کردن بهترین کران پایین به صورت زیر تعریف می‌شود:formula_52این مسئله، مسئله دوگان نامیده می‌شود. مقدار بهینه آن formula_14، مقدار بهینه دوگان نام دارد. همان‌طور که در بالا بیان شد، formula_46 مقعر است. این به آن معنی است که مسئله دوگان، که شامل حداکثرسازی formula_46، یک مسئله بهینه‌سازی محدب می‌باشد.
در این حالت یک قید دیگر به صورت formula_56به مسئله اصلی افزوده می‌شود. برای حل آن به روش دوگان، متغیر دوگان formula_57 را تعریف می‌کنند و باکمک آن تابع دوگان را تشکیل می‌دهیم؛ یعنی در تابع دوگان جمله formula_58 افزوده می‌شود. متغیر formula_57 شرط formula_60 را ندارد.