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

**برنامه [[مخروط مرتبه دوم|مخروط دوگان]]** (**SOCP**) یکی از مسائل بهینه‌سازی محدب می‌باشد؛ و به این صورت است:
:\ f^T x \  را کمینه کنید
: اگر داشته باشیم
::\lVert A_i x + b_i \rVert_2 \leq c_i^T x + d_i,\quad i = 1,\dots,m
::Fx = g \ 
با پارامترهای f \in \mathbb{R}^n, \ A_i \in \mathbb{R}^.

مخروط نرم مرتبه دوم، به ازای نرم اقلیدسی تعریف می‌شود که به‌طور مثال در {\R ^3} به صورت زیر خواهد بود،


\left\{ {\left(  \;\;{f^T}x\\
{\rm{subject} \;\; \rm{  to}}\left\|  \right\| \le c_i^Tx + {d_i}\;\;\;\;\;i = 1,...,m\\
\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;Fx = g
\end{array}


که x \in {\mathbb{R}^n} متغیر بهینه‌سازی است، {A_i} \in {\mathbb{R}^، و F \in {\mathbb{R}^{p \times n}} می‌باشند.

در حالتی که {c_i} = 0 باشد، مسئله برنامه‌ریزی مخروط مرتبه دوم به برنامه‌ریزی مربعی با قیود مربعی (QCQP) تبدیل می‌شود. همچنین در حالت دیگر اگر {A_i} = 0 باشد این مسئله به یک مسئله برنامه‌ریزی خطی تبدیل می‌شود.

## مثال: برنامه ریزی خطی آماری
برنامه ریزی خطی آماری با قیود نامساوی را به شکل زیر در نظر بگیرید:


\begin{array}{l}
{\rm{minimize}} \;\;{c^T}x\\
{\rm{subject} \;\; \rm{  to}} \;\;{P(a_i^Tx + {b_i}})  \ge p,\;\;\;\;\;i = 1,...,m\\
\end{array}


که a_i متغیر گوسی مستقل با متوسط \bar{a}_i و کوواریانس \Sigma_i \  هستند و p\geq0.5، این مسئله را می‌توان به فرم یک مسئله مخروط مرتبه دوم به شکل زیر نوشت:


\begin{array}{l}
{\rm{minimize}} \;\;{c^T}x\\
{\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}


که در اینجا \Phi^{-1} معکوس تابع توزیع تجمعی گوسی می‌باشد.

## مثال: قید مربعی
در این مثال دیده می‌شود که قید مربعی زیر:

: x^T A^T A x + b^T x + c \leq 0. 

را می‌توان به شکل قید SOCP همانند زیر بازنویسی کرد:

: \left\|
\begin{matrix}
(1 + b^T x +c)/2\\
Ax
\end{matrix} \right\|_2

\leq (1 - b^T x -c)/2.

## مثال: مربعات خطا مقاوم
فرض کنید که مجموعه فرامعینی از معادلات به فرم  Ax \approx b  که  A \in {\mathbb{R}^{m \times n}} و b \in {\mathbb{R}^m} مجهول هستند اما به صورت \left\| {\delta A} \right\| \leqslant \rho  و \left\| {\delta b} \right\| \leqslant \xi  محدود شده‌اند (نرم ماتریسی در اینجا همان نرم طیفی یا حداکثر مقدار تکین است). می‌توان جواب حداقل مربعات مقاوم را معادل با \hat x \in {\mathbb{R}^n} که جواب حداقل سازی بزرگترین باقی‌مانده ممکن است و به صورت زیر تعریف می‌شود، در نظر گرفت:

{\text{minimize}}\;\;\;\;\;\mathop }\limits_{\left\| {\delta A} \right\| \leqslant \rho ,\left\| {\delta b} \right\| \leqslant \xi } {\text{ }}\left\| {\left( {A + \delta A} \right)x - \left( {b + \delta b} \right)} \right\|

این مسئله، مسئله حداقل مربعات مقاوم است.

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

\mathop }\limits_{\left\| {\delta A} \right\| \leqslant \rho ,\left\| {\delta b} \right\| \leqslant \xi } {\text{ }}\left\| {\left( {A + \delta A} \right)x - \left( {b + \delta b} \right)} \right\| = \mathop }\limits_{\left\| {\delta A} \right\| \leqslant \rho ,\left\| {\delta b} \right\| \leqslant \xi } \mathop }\limits_{\left\| y \right\| \leqslant 1} {\text{ }}{y^T}\left( {Ax - b} \right){\text{ + }}{y^T}\delta Ax - {y^T}\delta b

 = \mathop }\limits_{\left\| z \right\| \leqslant \rho } \mathop }\limits_{\left\| y \right\| \leqslant 1} {\text{ }}{y^T}\left( {Ax - b} \right){\text{ + }}{z^T}x + \xi  = \left\| {Ax - b} \right\| + \rho \left\| x \right\| + \xi 

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

{\text{minimize}}\left\| {Ax - b} \right\| + \rho \left\| x \right\| + \xi 

که مجموع نرمهای اقلیدسی است.

این مجموع می‌تواند به عنوان یک فرم SOCP مد نظر قرار گیرد. با اینحال، در صورت استفاده از تجزیه مقدار تکین A می‌توان به حل ساده‌تری دست پیدا کرد. مسئله SOCP با قیود دیگر مفیدتر خواهد بود به‌طور مثال در نظر گرفتن قیود نامنفی.
می‌توان صورت دیگری برای این مسئله متصور بود. به این صورت که فرض کنید، سطرهای ماتریس A مرتبط با خطاهای مستقل هستند و البته درون یک بیضی‌گون هستند؛ به عبارتی {a_i} \in {\varepsilon _i}، که:


{\varepsilon _i} = \left\{ }

با انجام برخی اعمال ریاضی می‌توان رابطه بالا را به صورت زیر بازنویسی کرد:

{\text{minimize}}{\left( {\sum\limits_{i = 1}^n  \right| + \left\|  } \right)^{\frac{1}{2}}}

که به صورت مسئله SOCP زیر قابل بازنویسی خواهد بود:

: \begin{align}

& \underset{}{\operatorname{minimize}}\;\;\;\;\;\;\;\; s \\

&\operatorname{subject\;to}

\;\;\;\;\;\;\left\| t \right\| \leqslant s \\

&\;\;\;\;\;\;\;\;\;\;\;\;\left| {\bar a_i^Tx - {b_i}} \right| + \left\| {\operatorname{max}}\;\;\;\;\;\;\;\; \left| {y\left( \theta  \right)} \right| \\

&\operatorname{subject\;to}

\;\;\;\;\;\;\;\;\; y\left(  \right) = 1

\end{align}

که {y\left( \theta  \right) = \sum\limits_{i = 1}^n  \right| > \Delta } که در حداقل سازی مورد نظر است ملزم می‌دارد که امواج رسیده از سایر جهات غیر از جهت هدف (\theta _t) حداقل شوند. همچنین 
  {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|  \right|> \Delta \;\;\;\;y\left(  \right) = 1

\end{align}

که زمانیکه به صورت ترمهای از بخش‌های حقیقی و موهومی نوشته شود، فرم SOCP خواهد داشت.

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

## منابع

رده:بهینه‌سازی ریاضی
رده:بهینه‌سازی محدب
رده:روش‌های بهینه‌سازی