सेमिडेफिनिट प्रोग्रामिंग

सेमीडेफिनिट प्रोग्रामिंग (एसडीपी) [[उत्तल अनुकूलन]] का एक उपक्षेत्र है जो एक रैखिक उद्देश्य फ़ंक्शन (एक उपयोगकर्ता-निर्दिष्ट फ़ंक्शन जिसे उपयोगकर्ता कम या अधिकतम करना चाहता है) के अनुकूलन से संबंधित है। सकारात्मक-निश्चित मैट्रिक्स # नकारात्मक-निश्चित, अर्ध-निश्चित और अनिश्चित मैट्रिक्स मैट्रिक्स (गणित) के शंकु (रैखिक बीजगणित) के चौराहे पर एक affine अंतरिक्ष, यानी एक स्पेक्ट्राहेड्रॉन के साथ।

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

प्रेरणा और परिभाषा

प्रारंभिक प्रेरणा

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

${\begin{array}{rl}{\displaystyle \min _{x^{1},\ldots ,x^{n}\in \mathbb {R} ^{n}}}&{\displaystyle \sum _{i,j\in [n]}c_{i,j}(x^{i}\cdot x^{j})}\\{\text{subject to}}&{\displaystyle \sum _{i,j\in [n]}a_{i,j,k}(x^{i}\cdot x^{j})\leq b_{k}}{\text{ for all }}k\\\end{array}}$

जहां $c_{i,j},a_{i,j,k}$, और यह $b_{k}$ वास्तविक संख्याएँ हैं और $x^{i}\cdot x^{j}$ का डॉट उत्पाद है $x^{i}$ और $x^{j}$.

समतुल्य फॉर्मूलेशन

एक $n\times n$ आव्यूह $M$ धनात्मक-निश्चित मैट्रिक्स#सकारात्मक-अर्द्धपरिमित कहा जाता है यदि यह कुछ सदिशों का ग्राम आव्यूह है (अर्थात यदि सदिश मौजूद हैं $x^{1},\ldots ,x^{n}$ ऐसा है कि $m_{i,j}=x^{i}\cdot x^{j}$ सभी के लिए $i,j$). यदि ऐसा है, तो हम इसे इस रूप में निरूपित करते हैं $M\succeq 0$. ध्यान दें कि सकारात्मक अर्ध-निश्चित होने की कई अन्य समकक्ष परिभाषाएं हैं, उदाहरण के लिए, सकारात्मक अर्ध-निश्चित मैट्रिक्स स्व-संलग्न मैट्रिक्स हैं जिनके पास केवल गैर-नकारात्मक ईजेनवेल्यूज और ईजेनवेक्टर हैं।

द्वारा निरूपित करें $\mathbb {S} ^{n}$ सभी का स्थान $n\times n$ वास्तविक सममित मैट्रिक्स। अंतरिक्ष आंतरिक उत्पाद स्थान से सुसज्जित है (जहाँ ${\rm {tr}}$ ट्रेस (रैखिक बीजगणित) को दर्शाता है) $\langle A,B\rangle _{\mathbb {S} ^{n}}={\rm {tr}}(A^{T}B)=\sum _{i=1,j=1}^{n}A_{ij}B_{ij}.$ हम पिछले भाग में दिए गए गणितीय प्रोग्राम को समतुल्य रूप में फिर से लिख सकते हैं

${\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle _{\mathbb {S} ^{n}}\\{\text{subject to}}&\langle A_{k},X\rangle _{\mathbb {S} ^{n}}\leq b_{k},\quad k=1,\ldots ,m\\&X\succeq 0.\end{array}}$

जहां प्रवेश $i,j$ में $C$ द्वारा दिया गया है ${\frac {c_{i,j}+c_{j,i}}{2}}$ पिछले खंड से और $A_{k}$ एक सममित है $n\times n$ मैट्रिक्स होना $i,j$फिर कोशिश करो ${\frac {a_{i,j,k}+a_{j,i,k}}{2}}$ पिछले खंड से। इस प्रकार, मेट्रिसेस $C$ और $A_{k}$ सममित हैं और उपरोक्त आंतरिक उत्पाद अच्छी तरह से परिभाषित हैं।

ध्यान दें कि यदि हम उचित रूप से सुस्त चर जोड़ते हैं, तो इस SDP को किसी एक रूप में परिवर्तित किया जा सकता है

${\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle _{\mathbb {S} ^{n}}\\{\text{subject to}}&\langle A_{k},X\rangle _{\mathbb {S} ^{n}}=b_{k},\quad k=1,\ldots ,m\\&X\succeq 0.\end{array}}$

सुविधा के लिए, एक SDP को थोड़े अलग, लेकिन समतुल्य रूप में निर्दिष्ट किया जा सकता है। उदाहरण के लिए, गैर-नकारात्मक स्केलर (गणित) चर वाले रैखिक भावों को प्रोग्राम विनिर्देश में जोड़ा जा सकता है। यह एक एसडीपी बना रहता है क्योंकि प्रत्येक चर को मैट्रिक्स में शामिल किया जा सकता है $X$ विकर्ण प्रविष्टि के रूप में ($X_{ii}$ कुछ के लिए $i$). यह सुनिश्चित करने के लिए $X_{ii}\geq 0$, प्रतिबंध $X_{ij}=0$ सभी के लिए जोड़ा जा सकता है $j\neq i$. एक अन्य उदाहरण के रूप में, ध्यान दें कि किसी भी सकारात्मक अर्ध निश्चित मैट्रिक्स के लिए $X$, वैक्टर का एक सेट मौजूद है $\{v_{i}\}$ ऐसा कि $i$, $j$ का प्रवेश $X$ है $X_{ij}=(v_{i},v_{j})$ का डॉट उत्पाद $v_{i}$ और $v_{j}$. इसलिए, SDPs को अक्सर सदिशों के अदिश गुणनफलों पर रेखीय व्यंजकों के रूप में तैयार किया जाता है। मानक रूप में एसडीपी के समाधान को देखते हुए, वैक्टर $\{v_{i}\}$ में वसूल किया जा सकता है $O(n^{3})$ समय (उदाहरण के लिए, एक्स के अपूर्ण चोलस्की अपघटन का उपयोग करके)।

द्वैत सिद्धांत

परिभाषाएँ

समान रूप से लीनियर प्रोग्रामिंग के लिए, फॉर्म का एक सामान्य एसडीपी दिया गया

${\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle _{\mathbb {S} ^{n}}\\{\text{subject to}}&\langle A_{i},X\rangle _{\mathbb {S} ^{n}}=b_{i},\quad i=1,\ldots ,m\\&X\succeq 0\end{array}}$

(प्राइमल प्रॉब्लम या P-SDP), हम दोहरी समस्या सेमीडिफिनिट प्रोग्राम (D-SDP) को इस रूप में परिभाषित करते हैं

${\begin{array}{rl}{\displaystyle \max _{y\in \mathbb {R} ^{m}}}&\langle b,y\rangle _{\mathbb {R} ^{m}}\\{\text{subject to}}&{\displaystyle \sum _{i=1}^{m}}y_{i}A_{i}\preceq C\end{array}}$

जहां किसी भी दो मैट्रिक्स के लिए $P$ और $Q$, $P\succeq Q$ साधन $P-Q\succeq 0$.

कमजोर द्वैत

कमजोर द्वैत प्रमेय कहता है कि मौलिक एसडीपी का मूल्य कम से कम दोहरी एसडीपी का मूल्य है। इसलिए, दोहरे एसडीपी के लिए कोई भी व्यवहार्य समाधान प्राथमिक एसडीपी मूल्य को कम करता है, और इसके विपरीत, प्राथमिक एसडीपी के लिए कोई भी संभव समाधान दोहरी एसडीपी मूल्य को ऊपरी सीमा में रखता है। यह है क्योंकि

$\langle C,X\rangle -\langle b,y\rangle =\langle C,X\rangle -\sum _{i=1}^{m}y_{i}b_{i}=\langle C,X\rangle -\sum _{i=1}^{m}y_{i}\langle A_{i},X\rangle =\langle C-\sum _{i=1}^{m}y_{i}A_{i},X\rangle \geq 0,$

जहां अंतिम असमानता है क्योंकि दोनों मेट्रिसेस सकारात्मक अर्ध निश्चित हैं, और इस फ़ंक्शन के परिणाम को कभी-कभी द्वैत अंतराल के रूप में संदर्भित किया जाता है।

प्रबल द्वैत

जब मूल और द्वैत SDPs का मान समान होता है, तो SDP को प्रबल द्वैत गुण को संतुष्ट करने वाला कहा जाता है। रेखीय प्रोग्रामिंग के विपरीत, जहां प्रत्येक दोहरे रेखीय कार्यक्रम का इष्टतम उद्देश्य प्राथमिक उद्देश्य के बराबर होता है, प्रत्येक एसडीपी मजबूत द्वैत को संतुष्ट नहीं करता है; सामान्य तौर पर, दोहरी एसडीपी का मूल्य मूल के मूल्य से सख्ती से नीचे हो सकता है, और पी-एसडीपी और डी-एसपीडी निम्नलिखित गुणों को पूरा करते हैं:

(i) मान लीजिए कि मूल समस्या (P-SDP) नीचे और सख्ती से बंधी हुई है व्यवहार्य (यानी, मौजूद है $X_{0}\in \mathbb {S} ^{n},X_{0}\succ 0$ ऐसा है कि $\langle A_{i},X_{0}\rangle _{\mathbb {S} ^{n}}=b_{i}$, $i=1,\ldots ,m$). तब एक इष्टतम समाधान होता है $y^{*}$ (डी-एसडीपी) और

$\langle C,X^{*}\rangle _{\mathbb {S} ^{n}}=\langle b,y^{*}\rangle _{\mathbb {R} ^{m}}.$

(ii) मान लीजिए कि दोहरी समस्या (डी-एसडीपी) ऊपर और सख्ती से बंधी हुई है व्यवहार्य (यानी, $\sum _{i=1}^{m}(y_{0})_{i}A_{i}\prec C$ कुछ के लिए $y_{0}\in \mathbb {R} ^{m}$). तब एक इष्टतम समाधान होता है $X^{*}$ (पी-एसडीपी) और (i) से समानता रखती है।

एक एसडीपी समस्या (और सामान्य तौर पर, किसी भी उत्तल अनुकूलन समस्या के लिए) के लिए मजबूत द्वैत के लिए एक पर्याप्त स्थिति स्लेटर की स्थिति है। रमन द्वारा प्रस्तावित विस्तारित दोहरी समस्या का उपयोग करके अतिरिक्त नियमितता शर्तों के बिना एसडीपी के लिए मजबूत द्वैत प्राप्त करना भी संभव है।

उदाहरण

उदाहरण 1

तीन यादृच्छिक चरों पर विचार करें $A$, $B$, और $C$. परिभाषा के अनुसार, उनका सहसंबंध $\rho _{AB},\ \rho _{AC},\rho _{BC}$ मान्य हैं अगर और केवल अगर

${\begin{pmatrix}1&\rho _{AB}&\rho _{AC}\\\rho _{AB}&1&\rho _{BC}\\\rho _{AC}&\rho _{BC}&1\end{pmatrix}}\succeq 0,$

इस मामले में इस मैट्रिक्स को सहसंबंध मैट्रिक्स कहा जाता है। मान लीजिए कि हम कुछ पूर्व ज्ञान (उदाहरण के लिए एक प्रयोग के अनुभवजन्य परिणाम) से जानते हैं कि $-0.2\leq \rho _{AB}\leq -0.1$ और $0.4\leq \rho _{BC}\leq 0.5$. सबसे छोटे और सबसे बड़े मूल्यों को निर्धारित करने की समस्या $\rho _{AC}\$ ले सकते हैं द्वारा दिया गया है:

${\begin{array}{rl}{\displaystyle \min /\max }&x_{13}\\{\text{subject to}}&-0.2\leq x_{12}\leq -0.1\\&0.4\leq x_{23}\leq 0.5\\&{\begin{pmatrix}1&x_{12}&x_{13}\\x_{12}&1&x_{23}\\x_{13}&x_{23}&1\end{pmatrix}}\succeq 0\end{array}}$

हमलोग तैयार हैं $\rho _{AB}=x_{12},\ \rho _{AC}=x_{13},\ \rho _{BC}=x_{23}$ उत्तर प्राप्त करने के लिए। यह एक एसडीपी द्वारा तैयार किया जा सकता है। उदाहरण के लिए, चर मैट्रिक्स को बढ़ाकर और सुस्त चरों को पेश करके हम असमानता की बाधाओं को संभालते हैं

$\mathrm {tr} \left(\left({\begin{array}{cccccc}0&1&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&1&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\end{array}}\right)\cdot \left({\begin{array}{cccccc}1&x_{12}&x_{13}&0&0&0\\x_{12}&1&x_{23}&0&0&0\\x_{13}&x_{23}&1&0&0&0\\0&0&0&s_{1}&0&0\\0&0&0&0&s_{2}&0\\0&0&0&0&0&s_{3}\end{array}}\right)\right)=x_{12}+s_{1}=-0.1$ इस SDP को हल करने पर, का न्यूनतम और अधिकतम मान प्राप्त होता है $\rho _{AC}=x_{13}\$ जैसा $-0.978$ और $0.872$ क्रमश।

उदाहरण 2

समस्या पर विचार करें

छोटा करना ${\frac {(c^{T}x)^{2}}{d^{T}x}}$

का विषय है $Ax+b\geq 0$

जहां हम मानते हैं $d^{T}x>0$ जब कभी भी $Ax+b\geq 0$.

एक सहायक चर का परिचय $t$ समस्या का सुधार किया जा सकता है:

छोटा करना $t$

का विषय है $Ax+b\geq 0,\,{\frac {(c^{T}x)^{2}}{d^{T}x}}\leq t$

इस सूत्रीकरण में, उद्देश्य चरों का एक रैखिक कार्य है $x,t$.

पहले प्रतिबंध के रूप में लिखा जा सकता है

${\textbf {diag}}(Ax+b)\geq 0$

जहां मैट्रिक्स ${\textbf {diag}}(Ax+b)$ विकर्ण में मान के साथ वर्ग मैट्रिक्स बराबर है वेक्टर के तत्वों के लिए $Ax+b$.

दूसरे प्रतिबंध के रूप में लिखा जा सकता है

$td^{T}x-(c^{T}x)^{2}\geq 0$

परिभाषित $D$ निम्नलिखित नुसार

$D=\left[{\begin{array}{cc}t&c^{T}x\\c^{T}x&d^{T}x\end{array}}\right]$

इसे देखने के लिए हम शूर कॉम्प्लिमेंट्स के सिद्धांत का उपयोग कर सकते हैं

$D\succeq 0$

(बॉयड और वैंडेनबर्ग, 1996)

इस समस्या से जुड़ा सेमीडिफिनिट प्रोग्राम है

छोटा करना $t$

का विषय है $\left[{\begin{array}{ccc}{\textbf {diag}}(Ax+b)&0&0\\0&t&c^{T}x\\0&c^{T}x&d^{T}x\end{array}}\right]\succeq 0$

उदाहरण 3 (गोमैन्स-विलियमसन मैक्स कट सन्निकटन एल्गोरिथम)

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

अधिकतम करें $\sum _{(i,j)\in E}{\frac {1-v_{i}v_{j}}{2}},$ ऐसा है कि प्रत्येक $v_{i}\in \{1,-1\}$.

जब तक पी = एनपी, हम इस अधिकतमकरण समस्या को कुशलतापूर्वक हल नहीं कर सकते। हालाँकि, गोमेन्स और विलियमसन ने इस तरह की समस्या पर हमला करने के लिए एक सामान्य तीन-चरणीय प्रक्रिया देखी:

1. एक एसडीपी में पूर्णांक द्विघात कार्यक्रम को आराम दें।
2. एसडीपी को हल करें (मनमाने ढंग से छोटी योजक त्रुटि के भीतर $\epsilon$).
3. मूल पूर्णांक द्विघात कार्यक्रम का अनुमानित समाधान प्राप्त करने के लिए SDP समाधान को गोल करें।

अधिकतम कटौती के लिए, सबसे स्वाभाविक विश्राम है

$\max \sum _{(i,j)\in E}{\frac {1-\langle v_{i},v_{j}\rangle }{2}},$ ऐसा है कि $\lVert v_{i}\rVert ^{2}=1$, जहां अधिकतम सदिशों पर है $\{v_{i}\}$ पूर्णांक स्केलर्स के बजाय।

यह एक एसडीपी है क्योंकि उद्देश्य फ़ंक्शन और बाधाएं वेक्टर आंतरिक उत्पादों के सभी रैखिक कार्य हैं। एसडीपी को हल करने से यूनिट वैक्टर का एक सेट मिलता है $\mathbf {R^{n}}$; चूँकि सदिशों को समरेख होने की आवश्यकता नहीं है, इस शिथिल कार्यक्रम का मान केवल मूल द्विघात पूर्णांक कार्यक्रम के मान से अधिक हो सकता है। अंत में, विभाजन प्राप्त करने के लिए एक राउंडिंग प्रक्रिया की आवश्यकता होती है। Goemans और विलियमसन बस मूल के माध्यम से एक समान रूप से यादृच्छिक हाइपरप्लेन चुनते हैं और हाइपरप्लेन के किस तरफ संबंधित वैक्टर झूठ बोलते हैं, इसके अनुसार कोने को विभाजित करते हैं। सरल विश्लेषण से पता चलता है कि यह कार्यविधि 0.87856 - ε के अपेक्षित सन्निकटन अनुपात (प्रदर्शन गारंटी) को प्राप्त करती है। (कटे जाने का अपेक्षित मूल्य किनारे के कटने की प्रायिकता का योग है, जो कोण के समानुपाती है $\cos ^{-1}\langle v_{i},v_{j}\rangle$ किनारों के अंत बिंदुओं पर वैक्टर के बीच $\pi$. इस संभावना की तुलना $(1-\langle v_{i},v_{j}\rangle )/{2}$, उम्मीद में अनुपात हमेशा कम से कम 0.87856 होता है।) अद्वितीय गेम अनुमान मानते हुए, यह दिखाया जा सकता है कि यह सन्निकटन अनुपात अनिवार्य रूप से इष्टतम है।

Goemans और विलियमसन के मूल पेपर के बाद से, SDPs को कई सन्निकटन एल्गोरिदम विकसित करने के लिए लागू किया गया है। हाल ही में, प्रसाद राघवेंद्र ने अद्वितीय गेम अनुमान के आधार पर बाधा संतुष्टि समस्याओं के लिए एक सामान्य रूपरेखा विकसित की है।

एल्गोरिदम

एसडीपी को हल करने के लिए कई प्रकार के एल्गोरिदम हैं। ये एल्गोरिदम एसडीपी के मूल्य को एक योगात्मक त्रुटि तक आउटपुट करते हैं $\epsilon$ उस समय में जो प्रोग्राम विवरण आकार में बहुपद है और $\log(1/\epsilon )$.

फेशियल रिडक्शन एल्गोरिदम भी हैं जिनका उपयोग समस्या की बाधाओं का निरीक्षण करके एसडीपी समस्याओं को प्रीप्रोसेस करने के लिए किया जा सकता है। इनका उपयोग सख्त व्यवहार्यता की कमी का पता लगाने, अनावश्यक पंक्तियों और स्तंभों को हटाने और चर मैट्रिक्स के आकार को कम करने के लिए भी किया जा सकता है।

आंतरिक बिंदु तरीके

अधिकांश कोड आंतरिक बिंदु विधियों (CSDP, MOSEK, SeDuMi, SDPT3, DSDP, SDPA) पर आधारित होते हैं। सामान्य रेखीय एसडीपी समस्याओं के लिए मजबूत और कुशल। इस तथ्य से प्रतिबंधित है कि एल्गोरिदम दूसरे क्रम के तरीके हैं और एक बड़े (और अक्सर घने) मैट्रिक्स को स्टोर और फ़ैक्टराइज़ करने की आवश्यकता होती है। सैद्धांतिक रूप से, अत्याधुनिक उच्च सटीकता एसडीपी एल्गोरिदम इस दृष्टिकोण पर आधारित हैं।

पहले क्रम के तरीके

शांकव अनुकूलन के लिए प्रथम-क्रम के तरीके एक बड़े हेसियन मैट्रिक्स की गणना, भंडारण और गुणनखंडन से बचते हैं और आंतरिक बिंदु विधियों की तुलना में सटीकता में कुछ लागत पर बहुत बड़ी समस्याओं को मापते हैं। स्प्लिटिंग कोन सॉल्वर (SCS) में एक प्रथम-क्रम विधि लागू की गई है। एक अन्य प्रथम-क्रम विधि गुणक (एडीएमएम) की वैकल्पिक दिशा विधि है। इस विधि के लिए प्रत्येक चरण में अर्ध-निश्चित मेट्रिसेस के शंकु पर प्रक्षेपण की आवश्यकता होती है।

बंडल विधि

कोड कॉनिकबंडल एसडीपी समस्या को एक गैर-चिकनी अनुकूलन समस्या के रूप में तैयार करता है और इसे गैर-चिकनी अनुकूलन के स्पेक्ट्रल बंडल विधि द्वारा हल करता है। रैखिक एसडीपी समस्याओं के एक विशेष वर्ग के लिए यह दृष्टिकोण बहुत कुशल है।

अन्य हल करने के तरीके

संवर्धित Lagrangian विधि (PENSDP) पर आधारित एल्गोरिदम व्यवहार में आंतरिक बिंदु विधियों के समान हैं और कुछ बहुत बड़े पैमाने की समस्याओं के लिए विशिष्ट हो सकते हैं। अन्य एल्गोरिदम एक गैर-रैखिक प्रोग्रामिंग समस्या (एसडीपीएलआर) के रूप में एसडीपी के निम्न-श्रेणी की जानकारी और सुधार का उपयोग करते हैं।

अनुमानित तरीके

एसडीपी को लगभग हल करने वाले एल्गोरिद्म भी प्रस्तावित किए गए हैं। ऐसे तरीकों का मुख्य लक्ष्य उन अनुप्रयोगों में कम जटिलता प्राप्त करना है जहां अनुमानित समाधान पर्याप्त हैं और जटिलता न्यूनतम होनी चाहिए। मल्टीपल-इनपुट मल्टीपल-आउटपुट (MIMO) वायरलेस सिस्टम में डेटा का पता लगाने के लिए इस्तेमाल की जाने वाली एक प्रमुख विधि त्रिकोणीय अनुमानित SEmidefinite रिलैक्सेशन (TASER) है। जो अर्ध-निश्चित मैट्रिक्स के बजाय अर्ध-निश्चित मैट्रिक्स के चोल्स्की अपघटन कारकों पर संचालित होता है। यह विधि अधिकतम-कट-जैसी समस्या के लिए अनुमानित समाधानों की गणना करती है जो अक्सर सटीक सॉल्वरों के समाधानों के बराबर होती हैं लेकिन केवल 10-20 एल्गोरिथम पुनरावृत्तियों में।

अनुप्रयोग

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

संदर्भ

• Lieven Vandenberghe, Stephen Boyd, "Semidefinite Programming", SIAM Review 38, March 1996, pp. 49–95. pdf
• Monique Laurent, Franz Rendl, "Semidefinite Programming and Integer Programming", Report PNA-R0210, CWI, Amsterdam, April 2002. optimization-online
• E. de Klerk, "Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications", Kluwer Academic Publishers, March 2002, ISBN 1-4020-0547-4.
• Robert M. Freund, "Introduction to Semidefinite Programming (SDP), SDP-Introduction

बाहरी संबंध

• Links to introductions and events in the field
• Lecture notes from László Lovász on Semidefinite Programming

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

• Evolutionary algorithm
• Hill climbing
• Local search
• Simulated annealing
• Tabu search

| below =

• Software

}} | group5 =Metaheuuristic |abbr5 = heuristic | list5 =*विकासवादी एल्गोरिथ्म

• पहाड़ी की चढ़ाई
• स्थानीय खोज
• तैयार किए हुयी धातु पे पानी चढाने की कला
• तब्बू खोज

| below =* सॉफ्टवेयर

}}