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

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

छोटा करना $\ 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)$ दूसरे क्रम के उत्तल शंकु में स्थित $\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$, एसओसीपी रैखिक प्रोग्राम में परिवर्तित हो जाता है। जब $c_{i}=0$ के लिए $i=1,\dots ,m$, एसओसीपी उत्तल चतुर्भुज रूप से बाधित रैखिक प्रोग्राम के समान है।

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

उदाहरण

द्विघात बाधा

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

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

यह एसओसीपी बाधा के समतुल्य है

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

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

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

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

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

नाम	लाइसेंस	संक्षिप्त सूचना
एएमपीएल	व्यावसायिक	सीएससीपी समर्थन के साथ एक बीजगणितीय मॉडलिंग भाषा
आर्टेलिस निट्रो	व्यावसायिक
सीप्लेक्स	व्यावसायिक
फीको एक्सप्रेस	व्यावसायिक
गुरोबी ऑप्टिमाइज़र	व्यावसायिक
मैटलैब	व्यावसायिक	कॉनप्रोग फलन इलेक्ट्रिसिटीसीपी समस्याओं का समाधान करता है आंतरिक-बिंदु एल्गोरिदम का उपयोग करना
मोसेक	व्यावसायिक	समानांतर आंतरिक-बिंदु एल्गोरिथ्म
एनएजी न्यूमेरिकल लाइब्रेरी	व्यावसायिक	एसओसीपी सॉल्वर के साथ सामान्य प्रयोजन संख्यात्मक लाइब्रेरी