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

در نظریه بهینه‌سازی ریاضیاتی، دوگانگی بدین معنی است که مسائل بهینه‌سازی را می‌توان از هر یک از دو دیدگاه مسئلهٔ اصلی (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 و گروهش منتشر شد.

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

معمولاً مسئلهٔ دوگانگی اشاره با مسئلهٔ دو گانگی لاگرانژی دارد؛ ولی مسائل دوگانگی دیگری نیز، مانند مسئلهٔ دوگانگی Wolfe و مسئله ی دوگانگی Fenchel، مورد استفاده قرار می‌گیرند. مسئلهٔ دوگانگی لاگرانژی با تشکیل لاگرانژین (Lagrangian)، با استفاده از ضرایب نامنفی لاگرانژی، به منظور افزودن قیدها به تابع هدف و سپس حل کردن آن برای برخی مقادیر متغیر اصلی که لاگرانژین را کمینه می‌کند، به دست می‌آید. این راه حل متغیرهای اصلی (the primal variables) را به عنوان تابعی از ضرایب لاگرانژ ارائه می‌دهد که به آن‌ها متغیرهای دوگان (dual varibales) می‌گویند؛ بنابراین مسئلهٔ جدید این است که تابع هدف را نسبت به متغیرهای دوگان در شرایط حاصل از متغیزهای دوگان (مثلاً حداقل نامنفی بودن آنها) بیشینه کنیم. معمولاً با داشتن دو زوج دوگانه (dual pairs) از فضاهای محدب محلی مجزا (separated locally convex spaces) $\left(X,X^{*}\right)$ و $\left(Y,Y^{*}\right)$ و تابع $f:X\to \mathbb {R} \cup \{+\infty \}$ می‌توانیم مسئلهٔ اصلی (primal problem) را به صورت یافتن $x$ به‌طوری‌که $x$ برابر $\inf _{x\in X}f(x)\,$، تعریف کنیم.

اگر constraint conditions وجود داشته باشد، امکان اعمال آن‌ها به تابع $f$ به واسطهٔ قرار دادن ${\tilde {f}}=f+I_{\mathrm {constraints} }$ که در آن $I$ تابع مشخصه (indicator function) است وجود دارد. آنگاه $F:X\times Y\to \mathbb {R} \cup \{+\infty \}$ را به عنوان یک تابع اغتشاش (perturbation function) به صورتی که در آن $F(x,0)=f(x)$ است، در نظر گرفت.

شکاف دوگانگی عبارت از اختلاف سمت راست و چپ نامعادلهٔ $\sup _{y^{*}\in Y^{*}}-F^{*}(0,y^{*})\leq \inf _{x\in X}F(x,0),\,$ است که در آن مزدوج محدب (convex conjugate) در هر دو متغیر و $sup$ نشانگر سوپریمم (کوچکترین کران بالا) است.

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

شکاف دوگانگی عبارت از تفاوت بین متغیرهای هر راه حل اصلی و هر راه حل دوگان است. اگر $d^{*}$ مقدار دوگان ی بهینه و $p^{*}$ مقداراصلی ی بهینه باشد، آنگاه شکاف دوگانگی برابر $p^{*}-d^{*}$ است. این مقدار همیشه بزرگتر با مساوی صفر است. شکاف دوگانگی صفر است اگر و تنها اگر دوگانگی قوی (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) که به منظور امکان‌پذیر شدن تعریف جهتی به سوی راه حل بهینه، ضروری‌اند. یک راه حل بهینه آنی است که یک بهینهٔ محلی است ولی احتمالاً یک بهینهٔ سراسری نیست.

اصل قوی لاگرانژی: دوگانگی لاگرانژی

برای یک مسئلهٔ برنامه‌ریزی غیر خطی داده شده با فرم استاندارد

${\begin{aligned}{\text{minimize }}&f_{0}(x)\\{\text{subject to }}&f_{i}(x)\leq 0,\ i\in \left\{1,\dots ,m\right\}\\&h_{i}(x)=0,\ i\in \left\{1,\dots ,p\right\}\end{aligned}}$

با دامنهٔ ${\mathcal {D}}\subset \mathbb {R} ^{n}$ که Interior غیر تهی، دارد، تابع لاگرانژین $\Lambda :\mathbb {R} ^{n}\times \mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R}$ به صورت $\Lambda (x,\lambda ,\nu )=f_{0}(x)+\sum _{i=1}^{m}\lambda _{i}f_{i}(x)+\sum _{i=1}^{p}\nu _{i}h_{i}(x)$ تعریف می‌شود.

بردارهای $\lambda$ و $\nu$ را متغیرهای دوگان یا بردارهای ضرایب لاگرانژ مرتبط با مسئله می‌نامند. تابع دوگان لاگرانژ $g:\mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R}$ به صورت $g(\lambda ,\nu )=\inf _{x\in {\mathcal {D}}}\Lambda (x,\lambda ,\nu )=\inf _{x\in {\mathcal {D}}}\left(f_{0}(x)+\sum _{i=1}^{m}\lambda _{i}f_{i}(x)+\sum _{i=1}^{p}\nu _{i}h_{i}(x)\right)$ زیر تعریف می‌شود.

تابع دوگان g مقعر است حتی هنگامی که مسئلهٔ آغازین محدب نیست. تابع دوگان کرانهای پایین مقدار بهینهٔ $p^{*}$ مسئلهٔ آغازین را می‌دهد؛ برای $\lambda \geq 0$ هر و هر $\nu$ داریم: $g(\lambda ,\nu )\leq p^{*}$

اگر یک constraint qualification مثل شرط Slater برقرار باشد و مسئلهٔ اصلی مقعر باشد آنگاه دوگانگی قوی داریم، یعنی $d^{*}=\max _{\lambda \geq 0,\nu }g(\lambda ,\nu )=\inf f_{0}=p^{*}$.

مسائل محدب

برای یک مسئلهٔ کمینه‌سازی محدب با شرایط نامعادلهٔ

${\begin{aligned}&{\underset {x}{\operatorname {minimize} }}&&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\end{aligned}}$

مسئلهٔ دوگان لاگرانژی${\begin{aligned}&{\underset {u}{\operatorname {maximize} }}&&\inf _{x}\left(f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)\right)\\&\operatorname {subject\;to} &&u_{i}\geq 0,\quad i=1,\dots ,m\end{aligned}}$ است که تابع هدف تابع دوگان لاگرانژ است. به شرط این که توابع $f$ و $g_{1},\cdots ,g_{m}$ به صورت پیوسته مشتق پذیر باشند، اینفیمم هنگامی که گرادیان برابر صفر باشد رخ می‌دهد. مسئلهٔ ${\begin{aligned}&{\underset {x,u}{\operatorname {maximize} }}&&f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)\\&\operatorname {subject\;to} &&\nabla f(x)+\sum _{j=1}^{m}u_{j}\nabla g_{j}(x)=0\\&&&u_{i}\geq 0,\quad i=1,\dots ,m\end{aligned}}$ مسئلهٔ دوگان Wolfe نامیده می‌شود. شاید حل این مسئله با کامپیوتر دشوار باشد، زیرا تابع هدف در متغیرهای مشترک $(u,x)$ مقعر نیست. همچنین شرط تساوی $\nabla f(x)+\sum _{j=1}^{m}u_{j}\nabla g_{j}(x)$ معمولاً غیر خطی است، بنابراین مسئلهٔ دوگان Wolfe به‌طور معمول یک مسئلهٔ بهینه‌سازی غیر مقعر است. در هر صورت دوگانگی ضعیف برقرار است.

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

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

مسئله اصلی

فرم استاندارد یک مسئله بهینه‌سازی به صورت زیر می‌باشد:

$$minf_{0}(x);$$

$$s.t.f_{i}(x)\leq 0,i=1,...,m$$

به این مسئله، مسئله اصلی می‌گویند. متغیر بهینه‌سازی $x$، را پارامتر اولیه گویند. $f_{i}(x)\leq 0,i=1,...,m$ قیود نامساوی می‌باشند.

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

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

$$L(x,y)=f_{0}(x)+\sum _{i=1}^{m}y_{i}f_{i}(x)$$

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

تابع دوگان

با کمک تابع لاگرانژی می‌توان یک تابع جدید (تنها از متغیر دوگان) بنام تابع دوگان ساخت. این تابع را می‌توان بفرم زیر نمایش داد:

$$g(y)=minL(x,y)=minf_{0}(x)+\sum _{i=1}^{m}y_{i}f_{i}(x)$$

g به صورت حداقل نقطه‌ای تعریف می‌شود پس مقعر است.

به ازای هر$x,y$ داریم:${\textstyle L(x,y)\geq g(y)}$ . تابع $g$ کران پایینی از تابع هدف در ناحیه شدنی ارائه می‌دهد را ارائه می‌دهد.

در این حالت می‌توان مسئله دوگان را به صورت ضمنی حل کرد. در واقع مسئله فوق نامقید، با تابع هدف محدب (از متغیر$x$) است، بنابراین بهینهٔ سراسری را می‌توان با برابر صفر قرار دادن مشتق تابع هدف نسبت به $x$ به دست آورد.

مسئله دوگان

از آنجا که کران پایین برای هر $y\geq 0$ صادق است، باید به دنبال بهترین آن بود، که آن بزرگترین کران پایین است:

$$P^{*}\geq d^{*}=maxg(y);y\geq 0$$

به دست آوردن کران پایین از طریق مسئله دوگان ساده‌تر است زیرا محاسبه $g(y)$ با قیود کمتری همراه است. مسئله پیدا کردن بهترین کران پایین به صورت زیر تعریف می‌شود:

$$d^{*}=maxg(y);y\geq 0$$

این مسئله، مسئله دوگان نامیده می‌شود. مقدار بهینه آن $d^{*}$، مقدار بهینه دوگان نام دارد. همان‌طور که در بالا بیان شد، $g$ مقعر است. این به آن معنی است که مسئله دوگان، که شامل حداکثرسازی $g$، یک مسئله بهینه‌سازی محدب می‌باشد.

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

در این حالت یک قید دیگر به صورت ${\textstyle hi(x)=0,i=1,...,p}$به مسئله اصلی افزوده می‌شود. برای حل آن به روش دوگان، متغیر دوگان $v$ را تعریف می‌کنند و باکمک آن تابع دوگان را تشکیل می‌دهیم؛ یعنی در تابع دوگان جمله $\sum _{i=1}^{p}v_{i}h_{i}(x)$ افزوده می‌شود. متغیر $v$ شرط $v\geq 0$ را ندارد.

برای مطالعهٔ بیشتر

• Duality
• رهاسازی محدب

منابع

• Ahuja, Ravindra K.; Magnanti, Thomas L.; and Orlin, James B. (1993). Network Flows: Theory, Algorithms and Applications. Prentice Hall. ISBN 0-13-617549-X.{{cite book}}: نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)
• Bertsekas, Dimitri P. (1999). Nonlinear Programming (2nd ed.). Athena Scientific. ISBN 1-886529-00-0.
• Bonnans, J.  Frédéric; Gilbert, J.  Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Numerical optimization: Theoretical and practical aspects. Universitext (Second revised ed. of translation of 1997 French ed.). Berlin: Springer-Verlag. pp. xiv+490. doi:10.1007/978-3-540-35447-5. ISBN 3-540-35445-X. MR 2265882.
• Cook, William J.; Cunningham, William H.; Pulleyblank, William R.; Schrijver, Alexander (November 12, 1997). Combinatorial Optimization (1st ed.). John Wiley & Sons. ISBN 0-471-55894-X.
• Dantzig, George B. (1963). Linear Programming and Extensions. Princeton, NJ: Princeton University Press.
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). Convex analysis and minimization algorithms, Volume I: Fundamentals. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Vol. 305. Berlin: Springer-Verlag. pp. xviii+417. ISBN 3-540-56850-6. MR 1261420.
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). "14 Duality for Practitioners". Convex analysis and minimization algorithms, Volume II: Advanced theory and bundle methods. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Vol. 306. Berlin: Springer-Verlag. pp. xviii+346. ISBN 3-540-56852-2. MR 1295240.{{cite book}}: نگهداری CS1: نقطه‌گذاری اضافه (link)
• Lasdon, Leon S. (2002) [Reprint of the 1970 Macmillan]. Optimization theory for large systems. Mineola, New York: Dover Publications, Inc. pp. xiii+523. ISBN 978-0-486-41999-2. MR 1888251.
• Lawler, Eugene (2001). "4.5. Combinatorial Implications of Max-Flow Min-Cut Theorem, 4.6. Linear Programming Interpretation of Max-Flow Min-Cut Theorem". Combinatorial Optimization: Networks and Matroids. Dover. pp. 117–120. ISBN 0-486-41453-1.
• Lemaréchal, Claude (2001). "Lagrangian relaxation". In Jünger, Michael; and Naddef, Denis (ed.). Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000. Lecture Notes in Computer Science (LNCS). Vol. 2241. Berlin: Springer-Verlag. pp. 112–156. doi:10.1007/3-540-45586-8_4. ISBN 3-540-42877-1. MR 1900016.{{cite book}}: نگهداری یادکرد:نام‌های متعدد:فهرست ویراستاران (link)
• Minoux, Michel (1986). Mathematical programming: Theory and algorithms (Translated by Steven Vajda from the (1983 Paris: Dunod) French ed.). Chichester: A Wiley-Interscience Publication. John Wiley & Sons, Ltd. pp. xxviii+489. ISBN 0-471-90170-9. MR 0868279. (2008 Second ed. , in French: Programmation mathématique: Théorie et algorithmes, Éditions Tec & Doc, Paris, 2008. xxx+711 pp.)). {{cite book}}: Unknown parameter |note= ignored (help)
• Nering, Evar D.; Tucker, Albert W. (1993). Linear Programming and Related Problems. Boston, MA: Academic Press. ISBN 978-0-12-515440-6.
• Papadimitriou, Christos H.; Steiglitz, Kenneth (July 1998). Combinatorial Optimization: Algorithms and Complexity (Unabridged ed.). Dover. ISBN 0-486-40258-4.{{cite book}}: نگهداری یادکرد:تاریخ و سال (link)
• Ruszczyński, Andrzej (2006). Nonlinear Optimization. Princeton, NJ: Princeton University Press. pp. xii+454. ISBN 978-0-691-11915-1. MR 2199043.
• پرش به بالا↑ jemdoc. "Dual Problem».
• پرش به بالا↑ Boyd, stephan. convex optimization. newyork: Cambridge university press، ۲۰۰۴.
• Everett, Hugh, III (1963). "Generalized Lagrange multiplier method for solving problems of optimum allocation of resources". Operations Research. 11 (3): 399–417. doi:10.1287/opre.11.3.39. JSTOR 168028. MR 0152360. Archived from the original on 24 July 2011. Retrieved 27 November 2013.
• Kiwiel, Krzysztof C.; Larsson, Torbjörn; Lindberg, P.  O. (2007). "Lagrangian relaxation via ballstep subgradient methods". Mathematics of Operations Research. 32 (3): 669–686. doi:10.1287/moor.1070.0261. MR 2348241. Archived from the original on 26 July 2011. Retrieved 27 November 2013. {{cite journal}}: Unknown parameter |month= ignored (help)

en:Convex optimization en:Mathematical optimization