ⓘ دوگانگی, بهینه‌سازی. در نظریه بهینه‌سازی ریاضیاتی، دوگانگی بدین معنی است که مسائل بهینه‌سازی را می‌توان از هر یک از دو دیدگاه مسئلهٔ اصلی و مسئلهٔ دوگان نگریست. ..

                                     

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

در نظریه بهینه‌سازی ریاضیاتی، دوگانگی بدین معنی است که مسائل بهینه‌سازی را می‌توان از هر یک از دو دیدگاه مسئلهٔ اصلی و مسئلهٔ دوگان نگریست. راه حل مسئله ی دوگان کران پایینی برای راه حل مسئلهٔ اصلی ارائه می‌کند. هرچند به‌طور معمول دلیلی ندارد که مقادیر بهینهٔ مسائل اصلی و دوگان برابر باشند. به اختلاف این دو شکاف دوگانگی گویند. البته در مسائل بهینه‌سازی محدب ، شکاف دوگانگی تحت یک شرط constraint qualification می‌تواند صفر باشد؛ بنابراین راه حل مسئلهٔ دوگان کرانی برای مقدار راه حل مسئلهٔ اصلی است؛ وقتی مسئله محدب است و یک constraint qualification را تأمین می‌کند در این صورت مقدار یک راه حل بهینهٔ مسئلهٔ اصلی توسط مسئلهٔ دوگان داده می‌شود.

                                     

1. تاریخچه

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

                                     

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

معمولاً مسئلهٔ دوگانگی اشاره با مسئلهٔ دو گانگی لاگرانژی دارد؛ ولی مسائل دوگانگی دیگری نیز، مانند مسئلهٔ دوگانگی Wolfe و مسئله ی دوگانگی Fenchel، مورد استفاده قرار می‌گیرند. مسئلهٔ دوگانگی لاگرانژی با تشکیل لاگرانژین Lagrangian، با استفاده از ضرایب نامنفی لاگرانژی، به منظور افزودن قیدها به تابع هدف و سپس حل کردن آن برای برخی مقادیر متغیر اصلی که لاگرانژین را کمینه می‌کند، به دست می‌آید. این راه حل متغیرهای اصلی the primal variables را به عنوان تابعی از ضرایب لاگرانژ ارائه می‌دهد که به آن‌ها متغیرهای دوگان dual varibales می‌گویند؛ بنابراین مسئلهٔ جدید این است که تابع هدف را نسبت به متغیرهای دوگان در شرایط حاصل از متغیزهای دوگان مثلاً حداقل نامنفی بودن آنها بیشینه کنیم. معمولاً با داشتن دو زوج دوگانه dual pairs از فضاهای محدب محلی مجزا separated locally convex spaces X, X ∗ {\displaystyle \leftX,X^{*}\right} و Y, Y ∗ {\displaystyle \leftY,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}fx\,} ، تعریف کنیم.

اگر constraint conditions وجود داشته باشد، امکان اعمال آن‌ها به تابع f {\displaystyle f} به واسطهٔ قرار دادن f ~ = f + I c o n s t r a i n t s {\displaystyle {\tilde {f}}=f+I_{\mathrm {constraints} }} که در آن I {\displaystyle I} تابع مشخصه indicator function است وجود دارد. آنگاه F: X × Y → R ∪ { + ∞ } {\displaystyle F:X\times Y\to \mathbb {R} \cup \{+\infty \}} را به عنوان یک تابع اغتشاش perturbation function به صورتی که در آن F x, 0 = f x {\displaystyle Fx,0=fx} است، در نظر گرفت.

شکاف دوگانگی عبارت از اختلاف سمت راست و چپ نامعادلهٔ sup y ∗ ∈ Y ∗ − F ∗ 0, y ∗ ≤ inf x ∈ X F x, 0, {\displaystyle \sup _{y^{*}\in Y^{*}}-F^{*}0,y^{*}\leq \inf _{x\in X}Fx,0,\,} است که در آن مزدوج محدب convex conjugate در هر دو متغیر و s u p {\displaystyle sup} نشانگر سوپریمم کوچکترین کران بالا است.

                                     

2.1. مسئلهٔ دوگانگی Dual Problem شکاف دوگانگی duality gap

شکاف دوگانگی عبارت از تفاوت بین متغیرهای هر راه حل اصلی و هر راه حل دوگان است. اگر d ∗ {\displaystyle d^{*}} مقدار دوگان ی بهینه و p ∗ {\displaystyle p^{*}} مقداراصلی ی بهینه باشد، آنگاه شکاف دوگانگی برابر p ∗ − d ∗ {\displaystyle 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 را دارد که عبارت از پوش محدب بستهٔ تابع اصلی هدف اصلی است.

                                     

3. مورد خطی the linear case

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

                                     

3.1. مورد خطی the linear case رابطهٔ بین مسئلهٔ اصلی و مسئلهٔ دوگان

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

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

                                     

3.2. مورد خطی the linear case تفسیر اقتصادی

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

                                     

4. حالت غیر خطی

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

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

                                     

4.1. حالت غیر خطی اصل قوی لاگرانژی: دوگانگی لاگرانژی

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

minimize f 0 x subject to f i x ≤ 0, i ∈ { 1, …, m } h i x = 0, i ∈ { 1, …, p } {\displaystyle {\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}}}

با دامنهٔ D ⊂ R n {\displaystyle {\mathcal {D}}\subset \mathbb {R} ^{n}} که Interior غیر تهی، دارد، تابع لاگرانژین Λ: R n × R m × R p → R {\displaystyle \Lambda:\mathbb {R} ^{n}\times \mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R} } به صورت Λ x, λ, ν = f 0 x + ∑ i = 1 m λ i f i x + ∑ i = 1 p ν i h i x {\displaystyle \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} تعریف می‌شود.

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

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

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

                                     

4.2. حالت غیر خطی مسائل محدب

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

minimize x f x s u b j e c t o g i x ≤ 0, i = 1, …, m {\displaystyle {\begin{aligned}&{\underset {x}{\operatorname {minimize} }}&&fx\\&\operatorname {subject\;to} &&g_{i}x\leq 0,\quad i=1,\dots,m\end{aligned}}}

مسئلهٔ دوگان لاگرانژی maximize u inf x f x + ∑ j = 1 m u j g j x) s u b j e c t o u i ≥ 0, i = 1, …, m {\displaystyle {\begin{aligned}&{\underset {u}{\operatorname {maximize} }}&&\inf _{x}\leftfx+\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 {\displaystyle f} و g 1, ⋯, g m {\displaystyle g_{1},\cdots,g_{m}} به صورت پیوسته مشتق پذیر باشند، اینفیمم هنگامی که گرادیان برابر صفر باشد رخ می‌دهد. مسئلهٔ maximize x, u f x + ∑ j = 1 m u j g j x s u b j e c t o ∇ f x + ∑ j = 1 m u j ∇ g j x = 0 u i ≥ 0, i = 1, …, m {\displaystyle {\begin{aligned}&{\underset {x,u}{\operatorname {maximize} }}&&fx+\sum _{j=1}^{m}u_{j}g_{j}x\\&\operatorname {subject\;to} &&\nabla fx+\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 {\displaystyle u,x} مقعر نیست. همچنین شرط تساوی ∇ f x + ∑ j = 1 m u j ∇ g j x {\displaystyle \nabla fx+\sum _{j=1}^{m}u_{j}\nabla g_{j}x} معمولاً غیر خطی است، بنابراین مسئلهٔ دوگان Wolfe به‌طور معمول یک مسئلهٔ بهینه‌سازی غیر مقعر است. در هر صورت دوگانگی ضعیف برقرار است.

                                     

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

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

                                     

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

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

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

5.2. حل مسئله بهینه‌سازی از طریق دوگان تابع لاگرانژی

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

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

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

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

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

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

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

                                     

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

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

به دست آوردن کران پایین از طریق مسئله دوگان ساده‌تر است زیرا محاسبه g y {\displaystyle gy} با قیود کمتری همراه است. مسئله پیدا کردن بهترین کران پایین به صورت زیر تعریف می‌شود:این مسئله، مسئله دوگان نامیده می‌شود. مقدار بهینه آن d ∗ {\displaystyle d^{*}} ، مقدار بهینه دوگان نام دارد. همان‌طور که در بالا بیان شد، g {\displaystyle g} مقعر است. این به آن معنی است که مسئله دوگان، که شامل حداکثرسازی g {\displaystyle g} ، یک مسئله بهینه‌سازی محدب می‌باشد.
                                     

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

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

                                     

6. منابع

  • Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude 1993. Convex analysis and minimization algorithms, Volume I: Fundamentals. Grundlehren der Mathematischen Wissenschaften. 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.
  • Bertsekas, Dimitri P. 1999. Nonlinear Programming 2nd ed. Athena Scientific. ISBN 1-886529-00-0.
  • Ruszczyński, Andrzej 2006. Nonlinear Optimization. Princeton, NJ: Princeton University Press. pp. xii+454. ISBN 978-0-691-11915-1. MR 2199043.
  • Nering, Evar D.; Tucker, Albert W. 1993. Linear Programming and Related Problems. Boston, MA: Academic Press. ISBN 978-0-12-515440-6.
  • 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.
  • پرش به بالا↑ jemdoc. "Dual Problem".
  • Ahuja, Ravindra K.; Magnanti, Thomas L.; and Orlin, James B. 1993. Network Flows: Theory, Algorithms and Applications. Prentice Hall. ISBN 0-13-617549-X. نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان link
  • پرش به بالا↑ Boyd, stephan. convex optimization. newyork: Cambridge university press، ۲۰۰۴.
  • Dantzig, George B. 1963. Linear Programming and Extensions. Princeton, NJ: Princeton University Press.
  • 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. نگهداری یادکرد:نام‌های متعدد:فهرست ویراستاران link
  • 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.
  • 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.
  • 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.
  • 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).
  • Papadimitriou, Christos H.; Steiglitz, Kenneth July 1998. Combinatorial Optimization: Algorithms and Complexity Unabridged ed. Dover. ISBN 0-486-40258-4. نگهداری یادکرد:تاریخ و سال link

en:Convex optimization en:Mathematical optimization