सेमिडेफिनिट प्रोग्रामिंग: Difference between revisions

Revision as of 10:53, 16 February 2023

अर्धनिश्चित क्रमादेशन (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]^[2]

उदाहरण

उदाहरण 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, हम इस अधिकतमकरण समस्या को कुशलतापूर्वक हल नहीं कर सकते। हालाँकि, गोमेन्स और विलियमसन ने इस तरह की समस्या पर आक्रमण करने के लिए एक सामान्य तीन-चरणीय प्रक्रिया देखी:

एक SDP में पूर्णांक द्विघात फलन को आराम दें।
SDP को हल करें (अव्यवस्थिततः छोटी योजक त्रुटि $\epsilon$ के भीतर ).
मूल पूर्णांक द्विघात फलन का अनुमानित समाधान प्राप्त करने के लिए 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 को कई सन्निकटन कलन विधि विकसित करने के लिए लागू किया गया है। हाल ही में, प्रसाद राघवेंद्र ने अद्वितीय खेल अनुमान के आधार पर बाधा संतुष्टि समस्याओं के लिए एक सामान्य रूपरेखा विकसित की है।^[3]

कलन विधि

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

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

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

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

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

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

बंडल विधि

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

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

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

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

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

अनुप्रयोग

सांयोगिक इष्टमीकरण समस्याओं के अनुमानित समाधान खोजने के लिए अर्धनिश्चित क्रमादेशन को लागू किया गया है, जैसे अधिकतम कर्त समस्या का समाधान 0.87856 के अनुमानित अनुपात के साथ लागू किया गया है। SDP का उपयोग ज्यामिति में टेंग्रिटी लेखाचित्र निर्धारित करने के लिए भी किया जाता है, और रैखिक आव्यूह असमानता के रूप में नियंत्रण सिद्धांत में उत्पन्न होता है, और विपरीत दीर्घवृत्तीय गुणांक समस्याओं में उत्तल, गैर-रैखिक, अर्ध-निश्चितता बाधाओं के रूप में होता है।^[11] अनुरूप बूटस्ट्रैप के साथ अनुरूप क्षेत्र सिद्धांत को विवश करने के लिए भौतिकी में भी इसका व्यापक रूप से उपयोग किया जाता है।^[12]

संदर्भ

↑ Ramana, Motakuri V. (1997). "An exact duality theory for semidefinite programming and its complexity implications". Mathematical Programming (in English). 77 (1): 129–162. doi:10.1007/BF02614433. ISSN 0025-5610. S2CID 12886462.
↑ Vandenberghe, Lieven; Boyd, Stephen (1996). "Semidefinite Programming". SIAM Review (in English). 38 (1): 49–95. doi:10.1137/1038003. ISSN 0036-1445.
↑ Raghavendra, Prasad (2008). "Optimal algorithms and inapproximability results for every CSP?". Proceedings of the fortieth annual ACM symposium on Theory of computing. pp. 245–254. doi:10.1145/1374376.1374414. ISBN 9781605580470. S2CID 15075197.
↑ Zhu, Yuzixuan; Pataki, Gábor; Tran-Dinh, Quoc (2019), "Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs", Mathematical Programming Computation (in English), 11 (3): 503–586, arXiv:1710.08954, doi:10.1007/s12532-019-00164-4, ISSN 1867-2949, S2CID 53645581
↑ Jiang, Haotian; Kathuria, Tarun; Lee, Yin Tat; Padmanabhan, Swati; Song, Zhao (November 2020). "A Faster Interior Point Method for Semidefinite Programming". 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). Durham, NC, USA: IEEE: 910–918. arXiv:2009.10217. doi:10.1109/FOCS46700.2020.00089. ISBN 978-1-7281-9621-3. S2CID 221836388.
↑ Huang, Baihe; Jiang, Shunhua; Song, Zhao; Tao, Runzhou; Zhang, Ruizhe (2021-11-18). "Solving SDP Faster: A Robust IPM Framework and Efficient Implementation". arXiv:2101.08208 [math.OC].
↑ Brendan O'Donoghue, Eric Chu, Neal Parikh, Stephen Boyd, "Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding", Journal of Optimization Theory and Applications, 2016, pp 1042--1068, https://web.stanford.edu/~boyd/papers/pdf/scs.pdf.
↑ Wen, Zaiwen, Donald Goldfarb, and Wotao Yin. "Alternating direction augmented Lagrangian methods for semidefinite programming." Mathematical Programming Computation 2.3-4 (2010): 203-230.
↑ Burer, Samuel; Monteiro, Renato D. C. (2003), "A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization", Mathematical Programming (in English), 95 (2): 329–357, CiteSeerX 10.1.1.682.1520, doi:10.1007/s10107-002-0352-8, ISSN 1436-4646, S2CID 7691228
↑ Castañeda, O.; Goldstein, T.; Studer, C. (December 2016). "Data Detection in Large Multi-Antenna Wireless Systems via Approximate Semidefinite Relaxation". IEEE Transactions on Circuits and Systems I: Regular Papers. 63 (12): 2334–2346. arXiv:1609.01797. doi:10.1109/TCSI.2016.2607198. hdl:20.500.11850/448631. ISSN 1558-0806.
↑ Harrach, Bastian (2021), "Solving an inverse elliptic coefficient problem by convex non-linear semidefinite programming", Optimization Letters (in English), 16 (5): 1599–1609, arXiv:2105.11440, doi:10.1007/s11590-021-01802-4, S2CID 235166806
↑ Simmons-Duffin, David (2015-02-06). "A Semidefinite Program Solver for the Conformal Bootstrap". arXiv:1502.02033 [hep-th].

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 =

| below =

Software

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

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

}}

[1] Ramana, Motakuri V. (1997). "An exact duality theory for semidefinite programming and its complexity implications". Mathematical Programming (in English). 77 (1): 129–162. doi:10.1007/BF02614433. ISSN 0025-5610. S2CID 12886462.

[2] Vandenberghe, Lieven; Boyd, Stephen (1996). "Semidefinite Programming". SIAM Review (in English). 38 (1): 49–95. doi:10.1137/1038003. ISSN 0036-1445.

[3] Raghavendra, Prasad (2008). "Optimal algorithms and inapproximability results for every CSP?". Proceedings of the fortieth annual ACM symposium on Theory of computing. pp. 245–254. doi:10.1145/1374376.1374414. ISBN 9781605580470. S2CID 15075197.

[4] Zhu, Yuzixuan; Pataki, Gábor; Tran-Dinh, Quoc (2019), "Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs", Mathematical Programming Computation (in English), 11 (3): 503–586, arXiv:1710.08954, doi:10.1007/s12532-019-00164-4, ISSN 1867-2949, S2CID 53645581

[5] Jiang, Haotian; Kathuria, Tarun; Lee, Yin Tat; Padmanabhan, Swati; Song, Zhao (November 2020). "A Faster Interior Point Method for Semidefinite Programming". 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). Durham, NC, USA: IEEE: 910–918. arXiv:2009.10217. doi:10.1109/FOCS46700.2020.00089. ISBN 978-1-7281-9621-3. S2CID 221836388.

[6] Huang, Baihe; Jiang, Shunhua; Song, Zhao; Tao, Runzhou; Zhang, Ruizhe (2021-11-18). "Solving SDP Faster: A Robust IPM Framework and Efficient Implementation". arXiv:2101.08208 [math.OC].

[7] Brendan O'Donoghue, Eric Chu, Neal Parikh, Stephen Boyd, "Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding", Journal of Optimization Theory and Applications, 2016, pp 1042--1068, https://web.stanford.edu/~boyd/papers/pdf/scs.pdf.

[8] Wen, Zaiwen, Donald Goldfarb, and Wotao Yin. "Alternating direction augmented Lagrangian methods for semidefinite programming." Mathematical Programming Computation 2.3-4 (2010): 203-230.

[9] Burer, Samuel; Monteiro, Renato D. C. (2003), "A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization", Mathematical Programming (in English), 95 (2): 329–357, CiteSeerX 10.1.1.682.1520, doi:10.1007/s10107-002-0352-8, ISSN 1436-4646, S2CID 7691228

[10] Castañeda, O.; Goldstein, T.; Studer, C. (December 2016). "Data Detection in Large Multi-Antenna Wireless Systems via Approximate Semidefinite Relaxation". IEEE Transactions on Circuits and Systems I: Regular Papers. 63 (12): 2334–2346. arXiv:1609.01797. doi:10.1109/TCSI.2016.2607198. hdl:20.500.11850/448631. ISSN 1558-0806.

[11] Harrach, Bastian (2021), "Solving an inverse elliptic coefficient problem by convex non-linear semidefinite programming", Optimization Letters (in English), 16 (5): 1599–1609, arXiv:2105.11440, doi:10.1007/s11590-021-01802-4, S2CID 235166806

[12] Simmons-Duffin, David (2015-02-06). "A Semidefinite Program Solver for the Conformal Bootstrap". arXiv:1502.02033 [hep-th].

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

@@ Line 5: / Line 5: @@
 अर्धनिश्चित क्रमादेशन अनुकूलन का एक अपेक्षाकृत नया क्षेत्र है जो कई कारणों से बढ़ती रुचि का है। संचालन अनुसंधान और संयोजी अनुकूलन में कई व्यावहारिक समस्याओं को अर्ध-निश्चित क्रमादेशन समस्याओं के रूप में प्रतिरूपित या अनुमानित किया जा सकता है। स्वत: नियंत्रण सिद्धांत में, SDP का उपयोग [[रैखिक मैट्रिक्स असमानता|रैखिक आव्यूह असमानता]] के संदर्भ में किया जाता है। SDP असल में [[शंकु अनुकूलन]] की एक विशेष स्तिथि है और इसे आंतरिक बिंदु विधियों द्वारा कुशलता से हल किया जा सकता है।
-सभी [[रैखिक प्रोग्रामिंग|रैखिक क्रमादेशन]] और (उत्तल) [[द्विघात प्रोग्रामिंग|द्विघात क्रमादेशन]] को SDP के रूप में व्यक्त किया जा सकता है, और SDP के पदानुक्रम के माध्यम से बहुपद अनुकूलन समस्याओं के समाधान का अनुमान लगाया जा सकता है। जटिल प्रणालियों के अनुकूलन में अर्ध निश्चित क्रमादेशन का उपयोग किया गया है। हाल के वर्षों में, कुछ परिमाण परिप्रश्न उपद्रवता समस्याओं को अर्ध-निश्चित कार्यक्रमों के संदर्भ में तैयार किया गया है।
+सभी [[रैखिक प्रोग्रामिंग|रैखिक क्रमादेशन]] और (उत्तल) [[द्विघात प्रोग्रामिंग|द्विघात क्रमादेशन]] को SDP के रूप में व्यक्त किया जा सकता है, और SDP के पदानुक्रम के माध्यम से बहुपद अनुकूलन समस्याओं के समाधान का अनुमान लगाया जा सकता है। जटिल प्रणालियों के अनुकूलन में अर्ध निश्चित क्रमादेशन का उपयोग किया गया है। हाल के वर्षों में, कुछ परिमाण परिप्रश्न उपद्रवता समस्याओं को अर्ध-निश्चित फलनों के संदर्भ में तैयार किया गया है।
 == प्रेरणा और परिभाषा ==
@@ Line 89: / Line 89: @@
 === प्रबल द्वैत ===
-जब मूल और द्वैत SDPs का मान समान होता है, तो SDP को प्रबल द्वैत गुण को संतुष्ट करने वाला कहा जाता है। रेखीय क्रमादेशन के विपरीत, जहां प्रत्येक दोहरे रेखीय कार्यक्रम का इष्टतम उद्देश्य प्राथमिक उद्देश्य के बराबर होता है, प्रत्येक SDP [[मजबूत द्वैत|प्रबल द्वैत]] को संतुष्ट नहीं करता है; सामान्य तौर पर, दोहरी SDP का मूल्य मूल के मूल्य से अनुशासनपूर्वक नीचे हो सकता है, और P-SDP और D-SPD निम्नलिखित गुणों को पूरा करते हैं:
+जब मूल और द्वैत SDPs का मान समान होता है, तो SDP को प्रबल द्वैत गुण को संतुष्ट करने वाला कहा जाता है। रेखीय क्रमादेशन के विपरीत, जहां प्रत्येक दोहरे रेखीय फलन का इष्टतम उद्देश्य प्राथमिक उद्देश्य के बराबर होता है, प्रत्येक SDP [[मजबूत द्वैत|प्रबल द्वैत]] को संतुष्ट नहीं करता है; सामान्य तौर पर, दोहरी SDP का मूल्य मूल के मूल्य से अनुशासनपूर्वक नीचे हो सकता है, और P-SDP और D-SPD निम्नलिखित गुणों को पूरा करते हैं:
 (i) मान लीजिए कि मूल समस्या (P-SDP) नीचे और दृढता से बंधी हुई है (यानी, <math>X_0\in\mathbb{S}^n, X_0\succ 0</math> ऐसे उपस्थित है कि <math>\langle
@@ Line 177: / Line 177: @@
-=== उदाहरण 3 (गोमैन्स-विलियमसन मैक्स कट सन्निकटन एल्गोरिथम) ===
+=== उदाहरण 3 (गोमैन्स-विलियमसन अधिकतम कर्त सन्निकटन कलन विधि) ===
-<!-- this section is linked to from [[Randomized_rounding]], please update that link there if you change the section title here --nealeyoung May 31, 2010 -->
+NP-कड़ा अधिकतमकरण समस्याओं के लिए सन्निकटन कलन विधि विकसित करने के लिए अर्ध-निश्चित फलन महत्वपूर्ण उपकरण हैं। SDP पर आधारित पहला सन्निकटन कलन विधि [[माइकल गोमैन्स]] और डेविड पी. विलियमसन (JCM, 1995) के कारण है। उन्होंने [[अधिकतम कट|अधिकतम कर्त]] का अध्ययन किया: एक [[ग्राफ (असतत गणित)|लेखाचित्र (असतत गणित)]] G = (V, E) दिया गया है, लम्बवत V के एक सम्मुच्चय का एक विभाजन निर्गत करें ताकि एक तरफ से दूसरी तरफ जाने वाले किनारों की संख्या को अधिकतम किया जा सके। इस समस्या को द्विघात क्रमादेशन के रूप में व्यक्त किया जा सकता है:
-एनपी-हार्ड अधिकतमकरण समस्याओं के लिए सन्निकटन एल्गोरिदम विकसित करने के लिए अर्ध-निश्चित कार्यक्रम महत्वपूर्ण उपकरण हैं। SDP पर आधारित पहला सन्निकटन एल्गोरिथम [[माइकल गोमैन्स]] और डेविड पी. विलियमसन (जेएसीएम, 1995) के कारण है। उन्होंने [[अधिकतम कट]] का अध्ययन किया: एक [[ग्राफ (असतत गणित)]] G = (V, E) दिया गया है, वर्टिकल V के एक सम्मुच्चय का एक विभाजन आउटपुट करें ताकि एक तरफ से दूसरी तरफ जाने वाले किनारों की संख्या को अधिकतम किया जा सके। इस समस्या को द्विघात क्रमादेशन के रूप में व्यक्त किया जा सकता है:
+: <math>\sum_{(i,j) \in E} \frac{1-v_{i} v_{j}}{2}</math> इस प्रकार अधिकतम करें कि प्रत्येक <math>v_i\in\{1,-1\}</math>
-: अधिकतम करें <math>\sum_{(i,j) \in E} \frac{1-v_{i} v_{j}}{2},</math> ऐसा है कि प्रत्येक <math>v_i\in\{1,-1\}</math>.
-जब तक पी = एनपी, हम इस अधिकतमकरण समस्या को कुशलतापूर्वक हल नहीं कर सकते। हालाँकि, गोमेन्स और विलियमसन ने इस तरह की समस्या पर हमला करने के लिए एक सामान्य तीन-चरणीय प्रक्रिया देखी:
+जब तक P = NP, हम इस अधिकतमकरण समस्या को कुशलतापूर्वक हल नहीं कर सकते। हालाँकि, गोमेन्स और विलियमसन ने इस तरह की समस्या पर आक्रमण करने के लिए एक सामान्य तीन-चरणीय प्रक्रिया देखी:
-# एक SDP में पूर्णांक द्विघात कार्यक्रम को आराम दें।
+# एक SDP में पूर्णांक द्विघात फलन को आराम दें।
-# SDP को हल करें (मनमाने ढंग से छोटी योजक त्रुटि के भीतर <math>\epsilon</math>).
+# SDP को हल करें (अव्यवस्थिततः छोटी योजक त्रुटि <math>\epsilon</math> के भीतर ).
-# मूल पूर्णांक द्विघात कार्यक्रम का अनुमानित समाधान प्राप्त करने के लिए SDP समाधान को गोल करें।
+# मूल पूर्णांक द्विघात फलन का अनुमानित समाधान प्राप्त करने के लिए SDP समाधान को गोल करें।
-अधिकतम कटौती के लिए, सबसे स्वाभाविक विश्राम है
+अधिकतम कटौती के लिए, सबसे स्वाभाविक शिथिलता निम्न है
-:<math>\max \sum_{(i,j) \in E} \frac{1-\langle v_{i}, v_{j}\rangle}{2},</math> ऐसा है कि <math>\lVert v_i\rVert^2 = 1</math>, जहां अधिकतम सदिशों पर है <math>\{v_i\}</math> पूर्णांक स्केलर्स के स्थान पर।
+:<math>\max \sum_{(i,j) \in E} \frac{1-\langle v_{i}, v_{j}\rangle}{2},</math> इस प्रकार है कि <math>\lVert v_i\rVert^2 = 1</math>, जहां अधिकतम सदिशों पर <math>\{v_i\}</math> पूर्णांक अदिश के स्थान पर है।
-यह एक SDP है क्योंकि उद्देश्य फलन और बाधाएं सदिश आंतरिक उत्पादों के सभी रैखिक कार्य हैं। SDP को हल करने से यूनिट सदिश का एक सम्मुच्चय मिलता है <math>\mathbf{R^n}</math>; चूँकि सदिशों को समरेख होने की आवश्यकता नहीं है, इस शिथिल कार्यक्रम का मान केवल मूल द्विघात पूर्णांक कार्यक्रम के मान से अधिक हो सकता है। अंत में, विभाजन प्राप्त करने के लिए एक राउंडिंग प्रक्रिया की आवश्यकता होती है। Goemans और विलियमसन बस मूल के माध्यम से एक समान रूप से यादृच्छिक हाइपरप्लेन चुनते हैं और हाइपरप्लेन के किस तरफ संबंधित सदिश झूठ बोलते हैं, इसके अनुसार कोने को विभाजित करते हैं। सरल विश्लेषण से पता चलता है कि यह कार्यविधि 0.87856 - ε के अपेक्षित सन्निकटन अनुपात (प्रदर्शन गारंटी) को प्राप्त करती है। (कटे जाने का अपेक्षित मूल्य किनारे के कटने की प्रायिकता का योग है, जो कोण के समानुपाती है <math>\cos^{-1}\langle v_{i}, v_{j}\rangle</math> किनारों के अंत बिंदुओं पर सदिश के बीच <math>\pi</math>. इस संभावना की तुलना <math>(1-\langle v_{i}, v_{j}\rangle)/{2}</math>, उम्मीद में अनुपात हमेशा कम से कम 0.87856 होता है।) अद्वितीय गेम अनुमान मानते हुए, यह दिखाया जा सकता है कि यह सन्निकटन अनुपात अनिवार्य रूप से इष्टतम है।
+यह एक SDP है क्योंकि उद्देश्य फलन और बाधाएं सदिश आंतरिक उत्पादों के सभी रैखिक कार्य हैं। SDP को हल करने से एकक सदिश का एक सम्मुच्चय <math>\mathbf{R^n}</math> मिलता है; चूँकि सदिशों को समरेख होने की आवश्यकता नहीं है, इस शिथिल फलन का मान केवल मूल द्विघात पूर्णांक फलन के मान से अधिक हो सकता है। अंत में, विभाजन प्राप्त करने के लिए एक वक्रण प्रक्रिया की आवश्यकता होती है। गोमेन्स और विलियमसन बस मूल के माध्यम से एक समान रूप से यादृच्छिक अधिसमतल चुनते हैं और अधिसमतल के किस तरफ संबंधित सदिश निहित होते हैं, इसके अनुसार कोने को विभाजित करते हैं। सरल विश्लेषण से पता चलता है कि यह कार्यविधि 0.87856 - ε के अपेक्षित सन्निकटन अनुपात (प्रदर्शन प्रत्याभुति) को प्राप्त करती है। (कटे जाने का अपेक्षित मूल्य किनारे के कटने की प्रायिकता का योग है, जो किनारों के अंत बिंदुओं पर सदिश <math>\pi</math> के बीच कोण <math>\cos^{-1}\langle v_{i}, v_{j}\rangle</math> के समानुपाती है। इस संभावना की तुलना <math>(1-\langle v_{i}, v_{j}\rangle)/{2}</math>, अपेक्षा में अनुपात हमेशा कम से कम 0.87856 होता है।) अद्वितीय खेल अनुमान मानते हुए, यह दिखाया जा सकता है कि यह सन्निकटन अनुपात अनिवार्य रूप से इष्टतम है।
-Goemans और विलियमसन के मूल पेपर के बाद से, SDPs को कई सन्निकटन एल्गोरिदम विकसित करने के लिए लागू किया गया है। हाल ही में, प्रसाद राघवेंद्र ने अद्वितीय गेम अनुमान के आधार पर बाधा संतुष्टि समस्याओं के लिए एक सामान्य रूपरेखा विकसित की है।<ref>{{Cite book|chapter-url=http://doi.acm.org/10.1145/1374376.1374414|doi=10.1145/1374376.1374414|chapter=Optimal algorithms and inapproximability results for every CSP?|title=Proceedings of the fortieth annual ACM symposium on Theory of computing|year=2008|last1=Raghavendra|first1=Prasad|pages=245–254|isbn=9781605580470|s2cid=15075197}}</ref>
+गोमेन्स और विलियमसन के मूल पट्र के बाद से, SDPs को कई सन्निकटन कलन विधि विकसित करने के लिए लागू किया गया है। हाल ही में, प्रसाद राघवेंद्र ने अद्वितीय खेल अनुमान के आधार पर बाधा संतुष्टि समस्याओं के लिए एक सामान्य रूपरेखा विकसित की है।<ref>{{Cite book|chapter-url=http://doi.acm.org/10.1145/1374376.1374414|doi=10.1145/1374376.1374414|chapter=Optimal algorithms and inapproximability results for every CSP?|title=Proceedings of the fortieth annual ACM symposium on Theory of computing|year=2008|last1=Raghavendra|first1=Prasad|pages=245–254|isbn=9781605580470|s2cid=15075197}}</ref>
-== एल्गोरिदम ==
+== कलन विधि ==
-SDP को हल करने के लिए कई प्रकार के एल्गोरिदम हैं। ये एल्गोरिदम SDP के मूल्य को एक योगात्मक त्रुटि तक आउटपुट करते हैं <math>\epsilon</math> उस समय में जो प्रोग्राम विवरण आकार में बहुपद है और <math>\log (1/\epsilon)</math>.
+SDP को हल करने के लिए कई प्रकार के कलन विधि हैं। ये कलन विधि SDP के मूल्य को एक योगात्मक त्रुटि <math>\epsilon</math> तक निर्गत करते हैं उस समय में जो क्रमादेश विवरण आकार और <math>\log (1/\epsilon)</math> में बहुपद है
-फेशियल रिडक्शन एल्गोरिदम भी हैं जिनका उपयोग समस्या की बाधाओं का निरीक्षण करके SDP समस्याओं को प्रीप्रोसेस करने के लिए किया जा सकता है। इनका उपयोग सख्त व्यवहार्यता की कमी का पता लगाने, अनावश्यक पंक्तियों और स्तंभों को हटाने और चर आव्यूह के आकार को कम करने के लिए भी किया जा सकता है।<ref>{{citation|last1=Zhu|first1=Yuzixuan|last2=Pataki|first2=Gábor|last3=Tran-Dinh|first3=Quoc|date=2019|title=Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs|url=http://link.springer.com/10.1007/s12532-019-00164-4|journal=Mathematical Programming Computation|language=en|volume=11|issue=3|pages=503–586|doi=10.1007/s12532-019-00164-4|issn=1867-2949|arxiv=1710.08954|s2cid=53645581}}</ref>
+आनन लघूकरण कलन विधि भी हैं जिनका उपयोग समस्या की बाधाओं का निरीक्षण करके SDP समस्याओं को पूर्वप्रक्रम करने के लिए किया जा सकता है। इनका उपयोग यथार्थ व्यवहार्यता की कमी का पता लगाने, अनावश्यक पंक्तियों और स्तंभों को हटाने और चर आव्यूह के आकार को कम करने के लिए भी किया जा सकता है।<ref>{{citation|last1=Zhu|first1=Yuzixuan|last2=Pataki|first2=Gábor|last3=Tran-Dinh|first3=Quoc|date=2019|title=Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs|url=http://link.springer.com/10.1007/s12532-019-00164-4|journal=Mathematical Programming Computation|language=en|volume=11|issue=3|pages=503–586|doi=10.1007/s12532-019-00164-4|issn=1867-2949|arxiv=1710.08954|s2cid=53645581}}</ref>
-=== आंतरिक बिंदु तरीके ===
+=== आंतरिक बिंदु प्रणाली ===
-अधिकांश कोड आंतरिक बिंदु विधियों (CSDP, [[MOSEK]], SeDuMi, [https://www.math.cmu.edu/~reha/sdpt3.html SDPT3], DSDP, SDPA) पर आधारित होते हैं। सामान्य रेखीय SDP समस्याओं के लिए मजबूत और कुशल। इस तथ्य से प्रतिबंधित है कि एल्गोरिदम दूसरे क्रम के तरीके हैं और एक बड़े (और प्रायः घने) आव्यूह को स्टोर और फ़ैक्टराइज़ करने की आवश्यकता होती है। सैद्धांतिक रूप से, अत्याधुनिक उच्च सटीकता SDP एल्गोरिदम<ref>{{Cite journal |last1=Jiang |first1=Haotian |last2=Kathuria |first2=Tarun |last3=Lee |first3=Yin Tat |last4=Padmanabhan |first4=Swati |last5=Song |first5=Zhao |date=November 2020 |title=A Faster Interior Point Method for Semidefinite Programming |url=https://ieeexplore.ieee.org/document/9317892 |journal=2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) |location=Durham, NC, USA |publisher=IEEE |pages=910–918 |doi=10.1109/FOCS46700.2020.00089 |arxiv=2009.10217 |isbn=978-1-7281-9621-3|s2cid=221836388 }}</ref><ref>{{Cite arXiv |last1=Huang |first1=Baihe |last2=Jiang |first2=Shunhua |last3=Song |first3=Zhao |last4=Tao |first4=Runzhou |last5=Zhang |first5=Ruizhe |date=2021-11-18 |title=Solving SDP Faster: A Robust IPM Framework and Efficient Implementation |class=math.OC |eprint=2101.08208}}</ref> इस दृष्टिकोण पर आधारित हैं।
+अधिकांश कूट आंतरिक बिंदु विधियों (CSDP, [[MOSEK|मोसेक]], सेडूमी, [https://www.math.cmu.edu/~reha/sdpt3.html SDPT3], DSDP, SDPA) पर आधारित होते हैं। सामान्य रेखीय SDP समस्याओं के लिए दृढ़ और कुशल होते हैं। इस तथ्य से प्रतिबंधित है कि कलन विधि दूसरे क्रम की प्रणाली हैं और एक बड़े (और प्रायः घने) आव्यूह को संग्रह और गुणनखंड करने की आवश्यकता होती है। सैद्धांतिक रूप से, अत्याधुनिक उच्च सटीकता SDP कलन विधि<ref>{{Cite journal |last1=Jiang |first1=Haotian |last2=Kathuria |first2=Tarun |last3=Lee |first3=Yin Tat |last4=Padmanabhan |first4=Swati |last5=Song |first5=Zhao |date=November 2020 |title=A Faster Interior Point Method for Semidefinite Programming |url=https://ieeexplore.ieee.org/document/9317892 |journal=2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) |location=Durham, NC, USA |publisher=IEEE |pages=910–918 |doi=10.1109/FOCS46700.2020.00089 |arxiv=2009.10217 |isbn=978-1-7281-9621-3|s2cid=221836388 }}</ref><ref>{{Cite arXiv |last1=Huang |first1=Baihe |last2=Jiang |first2=Shunhua |last3=Song |first3=Zhao |last4=Tao |first4=Runzhou |last5=Zhang |first5=Ruizhe |date=2021-11-18 |title=Solving SDP Faster: A Robust IPM Framework and Efficient Implementation |class=math.OC |eprint=2101.08208}}</ref> इस दृष्टिकोण पर आधारित हैं।
-=== पहले क्रम के तरीके ===
+=== पहले क्रम के प्रणाली ===
-शांकव अनुकूलन के लिए प्रथम-क्रम के तरीके एक बड़े हेसियन आव्यूह की गणना, भंडारण और गुणनखंडन से बचते हैं और आंतरिक बिंदु विधियों की तुलना में सटीकता में कुछ लागत पर बहुत बड़ी समस्याओं को मापते हैं। स्प्लिटिंग कोन सॉल्वर (SCS) में एक प्रथम-क्रम विधि लागू की गई है।<ref>Brendan O'Donoghue, Eric Chu,
+शांकव अनुकूलन के लिए प्रथम-क्रम के प्रणाली एक बड़े हेसियन आव्यूह की गणना, भंडारण और गुणनखंडन से बचते हैं और आंतरिक बिंदु विधियों की तुलना में सटीकता में कुछ लागत पर बहुत बड़ी समस्याओं को मापते हैं। विभाजन शंकु समाधानकर्ता (SCS) में एक प्रथम-क्रम विधि लागू की गई है।<ref>Brendan O'Donoghue, Eric Chu,
 Neal Parikh, Stephen Boyd, "Conic Optimization via Operator Splitting and
 Homogeneous Self-Dual Embedding",
@@ Line 212: / Line 211: @@
 pp 1042--1068,
 https://web.stanford.edu/~boyd/papers/pdf/scs.pdf.
-</ref> एक अन्य प्रथम-क्रम विधि गुणक (एडीएमएम) की वैकल्पिक दिशा विधि है।<ref>Wen, Zaiwen, Donald Goldfarb, and Wotao Yin. "Alternating direction augmented Lagrangian methods for semidefinite programming." Mathematical Programming Computation 2.3-4 (2010): 203-230.</ref> इस विधि के लिए प्रत्येक चरण में अर्ध-निश्चित आव्यूह के शंकु पर प्रक्षेपण की आवश्यकता होती है।
+</ref> एक अन्य प्रथम-क्रम विधि गुणक (ADMM) की वैकल्पिक दिशा विधि है।<ref>Wen, Zaiwen, Donald Goldfarb, and Wotao Yin. "Alternating direction augmented Lagrangian methods for semidefinite programming." Mathematical Programming Computation 2.3-4 (2010): 203-230.</ref> इस विधि के लिए प्रत्येक चरण में अर्ध-निश्चित आव्यूह के शंकु पर प्रक्षेपण की आवश्यकता होती है।
 === बंडल विधि ===
-कोड कॉनिकबंडल SDP समस्या को एक [[गैर-चिकनी अनुकूलन]] समस्या के रूप में तैयार करता है और इसे गैर-चिकनी अनुकूलन के स्पेक्ट्रल बंडल विधि द्वारा हल करता है। रैखिक SDP समस्याओं के एक विशेष वर्ग के लिए यह दृष्टिकोण बहुत कुशल है।
+कूट शंक्वाकार बंडल SDP समस्या को एक [[गैर-चिकनी अनुकूलन|गैर-सुचारू अनुकूलन]] समस्या के रूप में तैयार करता है और इसे गैर-सुचारू अनुकूलन के वर्णक्रमीय पूल विधि द्वारा हल करता है। रैखिक SDP समस्याओं के एक विशेष वर्ग के लिए यह दृष्टिकोण बहुत कुशल है।
-=== अन्य हल करने के तरीके ===
+=== अन्य हल करने के प्रणाली ===
-[[संवर्धित Lagrangian विधि]] (PENSDP) पर आधारित एल्गोरिदम व्यवहार में आंतरिक बिंदु विधियों के समान हैं और कुछ बहुत बड़े पैमाने की समस्याओं के लिए विशिष्ट हो सकते हैं। अन्य एल्गोरिदम एक गैर-रैखिक क्रमादेशन समस्या (SDPएलआर) के रूप में SDP के निम्न-श्रेणी की जानकारी और सुधार का उपयोग करते हैं।<ref>{{citation|last2=Monteiro|first2=Renato D. C.|last1=Burer|first1=Samuel|date=2003|title=A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization|journal=Mathematical Programming|language=en|volume=95|issue=2|pages=329–357|doi=10.1007/s10107-002-0352-8|issn=1436-4646|citeseerx=10.1.1.682.1520|s2cid=7691228}}</ref>
+[[संवर्धित Lagrangian विधि|संवर्धित लाग्रंगियन विधि]] (PENSDP) पर आधारित कलन विधि व्यवहार में आंतरिक बिंदु विधियों के समान हैं और कुछ बहुत बड़े अनुपात की समस्याओं के लिए विशिष्ट हो सकते हैं। अन्य कलन विधि एक गैर-रैखिक क्रमादेशन समस्या (SDPLR) के रूप में SDP के निम्न-श्रेणी की जानकारी और सुधार का उपयोग करते हैं।<ref>{{citation|last2=Monteiro|first2=Renato D. C.|last1=Burer|first1=Samuel|date=2003|title=A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization|journal=Mathematical Programming|language=en|volume=95|issue=2|pages=329–357|doi=10.1007/s10107-002-0352-8|issn=1436-4646|citeseerx=10.1.1.682.1520|s2cid=7691228}}</ref>
-=== अनुमानित तरीके ===
+=== अनुमानित प्रणाली ===
-SDP को लगभग हल करने वाले एल्गोरिद्म भी प्रस्तावित किए गए हैं। ऐसे तरीकों का मुख्य लक्ष्य उन अनुप्रयोगों में कम जटिलता प्राप्त करना है जहां अनुमानित समाधान पर्याप्त हैं और जटिलता न्यूनतम होनी चाहिए। मल्टीपल-इनपुट मल्टीपल-आउटपुट (MIMO) वायरलेस सिस्टम में डेटा का पता लगाने के लिए इस्तेमाल की जाने वाली एक प्रमुख विधि त्रिकोणीय अनुमानित SEmidefinite रिलैक्सेशन (TASER) है।<ref>{{Cite journal|last1=Castañeda|first1=O.|last2=Goldstein|first2=T.|last3=Studer|first3=C.|date=December 2016|title=Data Detection in Large Multi-Antenna Wireless Systems via Approximate Semidefinite Relaxation|journal=IEEE Transactions on Circuits and Systems I: Regular Papers|volume=63|issue=12|pages=2334–2346|doi=10.1109/TCSI.2016.2607198|arxiv=1609.01797|hdl=20.500.11850/448631|issn=1558-0806|doi-access=free}}</ref> जो अर्ध-निश्चित आव्यूह के स्थान पर अर्ध-निश्चित आव्यूह के चोल्स्की अपघटन कारकों पर संचालित होता है। यह विधि अधिकतम-कट-जैसी समस्या के लिए अनुमानित समाधानों की गणना करती है जो प्रायः सटीक सॉल्वरों के समाधानों के बराबर होती हैं लेकिन केवल 10-20 एल्गोरिथम पुनरावृत्तियों में।
+SDP को लगभग हल करने वाले कलन विधि भी प्रस्तावित किए गए हैं। ऐसे तरीकों का मुख्य लक्ष्य उन अनुप्रयोगों में कम जटिलता प्राप्त करना है जहां अनुमानित समाधान पर्याप्त हैं और जटिलता न्यूनतम होनी चाहिए। एकाधिक-निविष्ट एकाधिक-निर्गत (MIMO) तारविहीन प्रणाली में आकड़ों का पता लगाने के लिए इस्तेमाल की जाने वाली एक प्रमुख विधि त्रिकोणीय अनुमानित अर्धनिश्चित शिथिलिकरण (TASER) है।<ref>{{Cite journal|last1=Castañeda|first1=O.|last2=Goldstein|first2=T.|last3=Studer|first3=C.|date=December 2016|title=Data Detection in Large Multi-Antenna Wireless Systems via Approximate Semidefinite Relaxation|journal=IEEE Transactions on Circuits and Systems I: Regular Papers|volume=63|issue=12|pages=2334–2346|doi=10.1109/TCSI.2016.2607198|arxiv=1609.01797|hdl=20.500.11850/448631|issn=1558-0806|doi-access=free}}</ref> जो अर्ध-निश्चित आव्यूह के स्थान पर अर्ध-निश्चित आव्यूह के चोल्स्की अपघटन कारकों पर संचालित होता है। यह विधि अधिकतम-कर्त-जैसी समस्या के लिए अनुमानित समाधानों की गणना करती है जो प्रायः सटीक समाधानकर्ता के समाधानों के बराबर होती हैं लेकिन केवल 10-20 कलन विधि पुनरावृत्तियों में।
 == अनुप्रयोग ==
-कॉम्बीनेटरियल ऑप्टिमाइज़ेशन समस्याओं के अनुमानित समाधान खोजने के लिए अर्धनिश्चित क्रमादेशन को लागू किया गया है, जैसे अधिकतम कट समस्या का समाधान 0.87856 के अनुमानित अनुपात के साथ। SDP का उपयोग ज्योमेट्री में टेंग्रिटी ग्राफ निर्धारित करने के लिए भी किया जाता है, और रैखिक आव्यूह असमानता के रूप में नियंत्रण सिद्धांत में उत्पन्न होता है, और उलटा अण्डाकार गुणांक समस्याओं में उत्तल, गैर-रैखिक, अर्ध-निश्चितता बाधाओं के रूप में होता है।<ref>{{citation|last1=Harrach|first1=Bastian|date=2021|title=Solving an inverse elliptic coefficient problem by convex non-linear semidefinite programming|journal=Optimization Letters|volume=16 |issue=5 |pages=1599–1609 |language=en|doi=10.1007/s11590-021-01802-4|arxiv=2105.11440|s2cid=235166806}}</ref> [[अनुरूप बूटस्ट्रैप]] के साथ [[अनुरूप क्षेत्र सिद्धांत]] को विवश करने के लिए भौतिकी में भी इसका व्यापक रूप से उपयोग किया जाता है।<ref>{{cite arXiv |last=Simmons-Duffin |first=David |date=2015-02-06 |title=A Semidefinite Program Solver for the Conformal Bootstrap |class=hep-th |eprint=1502.02033 }}</ref>
+सांयोगिक इष्टमीकरण समस्याओं के अनुमानित समाधान खोजने के लिए अर्धनिश्चित क्रमादेशन को लागू किया गया है, जैसे अधिकतम कर्त समस्या का समाधान 0.87856 के अनुमानित अनुपात के साथ लागू किया गया है। SDP का उपयोग ज्यामिति में टेंग्रिटी लेखाचित्र निर्धारित करने के लिए भी किया जाता है, और रैखिक आव्यूह असमानता के रूप में नियंत्रण सिद्धांत में उत्पन्न होता है, और विपरीत दीर्घवृत्तीय गुणांक समस्याओं में उत्तल, गैर-रैखिक, अर्ध-निश्चितता बाधाओं के रूप में होता है।<ref>{{citation|last1=Harrach|first1=Bastian|date=2021|title=Solving an inverse elliptic coefficient problem by convex non-linear semidefinite programming|journal=Optimization Letters|volume=16 |issue=5 |pages=1599–1609 |language=en|doi=10.1007/s11590-021-01802-4|arxiv=2105.11440|s2cid=235166806}}</ref> [[अनुरूप बूटस्ट्रैप]] के साथ [[अनुरूप क्षेत्र सिद्धांत]] को विवश करने के लिए भौतिकी में भी इसका व्यापक रूप से उपयोग किया जाता है।<ref>{{cite arXiv |last=Simmons-Duffin |first=David |date=2015-02-06 |title=A Semidefinite Program Solver for the Conformal Bootstrap |class=hep-th |eprint=1502.02033 }}</ref>

v t e Mathematical optimization software
Data formats	Mathematica MPS nl sol
Modeling tools	AIMMS AMPL APMonitor ECLiPSe-CLP GEKKO GAMS GNU MathProg JuMP LINDO OPL Mathematica OptimJ PuLP Pyomo TOMLAB Xpress Mosel ZIMPL
LP, MILP^∗ solvers	APOPT^∗ ANTIGONE^∗ Artelys Knitro^∗ BCP^∗ CLP CBC^∗ CPLEX^∗ FortMP^∗ GCG^∗ GLOP^∗ GLPK/GLPSOL^∗ HiGHS^∗ LINDO^∗ Lp_solve LOQO Mathematica MINOS MINTO^∗ MOSEK^∗ NAG SCIP^∗ SoPlex Octeract Engine^∗ SYMPHONY^∗ Xpress Optimizer^∗
QP, MIQP^∗ solvers	APOPT^∗ ANTIGONE^∗ Artelys Knitro^∗ CBC^∗ CLP CPLEX^∗ FortMP^∗ HiGHS IPOPT LINDO^∗ Mathematica MINOS MOSEK^∗ NAG Octeract Engine^∗ SCIP^∗ Xpress Optimizer^∗
QCP, MIQCP^∗ solvers	APOPT^∗ ANTIGONE^∗ Artelys Knitro^∗ CPLEX^∗ IPOPT LINDO^∗ Mathematica MINOS MOSEK^∗ NAG SCIP^∗ Octeract Engine^∗ Xpress Optimizer^∗ Xpress NonLinear^∗
SOCP, MISOCP^∗ solvers	Artelys Knitro^∗ CPLEX^∗ LINDO^∗ LOQO Mathematica MOSEK^∗ NAG SCIP^∗ Xpress Optimizer^∗
SDP, MISDP^∗ solvers	Mathematica MOSEK NAG
NLP, MINLP^∗ solvers	AOA^∗ APOPT^∗ ANTIGONE^∗ Artelys Knitro^∗ BARON^∗ Couenne^∗ Galahad library IPOPT LINDO^∗ LOQO MIDACO^∗ MINOS NAG NLPQLP NPSOL SCIP^∗ SNOPT^∗ Octeract Engine^∗ WORHP Xpress NonLinear^∗
GO solvers	ANTIGONE^∗ BARON Couenne^∗ Mathematica LINDO SCIP Octeract Engine
CP solvers	Artelys Kalis Comet CPLEX CP Optimizer Gecode Mathematica JaCoP Xpress Kalis
Metaheuristic solvers	OptaPlanner
List of optimization software Comparison of optimization software

Anonymous

Search

सेमिडेफिनिट प्रोग्रामिंग: Difference between revisions

Namespaces

More

Page actions

Revision as of 10:53, 16 February 2023

Contents

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

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

समतुल्य सूत्रीकरण

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

परिभाषाएँ

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

प्रबल द्वैत

उदाहरण

उदाहरण 1

उदाहरण 2

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

कलन विधि

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

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

बंडल विधि

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

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

अनुप्रयोग

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

सेमिडेफिनिट प्रोग्रामिंग: Difference between revisions

Revision as of 10:53, 16 February 2023

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

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

समतुल्य सूत्रीकरण

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

परिभाषाएँ

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

प्रबल द्वैत

उदाहरण

उदाहरण 1

उदाहरण 2

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

कलन विधि

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

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

बंडल विधि

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

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

अनुप्रयोग

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories