SOS متعدد الحدود

في الرياضيات ، يكون الشكل (أي متعددة الحدود المتجانسة) h ( x ) من الدرجة 2 m في المتجه الحقيقي ذي الأبعاد n x هو مجموع مربعات الأشكال (SOS) إذا وفقط إذا كانت هناك أشكال من الدرجة m بحيث ${\displaystyle g_{1}(x),\ldots ,g_{k}(x)}$$${\displaystyle h(x)=\مجموع i=1kgi(x)2}$$

كل شكل يكون SOS هو أيضًا كثير حدود موجب ، وعلى الرغم من أن العكس ليس صحيحًا دائمًا، فقد أثبت هيلبرت أنه بالنسبة لـ n = 2، أو 2 m = 2، أو n = 3 و2 m = 4، فإن الشكل يكون SOS إذا وفقط إذا كان موجبًا. ^[1] وينطبق نفس الشيء أيضًا على المشكلة التناظرية على الأشكال المتماثلة الموجبة . ^{[2] [3]}

على الرغم من أنه لا يمكن تمثيل كل شكل على أنه SOS، فقد تم العثور على شروط كافية صريحة ليكون الشكل SOS. ^{[4] [5]} وعلاوة على ذلك، يمكن تقريب كل شكل غير سلبي حقيقي بأكبر قدر ممكن من الدقة (في القاعدة - لمتجه معامله) من خلال سلسلة من الأشكال التي تكون SOS. ^[6]${\displaystyle l_{1}}$${\displaystyle \{f_{\epsilon }\}}$

لتحديد ما إذا كان الشكل h ( x ) هو SOS يعادل حل مشكلة تحسين محدبة . في الواقع، يمكن كتابة أي h ( x ) على النحو التالي حيث هو متجه يحتوي على قاعدة لأشكال الدرجة m في x (مثل جميع أحاديات الدرجة m في x )، يشير العدد الأولي ′ إلى المنقول ، H هو أي مصفوفة متماثلة تلبي و هو معلمة خطية للفضاء الخطي$${\displaystyle h(x)=x^{\{m\}'}\left(H+L(\alpha )\right)x^{\{m\}}}$$${\displaystyle x^{\{m\}}}$$${\displaystyle h(x)=x^{\left\{m\right\}'}Hx^{\{m\}}}$$${\displaystyle L(\alpha )}$ $${\displaystyle {\mathcal {L}}=\left\{L=L':~x^{\{m\}'}Lx^{\{m\}}=0\right\}.}$$

يتم تحديد أبعاد المتجه بواسطة بينما يتم تحديد أبعاد المتجه بواسطة${\displaystyle x^{\{m\}}}$$${\displaystyle \sigma (n,m)={\binom {n+m-1}{m}},}$$${\displaystyle \alpha }$$${\displaystyle \omega (n,2m)={\frac {1}{2}}\sigma (n,m)\left(1+\sigma (n,m)\right)-\sigma (n,2m).}$$

عندئذٍ، تكون h ( x ) SOS إذا وفقط إذا كان هناك متجه بحيث يعني أن المصفوفة موجبة وشبه محددة . هذا هو اختبار جدوى عدم المساواة الخطية للمصفوفة (LMI)، وهو مشكلة تحسين محدبة. تم تقديم التعبير في ^[7] باسم التمثيل المصفوفي المربع (SMR) من أجل تحديد ما إذا كان النموذج هو SOS عبر LMI. يُعرف هذا التمثيل أيضًا باسم مصفوفة جرام. ^[8]${\displaystyle \alpha }$$${\displaystyle H+L(\alpha )\geq 0,}$$ ${\displaystyle H+L(\alpha )}$${\displaystyle h(x)=x^{\{m\}'}\left(H+L(\alpha )\right)x^{\{m\}}}$

• لنأخذ شكل الدرجة 4 في متغيرين . لدينا بما أن هناك α بحيث ، أي ، يتبع ذلك أن h ( x ) هي SOS.${\displaystyle h(x)=x_{1}^{4}-x_{1}^{2}x_{2}^{2}+x_{2}^{4}}$$${\displaystyle 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}}\!.}$$${\displaystyle H+L(\alpha )\geq 0}$${\displaystyle \alpha =1}$
• لنأخذ شكل الدرجة 4 في ثلاثة متغيرات . لدينا بما أن بالنسبة إلى ، فإنه يتبع ذلك أن h ( x ) هي SOS.${\displaystyle 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}}$$${\displaystyle 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}}.}$$${\displaystyle H+L(\alpha )\geq 0}$${\displaystyle \alpha =(1.18,-0.43,0.73,1.13,-0.37,0.57)}$

شكل مصفوفة F ( x ) (أي مصفوفة مدخلاتها عبارة عن أشكال) ذات بعد r ودرجة 2 m في متجه x الحقيقي ذي الأبعاد n يكون SOS إذا وفقط إذا كانت هناك أشكال مصفوفة من الدرجة m بحيث ${\displaystyle G_{1}(x),\ldots ,G_{k}(x)}$$${\displaystyle F(x)=\مجموع _{i=1}^{k}G_{i}(x)'G_{i}(x).}$$

إن تحديد ما إذا كانت مصفوفة F ( x ) هي SOS يعادل حل مشكلة تحسين محدبة. في الواقع، على غرار الحالة القياسية، يمكن كتابة أي F ( x ) وفقًا لـ SMR على النحو التالي حيث هو حاصل ضرب كرونيكر للمصفوفات، H هي أي مصفوفة متماثلة تلبي و هي معلمة خطية للفضاء الخطي $${\displaystyle F(x)=\left(x^{\{m\}}\otimes I_{r}\right)'\left(H+L(\alpha )\right)\left(x^{\{m\}}\otimes I_{r}\right)}$$${\displaystyle \otimes }$$${\displaystyle F(x)=\left(x^{\{m\}}\otimes I_{r}\right)'H\left(x^{\{m\}}\otimes I_{r}\right)}$$${\displaystyle L(\alpha )}$$${\displaystyle {\mathcal {L}}=\left\{L=L':~\left(x^{\{m\}}\otimes I_{r}\right)'L\left(x^{\{m\}}\otimes I_{r}\right)=0\right\}.}$$

يتم تحديد أبعاد المتجه بواسطة${\displaystyle \alpha }$$${\displaystyle \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 ) هي SOS إذا وفقط إذا كان هناك متجه بحيث ينطبق LMI التالي: ${\displaystyle \alpha }$$${\displaystyle H+L(\alpha )\geq 0.}$$

تم تقديم التعبير في ^[9] لتحديد ما إذا كان شكل المصفوفة هو SOS عبر LMI. ${\displaystyle F(x)=\left(x^{\{m\}}\otimes I_{r}\right)'\left(H+L(\alpha )\right)\left(x^{\{m\}}\otimes I_{r}\right)}$

فكر في الجبر الحر R ⟨ X ⟩ الناتج عن n حرف غير قابل للتبديل X = ( X ₁ , ..., X _n ) والمجهز بالانعكاس ^T ، بحيث يثبت ^T R و X ₁ , ..., X _n ويعكس الكلمات المكونة من X ₁ , ..., X _n . وبالقياس على الحالة التبديلية، فإن الحدوديات المتماثلة غير التبديلية f هي الحدوديات غير التبديلية من الشكل f = f ^T. عندما يتم تقييم أي مصفوفة حقيقية لأي بعد r × r عند متعددة حدودية غير تبديلية متماثلة f ينتج عنها مصفوفة شبه محددة موجبة ، يقال إن f موجبة للمصفوفة.

تكون الحدود غير التبادلية متعددة الحدود SOS إذا كانت هناك حدود غير تبادلية مثل ${\displaystyle h_{1},\ldots ,h_{k}}$$${\displaystyle f(X)=\sum _{i=1}^{k}h_{i}(X)^{T}h_{i}(X).}$$

من المثير للدهشة أنه في السيناريو غير التبادلي، تكون الحدود غير التبادلية SOS إذا وفقط إذا كانت موجبة للمصفوفة. ^[10] علاوة على ذلك، توجد خوارزميات متاحة لتحليل الحدود الموجبة للمصفوفة في مجموع مربعات الحدود غير التبادلية. ^[11]

• تحسين مجموع المربعات
• حدود موجبة
• مسألة هيلبرت السابعة عشر
• SOS-التحدب