बहुपद एसओएस

This article is about representing a non-negative polynomial as sum of squares of polynomials. For representing polynomial as a sum of squares of rational functions, see Hilbert's seventeenth problem. For the sum of squares of consecutive integers, see square pyramidal number. For representing an integer as a sum of squares of integers, see Lagrange's four-square theorem.

गणित में, एक सजातीय बहुपद (यानी एक सजातीय बहुपद) h(x) एक बहुपद की डिग्री 2m वास्तविक संख्या n-आयामी सदिश x में रूपों (SOS) के वर्गों का योग होता है यदि और केवल यदि रूप मौजूद हों $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).$$

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

यह भी देखें

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

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