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

अर्धनिश्चित क्रमादेशन (SDP) उत्तल अनुकूलन का एक उपक्षेत्र है जो एक रैखिक उद्देश्य फलन (एक उपयोगकर्ता-निर्दिष्ट फलन जिसे उपयोगकर्ता कम या अधिकतम करना चाहता है) के अनुकूलन से संबंधित है।

एक सजातीय स्थान के साथ सकारात्मक अर्ध-निश्चित आव्यूह के शंकु के प्रतिच्छेदन पर, i.e, एक स्पेक्ट्राहेड्रॉन।

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

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

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

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

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

${\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$ सकारात्मक-अर्द्धपरिमित कहा जाता है यदि यह कुछ सदिशों का ग्राम आव्यूह है। यदि ऐसा है, तो हम इसे $M\succeq 0$ इस रूप में निरूपित करते हैं। ध्यान दें कि सकारात्मक अर्ध-निश्चित होने की कई अन्य समकक्ष परिभाषाएं हैं, उदाहरण के लिए, सकारात्मक अर्ध-निश्चित आव्यूह स्व-संलग्न आव्यूह हैं जिनके पास केवल गैर-नकारात्मक आइगेनवैल्यू और आइगेनसदिश हैं।

सभी $n\times n$ वास्तविक सममित आव्यूह का स्थान $\mathbb {S} ^{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}}$

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

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

परिभाषाएँ

समान रूप से रैखीय क्रमादेशन के लिए, प्रारूप का एक सामान्य SDP दिया गया

${\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$.

शक्तिहीन द्वैत

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

$\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 को प्रबल द्वैत गुण को संतुष्ट करने वाला कहा जाता है। रेखीय क्रमादेशन के विपरीत, जहां प्रत्येक दोहरे रेखीय कार्यक्रम का इष्टतम उद्देश्य प्राथमिक उद्देश्य के बराबर होता है, प्रत्येक SDP प्रबल द्वैत को संतुष्ट नहीं करता है; सामान्य तौर पर, दोहरी SDP का मूल्य मूल के मूल्य से अनुशासनपूर्वक नीचे हो सकता है, और P-SDP और D-SPD निम्नलिखित गुणों को पूरा करते हैं:

(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^{*}$ (D-SDP) और $\langle C,X^{*}\rangle _{\mathbb {S} ^{n}}=\langle b,y^{*}\rangle _{\mathbb {R} ^{m}}$होता है।

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

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

उदाहरण

उदाहरण 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}$ को उत्तर प्राप्त करने के लिए व्यवस्थित करते हैं। यह एक SDP द्वारा तैयार किया जा सकता है। उदाहरण के लिए, चर आव्यूह को बढ़ाकर और सुस्त चरों को प्रस्तुत करके हम असमानता की बाधाओं को संभालते हैं

$\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 (गोमैन्स-विलियमसन मैक्स कट सन्निकटन एल्गोरिथम)

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

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

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

1. एक SDP में पूर्णांक द्विघात कार्यक्रम को आराम दें।
2. SDP को हल करें (मनमाने ढंग से छोटी योजक त्रुटि के भीतर $\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}\}$ पूर्णांक स्केलर्स के स्थान पर।

यह एक SDP है क्योंकि उद्देश्य फलन और बाधाएं सदिश आंतरिक उत्पादों के सभी रैखिक कार्य हैं। SDP को हल करने से यूनिट सदिश का एक सम्मुच्चय मिलता है $\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 को कई सन्निकटन एल्गोरिदम विकसित करने के लिए लागू किया गया है। हाल ही में, प्रसाद राघवेंद्र ने अद्वितीय गेम अनुमान के आधार पर बाधा संतुष्टि समस्याओं के लिए एक सामान्य रूपरेखा विकसित की है।

एल्गोरिदम

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

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

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

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

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

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

बंडल विधि

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

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

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

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

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

अनुप्रयोग

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

संदर्भ

• 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 =* सॉफ्टवेयर

}}