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

अर्धनिश्चित प्रोग्रामिंग (एसडीपी) उत्तल अनुकूलन का एक उपक्षेत्र है जो एक रैखिक उद्देश्य फलन (एक उपयोगकर्ता-निर्दिष्ट फलन जिसे उपयोगकर्ता कम या अधिकतम करना चाहता है) एक सजातीय स्थान के साथ सकारात्मक अर्ध-निश्चित आव्यूह के शंकु के प्रतिच्छेदन पर, i.e, स्पेक्ट्राहेड्रॉन के अनुकूलन से संबंधित है।

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

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

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

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

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

${\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}$ सममित हैं और उपरोक्त आंतरिक उत्पाद पूर्णतः स्पष्ट परिभाषित हैं।

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

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

सुविधा के लिए, एक एसडीपी को थोड़े अलग, लेकिन समतुल्य रूप में निर्दिष्ट किया जा सकता है। उदाहरण के लिए, गैर-नकारात्मक अदिश (गणित) चर वाले रैखिक भावों को क्रमादेश विनिर्देश में जोड़ा जा सकता है। यह एक एसडीपी बना रहता है क्योंकि प्रत्येक चर को $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}$ का बिंदु उत्पाद है। इसलिए, एसडीपीs को प्रायः सदिशों के अदिश गुणनफलों पर रेखीय व्यंजकों के रूप में प्रस्तुत किया जाता है। मानक रूप में एसडीपी के समाधान को देखते हुए, सदिश $\{v_{i}\}$ $O(n^{3})$ समय में पुनराप्‍त किया जा सकता है (उदाहरण के लिए, X के अपूर्ण चोलस्की अपघटन का उपयोग करके)।

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

परिभाषाएँ

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

${\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-एसडीपी), हम द्वैध समस्या अर्धनिश्चित क्रमादेश (D-एसडीपी) को इस रूप में परिभाषित करते हैं

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

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

प्रबल द्वैत

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

(i) मान लीजिए कि मूल समस्या (P-एसडीपी) नीचे और दृढता से बंधी हुई है (अर्थात, $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-एसडीपी) और $\langle C,X^{*}\rangle _{\mathbb {S} ^{n}}=\langle b,y^{*}\rangle _{\mathbb {R} ^{m}}$होता है।

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

इस एसडीपी को हल करने पर, $\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-कड़ा अधिकतमकरण समस्याओं के लिए सन्निकटन कलन विधि विकसित करने के लिए अर्ध-निश्चित फलन महत्वपूर्ण उपकरण हैं। एसडीपी पर आधारित पहला सन्निकटन कलन विधि माइकल गोमैन्स और डेविड पी. विलियमसन (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. एक एसडीपी में पूर्णांक द्विघात फलन को आराम दें।
2. एसडीपी को हल करें (अव्यवस्थिततः छोटी योजक त्रुटि $\epsilon$ के भीतर ).
3. मूल पूर्णांक द्विघात फलन का सन्निकटन समाधान प्राप्त करने के लिए एसडीपी समाधान को गोल करें।

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

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

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

कलन विधि

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

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

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

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

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

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

पूलिका विधि

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

अन्य समाधान विधि

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

सन्निकटन प्रणाली

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

बाहरी संबंध

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