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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در نظریه بهینه‌سازی ریاضیاتی، دوگانگی بدین معنی است که مسائل بهینه‌سازی را می توان از هر یک از دو دیدگاه مساله ی اصلی (the primal problem) و مساله ی دوگان (the dual problem) نگریست (اصل دوگانگی). راه حل مساله ی دوگان کران پایینی برای راه حل مساله ی اصلی (minimization) ارائه می کند.[۱] هرچند به طور معمول دلیلی ندارد که مقادیر بهینه ی مسائل اصلی و دوگان برابر باشند. به اختلاف این دو شکاف دوگانگی (duality gap) گویند.البته در مسائل بهینه سازی محدب (convex optimization problems)، شکاف دوگانگی تحت یک شرط constraint qualification می تواند صفر باشد. بنابراین راه حل مساله ی دوگان کرانی برای مقدار راه حل مساله ی اصلی است؛ وقتی مساله محدب (convex) است و یک constraint qualification را تامین می کند در این صورت مقدار یک راه حل بهینه ی مساله ی اصلی توسط مساله ی دوگان داده می شود.

مساله ی دوگانگی 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^*) \le \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_(mathematics | epigraph]]) را دارد که عبارت از پوش محدب بسته ی تابع اصلی هدف اصلی است[۶][۷][۸][۹][۱۰][۱۱][۱۲][۱۳][۱۴].

مورد خطی the linear case[ویرایش]

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

رابطه ی بین مساله ی اصلی و مساله ی دوگان[ویرایش]

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

این شهود به وسیله ی معادلات برنامه ریزی خطی : دوگانگی (Linear programming: Duality) به صورت فرمال در آمده است.

تفسیر اقتصادی[ویرایش]

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

حالت غیر خطی[ویرایش]

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

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

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

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

\begin{align}
\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{align}

با دامنه ی \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 \ge 0, \nu} g(\lambda,\nu) = \inf f_0 = p^*.

مسائل محدب[ویرایش]

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

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

مساله ی دوگان لاگرانژی\begin{align}
&\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{align} است که تابع هدف تابع دوگان لاگرانژ است. به شرط این که توابع f و g_1, \cdots, g_m به صورت پیوسته مشتق پذیر باشند، اینفیمم هنگامی که گرادیان برابر صفر باشد رخ می دهد. مساله ی \begin{align}
&\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{align} مساله ی دوگان Wolfe نامیده می شود. شاید حل این مساله با کامپیوتر دشوار باشد، زیرا تابع هدف در متغیرهای مشترک (u,x) مقعر نیست. همچنین شرط تساوی \nabla f(x) + \sum_{j=1}^m u_j \nabla g_j(x) معمولاً غیر خطی است، بنابراین مساله ی دوگان Wolfe به طور معمول یک مساله ی بهینه سازی غیر مقعر است. در هر صورت دوگانگی ضعیف برقرار است [۱۵].

تاریخچه[ویرایش]

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

برای مطالعه ی بیشتر[ویرایش]

نوشته ها[ویرایش]

  1. Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization (pdf). Cambridge University Press. ISBN 978-0-521-83378-3. Retrieved October 15, 2011. 
  2. ۲٫۰ ۲٫۱ Boţ, Radu Ioan; Wanka, Gert; Grad, Sorin-Mihai (2009). Duality in Vector Optimization. Springer. ISBN 978-3-642-02885-4. 
  3. Csetnek, Ernö Robert (2010). Overcoming the failure of the classical generalized interior-point regularity conditions in convex optimization. Applications of the duality theory to enlargements of maximal monotone operators. Logos Verlag Berlin GmbH. ISBN 978-3-8325-2503-3. 
  4. Zălinescu, Constantin (2002). Convex analysis in general vector spaces (J). River Edge, NJ: World Scientific Publishing Co., Inc. pp. 106–113. ISBN 981-238-067-1. MR 1921556. 
  5. Borwein, Jonathan; Zhu, Qiji (2005). Techniques of Variational Analysis. Springer. ISBN 978-1-4419-2026-3. 
  6. Ahuja, Ravindra K.; Magnanti, Thomas L.; and Orlin, James B. (1993). Network Flows: Theory, Algorithms and Applications. Prentice Hall. ISBN 0-13-617549-X. 
  7. Bertsekas, Dimitri P. (1999). Nonlinear Programming (2nd ed.). Athena Scientific. ISBN 1-886529-00-0. 
  8. 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. 
  9. 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] 305. Berlin: Springer-Verlag. pp. xviii+417. ISBN 3-540-56850-6. MR 1261420. 
  10. 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] 306. Berlin: Springer-Verlag. pp. xviii+346. ISBN 3-540-56852-2. MR 1295240. 
  11. 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. 
  12. Lemaréchal, Claude (2001). "Lagrangian relaxation". In Jünger, Michael; and Naddef, Denis. Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000. Lecture Notes in Computer Science (LNCS) 2241. Berlin: Springer-Verlag. pp. 112–156. doi:10.1007/3-540-45586-8_4. ISBN 3-540-42877-1. MR 1900016. 
  13. 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 868279. (2008 Second ed., in French: Programmation mathématique : Théorie et algorithmes, Éditions Tec & Doc, Paris, 2008. xxx+711 pp. ).  Unknown parameter |note= ignored (help)
  14. Shapiro, Jeremy F. (1979). Mathematical programming: Structures and algorithms. New York: Wiley-Interscience [John Wiley & Sons]. pp. xvi+388. ISBN 0-471-77886-9. MR 544669. 
  15. Geoffrion, Arthur M. (1971). "Duality in Nonlinear Programming: A Simplified Applications-Oriented Development". SIAM Review 13 (1): 1–37. doi:10.1137/1013001. JSTOR 2028848. 

منابع[ویرایش]

کتاب ها[ویرایش]

  • Ahuja, Ravindra K.; Magnanti, Thomas L.; and Orlin, James B. (1993). Network Flows: Theory, Algorithms and Applications. Prentice Hall. ISBN 0-13-617549-X. 
  • 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] 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] 306. Berlin: Springer-Verlag. pp. xviii+346. ISBN 3-540-56852-2. MR 1295240. 
  • 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. Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000. Lecture Notes in Computer Science (LNCS) 2241. Berlin: Springer-Verlag. pp. 112–156. doi:10.1007/3-540-45586-8_4. ISBN 3-540-42877-1. MR 1900016. 
  • 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 868279. (2008 Second ed., in French: Programmation mathématique : Théorie et algorithmes, Éditions Tec & Doc, Paris, 2008. xxx+711 pp. )).  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. 
  • Ruszczyński, Andrzej (2006). Nonlinear Optimization. Princeton, NJ: Princeton University Press. pp. xii+454. ISBN 978-0691119151. MR 2199043. 

مقالات[ویرایش]