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

Latest revision as of 15:56, 3 November 2023

सेमिडेफिनिट प्रोग्रामिंग (एसडीपी) उत्तल अनुकूलन का एक उपक्षेत्र है जो एक रैखिक उद्देश्य फलन (एक उपयोगकर्ता-निर्दिष्ट फलन जिसे उपयोगकर्ता कम या अधिकतम करना चाहता है) एक सजातीय स्थान के साथ सकारात्मक अर्ध-निश्चित आव्यूह के शंकु के प्रतिच्छेदन पर, 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]^[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}$ को उत्तर प्राप्त करने के लिए व्यवस्थित करते हैं। यह एक एसडीपी द्वारा प्रस्तुत किया जा सकता है। उदाहरण के लिए, चर आव्यूह को बढ़ाकर और सुस्त चरों को प्रस्तुत करके हम असमानता की बाधाओं को संभालते हैं

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

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

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

\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 को कई सन्निकटन कलन विधि विकसित करने के लिए लागू किया गया है। हाल ही में, प्रसाद राघवेंद्र ने अद्वितीय खेल सन्निकटन के आधार पर बाधा संतुष्टि समस्याओं के लिए एक सामान्य रूपरेखा विकसित की है।^[3]

कलन विधि

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

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

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

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

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

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

पूलिका विधि

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

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

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

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

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

अनुप्रयोग

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

बाहरी संबंध

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

[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 1: / Line 1: @@
-अर्धनिश्चित क्रमादेशन (SDP) उत्तल [[अनुकूलन]] का एक उपक्षेत्र है जो एक रैखिक उद्देश्य फलन (एक उपयोगकर्ता-निर्दिष्ट फलन जिसे उपयोगकर्ता कम या अधिकतम करना चाहता है) के अनुकूलन से संबंधित है।
+सेमिडेफिनिट प्रोग्रामिंग (एसडीपी) उत्तल [[अनुकूलन]] का एक उपक्षेत्र है जो एक रैखिक उद्देश्य फलन (एक उपयोगकर्ता-निर्दिष्ट फलन जिसे उपयोगकर्ता कम या अधिकतम करना चाहता है) एक सजातीय स्थान के साथ सकारात्मक अर्ध-निश्चित आव्यूह के शंकु के प्रतिच्छेदन पर, i.e, स्पेक्ट्राहेड्रॉन के अनुकूलन से संबंधित है।
-एक सजातीय स्थान के साथ सकारात्मक अर्ध-निश्चित आव्यूह के शंकु के प्रतिच्छेदन पर, i.e, एक स्पेक्ट्राहेड्रॉन।
+सेमिडेफिनिट प्रोग्रामिंग अनुकूलन का एक अपेक्षाकृत नया क्षेत्र है जो कई कारणों से बढ़ती रुचि का क्षेत्र है। संचालन अनुसंधान और संयोजी अनुकूलन में कई व्यावहारिक समस्याओं को अर्ध-निश्चित प्रोग्रामिंग समस्याओं के रूप में प्रतिरूपित या सन्निकटन किया जा सकता है। स्वत: नियंत्रण सिद्धांत में, एसडीपी का उपयोग [[रैखिक मैट्रिक्स असमानता|रैखिक आव्यूह असमानता]] के संदर्भ में किया जाता है। एसडीपी वस्तुत: [[शंकु अनुकूलन]] की एक विशेष स्तिथि है और इसे आंतरिक बिंदु विधियों द्वारा कुशलता से हल किया जा सकता है।
-अर्धनिश्चित क्रमादेशन अनुकूलन का एक अपेक्षाकृत नया क्षेत्र है जो कई कारणों से बढ़ती रुचि का है। संचालन अनुसंधान और संयोजी अनुकूलन में कई व्यावहारिक समस्याओं को अर्ध-निश्चित क्रमादेशन समस्याओं के रूप में प्रतिरूपित या अनुमानित किया जा सकता है। स्वत: नियंत्रण सिद्धांत में, SDP का उपयोग [[रैखिक मैट्रिक्स असमानता|रैखिक आव्यूह असमानता]] के संदर्भ में किया जाता है। SDP असल में [[शंकु अनुकूलन]] की एक विशेष स्तिथि है और इसे आंतरिक बिंदु विधियों द्वारा कुशलता से हल किया जा सकता है।
+सभी [[रैखिक प्रोग्रामिंग]] और (उत्तल) [[द्विघात प्रोग्रामिंग]] को एसडीपी के रूप में व्यक्त किया जा सकता है, और एसडीपी के पदानुक्रम के माध्यम से बहुपद अनुकूलन समस्याओं के समाधान को सन्निकटित किया जा सकता है। जटिल प्रणालियों के अनुकूलन में अर्ध निश्चित प्रोग्रामिंग का उपयोग किया गया है। नवीन वर्षों में, कुछ परिमाण परिप्रश्न उपद्रवता समस्याओं को अर्ध-निश्चित फलनों के संदर्भ में प्रस्तुत किया गया है।
-सभी [[रैखिक प्रोग्रामिंग|रैखिक क्रमादेशन]] और (उत्तल) [[द्विघात प्रोग्रामिंग|द्विघात क्रमादेशन]] को SDP के रूप में व्यक्त किया जा सकता है, और SDP के पदानुक्रम के माध्यम से बहुपद अनुकूलन समस्याओं के समाधान का अनुमान लगाया जा सकता है। जटिल प्रणालियों के अनुकूलन में अर्ध निश्चित क्रमादेशन का उपयोग किया गया है। हाल के वर्षों में, कुछ परिमाण परिप्रश्न उपद्रवता समस्याओं को अर्ध-निश्चित कार्यक्रमों के संदर्भ में तैयार किया गया है।
 == प्रेरणा और परिभाषा ==
@@ Line 11: / Line 9: @@
 === प्रारंभिक प्रेरणा ===
-एक रैखिक क्रमादेशन समस्या वह है जिसमें हम एक [[polytope|बहुतलीय]] पर वास्तविक चर के रैखिक उद्देश्य फलन को अधिकतम या कम करना चाहते हैं। अर्ध-निश्चित क्रमादेशन में, हम इसके स्थान पर वास्तविक-मूल्य वाले सदिश का उपयोग करते हैं और सदिश के बिन्दु उत्पाद लेने की अनुमति देते हैं; LP (रैखिक क्रमादेशन) में वास्तविक चर पर गैर-नकारात्मकता बाधाओं को SDP (अर्ध-परिमित क्रमादेशन) में आव्यूह चर पर अर्ध-निश्चितता बाधाओं द्वारा प्रतिस्थापित किया जाता है। विशेष रूप से, एक सामान्य अर्ध निश्चित क्रमादेशन समस्या को प्रपत्र की किसी भी गणितीय क्रमादेशन समस्या के रूप में परिभाषित किया जा सकता है
+रैखिक प्रोग्रामिंग समस्या वह है जिसमें हम एक [[polytope|बहुतलीय]] पर वास्तविक चर के रैखिक उद्देश्य फलन को अधिकतम या कम करना चाहते हैं। अर्ध-निश्चित प्रोग्रामिंग में, हम इसके स्थान पर वास्तविक-मूल्य वाले सदिश का उपयोग करते हैं और सदिश के बिन्दु उत्पाद लेने की अनुमति देते हैं; LP (रैखिक प्रोग्रामिंग) में वास्तविक चर पर गैर-नकारात्मकता बाधाओं को एसडीपी (अर्ध-परिमित प्रोग्रामिंग) में आव्यूह चर पर अर्ध-निश्चितता बाधाओं द्वारा प्रतिस्थापित किया जाता है। विशेष रूप से, एक सामान्य अर्ध निश्चित प्रोग्रामिंग समस्या को प्रपत्र की किसी भी गणितीय प्रोग्रामिंग समस्या के रूप में परिभाषित किया जा सकता है
 :<math>
@@ Line 19: / Line 17: @@
 \end{array}
 </math>
-जहां <math>c_{i,j}, a_{i,j,k}</math>, और <math> b_k </math> यह वास्तविक संख्याएँ हैं और <math>x^i \cdot x^j</math> का [[डॉट उत्पाद]]  <math>x^i</math> और  <math>x^j</math> है।
+जहां <math>c_{i,j}, a_{i,j,k}</math>, और <math> b_k </math> यह वास्तविक संख्याएँ हैं और <math>x^i \cdot x^j</math> का [[डॉट उत्पाद|बिंदु उत्पाद]] <math>x^i</math> और <math>x^j</math> है।
 === समतुल्य सूत्रीकरण ===
-एक <math>n \times n</math> आव्यूह <math>M</math> सकारात्मक-अर्द्धपरिमित कहा जाता है यदि यह कुछ सदिशों का ग्राम आव्यूह है। यदि ऐसा है, तो हम इसे <math>M \succeq 0</math> इस रूप में निरूपित करते हैं। ध्यान दें कि सकारात्मक अर्ध-निश्चित होने की कई अन्य समकक्ष परिभाषाएं हैं, उदाहरण के लिए, सकारात्मक अर्ध-निश्चित आव्यूह स्व-संलग्न आव्यूह हैं जिनके पास केवल गैर-नकारात्मक आइगेनवैल्यू और आइगेनवेक्टर हैं।
+एक <math>n \times n</math> आव्यूह <math>M</math> सकारात्मक-अर्द्धपरिमित कहा जाता है यदि यह कुछ सदिशों का ग्राम आव्यूह है। यदि ऐसा है, तो हम इसे <math>M \succeq 0</math> इस रूप में निरूपित करते हैं। ध्यान दें कि सकारात्मक अर्ध-निश्चित होने की कई अन्य समकक्ष परिभाषाएं हैं, उदाहरण के लिए, सकारात्मक अर्ध-निश्चित आव्यूह स्व-संलग्न आव्यूह हैं जिनके पास केवल गैर-नकारात्मक आइगेनवैल्यू और आइगेनसदिश हैं।
 सभी <math>n \times n</math> वास्तविक सममित आव्यूह का स्थान <math>\mathbb{S}^n</math> द्वारा निरूपित करें। दिकस्थान [[आंतरिक उत्पाद स्थान|आंतरिक उत्पाद]] से सुसज्जित है (जहाँ <math>{\rm tr}</math> [[ट्रेस (रैखिक बीजगणित)|अनुरेख (रैखिक बीजगणित)]] को दर्शाता है)
@@ Line 41: / Line 39: @@
 \end{array}
 </math>
-जहां <math>C</math> में प्रवेश <math>i,j</math> पिछले खंड से <math>\frac{c_{i,j} + c_{j,i}}{2}</math> द्वारा दिया गया है। और <math>A_k</math> एक सममित <math>n \times n</math> पिछले खंड से <math>i,j</math> आव्यूह <math>\frac{a_{i,j,k}+a_{j,i,k}}{2}</math> है। इस प्रकार, आव्यूह <math>C</math> और <math>A_k</math> सममित हैं और उपरोक्त आंतरिक उत्पाद अच्छी तरह से परिभाषित हैं।
+जहां <math>C</math> में पिछले खंड से <math>\frac{c_{i,j} + c_{j,i}}{2}</math> द्वारा प्रवेश <math>i,j</math> दिया गया है। और <math>A_k</math> एक सममित <math>n \times n</math> पिछले खंड से <math>i,j</math> आव्यूह <math>\frac{a_{i,j,k}+a_{j,i,k}}{2}</math> है। इस प्रकार, आव्यूह <math>C</math> और <math>A_k</math> सममित हैं और उपरोक्त आंतरिक उत्पाद पूर्णतः स्पष्ट परिभाषित हैं।
-ध्यान दें कि यदि हम उचित रूप से [[सुस्त चर]] जोड़ते हैं, तो इस SDP को किसी एक रूप में परिवर्तित किया जा सकता है
+ध्यान दें कि यदि हम उचित रूप से [[सुस्त चर|मंदगामी चर]] जोड़ते हैं, तो इस एसडीपी को किसी एक रूप में परिवर्तित किया जा सकता है
 :<math>
@@ Line 52: / Line 50: @@
 \end{array}
 </math>
-सुविधा के लिए, एक SDP को थोड़े अलग, लेकिन समतुल्य रूप में निर्दिष्ट किया जा सकता है। उदाहरण के लिए, गैर-नकारात्मक अदिश (गणित) चर वाले रैखिक भावों को क्रमादेश विनिर्देश में जोड़ा जा सकता है। यह एक SDP बना रहता है क्योंकि प्रत्येक चर को <math>X</math> विकर्ण प्रविष्टि के रूप में (<math>X_{ii}</math> कुछ के लिए <math>i</math>) आव्यूह में सम्मिलित किया जा सकता है। यह सुनिश्चित करने के लिए <math>X_{ii} \geq 0</math>, प्रतिबंध <math>X_{ij} = 0</math> सभी के लिए <math>j \neq i</math> जोड़ा जा सकता है। एक अन्य उदाहरण के रूप में, ध्यान दें कि किसी भी सकारात्मक अर्ध निश्चित आव्यूह के लिए <math>X</math>, सदिश का एक सम्मुच्चय <math>\{ v_i \}</math> उपस्थित है  ऐसा कि <math>X</math> का <math>i</math>, <math>j</math> प्रवेश <math>X_{ij} = (v_i, v_j)</math> <math>v_i</math> और <math>v_j</math> का डॉट उत्पाद है। इसलिए, SDPs को प्रायः सदिशों के अदिश गुणनफलों पर रेखीय व्यंजकों के रूप में तैयार किया जाता है। मानक रूप में SDP के समाधान को देखते हुए, सदिश <math>\{ v_i \}</math> <math>O(n^3)</math> समय में पुनराप्‍त किया जा सकता है (उदाहरण के लिए, X के अपूर्ण चोलस्की अपघटन का उपयोग करके)।
+सुविधा के लिए, एक एसडीपी को थोड़े अलग, लेकिन समतुल्य रूप में निर्दिष्ट किया जा सकता है। उदाहरण के लिए, गैर-नकारात्मक अदिश (गणित) चर वाले रैखिक भावों को क्रमादेश विनिर्देश में जोड़ा जा सकता है। यह एक एसडीपी बना रहता है क्योंकि प्रत्येक चर को <math>X</math> विकर्ण प्रविष्टि के रूप में (<math>X_{ii}</math> कुछ <math>i</math> के लिए) आव्यूह में सम्मिलित किया जा सकता है। यह सुनिश्चित करने के लिए कि <math>X_{ii} \geq 0</math>, प्रतिबंध <math>X_{ij} = 0</math> सभी के लिए <math>j \neq i</math> जोड़ा जा सकता है। एक अन्य उदाहरण के रूप में, ध्यान दें कि किसी भी सकारात्मक अर्ध निश्चित आव्यूह के लिए <math>X</math>, सदिश का एक सम्मुच्चय <math>\{ v_i \}</math> उपस्थित है ऐसा कि <math>X</math> का <math>i</math>, <math>j</math> प्रवेश <math>X_{ij} = (v_i, v_j)</math> <math>v_i</math> और <math>v_j</math> का बिंदु उत्पाद है। इसलिए, एसडीपीs को प्रायः सदिशों के अदिश गुणनफलों पर रेखीय व्यंजकों के रूप में प्रस्तुत किया जाता है। मानक रूप में एसडीपी के समाधान को देखते हुए, सदिश <math>\{ v_i \}</math> <math>O(n^3)</math> समय में पुनराप्‍त किया जा सकता है (उदाहरण के लिए, X के अपूर्ण चोलस्की अपघटन का उपयोग करके)।
 == द्वैत सिद्धांत ==
@@ Line 58: / Line 56: @@
 === परिभाषाएँ ===
-समान रूप से रैखीय क्रमादेशन के लिए, प्रारूप का एक सामान्य SDP दिया गया
+समान रूप से रैखीय प्रोग्रामिंग के लिए, प्रारूप का एक सामान्य एसडीपी दिया गया
 :<math>
@@ Line 67: / Line 65: @@
 \end{array}
 </math>
-(आद्यसमस्या या P-SDP), हम [[दोहरी समस्या|द्वैध समस्या]] अर्धनिश्चित क्रमादेश (D-SDP) को इस रूप में परिभाषित करते हैं
+(आद्यसमस्या या P-एसडीपी), हम [[दोहरी समस्या|द्वैध समस्या]] सेमिडेफिनिट क्रमादेश (D-एसडीपी) को इस रूप में परिभाषित करते हैं
 :<math>
 \begin{array}{rl}
@@ Line 78: / Line 76: @@
 === [[कमजोर द्वैत|शक्तिहीन द्वैत]] ===
-शक्तिहीन द्वैत प्रमेय कहता है कि मौलिक SDP का मूल्य कम से कम दोहरी SDP का मूल्य है। इसलिए, दोहरे SDP के लिए कोई भी व्यवहार्य समाधान प्राथमिक SDP मूल्य को कम करता है, और इसके विपरीत, प्राथमिक SDP के लिए कोई भी संभव समाधान दोहरी SDP मूल्य को ऊपरी सीमा में रखता है। यह है क्योंकि
+शक्तिहीन द्वैत प्रमेय कहता है कि मौलिक एसडीपी का मूल्य कम से कम दोहरी एसडीपी का मूल्य है। इसलिए, दोहरे एसडीपी के लिए कोई भी व्यवहार्य समाधान प्राथमिक एसडीपी मूल्य को कम करता है, और इसके विपरीत, प्राथमिक एसडीपी के लिए कोई भी संभव समाधान दोहरी एसडीपी मूल्य को ऊपरी सीमा में रखता है। यह है क्योंकि
 :<math>
 \langle C, X \rangle - \langle b, y \rangle
@@ Line 89: / Line 87: @@
 === प्रबल द्वैत ===
-जब मूल और द्वैत SDPs का मान समान होता है, तो SDP को प्रबल द्वैत गुण को संतुष्ट करने वाला कहा जाता है। रेखीय क्रमादेशन के विपरीत, जहां प्रत्येक दोहरे रेखीय कार्यक्रम का इष्टतम उद्देश्य प्राथमिक उद्देश्य के बराबर होता है, प्रत्येक SDP [[मजबूत द्वैत|प्रबल द्वैत]] को संतुष्ट नहीं करता है; सामान्य तौर पर, दोहरी SDP का मूल्य मूल के मूल्य से अनुशासनपूर्वक नीचे हो सकता है, और P-SDP और D-SPD निम्नलिखित गुणों को पूरा करते हैं:
+जब मूल और द्वैत एसडीपीs का मान समान होता है, तो एसडीपी को प्रबल द्वैत गुण को संतुष्ट करने वाला कहा जाता है। रेखीय प्रोग्रामिंग के विपरीत, जहां प्रत्येक दोहरे रेखीय फलन का इष्टतम उद्देश्य प्राथमिक उद्देश्य के समकक्ष होता है, प्रत्येक एसडीपी [[मजबूत द्वैत|प्रबल द्वैत]] को संतुष्ट नहीं करता है; सामान्यतः, दोहरी एसडीपी का मूल्य मूल के मूल्य से अनुशासनपूर्वक नीचे हो सकता है, और P-एसडीपी और D-SPD निम्नलिखित गुणों को पूरा करते हैं:
-(i) मान लीजिए कि मूल समस्या (P-SDP) नीचे और दृढता से बंधी हुई है (यानी, <math>X_0\in\mathbb{S}^n, X_0\succ 0</math> ऐसे उपस्थित है कि <math>\langle
+(i) मान लीजिए कि मूल समस्या (P-एसडीपी) नीचे और दृढता से बंधी हुई है (अर्थात, <math>X_0\in\mathbb{S}^n, X_0\succ 0</math> ऐसे उपस्थित है कि <math>\langle
-A_i,X_0\rangle_{\mathbb{S}^n} = b_i</math>, <math>i=1,\ldots,m</math>)। तब एक इष्टतम समाधान  <math>y^*</math> (D-SDP) और <math>\langle C,X^*\rangle_{\mathbb{S}^n} = \langle b,y^*\rangle_{\R^m}</math>होता है।
+A_i,X_0\rangle_{\mathbb{S}^n} = b_i</math>, <math>i=1,\ldots,m</math>)। तब एक इष्टतम समाधान <math>y^*</math> (D-एसडीपी) और <math>\langle C,X^*\rangle_{\mathbb{S}^n} = \langle b,y^*\rangle_{\R^m}</math>होता है।
 :
-(ii) मान लीजिए कि दोहरी समस्या (D-SDP) ऊपर और दृढता से संभाव्य है (यानी,
+(ii) मान लीजिए कि दोहरी समस्या (D-एसडीपी) ऊपर और दृढता से संभाव्य है (अर्थात, <math>\sum_{i=1}^m (y_0)_i A_i
-<math>\sum_{i=1}^m (y_0)_i A_i
+\prec C</math> कुछ <math>y_0\in\R^m</math> के लिए)। तब एक इष्टतम समाधान <math>X^*</math>(P-एसडीपी) होता है और (i) से समानता धारण करती है।
-\prec C</math> कुछ <math>y_0\in\R^m</math> के लिए)। तब एक इष्टतम समाधान <math>X^*</math>(P-SDP) होता है और (i) से समानता धारण करती है।
-एक SDP समस्या (और सामान्य तौर पर, किसी भी उत्तल अनुकूलन समस्या के लिए) के लिए मजबूत द्वैत के लिए एक पर्याप्त स्थिति स्लेटर की स्थिति है। रमन द्वारा प्रस्तावित विस्तारित द्वैध समस्या का उपयोग करके अतिरिक्त नियमितता शर्तों के बिना SDP के लिए मजबूत द्वैत प्राप्त करना भी संभव है।<ref>{{Cite journal |last=Ramana |first=Motakuri V. |date=1997 |title=An exact duality theory for semidefinite programming and its complexity implications |url=http://link.springer.com/10.1007/BF02614433 |journal=Mathematical Programming |language=en |volume=77 |issue=1 |pages=129–162 |doi=10.1007/BF02614433 |s2cid=12886462 |issn=0025-5610}}</ref><ref>{{Cite journal |last1=Vandenberghe |first1=Lieven |last2=Boyd |first2=Stephen |date=1996 |title=Semidefinite Programming |url=http://epubs.siam.org/doi/10.1137/1038003 |journal=SIAM Review |language=en |volume=38 |issue=1 |pages=49–95 |doi=10.1137/1038003 |issn=0036-1445}}</ref>
+एक एसडीपी समस्या (और सामान्यतः, किसी भी उत्तल अनुकूलन समस्या के लिए) के लिए मजबूत द्वैत के लिए एक पर्याप्त स्थिति स्लेटर की स्थिति है। रमन द्वारा प्रस्तावित विस्तारित द्वैध समस्या का उपयोग करके अतिरिक्त नियमितता शर्तों के बिना एसडीपी के लिए मजबूत द्वैत प्राप्त करना भी संभव है।<ref>{{Cite journal |last=Ramana |first=Motakuri V. |date=1997 |title=An exact duality theory for semidefinite programming and its complexity implications |url=http://link.springer.com/10.1007/BF02614433 |journal=Mathematical Programming |language=en |volume=77 |issue=1 |pages=129–162 |doi=10.1007/BF02614433 |s2cid=12886462 |issn=0025-5610}}</ref><ref>{{Cite journal |last1=Vandenberghe |first1=Lieven |last2=Boyd |first2=Stephen |date=1996 |title=Semidefinite Programming |url=http://epubs.siam.org/doi/10.1137/1038003 |journal=SIAM Review |language=en |volume=38 |issue=1 |pages=49–95 |doi=10.1137/1038003 |issn=0036-1445}}</ref>
@@ Line 123: / Line 120: @@
 \end{pmatrix} \succeq 0
 \end{array}</math>
-हम <math>\rho_{AB} = x_{12}, \ \rho_{AC} = x_{13}, \ \rho_{BC} = x_{23} </math> को उत्तर प्राप्त करने के लिए व्यवस्थित करते हैं। यह एक SDP द्वारा तैयार किया जा सकता है। उदाहरण के लिए, चर आव्यूह को बढ़ाकर और सुस्त चरों को प्रस्तुत करके हम असमानता की बाधाओं को संभालते हैं
+हम <math>\rho_{AB} = x_{12}, \ \rho_{AC} = x_{13}, \ \rho_{BC} = x_{23} </math> को उत्तर प्राप्त करने के लिए व्यवस्थित करते हैं। यह एक एसडीपी द्वारा प्रस्तुत किया जा सकता है। उदाहरण के लिए, चर आव्यूह को बढ़ाकर और सुस्त चरों को प्रस्तुत करके हम असमानता की बाधाओं को संभालते हैं
 <math>\mathrm{tr}\left(\left(\begin{array}{cccccc}
@@ Line 139: / Line 136: @@
 & 0 & 0 & 0 & 0 & s_{3}\end{array}\right)\right)=x_{12} + s_{1}=-0.1</math>
-इस SDP को हल करने पर, <math>\rho_{AC} = x_{13} \ </math>का न्यूनतम और अधिकतम मान <math>-0.978</math> और <math> 0.872 </math> क्रमशः प्राप्त होता है।
+इस एसडीपी को हल करने पर, <math>\rho_{AC} = x_{13} \ </math>का न्यूनतम और अधिकतम मान <math>-0.978</math> और <math> 0.872 </math> क्रमशः प्राप्त होता है।
 === उदाहरण 2 ===
-'''समस्या पर विचार करें'''
+समस्या पर विचार करें
-: '''छोटा करना <math>\frac{(c^T x)^2}{d^Tx} </math>'''
+: <math>\frac{(c^T x)^2}{d^Tx} </math> न्यूनतमीकरण
-: '''का विषय है <math>Ax +b\geq 0</math>'''
+: <math>Ax +b\geq 0</math> के अध्यधीन है।
-'''जहां हम मानते हैं <math>d^Tx>0</math> जब कभी भी <math>Ax+b\geq 0</math>.'''
+जहां हम जहाँ हम यह मानते हैं कि <math>d^Tx>0</math> जब कभी भी <math>Ax+b\geq 0</math> होता है
-'''एक सहायक चर का''' परिचय <math>t</math> समस्या का सुधार किया जा सकता है:
+एक सहायक चर <math>t</math> का परिचय समस्या का सुधार किया जा सकता है:
-: छोटा करना <math>t</math>
+: <math>t</math> न्यूनतमीकरण
-: का विषय है <math>Ax+b\geq 0, \, \frac{(c^T x)^2}{d^Tx}\leq t</math>
+: <math>Ax+b\geq 0, \, \frac{(c^T x)^2}{d^Tx}\leq t</math> के अध्यधीन है।
-इस सूत्रीकरण में, उद्देश्य चरों का एक रैखिक कार्य है <math>x,t</math>.
+इस सूत्रीकरण में, उद्देश्य चरों का एक रैखिक कार्य <math>x,t</math> है
-पहले प्रतिबंध के रूप में लिखा जा सकता है
+पहले प्रतिबंध को निम्न रूप में लिखा जा सकता है
 : <math>\textbf{diag}(Ax+b)\geq 0</math>
-जहां आव्यूह <math>\textbf{diag}(Ax+b)</math> विकर्ण में मान के साथ वर्ग आव्यूह बराबर है
+जहां आव्यूह <math>\textbf{diag}(Ax+b)</math> विकर्ण में मान के साथ वर्ग आव्यूह सदिश <math>Ax+b</math> के तत्वों के लिए समकक्ष है
-वेक्टर के तत्वों के लिए <math>Ax+b</math>.
-दूसरे प्रतिबंध के रूप में लिखा जा सकता है
+दूसरे प्रतिबंध को निम्न रूप में लिखा जा सकता है
 : <math>td^Tx-(c^Tx)^2\geq 0</math>
-परिभाषित <math>D</math> निम्नलिखित नुसार
+<math>D</math> को निम्नानुसार परिभाषित करना
 : <math>D=\left[\begin{array}{cc}t&c^Tx\\c^Tx&d^Tx\end{array}\right]</math>
-इसे देखने के लिए हम शूर कॉम्प्लिमेंट्स के सिद्धांत का उपयोग कर सकते हैं
+इसे देखने के लिए हम शूर पूरक के सिद्धांत का उपयोग कर सकते हैं
 :<math>D \succeq 0</math>
 (बॉयड और वैंडेनबर्ग, 1996)
-इस समस्या से जुड़ा अर्धनिश्चित प्रोग्राम है
+इस समस्या से जुड़ा सेमिडेफिनिट क्रमादेश है
-: छोटा करना <math>t</math>
+: <math>t</math> न्यूनतमीकरण
-: का विषय है <math>\left[\begin{array}{ccc}\textbf{diag}(Ax+b)&0&0\\0&t&c^Tx\\0&c^Tx&d^Tx\end{array}\right] \succeq 0</math>
+: <math>\left[\begin{array}{ccc}\textbf{diag}(Ax+b)&0&0\\0&t&c^Tx\\0&c^Tx&d^Tx\end{array}\right] \succeq 0</math> के अध्यधीन है।
-=== उदाहरण 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-कड़ा अधिकतमकरण समस्याओं के लिए सन्निकटन कलन विधि विकसित करने के लिए अर्ध-निश्चित फलन महत्वपूर्ण उपकरण हैं। एसडीपी पर आधारित पहला सन्निकटन कलन विधि [[माइकल गोमैन्स]] और डेविड पी. विलियमसन (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 को हल करें (मनमाने ढंग से छोटी योजक त्रुटि के भीतर <math>\epsilon</math>).
+# एसडीपी को हल करें (अव्यवस्थिततः छोटी योजक त्रुटि <math>\epsilon</math> के भीतर ).
-# मूल पूर्णांक द्विघात कार्यक्रम का अनुमानित समाधान प्राप्त करने के लिए 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 होता है।) अद्वितीय गेम अनुमान मानते हुए, यह दिखाया जा सकता है कि यह सन्निकटन अनुपात अनिवार्य रूप से इष्टतम है।
+यह एक एसडीपी है क्योंकि उद्देश्य फलन और बाधाएं सदिश आंतरिक उत्पादों के सभी रैखिक कार्य हैं। एसडीपी को हल करने से एकक सदिश का एक सम्मुच्चय <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>
+गोमेन्स और विलियमसन के मूल पट्र के बाद से, एसडीपीs को कई सन्निकटन कलन विधि विकसित करने के लिए लागू किया गया है। हाल ही में, प्रसाद राघवेंद्र ने अद्वितीय खेल सन्निकटन के आधार पर बाधा संतुष्टि समस्याओं के लिए एक सामान्य रूपरेखा विकसित की है।<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>.
+एसडीपी को हल करने के लिए कई प्रकार के कलन विधि हैं। ये कलन विधि एसडीपी के मूल्य को एक योगात्मक त्रुटि <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>
+आनन लघूकरण कलन विधि भी हैं जिनका उपयोग समस्या की बाधाओं का निरीक्षण करके एसडीपी समस्याओं को पूर्वप्रक्रम करने के लिए किया जा सकता है। इनका उपयोग यथार्थ व्यवहार्यता की कमी का पता लगाने, अनावश्यक पंक्तियों और स्तंभों को हटाने और चर आव्यूह के आकार को कम करने के लिए भी किया जा सकता है।<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> इस दृष्टिकोण पर आधारित हैं।
+अधिकांश कूट आंतरिक बिंदु विधियों (Cएसडीपी, [[MOSEK|मोसेक]], सेडूमी, [https://www.math.cmu.edu/~reha/sdpt3.html एसडीपीT3], Dएसडीपी, एसडीपीA) पर आधारित होते हैं। सामान्य रेखीय एसडीपी समस्याओं के लिए दृढ़ और कुशल होते हैं। इस तथ्य से प्रतिबंधित है कि कलन विधि दूसरे क्रम की प्रणाली हैं और एक बड़े (और प्रायः घने) आव्यूह को संग्रह और गुणनखंड करने की आवश्यकता होती है। सैद्धांतिक रूप से, अत्याधुनिक उच्च सटीकता एसडीपी कलन विधि<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 213: / Line 208: @@
 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 समस्याओं के एक विशेष वर्ग के लिए यह दृष्टिकोण बहुत कुशल है।
+कूट शंक्वाकार पूलिका एसडीपी समस्या को एक [[गैर-चिकनी अनुकूलन|गैर-सुचारू अनुकूलन]] समस्या के रूप में उद्यत करता है और इसे गैर-सुचारू अनुकूलन के वर्णक्रमीय पूल विधि द्वारा हल करता है। रैखिक एसडीपी समस्याओं के एक विशेष वर्ग के लिए यह दृष्टिकोण बहुत कुशल है।
-=== अन्य हल करने के तरीके ===
+=== अन्य समाधान विधि ===
-[[संवर्धित 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 विधि|संवर्धित लाग्रंगियन विधि]] (PENएसडीपी) पर आधारित कलन विधि व्यवहार में आंतरिक बिंदु विधियों के समान हैं और कुछ बहुत बड़े अनुपात की समस्याओं के लिए विशिष्ट हो सकते हैं। अन्य कलन विधि एक गैर-रैखिक प्रोग्रामिंग समस्या (एसडीपीLR) के रूप में एसडीपी के निम्न-श्रेणी की जानकारी और सुधार का उपयोग करते हैं।<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 एल्गोरिथम पुनरावृत्तियों में।
+एसडीपी को लगभग हल करने वाले कलन विधि भी प्रस्तावित किए गए हैं। ऐसे तरीकों का मुख्य लक्ष्य उन अनुप्रयोगों में कम जटिलता प्राप्त करना है जहां सन्निकटन समाधान पर्याप्त हैं और जटिलता न्यूनतम होनी चाहिए। एकाधिक-निविष्ट एकाधिक-निर्गत (MIMO) तारविहीन प्रणाली में आकड़ों का पता लगाने के लिए इस्तेमाल की जाने वाली एक प्रमुख विधि त्रिकोणीय सन्निकटन सेमिडेफिनिट शिथिलिकरण (टसर) है।<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 के सन्निकटन अनुपात के साथ लागू किया गया है। एसडीपी का उपयोग ज्यामिति में टेंग्रिटी लेखाचित्र निर्धारित करने के लिए भी किया जाता है, और रैखिक आव्यूह असमानता के रूप में नियंत्रण सिद्धांत में उत्पन्न होता है, और विपरीत दीर्घवृत्तीय गुणांक समस्याओं में उत्तल, गैर-रैखिक, अर्ध-निश्चितता बाधाओं के रूप में होता है।<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>
@@ Line 234: / Line 229: @@
 * Monique Laurent, Franz Rendl, "Semidefinite Programming and Integer Programming", Report PNA-R0210, CWI, Amsterdam, April 2002. [http://www.optimization-online.org/DB_HTML/2002/12/585.html 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), [http://ocw.mit.edu/courses/sloan-school-of-management/15-094j-systems-optimization-models-and-computation-sma-5223-spring-2004/lecture-notes/sdp094_digest.pdf SDP-Introduction]
+* Robert M. Freund, "Introduction to Semidefinite Programming (एसडीपी), [http://ocw.mit.edu/courses/sloan-school-of-management/15-094j-systems-optimization-models-and-computation-sma-5223-spring-2004/lecture-notes/sdp094_digest.pdf एसडीपी-Introduction]
@@ Line 241: / Line 236: @@
 *[http://www.cs.elte.hu/~lovasz/semidef.ps Lecture notes] from [[László Lovász]] on Semidefinite Programming
-{{optimization algorithms|convex}}
+[[Category:CS1 English-language sources (en)]]
-{{Mathematical optimization software}}
-[[Category: उत्तल अनुकूलन]] [[Category: पी-पूर्ण समस्याएं]] [[Category: वास्तविक बीजगणितीय ज्यामिति]] [[Category: रैखिक प्रोग्रामिंग]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 13/02/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:उत्तल अनुकूलन]]
+[[Category:पी-पूर्ण समस्याएं]]
+[[Category:रैखिक प्रोग्रामिंग]]
+[[Category:वास्तविक बीजगणितीय ज्यामिति]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 15:56, 3 November 2023

Contents

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

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

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

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

परिभाषाएँ

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

प्रबल द्वैत

उदाहरण

उदाहरण 1

उदाहरण 2

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

कलन विधि

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

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

पूलिका विधि

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

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

अनुप्रयोग

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 15:56, 3 November 2023

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

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

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

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

परिभाषाएँ

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

प्रबल द्वैत

उदाहरण

उदाहरण 1

उदाहरण 2

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

कलन विधि

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

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

पूलिका विधि

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

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

अनुप्रयोग

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories