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

یک درجه‌دو محدود شده به صورت زیر را در نظر بگیرید

${\displaystyle x^T{A}^{T}Ax+b^{T}x+c\le 0.}$

این معادل است با SOC محدود شده

${\displaystyle {\Vert \begin{array}{c}(1+b^{T}x+c)/2\\ Ax\end{array}\Vert }_2\le (1-b^{T}x-c)/2.}$

یک برنامه خطی تصادفی به صورت زیر را در نظر بگیرید

${\displaystyle c^{T}x}$

را کمینه کنید

اگر داشته باشیم

${\displaystyle P(a_i^{T}x\le b_i)\ge p,i=1,\dots ,m}$

که در آن پارامترهای ${\displaystyle a_i}$

${\displaystyle c^{T}x}$

را کمینه کنید

اگر داشته باشیم

${\displaystyle {\overline{a}}_i^{T}x+{\mathrm{\Phi }}^{-1}(p)\Vert {\mathrm{\Sigma }}_i^{1/2}x{\Vert }_2\le b_i,i=1,\dots ,m}$

که در آن ${\displaystyle {\mathrm{\Phi }}^{-1}}$

ما با نام بردن از برنامه‌های مخروط دوگان به برنامه‌های مخروط دوگان قطعی اطلاق می‌کردیم. چون داده‌های تعریف کننده آن‌ها همگی قطعی هستند. برنامه‌های مخروط دوگان تصادفی یک کلاس از مسائل بهینه‌سازی است که مسئولیت رسیدگی به عدم قطعیت در داده‌هایی که قطعی تعریف شده‌اند را دارد

برنامه ریزی مخروط مرتبه دوم بسط برنامه‌ریزی مربعی و برنامه‌ریزی خطی است که در آن ترکیب افاین متغیرها به صورت قید داخل یک مخروط مرتبه دوم تعریف می‌شوند. این نوع برنامه‌ریزی در حل مسائل هندسی کاربرد دارد و همچنین در برنامه ریزیهای خطی که داده‌ها با خطا همراه هستند و به‌طور دقیق مشخص نیستند کاربرد دارد.

به مجموعه زیر، مخروط نرم مرتبط با نرم ${\displaystyle \Vert .\Vert }$

${\displaystyle C=\left\{\left(x,t\right)|\Vert x\Vert \le t\right\}\subseteq {\mathbb{R}}^{n+1}.}$

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

${\displaystyle \left\{\left(x1,x_2,t\right)|{\left(x_1^2+x_2^2\right)}^{1/2}⩽t\right\}}$

این مخروط به علت شکلی که دارد (به‌طور مثال در ${\displaystyle {\mathbb{R}}^3}$

برنامه ریزی مخروط مرتبه دوم با در نظر گرفتن تابع هدف خطی و قیود نامساوی که به فرم مخروط مرتبه دوم هستند و قیود تساوی افاین به شکل زیر نوشته می‌شود:

${\displaystyle \begin{array}{l}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}{f}^{T}x\\ \mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{o}\Vert Aix+b_i\Vert \le c_i^{T}x+d_{i}i=1,...,m\\ Fx=g\end{array}}$

که ${\displaystyle x\in {\mathbb{R}}^n}$

در حالتی که ${\displaystyle c_i=0}$

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

${\displaystyle \begin{array}{l}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}{c}^{T}x\\ \mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{o}P(a_i^{T}x+b_i)\ge p,i=1,...,m\end{array}}$

که ${\displaystyle a_i}$

${\displaystyle \begin{array}{l}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e}{c}^{T}x\\ \mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{o}{\overline{a}}_i^{T}x+{\mathrm{\Phi }}^{-1}(p)\Vert {\mathrm{\Sigma }}_i^{1/2}x{\Vert }_2\le b_i,i=1,\dots ,m\end{array}}$

که در اینجا ${\displaystyle {\mathrm{\Phi }}^{-1}}$

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

${\displaystyle x^T{A}^{T}Ax+b^{T}x+c\le 0.}$

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

${\displaystyle {\Vert \begin{array}{c}(1+b^{T}x+c)/2\\ Ax\end{array}\Vert }_2\le (1-b^{T}x-c)/2.}$

فرض کنید که مجموعه فرامعینی از معادلات به فرم ${\displaystyle Ax\approx b}$

${\displaystyle \text{minimize}\underset{\Vert \delta A\Vert ⩽\rho ,\Vert \delta b\Vert ⩽\xi }{\text{max}}\Vert \left(A+\delta A\right)x-\left(b+\delta b\right)\Vert }$

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

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

${\displaystyle \underset{\Vert \delta A\Vert ⩽\rho ,\Vert \delta b\Vert ⩽\xi }{\text{max}}\Vert \left(A+\delta A\right)x-\left(b+\delta b\right)\Vert =\underset{\Vert \delta A\Vert ⩽\rho ,\Vert \delta b\Vert ⩽\xi }{\text{max}}\underset{\Vert y\Vert ⩽1}{\text{max}}{y}^T\left(Ax-b\right)\text{ + }{y}^T\delta Ax-y^T\delta b}$

${\displaystyle =\underset{\Vert z\Vert ⩽\rho }{\text{max}}\underset{\Vert y\Vert ⩽1}{\text{max}}{y}^T\left(Ax-b\right)\text{ + }{z}^{T}x+\xi =\Vert Ax-b\Vert +\rho \Vert x\Vert +\xi }$

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

${\displaystyle \text{minimize}\Vert Ax-b\Vert +\rho \Vert x\Vert +\xi }$

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

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

${\displaystyle {\epsilon }_i=\left\{{\overline{a}}_i+P_{i}u|\Vert u\Vert ⩽1\right\}\left(Pi=P_i^T\succ 0\right)}$

حال می‌توان تخمین مربعات خطا مقاوم را با حداقل سازی بدترین باقی‌مانده به فرم زیر بدست آورد:

${\displaystyle \text{minimize}\text{max}ai\in {\epsilon }_i(\sum _{i=1}^n{(a_i^{T}x-b)}^2{)}^{\frac{1}{2}}}$

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

${\displaystyle \text{minimize}{\left(\sum _{i=1}^n{\left(\left|{\overline{a}}_i^{T}x-b_i\right|+\Vert Pix\Vert \right)}^2\right)}^{\frac{1}{2}}}$

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

طراحی وزن آرایه‌های آنتن

در بحث آرایه آنتنی، خروجی المانهای آنتن به صورت خطی با یکدیگر ترکیب شده و خروجی نهایی را تشکیل می‌دهند. خروجی آرایه دارای جهتی است که وابسته به وزنهای نسبی المانها ربط دارد و هدف از داشتن آرایه‌ای از آنتنها این است که در جهت دلخواهی که مد نظر است بتوانیم جهت خروجی را تنظیم کنیم. مسئله را می‌توان به شکل زیر تعریف کرد:

که ${\displaystyle y\left(\theta \right)=\sum _{i=1}^{n}yi\left(\theta \right)}$

این مسئله، با گسسته سازی زاویه ${\displaystyle \theta }$

${\displaystyle \tilde{y}=Aw}$

که ${\displaystyle \tilde{y}\in {\mathbb{C}}^m,A\in {\mathbb{C}}^{m\times n}}$

${\displaystyle \tilde{y}=\left[\begin{array}{c}y\left({\theta }_1\right)\\ ⋮\\ y\left({\theta }_m\right)\end{array}\right],A=\left[\begin{array}{c}a\left({\theta }_1\right)\\ ⋮\\ a\left({\theta }_m\right)\end{array}\right].}$

آنگاه مسئله بهینه‌سازی می‌تواند به فرم SOCP زیر تقریب زده شود:

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

سایر کاربردها

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