बहुपद एसओएस

This article is about यह लेख गैर-ऋणात्मक बहुपद को बहुपदों के वर्गों के योग के रूप में प्रस्तुत करने के बारे में है।. For तर्कसंगत कार्यों के वर्गों के योग के रूप में बहुपद का प्रतिनिधित्व करने के लिए है, see हिल्बर्ट की सत्रहवीं समस्या. For लगातार पूर्णांकों के वर्गों का योग, see वर्ग पिरामिड संख्या. For पूर्णांकों के वर्गों के योग के रूप में एक पूर्णांक का प्रतिनिधित्व करना है।, see लैग्रेंज का चार वर्ग प्रमेय.

गणित में, वास्तविक संख्या n आयामी सदिश x में बहुपद की डिग्री 2m का एक सजातीय बहुपद h(x) के रूप (एसओएस) के वर्गों का योग होता है और यदि केवल डिग्री एम के $g_{1}(x),\ldots ,g_{k}(x)$ के रूप में उपस्थित होती है। जैसे कि,

$$h(x)=\sum _{i=1}^{k}g_{i}(x)^{2}.$$

एसओएस का हर रूप एक सकारात्मक बहुपद के रूप में होता है और चूंकि विलोम (तर्क) हमेशा सत्य नहीं होता है, हिल्बर्ट ने सिद्ध किया कि एन = 2, 2 एम = 2 या एन = 3 और 2 एम = 4 के लिए एक फॉर्म एसओएस के रूप में होता है, यदि और केवल यदि यह सकारात्मक होता है। सकारात्मक सममित रूपों पर एनालॉग समस्या के लिए भी यही मान्य होता है।

चूंकि प्रत्येक फॉर्म को एसओएस के रूप में प्रदर्शित नहीं किया जा सकता है, एसओएस होने के लिए एक फॉर्म के लिए स्पष्ट पर्याप्त शर्तें पाई गई हैं। इसके अतिरिक्त, हर वास्तविक गैर-नकारात्मक रूप को वांछित के रूप में निकटता से अनुमानित किया जाता है $l_{1}$इसके गुणांक वेक्टर का मानदंड रूपों के अनुक्रम द्वारा $\{f_{\epsilon }\}$ एसओएस के रूप में हैं।

वर्ग मैट्रिकियल प्रतिनिधित्व (एसएमआर)

यह स्थापित करने के लिए कि क्या एक फॉर्म h(x) उत्तल अनुकूलन समस्या को हल करने के लिए एसओएस राशि के रूप में होती है। वास्तव में, इसे h(x) के रूप में लिखा जा सकता है

$$h(x)=x^{\{m\}'}\left(H+L(\alpha )\right)x^{\{m\}}$$

जहाँ $x^{\{m\}}$ एक वेक्टर होता है, जिसमें एक्स में डिग्री एम के रूपों के आधार पर होता है, जैसे कि एक्स में डिग्री एम के सभी एकपद , प्राइम, अभाज्य स्थानान्तरण को दर्शाता है, एच कोई भी सममित मैट्रिक्स के रूप में संतोषजनक होता है,

$$h(x)=x^{\left\{m\right\}'}Hx^{\{m\}}$$

और $L(\alpha )$ सदिश स्थान का एक रैखिक पैरामीटरकरण के रूप में होता है

$${\mathcal {L}}=\left\{L=L':~x^{\{m\}'}Lx^{\{m\}}=0\right\}.$$

वेक्टर का आयाम $x^{\{m\}}$ द्वारा दिया गया है

$$\sigma (n,m)={\binom {n+m-1}{m}},$$

जबकि वेक्टर $\alpha$ अल्फा का आयाम द्वारा दिया गया है

$$\omega (n,2m)={\frac {1}{2}}\sigma (n,m)\left(1+\sigma (n,m)\right)-\sigma (n,2m).$$

तब, h(x) एसओएस के रूप में होता है, यदि और केवल यदि कोई वेक्टर उपस्थित $\alpha$ है ऐसा है कि

हेन, एच (एक्स) एसओएस है अगर और और केवल अगर वहां एक वेक्टर मौजूद है,

$$H+L(\alpha )\geq 0,$$

मतलब कि मैट्रिक्स (गणित) $H+L(\alpha )$ धनात्मक-अर्द्धपरिमित मैट्रिक्स के रूप में होती है। यह एक रैखिक मैट्रिक्स असमानता एलएमआई व्यवहार्यता परीक्षण है, जो एक उत्तल अनुकूलन समस्या के रूप में है। व्यंजक $h(x)=x^{\{m\}'}\left(H+L(\alpha )\right)x^{\{m\}}$ में प्रस्तुत किया गया है वर्ग मैट्रिक प्रतिनिधित्व एसएमआर नाम के साथ यह स्थापित करने के लिए कि एलएमआई के माध्यम से एक फॉर्म एसओएस के रूप में होता है या नहीं। इस प्रतिनिधित्व को ग्राम मैट्रिक्स के रूप में भी जाना जाता है।

उदाहरण

• दो चरों में घात 4 के रूप पर विचार करें $h(x)=x_{1}^{4}-x_{1}^{2}x_{2}^{2}+x_{2}^{4}$. अपने पास
  $$m=2,~x^{\{m\}}={\begin{pmatrix}x_{1}^{2}\\x_{1}x_{2}\\x_{2}^{2}\end{pmatrix}}\!,~H+L(\alpha )={\begin{pmatrix}1&0&-\alpha _{1}\\0&-1+2\alpha _{1}&0\\-\alpha _{1}&0&1\end{pmatrix}}\!.$$
  चूँकि वहाँ उपस्थित है α ऐसा कि $H+L(\alpha )\geq 0$, अर्थात् $\alpha =1$, यह इस प्रकार है कि h(x) SOS है।
• तीन चरों में घात 4 के रूप पर विचार करें $h(x)=2x_{1}^{4}-2.5x_{1}^{3}x_{2}+x_{1}^{2}x_{2}x_{3}-2x_{1}x_{3}^{3}+5x_{2}^{4}+x_{3}^{4}$. अपने पास
  $$m=2,~x^{\{m\}}={\begin{pmatrix}x_{1}^{2}\\x_{1}x_{2}\\x_{1}x_{3}\\x_{2}^{2}\\x_{2}x_{3}\\x_{3}^{2}\end{pmatrix}},~H+L(\alpha )={\begin{pmatrix}2&-1.25&0&-\alpha _{1}&-\alpha _{2}&-\alpha _{3}\\-1.25&2\alpha _{1}&0.5+\alpha _{2}&0&-\alpha _{4}&-\alpha _{5}\\0&0.5+\alpha _{2}&2\alpha _{3}&\alpha _{4}&\alpha _{5}&-1\\-\alpha _{1}&0&\alpha _{4}&5&0&-\alpha _{6}\\-\alpha _{2}&-\alpha _{4}&\alpha _{5}&0&2\alpha _{6}&0\\-\alpha _{3}&-\alpha _{5}&-1&-\alpha _{6}&0&1\end{pmatrix}}.$$
  तब से $H+L(\alpha )\geq 0$ के लिए $\alpha =(1.18,-0.43,0.73,1.13,-0.37,0.57)$, यह इस प्रकार है कि h(x) एसओएस है।

सामान्यीकरण

मैट्रिक्स मुसीबत का इशारा

वास्तविक n-आयामी सदिश x में आयाम r और डिग्री 2m का एक मैट्रिक्स रूप F(x) (अर्थात, एक मैट्रिक्स जिसकी प्रविष्टियाँ रूप हैं) SOS है यदि और केवल यदि मैट्रिक्स रूप उपस्थित हैं $G_{1}(x),\ldots ,G_{k}(x)$ डिग्री एम की ऐसी है कि

$$F(x)=\sum _{i=1}^{k}G_{i}(x)'G_{i}(x).$$

मैट्रिक्स एसएमआर

उत्तल अनुकूलन समस्या को हल करने के लिए एक मैट्रिक्स फॉर्म एफ (एक्स) एसओएस राशि है या नहीं यह स्थापित करने के लिए। दरअसल, स्केलर केस के समान किसी भी एफ (एक्स) को एसएमआर के अनुसार लिखा जा सकता है

$$F(x)=\left(x^{\{m\}}\otimes I_{r}\right)'\left(H+L(\alpha )\right)\left(x^{\{m\}}\otimes I_{r}\right)$$

जहाँ $\otimes$ आव्यूहों का क्रोनेकर गुणनफल है, H कोई सममित आव्यूह संतोषजनक है

$$F(x)=\left(x^{\{m\}}\otimes I_{r}\right)'H\left(x^{\{m\}}\otimes I_{r}\right)$$

और $L(\alpha )$ रैखिक स्थान का एक रैखिक पैरामीटरकरण है

$${\mathcal {L}}=\left\{L=L':~\left(x^{\{m\}}\otimes I_{r}\right)'L\left(x^{\{m\}}\otimes I_{r}\right)=0\right\}.$$

वेक्टर का आयाम $\alpha$ द्वारा दिया गया है

$$\omega (n,2m,r)={\frac {1}{2}}r\left(\sigma (n,m)\left(r\sigma (n,m)+1\right)-(r+1)\sigma (n,2m)\right).$$

तब, F(x) एसओएस है यदि और केवल यदि कोई वेक्टर उपस्थित है $\alpha$ जैसे कि निम्नलिखित LMI धारण करता है:

$$H+L(\alpha )\geq 0.$$

इजहार $F(x)=\left(x^{\{m\}}\otimes I_{r}\right)'\left(H+L(\alpha )\right)\left(x^{\{m\}}\otimes I_{r}\right)$ में प्रस्तुत किया गया था यह स्थापित करने के लिए कि एलएमआई के माध्यम से मैट्रिक्स फॉर्म एसओएस है या नहीं।

गैर अनुमेय बहुपद एसओएस

नि: शुल्क बीजगणित R⟨X⟩ पर विचार करें जो एन नॉनकम्यूटिंग अक्षर एक्स = (एक्स) द्वारा उत्पन्न होता है₁, ..., एक्स_n) और सम्मलित होने से लैस है ^टी, ऐसा कि ^T R और X को ठीक करता है₁, ..., एक्स_n और X द्वारा बनाए गए शब्दों को उलट देता है₁, ..., एक्स_n. कम्यूटेटिव स्थिति के अनुरूप, गैर-अनुक्रमिक सममित बहुपद f फॉर्म के गैर-अनुक्रमिक बहुपद हैं f = f^T. जब किसी भी आयाम r × r के किसी भी वास्तविक मैट्रिक्स का मूल्यांकन एक सममित गैर-अनुक्रमिक बहुपद f पर किया जाता है, जिसके परिणामस्वरूप एक सकारात्मक अर्ध-निश्चित मैट्रिक्स होता है, f को मैट्रिक्स-पॉजिटिव कहा जाता है।

एक गैर क्रमविनिमेय बहुपद SOS है यदि वहां गैर क्रमविनिमेय बहुपद उपस्थित हैं $h_{1},\ldots ,h_{k}$ ऐसा है कि

$$f(X)=\sum _{i=1}^{k}h_{i}(X)^{T}h_{i}(X).$$

हैरानी की बात है कि गैर-अनुक्रमिक परिदृश्य में एक गैर-अनुक्रमिक बहुपद एसओएस है यदि और केवल यदि यह मैट्रिक्स-पॉजिटिव है। इसके अतिरिक्त , गैर-अनुमेय बहुपदों के वर्गों के योग में मैट्रिक्स-पॉजिटिव बहुपदों को विघटित करने के लिए उपलब्ध एल्गोरिदम उपस्थित हैं।

यह भी देखें

• योग-का-वर्ग अनुकूलन
• सकारात्मक बहुपद
• हिल्बर्ट की सत्रहवीं समस्या
• एसओएस-उत्तलता

श्रेणी:सजातीय बहुपद श्रेणी:वास्तविक बीजगणितीय ज्यामिति