دوگانگی

دوگانگی (بهینه سازی). Duality
رهاسازی محدب
در نظریه بهینه سازی ریاضیاتی، دوگانگی بدین معنی است که مسائل بهینه سازی را می توان از هر یک از دو دیدگاه مسئلهٔ اصلی (the primal problem) و مسئلهٔ دوگان (the dual problem) نگریست (اصل دوگانگی). راه حل مسئله ی دوگان کران پایینی برای راه حل مسئلهٔ اصلی (minimization) ارائه می کند. هرچند به طور معمول دلیلی ندارد که مقادیر بهینهٔ مسائل اصلی و دوگان برابر باشند. به اختلاف این دو شکاف دوگانگی (duality gap) گویند. البته در مسائل بهینه سازی محدب (convex optimization problems)، شکاف دوگانگی تحت یک شرط constraint qualification می تواند صفر باشد؛ بنابراین راه حل مسئلهٔ دوگان کرانی برای مقدار راه حل مسئلهٔ اصلی است؛ وقتی مسئله محدب (convex) است و یک constraint qualification را تأمین می کند در این صورت مقدار یک راه حل بهینهٔ مسئلهٔ اصلی توسط مسئلهٔ دوگان داده می شود.
به گفتهٔ George Dantzig نظریهٔ دوگانگی برای بهینه سازی خطی بلافاصله پس از آنکه Dantzing مسئلهٔ برنامه ریزی خطی را ارائه داد، توسط جان فون نویمان، پیش بینی شده بود. Von Neumann اشاره کرد که از اطلاعات نظریه بازی های خودش استفاده کرده است و پیش بینی کرده که ماتریس مجموع صفر دو نفره معادل با برنامه ریزی خطی است. ابتدا در سال ۱۹۴۸ اثبات های پیچیده ای توسط Albert W. Tucker و گروهش منتشر شد.
معمولاً مسئلهٔ دوگانگی اشاره با مسئلهٔ دو گانگی لاگرانژی دارد؛ ولی مسائل دوگانگی دیگری نیز، مانند مسئلهٔ دوگانگی Wolfe و مسئله ی دوگانگی Fenchel، مورد استفاده قرار می گیرند. مسئلهٔ دوگانگی لاگرانژی با تشکیل لاگرانژین (Lagrangian)، با استفاده از ضرایب نامنفی لاگرانژی، به منظور افزودن قیدها به تابع هدف و سپس حل کردن آن برای برخی مقادیر متغیر اصلی که لاگرانژین را کمینه می کند، به دست می آید. این راه حل متغیرهای اصلی (the primal variables) را به عنوان تابعی از ضرایب لاگرانژ ارائه می دهد که به آن ها متغیرهای دوگان (dual varibales) می گویند؛ بنابراین مسئلهٔ جدید این است که تابع هدف را نسبت به متغیرهای دوگان در شرایط حاصل از متغیزهای دوگان (مثلاً حداقل نامنفی بودن آنها) بیشینه کنیم.معمولاً با داشتن دو زوج دوگانه (dual pairs) از فضاهای محدب محلی مجزا (separated locally convex spaces) ( X , X ∗ ) {\displaystyle \left(X,X^{*}\right)}   و ( Y , Y ∗ ) {\displaystyle \left(Y,Y^{*}\right)}   و تابع f : X → R ∪ { + ∞ } {\displaystyle f:X\to \mathbb {R} \cup \{+\infty \}}   می توانیم مسئلهٔ اصلی (primal problem) را به صورت یافتن x {\displaystyle x}   به طوری که x {\displaystyle x}   برابر inf x ∈ X f ( x ) {\displaystyle \inf _{x\in X}f(x)\,}  ، تعریف کنیم.