بهینه‌سازی مخروطی

بهینه‌سازی مخروطی شاخه‌ای از بهینه‌سازی محدب است که هدف آن کمینه کردن توابع محدب در فضای مشترک زیر فضاهای همگَر و مخروطهای محدب است. بهینه‌سازی مخروطی شامل برخی از نمونه‌های شناخته شده مسائل بهینه‌سازی محدب می‌شود، مسائلی مانند برنامه‌نویسی خطی و برنامه‌ریزی نیمه‌معین.

تعریف

با توجه به یک فضای بردار حقیقی $X$، و یک تابع محدب با مقادیر حقیقی $f:C\to \mathbb {R}$ که برای مخروط محدب $C\subset X$ تعریف شده‌است و یک زیرفضای همگر ${\mathcal {H}}$ که با محدودیت‌های $h_{i}(x)=0\$ مشخص می‌شود، یک مسئله بهینه‌سازی مخروطی پیداکردن یک نقط $x$ در $C\cap {\mathcal {H}}$ است به گونه‌ای که تابع $f(x)$ را کمینه کند.

مثالهای مخروط $C$ شامل متعامد کنجِ $\mathbb {R} _{+}^{n}=\left\{x\in \mathbb {R} ^{n}:\,x\geq \mathbf {0} \right\}$، ماتریسهای مثبت معین $\mathbb {S} _{+}^{n}$ و مخروط‌های درجه دومِ $\left\{(x,t)\in \mathbb {R} ^{n}\times \mathbb {R} :\lVert x\rVert \leq t\right\}$ می‌شود. تابع $f\$ معمولاً خطی است که باعث می‌شود مسئله بهینه‌سازی مخروطی به برنامه‌ریزی خطی، برنامه‌ریزی نیمه‌معین، یا برنامه‌ریزی مخروطی درجه دوم تقلیل پیدا کند.

دوگانگی

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

مخروطی LP

دوگانه برنامه خطی مخروطی

minimize $c^{T}x\$

subject to $Ax=b,x\in C\$

برابر است با

maximize $b^{T}y\$

subject to $A^{T}y+s=c,s\in C^{*}\$

در اینجا $C^{*}$ دوگانه مخروط $C$ است.

در حالتی که دوگانگی ضعیف در برنامه‌نویسی خطی مخروطی وجود دارد، دوگانگی قوی لزوماً برقرار نیست.

بهینه‌سازی نیمه معین

دوگانه یک مسئله بهینه‌سازی نیمه معین در شکل نابرابری پایین

minimize $c^{T}x\$

مشروط بر اینکه $x_{1}F_{1}+\cdots +x_{n}F_{n}+G\leq 0$ باشد.

برابر است با

maximize $\mathrm {tr} \ (GZ)\$

مشروط بر اینکه $\mathrm {tr} \ (F_{i}Z)+c_{i}=0,\quad i=1,\dots ,n$ و $Z\geq 0$ باشد.

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

• Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization (pdf). Cambridge University Press. ISBN 978-0-521-83378-3. Retrieved October 15, 2011.
• نرم افزار MOSEK قادر به حل مشکلات بهینه‌سازی مخروطی است.