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

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

مسئله اصلی

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

$$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$ را ندارد.

جستارهای وابسته

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

منابع

en:Convex optimization en:Mathematical optimization