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

{{ادغام با|دوگانگی (بهینه‌سازی)}}
در حل مسئله [[بهینه‌سازی]] به روش معادل سازی، یک مسئله معادل برای مسئله استاندارد تعریف می‌کنیم که پاسخ آن بسیار راحت‌تر از مسئله اولیه به دست می‌آید؛ برای به دست آوردن مسئله معادل روند مشخصی وجود ندارد اما برای برخلاف آن '''در حل مسئله بهینه‌سازی از طریق [[دوگانگی (بهینه‌سازی)|دوگان]]''' یک روند مشخص برای به دست آوردن مسئله دوگان وجود دارد. برای هر مسئله بهینه‌سازی می‌توان یک معادل محدب تعریف کرد. . پاسخ این مسئله یک کران پایین روی مسئله اصلی ارائه می‌دهد و در حالت محدب دقیقاً همان جواب است. 

== مسئله اصلی ==
فرم استاندارد یک مسئله بهینه‌سازی به صورت زیر می‌باشد:<math display="block">min f_0(x);
</math><math display="block">s.t.f_i(x)\leq0, i=1,...,m
</math>به این مسئله، مسئله اصلی می‌گویند. متغیر بهینه‌سازی <math>x</math>، را پارامتر اولیه گویند. <math>f_i(x)\leq0, i=1,...,m
</math> قیود نامساوی می‌باشند.

== تابع لاگرانژی ==
تابع لاگرانژی که یک مجموعه وزن دار از تابع هدف و قیود است را بفرم زیر نمایش می‌دهند:<math display="block">L(x,y)=f_0(x)+\sum_{i=1}^my_if_i(x)
</math>لاگرانژی تابعی از پارامتر اولیه و یک متغیر اضافه <math>y</math> می‌باشد که به آن متغیر دوگان گویند.

== تابع [[دوگانگی (بهینه‌سازی)|دوگان]] ==
با کمک تابع لاگرانژی می‌توان یک تابع جدید (تنها از متغیر دوگان) بنام تابع دوگان ساخت. این تابع را می‌توان بفرم زیر نمایش داد:<math display="block">g(y)=min L(x,y)= minf_0(x)+\sum_{i=1}^my_i f_i(x)</math>g به صورت حداقل نقطه‌ای تعریف می‌شود پس مقعر است.

به ازای هر<math>x,y</math> داریم:<math display="inline">L(x,y)\geq g(y)</math> . تابع <math>g</math> کران پایینی از تابع هدف در ناحیه شدنی ارائه می‌دهد را ارائه می‌دهد.

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

== مسئله دوگان ==
از آنجا که کران پایین برای هر <math>y\geq 0</math> صادق است، باید به دنبال بهترین آن بود، که آن بزرگترین کران پایین است:<math display="block">P^*\geq d^* = max g(y);y\geq 0</math>به دست آوردن کران پایین از طریق مسئله دوگان ساده‌تر است زیرا محاسبه <math>g(y)</math>  با قیود کمتری همراه است. مسئله پیدا کردن بهترین کران پایین به صورت زیر تعریف می‌شود:<math display="block">d^* = max g(y);y\geq 0</math>این مسئله، مسئله دوگان نامیده می‌شود. مقدار بهینه آن <math>d^*</math>، مقدار بهینه دوگان نام دارد. همان‌طور که در بالا بیان شد، <math>g</math> مقعر است. این به آن معنی است که مسئله دوگان، که شامل حداکثرسازی <math>g</math>، یک مسئله بهینه‌سازی محدب می‌باشد.<ref>{{یادکرد وب|نویسنده=jemdoc|کد زبان=En|تاریخ=|وبگاه=|نشانی=https://inst.eecs.berkeley.edu/~ee127a/book/login/l_dual_weak_lag.html|عنوان=Dual Problem|accessdate=۲۳ ژانویه ۲۰۱۷|archiveurl=https://web.archive.org/web/20141227104216/http://inst.eecs.berkeley.edu/~ee127a/book/login/l_dual_weak_lag.html|archivedate=۲۷ دسامبر ۲۰۱۴|dead-url=yes}}</ref>

== مسائل با قیود تساوی ==
در این حالت یک قید دیگر به صورت  <math display="inline">hi(x)=0, i=1,...,p</math>به مسئله اصلی افزوده می‌شود. برای حل آن به روش دوگان، متغیر دوگان <math>v</math> را تعریف می‌کنند و باکمک آن تابع دوگان را تشکیل می‌دهیم؛ یعنی در تابع دوگان جمله <math>\sum_{i=1}^p v_i h_i(x)</math> افزوده می‌شود. متغیر <math>v</math> شرط <math>v\geq 0</math> را ندارد.<ref>{{یادکرد کتاب|عنوان=convex optimization|نام خانوادگی=Boyd|نام=stephan|ناشر=Cambridge university press|سال=2004|شابک=|مکان=newyork|صفحات=}}</ref>
== جستارهای وابسته==
* [[دوگانگی (بهینه‌سازی)]]
== منابع ==
{{پانویس}}
[[رده:بهینه‌سازی ریاضی]]
[[رده:بهینه‌سازی]]
[[رده:بهینه‌سازی محدب]]
[[:en:Convex optimization]]
[[:en:Mathematical optimization]]