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

अर्धनिश्चित प्रोग्रामिंग (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$ में पिछले खंड से ${\frac {c_{i,j}+c_{j,i}}{2}}$ द्वारा प्रवेश $i,j$ दिया गया है। और $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 (गोमैन्स-विलियमसन अधिकतम कर्त सन्निकटन कलन विधि)

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

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

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

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

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

कलन विधि

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

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

आंतरिक बिंदु प्रणाली

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

पहले क्रम के प्रणाली

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

बंडल विधि

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

अन्य हल करने के प्रणाली

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

अनुमानित प्रणाली

SDP को लगभग हल करने वाले कलन विधि भी प्रस्तावित किए गए हैं। ऐसे तरीकों का मुख्य लक्ष्य उन अनुप्रयोगों में कम जटिलता प्राप्त करना है जहां अनुमानित समाधान पर्याप्त हैं और जटिलता न्यूनतम होनी चाहिए। एकाधिक-निविष्ट एकाधिक-निर्गत (MIMO) तारविहीन प्रणाली में आकड़ों का पता लगाने के लिए इस्तेमाल की जाने वाली एक प्रमुख विधि त्रिकोणीय अनुमानित अर्धनिश्चित शिथिलिकरण (टसर) है। जो अर्ध-निश्चित आव्यूह के स्थान पर अर्ध-निश्चित आव्यूह के चोल्स्की अपघटन कारकों पर संचालित होता है। यह विधि अधिकतम-कर्त-जैसी समस्या के लिए अनुमानित समाधानों की गणना करती है जो प्रायः सटीक समाधानकर्ता के समाधानों के समकक्ष होती हैं लेकिन केवल 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 =* सॉफ्टवेयर

}}