दूसरे क्रम की शंकु प्रोग्रामिंग

दूसरे क्रम का शंकु कार्यक्रम (एसओसीपी) प्रपत्र की उत्तल अनुकूलन समस्या है

छोटा करना $\ 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} ^{{n_{i}}\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}$ अनुकूलन चर है. $\lVert x\rVert _{2}$ यूक्लिडियन मानदंड है और $^{T}$ स्थानांतरण को इंगित करता है. एसओसीपी में दूसरे क्रम का शंकु बाधाओं से उत्पन्न होता है, जो एफ़िन फ़ंक्शन की आवश्यकता के बराबर है $(Ax+b,c^{T}x+d)$ दूसरे क्रम के Convex_cone में स्थित होना $\mathbb {R} ^{n_{i}+1}$.

एसओसीपी को आंतरिक बिंदु विधियों द्वारा हल किया जा सकता है और सामान्य तौर पर, अर्धनिश्चित प्रोग्रामिंग (एसडीपी) समस्याओं की तुलना में अधिक कुशलता से हल किया जा सकता है।एसओसीपी के कुछ इंजीनियरिंग अनुप्रयोगों में फिल्टर डिजाइन, एंटीना सरणी वजन डिजाइन, ट्रस डिजाइन और रोबोटिक्स में लोभी बल अनुकूलन शामिल हैं। मात्रात्मक वित्त में अनुप्रयोगों में पोर्टफोलियो अनुकूलन शामिल है; कुछ बाज़ार प्रभाव बाधाएँ, क्योंकि वे रैखिक नहीं हैं, द्विघात प्रोग्रामिंग द्वारा हल नहीं की जा सकती हैं, लेकिन उन्हें एसओसीपी समस्याओं के रूप में तैयार किया जा सकता है।

दूसरे क्रम का शंकु

आयाम का मानक या इकाई दूसरे क्रम का शंकु $n+1$ परिभाषित किया जाता है

${\mathcal {C}}_{n+1}=\left\{{\begin{bmatrix}x\\t\end{bmatrix}}{\Bigg |}x\in \mathbb {R} ^{n},t\in \mathbb {R} ,||x||_{2}\leq t\right\}$.

दूसरे क्रम के शंकु को द्विघात शंकु, आइसक्रीम शंकु या लोरेंत्ज़ शंकु के नाम से भी जाना जाता है। दूसरे क्रम का शंकु $\mathbb {R} ^{3}$ है $\left\{(x,y,z){\Big |}{\sqrt {x^{2}+y^{2}}}\leq z\right\}$.

दूसरे क्रम के शंकु बाधा को संतुष्ट करने वाले बिंदुओं का सेट एक एफ़िन मैपिंग के तहत इकाई दूसरे क्रम के शंकु की व्युत्क्रम छवि है:

$\lVert A_{i}x+b_{i}\rVert _{2}\leq c_{i}^{T}x+d_{i}\Leftrightarrow {\begin{bmatrix}A_{i}\\c_{i}^{T}\end{bmatrix}}x+{\begin{bmatrix}b_{i}\\d_{i}\end{bmatrix}}\in {\mathcal {C}}_{n_{i}+1}$ और इसलिए उत्तल है.

दूसरे क्रम के शंकु को सकारात्मक अर्धनिश्चित मैट्रिक्स के शंकु में एम्बेड किया जा सकता है

$||x||\leq t\Leftrightarrow {\begin{bmatrix}tI&x\\x^{T}&t\end{bmatrix}}\succcurlyeq 0,$ यानी, दूसरे क्रम का शंकु अवरोध एक रैखिक मैट्रिक्स असमानता के बराबर है (यहां)। $M\succcurlyeq 0$ साधन $M$ अर्धनिश्चित मैट्रिक्स है)। इसी प्रकार, हमारे पास भी है,

$\lVert A_{i}x+b_{i}\rVert _{2}\leq c_{i}^{T}x+d_{i}\Leftrightarrow {\begin{bmatrix}(c_{i}^{T}x+d_{i})I&A_{i}x+b_{i}\\(A_{i}x+b_{i})^{T}&c_{i}^{T}x+d_{i}\end{bmatrix}}\succcurlyeq 0$.

अन्य अनुकूलन समस्याओं के साथ संबंध

उत्तल अनुकूलन समस्याओं का एक पदानुक्रम. (एलपी: रैखिक कार्यक्रम, क्यूपी: द्विघात कार्यक्रम, एसओसीपी द्वितीय-क्रम शंकु कार्यक्रम, एसडीपी: अर्धनिश्चित कार्यक्रम, सीपी: शंकु कार्यक्रम।)

कब $A_{i}=0$ के लिए $i=1,\dots ,m$, SOCP एक रैखिक कार्यक्रम में परिवर्तित हो जाता है। कब $c_{i}=0$ के लिए $i=1,\dots ,m$, एसओसीपी एक उत्तल चतुर्भुज रूप से बाधित रैखिक कार्यक्रम के बराबर है।

उत्तल चतुर्भुज रूप से बाधित द्विघात कार्यक्रमों को उद्देश्य फ़ंक्शन को एक बाधा के रूप में सुधारकर एसओसीपी के रूप में भी तैयार किया जा सकता है।अर्धनिश्चित प्रोग्रामिंग एसओसीपी को समाहित करती है क्योंकि एसओसीपी बाधाओं को रैखिक मैट्रिक्स असमानता (एलएमआई) के रूप में लिखा जा सकता है और इसे अर्धनिश्चित कार्यक्रम के उदाहरण के रूप में पुन: तैयार किया जा सकता है।हालाँकि, इसका उलटा मान्य नहीं है: सकारात्मक अर्धनिश्चित शंकु हैं जो किसी भी दूसरे क्रम के शंकु प्रतिनिधित्व को स्वीकार नहीं करते हैं। वास्तव में, जबकि समतल में किसी भी बंद उत्तल अर्ध बीजगणितीय सेट को SOCP के व्यवहार्य क्षेत्र के रूप में लिखा जा सकता है, यह ज्ञात है कि ऐसे उत्तल अर्ध-बीजगणितीय सेट मौजूद हैं जिन्हें एसडीपी द्वारा प्रस्तुत नहीं किया जा सकता है, यानी, ऐसे उत्तल अर्ध-बीजगणितीय सेट मौजूद हैं जिन्हें एसडीपी के व्यवहार्य क्षेत्र के रूप में नहीं लिखा जा सकता है।

उदाहरण

द्विघात बाधा

प्रपत्र के उत्तल चतुर्भुज रूप से बाधित द्विघात प्रोग्राम पर विचार करें

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

यह SOCP बाधा के समतुल्य है

$\lVert A^{1/2}x+{\frac {1}{2}}A^{-1/2}b\rVert \leq \left({\frac {1}{4}}b^{T}A^{-1}b-c\right)^{\frac {1}{2}}$

स्टोकेस्टिक रैखिक प्रोग्रामिंग

असमानता रूप में एक स्टोकेस्टिक रैखिक कार्यक्रम पर विचार करें

छोटा करना $\ c^{T}x\$ :का विषय है

$\mathbb {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$. इस समस्या को SOCP के रूप में व्यक्त किया जा सकता है

छोटा करना $\ 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}(\cdot )\$ व्युत्क्रम सामान्य संचयी वितरण फलन है।

स्टोकेस्टिक द्वितीय-क्रम शंकु प्रोग्रामिंग

हम दूसरे क्रम के शंकु कार्यक्रमों का उल्लेख करते हैं नियतात्मक दूसरे क्रम के शंकु कार्यक्रमों के रूप में क्योंकि उन्हें परिभाषित करने वाला डेटा नियतात्मक है। स्टोकेस्टिक द्वितीय-क्रम शंकु कार्यक्रम अनुकूलन समस्याओं का एक वर्ग है जिन्हें नियतात्मक द्वितीय-क्रम शंकु कार्यक्रमों को परिभाषित करने वाले डेटा में अनिश्चितता को संभालने के लिए परिभाषित किया गया है।

सॉल्वर और स्क्रिप्टिंग (प्रोग्रामिंग) भाषाएँ

Name	License	Brief info
AMPL	commercial	An algebraic modeling language with SOCP support
Artelys Knitro	commercial
CPLEX	commercial
FICO Xpress	commercial
Gurobi Optimizer	commercial
MATLAB	commercial	The coneprog function solves SOCP problems using an interior-point algorithm
MOSEK	commercial	parallel interior-point algorithm
NAG Numerical Library	commercial	General purpose numerical library with SOCP solver