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

برنامه ریزی مخروط مرتبه دوم بسط برنامه‌ریزی مربعی و برنامه‌ریزی خطی است که در آن ترکیب افاین متغیرها به صورت قید داخل یک مخروط مرتبه دوم تعریف می‌شوند. این نوع برنامه‌ریزی در حل مسائل هندسی کاربرد دارد و همچنین در برنامه ریزیهای خطی که داده‌ها با خطا همراه هستند و به طور دقیق مشخص نیستند کاربرد دارد.
مخروط مرتبه دوم
به مجموعه زیر، مخروط نرم مرتبط با نرم گفته می‌شود،
مخروط نرم مرتبه دوم، به ازای نرم اقلیدسی تعریف می‌شود که به طور مثال در به صورت زیر خواهد بود،
\left\{ {\left( ,{x_2,t \right)\left| \leqslant t \right. \right\
این مخروط به علت شکلی که دارد (به طور مثال در مانند قیف بستنی است) با عنوان مخروط بستنی هم شناخته می‌شود.
نمایش فرمولی برنامه ریزی مخروط مرتبه دوم
برنامه ریزی مخروط مرتبه دوم با در نظر گرفتن تابع هدف خطی و قیود نامساوی که به فرم مخروط مرتبه دوم هستند و قیود تساوی افاین به شکل زیر نوشته می‌شود:
\begin{array{l
{\rm{minimize \;\;{f^Tx\\
{\rm{subject \;\; \rm{ to\left\| x + {b_i \right\| \le c_i^Tx + {d_i\;\;\;\;\;i = 1,…,m\\
\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;Fx = g
\end{array
که متغیر بهینه‌سازی است، ، و می‌باشند.
در حالتی که باشد، مسئله برنامه‌ریزی مخروط مرتبه دوم به برنامه‌ریزی مربعی با قیود مربعی (QCQP) تبدیل می‌شود. همچنین در حالت دیگر اگر باشد این مسئله به یک مسئله برنامه‌ریزی خطی تبدیل می‌شود.
مثال: برنامه ریزی خطی آماری
برنامه ریزی خطی آماری با قیود نامساوی را به شکل زیر در نظر بگیرید:
\begin{array{l
{\rm{minimize \;\;{c^Tx\\
{\rm{subject \;\; \rm{ to \;\;{P(a_i^Tx + {b_i) \ge p,\;\;\;\;\;i = 1,…,m\\
\end{array
که متغیر گوسی مستقل با متوسط و کوواریانس هستند و ، این مسئله را می‌توان به فرم یک مسئله مخروط مرتبه دوم به شکل زیر نوشت:
\begin{array{l
{\rm{minimize \;\;{c^Tx\\
{\rm{subject \;\; \rm{ to \;\;\bar{a_i^T x + \Phi^{-1(p) \lVert \Sigma_i^{1/2 x \rVert_2 \leq b_i , \quad i = 1,\dots,m\\
\end{array
که در اینجا معکوس تابع توزیع تجمعی گوسی می‌باشد.
مثال: قید مربعی
در این مثال دیده می‌شود که قید مربعی زیر:
را می‌توان به شکل قید SOCP همانند زیر بازنویسی کرد:
\left\|
\begin{matrix
(1 + b^T x +c)/2\\
Ax
\end{matrix \right\|_2
\leq (1 - b^T x -c)/2.
مثال: مربعات خطا مقاوم
فرض کنید که مجموعه فرامعینی از معادلات به فرم که و مجهول هستند اما به صورت و محدود شده‌اند (نرم ماتریسی در اینجا همان نرم طیفی یا حداکثر مقدار تکین است). می‌توان جواب حداقل مربعات مقاوم را معادل با که جواب حداقل سازی بزرگترین باقیمانده ممکن است و به صورت زیر تعریف می‌شود، در نظر گرفت:
این مسئله، مسئله حداقل مربعات مقاوم است.
در مسئله بالا تابع هدف با پیگیری روند زیر می‌تواند به فرم بسته نوشته شود:
بنابراین مسئله اصلی به صورت زیر تبدیل می‌شود:
که مجموع نرمهای اقلیدسی است.
این مجموع می‌تواند به عنوان یک فرم SOCP مد نظر قرار گیرد. با اینحال، در صورت استفاده از تجزیه مقدار تکین A می‌توان به حل ساده‌تری دست پیدا کرد. مسئله SOCP با قیود دیگر مفیدتر خواهد بود به طور مثال در نظر گرفتن قیود نامنفی.
می‌توان صورت دیگری برای این مسئله متصور بود. به این صورت که فرض کنید، سطرهای ماتریس مرتبط با خطاهای مستقل هستند و البته درون یک بیضی‌گون هستند؛ به عبارتی ، که:
{\varepsilon _i = \left\{ + {P_iu\left| {\left\| u \right\| \leqslant 1 \right. \right\\;\;\left( = P_i^T \succ 0 \right)
حال می‌توان تخمین مربعات خطا مقاوم را با حداقل سازی بدترین باقیمانده به فرم زیر بدست آورد:
با انجام برخی اعمال ریاضی می‌توان رابطه بالا را به صورت زیر بازنویسی کرد:
که به صورت مسئله SOCP زیر قابل بازنویسی خواهد بود:
\begin{align
- \underset{{\operatorname{minimize\;\;\;\;\;\;\;\; s \\
-\operatorname{subject\;to
\;\;\;\;\;\;\left\| t \right\| \leqslant s \\
-\;\;\;\;\;\;\;\;\;\;\;\;\left| {\bar a_i^Tx - {b_i \right| + \left\| x \right\| \leqslant {t_i,i = 1, \cdots ,n
\end{align
کاربردها
طراحی وزن آرایه‌های آنتن
در بحث آرایه آنتنی، خروجی المانهای آنتن به صورت خطی با یکدیگر ترکیب شده و خروجی نهایی را تشکیل می‌دهند. خروجی آرایه دارای جهتی است که وابسته به وزنهای نسبی المانها ربط دارد و هدف از داشتن آرایه‌ای از آنتنها این است که در جهت دلخواهی که مد نظر است بتوانیم جهت خروجی را تنظیم کنیم.
مسئله را می‌توان به شکل زیر تعریف کرد:
\begin{align
- \underset\operatorname{max\;\;\;\;\;\;\;\; \left| {y\left( \theta \right) \right| \\
-\operatorname{subject\;to
\;\;\;\;\;\;\;\;\; y\left( \right) = 1
\end{align
که است، پهنای بیم است و بازه که در حداقل سازی مورد نظر است ملزم می‌دارد که امواج رسیده از سایر جهات غیر از جهت هدف ( ) حداقل شوند. همچنین سیگنال باند پایه متناظر با سیگنال باند میانی است. علاوه بر این شرط به معنای نرمالیزه بودن است.
این مسئله، با گسسته سازی زاویه (به صورت به ازای ) می‌تواند به فرم یک مسئله SOCP تقریب زده شود. پاسخ آرایه را به صورت زیر در نظر بگیرید:
که و
\tilde y = \left {\begin{array{*{20{c
{y\left( \right) \\
\vdots \\
{y\left( \right)
\end{array \right,A = \left {\begin{array{*{20{c
{a\left( \right) \\
\vdots \\
{a\left( \right)
\end{array \right.
آنگاه مسئله بهینه‌سازی می‌تواند به فرم SOCP زیر تقریب زده شود:
\begin{align
- \underset{{\operatorname{minimize\;\;\;\;\;\;\;\; t \\
-\operatorname{subject\;to
\left| {y\left( \right) \right| \leqslant t\;for\;\;\left| - {\theta _k \right|> \Delta \;\;\;\;y\left( \right) = 1
\end{align
که زمانیکه به صورت ترمهای از بخشهای حقیقی و موهومی نوشته شود، فرم SOCP خواهد داشت.
سایر کاربردها
طراحی فیلتر با پاسخ ضربه متناهی هم نمونه دیگری از کاربرد برنامه‌ریزی SOCP است؛ که در آن هم سعی می‌شود خطای بین پاسخ ضربه دلخواه و پاسخ ضربه تولیدی توسط برخی ضرایب است را حداقل کنند. نشان داده شده است که این مسئله را هم به فرم SOCP درآورد.