نمایش مبدأ برای بهینه‌سازی محدب

مسئلهٔ '''بهینه‌سازی محدب''' یا '''بهینه‌سازی کوژ''' {{انگلیسی|Convex Optimization}} به یافتن مقدار حداقل یک [[تابع محدب]] (یا حداکثر یک [[تابع مقعر]]) از بین [[مجموعه محدب|مجموعه‌ای محدب]] گفته می‌شود. مهمترین مزیت این نوع مسائل بهینه‌سازی در این است که هر نقطهٔ بهینهٔ محلی یک نقطه بهینهٔ سراسری نیز است و هر الگوریتم بهینه‌سازی که یک نقطه بهینهٔ محلی را یافت در حقیقت یک نقطه بهینهٔ سراسری را یافته‌است.<ref>{{Cite journal|last= Rockafellar|first =R. Tyrrell|date= |title =Lagrange Multipliers and Optimality|url= |journal =SIAM Review|language= English|volume =35|issue= 2|pages =183–238|issn= 0036-1445|via =}}</ref>

== مسئله بهینه‌سازی شبه محدب ==
[[مسئله بهینه‌سازی]] شبه محدب، فرم استاندارد زیر را دارد:<ref name=":0">{{یادکرد کتاب|عنوان=Convex Optimization|نام خانوادگی= Boyd|نام =Stephen|ناشر= |سال =|شابک= |مکان =|صفحات=158}}</ref>

<math>\min f_o(x)\quad s.t. \quad f_i(x)\leq0 \quad i=1,...,m \quad, Ax=b</math>

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

=== پاسخ‌های بهینه محلی و شرایط بهینگی ===
مهمترین اختلاف بین بهینه‌سازی محدب و شبه محدب این است که مسائل بهینه‌سازی شبه محدب می‌توانند جواب‌های بهینه محلی داشته باشد. این پدیده می‌تواند حتی در ساده‌ترین مورد، کمینه سازی بدون قید یک تابع شبه محدب روی <math>R</math> دیده شود.

برای یک مسئله بهینه‌سازی محدب، x بهینه است اگر:

<math> \bigtriangledown f_0(x)^T(y-x)\geq 0 \,\,\, for\,\,\, all \,\,\,y\in X </math>

انواع شرایط بهینگی برای مسائل بهینه‌سازی شبه محدب با توابع هدف [[مشتق پذیر]] برقرار است. <math>X</math> را فضای شدنی برای مسئله بهینه‌سازی شبه محدب در نظر بگیرید، در این صورت <math>x</math> بهینه است اگر:

<math>x \in X,\quad\quad \bigtriangledown f_0(x)^T(y-x)>0 \,\,\, for\,\,\, all \,\,\,y\in X </math>

دو تفاوت مهم بین معیار فوق و معیار بهینگی برای مسائل محدب وجود دارد:

۱- معیار مسائل شبه محدب برای بهینگی پاسخ شرط کافی است و برقراری آن برای نقطه بهینه ضروری نیست اما برقراری رابطه فوق برای مسائل محدب [[شرط لازم و کافی]] برای بهینگی <math>x</math> می‌باشد.

۲-معیار فوق نیازمند این است که گرادیان تابع هدف غیر صفر باشد در حالی که در رابطه بهینگی مسائل محدب اینگونه نیست، در واقع زمانی که <math>\bigtriangledown f_0(x)=0</math>، معیار بهینگی مسائل محدب صادق است و <math>x</math> نقطه بهینه است.

یک روش کلی برای مسائل بهینه‌سازی شبه محدب وابسته به نمایش مجموعه‌های زیرسطحی از یک تابع شبه محدب است. <math>\phi_t:R^n \rightarrow \,\,t \in R</math> را به عنوان مجموعه‌ای از توابع محدب که در رابطه زیر صدق می‌کنند در نظر بگیرید.<ref>{{یادکرد ژورنال|عنوان=. Convergence and efficiency of subgradient methods for quasiconvex minimization|ژورنال=Mathematical programming|ناشر= |تاریخ =2001|زبان= |شاپا =|doi= |پیوند =|تاریخ دسترسی=}}</ref>

<math>f_0(x)\leq t \Leftrightarrow \phi_t(x)\leq 0</math>

و برای هر <math>x</math>، <math>\phi_t(x)</math> یک تابع غیر صعودی از <math>t</math> است. فرض کنید <math>p^*</math> جواب بهینه مسئله بهینه‌سازی شبه محدب باشد.

اگر مسئله امکان‌سنجی زیر،

<math>find \quad x\quad s.t. \quad \phi_t(x)\quad \leq0,\quad f_i(x)\leq0,\quad  Ax=b</math>

شدنی باشد سپس <math>p^* \leq t</math> را خواهیم داشت. در طرف مقابل اگر مسئله فوق نشدنی باشد می‌توانیم نتیجه بگیریم <math>p^*\geq t</math> خواهد بود. مسئله فوق یک مسئله امکان‌سنجی محدب است چون قیود نامساوی محدب هستند و قید تساوی نیز خطی است؛ بنابراین می‌توانیم بررسی کنیم آیا مقدار <math>p^*</math> کمتر یا بیشتر از مقدار <math>t</math> ای است که با [[حل مسئله]] امکان‌سنجی فوق به دست می‌آید. اگر مسئله امکان‌سنجی شدنی باشد پس خواهیم داشت <math>p^* \leq t</math> و هر نقطه شدنی مثل <math>x</math> برای مسئله شبه محدب نیز شدنی است و رابطه <math>f_0(x)\leq t</math> را ارضا می‌کند. اگر مسئله امکان‌سنجی محدب نشدنی باشد می‌توان نتیجه گرفت <math>p^*\geq t</math> خواهد بود.

== جستارهای وابسته ==
* [[رهاسازی_محدب]]
* [[تکمیل ماتریس]]
* [[مسئله بهینه‌سازی]]
*[[بهینه‌سازی پاوسته]]

== منابع ==
{{پانویس}}
{{چپ‌چین}}
* {{یادکرد کتاب | نام خانوادگی = Boyd| نام = Stephen| نام خانوادگی۲ = Vandenberghe| نام۲ = Lieven | عنوان = Convex Optimization| سال = | ناشر = |مکان = | شابک = 0521833787 | پیوند = http://www.stanford.edu/~boyd/cvxbook/| زبان = en}}
{{پایان چپ‌چین}}

== پیوند به بیرون ==
{{چپ‌چین}}
* [http://www.stanford.edu/class/ee364a/ EE364a: Convex Optimization I] and [http://www.stanford.edu/class/ee364b/ EE364b: Convex Optimization II], Stanford course homepages
* [http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-253-convex-analysis-and-optimization-spring-2012/index.htm 6.253: Convex Analysis and Optimization], an MIT OCW course homepage
* Brian Borchers, [https://web.archive.org/web/20170918180026/http://infohost.nmt.edu/~borchers/presentation.pdf An overview of software for convex optimization]
{{پایان چپ‌چین}}
{{الگوریتم‌های بهینه‌سازی}}
{{زیرمجموعه‌های اصلی بهینه‌سازی}}
{{آنالیز محدب}}

{{ریاضی-خرد}}

[[رده:بهینه‌سازی محدب]]
[[رده:آنالیز محدب]]
[[رده:بهینه‌سازی]]
[[رده:بهینه‌سازی ریاضی]]
[[رده:ویکی‌سازی رباتیک]]