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

برنامه مخروط دوگان (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} ^{{ni}\times n},\ b_{i}\in \mathbb {R} ^{n_{i}},\ c_{i}\in \mathbb {R} ^{n},\ d_{i}\in \mathbb {R} ,\ F\in \mathbb {R} ^{p\times n}$، و $g\in \mathbb {R} ^{p}$. در اینجا $x\in \mathbb {R} ^{n}$ متغیر بهینه‌سازی ما است. اگر$A_{i}=0$ برای $i=1,\dots ,m$، برنامه SOCP ما به یک مسئلهٔ برنامه‌سازی خطی کاهش می‌یابد. اگر $c_{i}=0$ برای $i=1,\dots ,m$، برنامه SOCP ما معادل یک مسئله برنامه‌سازی خطی کوژ-درجه‌دوم محدود شده می‌شود. برنامه‌سازی درجه‌دوم درجه‌دوم محدود شده را نیز می‌توان به صورت حالت خاصی از SOCP نوشت. بهی

مثال: محدودیت درجه‌دوم

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

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

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

$\left\|{\begin{matrix}(1+b^{T}x+c)/2\\Ax\end{matrix}}\right\|_{2}\leq (1-b^{T}x-c)/2.$

مثال: برنامه‌سازی خطی تصادفی

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

$\ c^{T}x\$ را کمینه کنید

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

$P(a_{i}^{T}x\leq b_{i})\geq p,\quad i=1,\dots ,m$

که در آن پارامترهای $a_{i}\$ بردارهای مستقل تصادفی گوسی هستند با میانگین ${\bar {a}}_{i}$ و کوواریانس $\Sigma _{i}\$ و $p\geq 0.5$. این معادل است با SOC به صورت زیر

$\ c^{T}x\$ را کمینه کنید

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

${\bar {a}}_{i}^{T}x+\Phi ^{-1}(p)\lVert \Sigma _{i}^{1/2}x\rVert _{2}\leq b_{i},\quad i=1,\dots ,m$

که در آن $\Phi ^{-1}\$ معکوس تابع توزیع تجمعی طبیعی.

مثال: برنامه‌سازی مخروط دوگان تصادفی

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

حل کننده و زبان‌های برنامه‌نویسی

نام	مجوز	اطلاعات مختصر
ورک	تجاری	جبری زبان
CPLEX	تجاری
Gurobi	تجاری
MOSEK	تجاری

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

مخروط مرتبه دوم

به مجموعه زیر، مخروط نرم مرتبط با نرم $\left\|.\right\|$ گفته می‌شود،

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

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

$\left\{{\left({{x1},{x_{2}},t}\right)\left|{{{\left({x_{1}^{2}+x_{2}^{2}}\right)}^{1/2}}\leqslant t}\right.}\right\}$

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

نمایش فرمولی برنامه ریزی مخروط مرتبه دوم

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

${\begin{array}{l}{\rm {minimize}}\;\;{f^{T}}x\\{\rm {{subject}\;\;{\rm {to}}}}\left\|{{Ai}x+{b_{i}}}\right\|\leq c_{i}^{T}x+{d_{i}}\;\;\;\;\;i=1,...,m\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;Fx=g\end{array}}$

که $x\in {\mathbb {R} ^{n}}$ متغیر بهینه‌سازی است، ${A_{i}}\in {\mathbb {R} ^{{ni}\times n}}$، و $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}^{T}x+{b_{i}}})\geq p,\;\;\;\;\;i=1,...,m\\\end{array}}$

که $a_{i}$ متغیر گوسی مستقل با متوسط ${\bar {a}}_{i}$ و کوواریانس $\Sigma _{i}\$ هستند و $p\geq 0.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}Ax+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 {\text{max}} \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 {\text{max}} \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 {\text{max}} \limits _{\left\|{\delta A}\right\|\leqslant \rho ,\left\|{\delta b}\right\|\leqslant \xi }\mathop {\text{max}} \limits _{\left\|y\right\|\leqslant 1}{\text{ }}{y^{T}}\left({Ax-b}\right){\text{ + }}{y^{T}}\delta Ax-{y^{T}}\delta b$

$=\mathop {\text{max}} \limits _{\left\|z\right\|\leqslant \rho }\mathop {\text{max}} \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\{{{{\bar {a}}_{i}}+{P_{i}}u\left|{\left\|u\right\|\leqslant 1}\right.}\right\}\;\;\left({{Pi}=P_{i}^{T}\succ 0}\right)$

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

${\text{minimize}}\;\;\mathop {\text{max}} \limits {{ai}\in {\varepsilon _{i}}}{(\sum \limits _{i=1}^{n}{{(a_{i}^{T}x-b)}^{2}})^{\frac {1}{2}}}$

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

${\text{minimize}}{\left({\sum \limits _{i=1}^{n}{{\left({\left|{{\bar {a}}_{i}^{T}x-{b_{i}}}\right|+\left\|{{Pi}x}\right\|}\right)}^{2}}}\right)^{\frac {1}{2}}}$

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

${\begin{aligned}&{\underset {}{\operatorname {minimize} }}\;\;\;\;\;\;\;\;s\\&\operatorname {subject\;to} \;\;\;\;\;\;\left\|t\right\|\leqslant s\\&\;\;\;\;\;\;\;\;\;\;\;\;\left|{{\bar {a}}_{i}^{T}x-{b_{i}}}\right|+\left\|{{Pi}x}\right\|\leqslant {t_{i}},i=1,\cdots ,n\end{aligned}}$

کاربردها

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

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

${\begin{aligned}&{\underset {\left|{\theta -{\theta _{t}}}\right|>\Delta }{\operatorname {max} }}\;\;\;\;\;\;\;\;\left|{y\left(\theta \right)}\right|\\&\operatorname {subject\;to} \;\;\;\;\;\;\;\;\;y\left({\theta _{t}}\right)=1\end{aligned}}$

که ${y\left(\theta \right)=\sum \limits _{i=1}^{n}{{yi}\left(\theta \right)}}$ است، $2\Delta$ پهنای بیم است و بازه ${\left|{\theta -{\theta _{t}}}\right|>\Delta }$ که در حداقل سازی مورد نظر است ملزم می‌دارد که امواج رسیده از سایر جهات غیر از جهت هدف ($\theta _{t}$) حداقل شوند. همچنین ${{yi}\left(\theta \right)}$ سیگنال باند پایه متناظر با سیگنال باند میانی $\exp \left({j\left({{xi}\cos \theta +{y_{i}}\sin \theta -\omega t}\right)}\right)$ است. علاوه بر این شرط $y\left({\theta _{t}}\right)=1$ به معنای نرمالیزه بودن است.

این مسئله، با گسسته سازی زاویه $\theta$ (به صورت ${\theta _{1}},\cdots ,{\theta _{m}}$ به ازای $m\gg n$) می‌تواند به فرم یک مسئله SOCP تقریب زده شود. پاسخ آرایه را به صورت زیر در نظر بگیرید:

${\tilde {y}}=Aw$

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

${\tilde {y}}=\left[{\begin{array}{*{20}{c}}{y\left({\theta _{1}}\right)}\\\vdots \\{y\left({\theta _{m}}\right)}\end{array}}\right],A=\left[{\begin{array}{*{20}{c}}{a\left({\theta _{1}}\right)}\\\vdots \\{a\left({\theta _{m}}\right)}\end{array}}\right].$

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

${\begin{aligned}&{\underset {}{\operatorname {minimize} }}\;\;\;\;\;\;\;\;t\\&\operatorname {subject\;to} \left|{y\left({\theta _{k}}\right)}\right|\leqslant t\;for\;\;\left|{{\theta _{i}}-{\theta _{k}}}\right|>\Delta \;\;\;\;y\left({\theta _{k}}\right)=1\end{aligned}}$

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

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

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