بهینه‌سازی محدب

مسئلهٔ بهینه‌سازی محدب یا بهینه‌سازی کوژ (به انگلیسی: Convex Optimization) به یافتن مقدار حداقل یک تابع محدب (یا حداکثر یک تابع مقعر) از بین مجموعه‌ای محدب گفته می‌شود. مهمترین مزیت این نوع مسائل بهینه‌سازی در این است که هر نقطهٔ بهینهٔ محلی یک نقطه بهینهٔ سراسری نیز است و هر الگوریتم بهینه‌سازی که یک نقطه بهینهٔ محلی را یافت در حقیقت یک نقطه بهینهٔ سراسری را یافته‌است.^[۱]

مسئله بهینه‌سازی شبه محدب

مسئله بهینه‌سازی شبه محدب، فرم استاندارد زیر را دارد:^[۲]

${\displaystyle \min f_{o}(x)\quad s.t.\quad f_{i}(x)\leq 0\quad i=1,...,m\quad ,Ax=b}$

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

پاسخ‌های بهینه محلی و شرایط بهینگی

مهمترین اختلاف بین بهینه‌سازی محدب و شبه محدب این است که مسائل بهینه‌سازی شبه محدب می‌توانند جواب‌های بهینه محلی داشته باشد. این پدیده می‌تواند حتی در ساده‌ترین مورد، کمینه سازی بدون قید یک تابع شبه محدب روی ${\displaystyle R}$ دیده شود.

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

${\displaystyle \bigtriangledown f_{0}(x)^{T}(y-x)\geq 0\,\,\,for\,\,\,all\,\,\,y\in X}$

انواع شرایط بهینگی برای مسائل بهینه‌سازی شبه محدب با توابع هدف مشتق پذیر برقرار است. ${\displaystyle X}$ را فضای شدنی برای مسئله بهینه‌سازی شبه محدب در نظر بگیرید، در این صورت ${\displaystyle x}$ بهینه است اگر:

${\displaystyle x\in X,\quad \quad \bigtriangledown f_{0}(x)^{T}(y-x)>0\,\,\,for\,\,\,all\,\,\,y\in X}$

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

۱- معیار مسائل شبه محدب برای بهینگی پاسخ شرط کافی است و برقراری آن برای نقطه بهینه ضروری نیست اما برقراری رابطه فوق برای مسائل محدب شرط لازم و کافی برای بهینگی ${\displaystyle x}$ می‌باشد.

۲-معیار فوق نیازمند این است که گرادیان تابع هدف غیر صفر باشد در حالی که در رابطه بهینگی مسائل محدب اینگونه نیست، در واقع زمانی که ${\displaystyle \bigtriangledown f_{0}(x)=0}$، معیار بهینگی مسائل محدب صادق است و ${\displaystyle x}$ نقطه بهینه است.

یک روش کلی برای مسائل بهینه‌سازی شبه محدب وابسته به نمایش مجموعه‌های زیرسطحی از یک تابع شبه محدب است. ${\displaystyle \phi _{t}:R^{n}\rightarrow \,\,t\in R}$ را به عنوان مجموعه‌ای از توابع محدب که در رابطه زیر صدق می‌کنند در نظر بگیرید.^[۳]

${\displaystyle f_{0}(x)\leq t\Leftrightarrow \phi _{t}(x)\leq 0}$

و برای هر ${\displaystyle x}$، ${\displaystyle \phi _{t}(x)}$ یک تابع غیر صعودی از ${\displaystyle t}$ است. فرض کنید ${\displaystyle p^{*}}$ جواب بهینه مسئله بهینه‌سازی شبه محدب باشد.

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

${\displaystyle find\quad x\quad s.t.\quad \phi _{t}(x)\quad \leq 0,\quad f_{i}(x)\leq 0,\quad Ax=b}$

شدنی باشد سپس ${\displaystyle p^{*}\leq t}$ را خواهیم داشت. در طرف مقابل اگر مسئله فوق نشدنی باشد می‌توانیم نتیجه بگیریم ${\displaystyle p^{*}\geq t}$ خواهد بود. مسئله فوق یک مسئله امکان‌سنجی محدب است چون قیود نامساوی محدب هستند و قید تساوی نیز خطی است؛ بنابراین می‌توانیم بررسی کنیم آیا مقدار ${\displaystyle p^{*}}$ کمتر یا بیشتر از مقدار ${\displaystyle t}$ ای است که با حل مسئله امکان‌سنجی فوق به دست می‌آید. اگر مسئله امکان‌سنجی شدنی باشد پس خواهیم داشت ${\displaystyle p^{*}\leq t}$ و هر نقطه شدنی مثل ${\displaystyle x}$ برای مسئله شبه محدب نیز شدنی است و رابطه ${\displaystyle f_{0}(x)\leq t}$ را ارضا می‌کند. اگر مسئله امکان‌سنجی محدب نشدنی باشد می‌توان نتیجه گرفت ${\displaystyle p^{*}\geq t}$ خواهد بود.

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

• رهاسازی_محدب
• تکمیل ماتریس
• مسئله بهینه‌سازی
• بهینه‌سازی پاوسته

منابع

1. Rockafellar, R. Tyrrell. "Lagrange Multipliers and Optimality". SIAM Review (به انگلیسی). 35 (2): 183–238. ISSN 0036-1445.
2. Boyd، Stephen. Convex Optimization. صص. ۱۵۸.
3. «. Convergence and efficiency of subgradient methods for quasiconvex minimization». Mathematical programming. ۲۰۰۱.

• Boyd, Stephen; Vandenberghe, Lieven. Convex Optimization (به انگلیسی).

پیوند به بیرون

• EE364a: Convex Optimization I and EE364b: Convex Optimization II, Stanford course homepages
• 6.253: Convex Analysis and Optimization, an MIT OCW course homepage
• Brian Borchers, An overview of software for convex optimization