تحسين مجموع المربعات

📅 آخر تحديث: ٢٩ يوليو ٢٠٢٦
✍️ نُشر في: ٢٩ يوليو ٢٠٢٦
📷 يحتوي على 80 صور
الموسوعة الحرة

برنامج تحسين مجموع المربعات هو مسألة تحسين ذات دالة تكلفة خطية وقيود تنص على أن تكون كثيرات حدود معينة مُنشأة من متغيرات القرار عبارة عن مجموع مربعات . عندما تكون الدرجة القصوى لكثيرات الحدود المعنية ثابتة، يُعرف تحسين مجموع المربعات أيضًا باسم تسلسل لاسير الهرمي لتقريبات البرمجة شبه المحددة .

طُبقت تقنيات تحسين مجموع المربعات في مجالات متنوعة، بما في ذلك نظرية التحكم (وخاصةً للبحث عن دوال ليابونوف متعددة الحدود للأنظمة الديناميكية الموصوفة بحقول متجهات متعددة الحدود)، والإحصاء، والتمويل، والتعلم الآلي . [ 1 ] [ 2 ] [ 3 ] [ 4 ]

خلفية

متعدد الحدودص{\displaystyle p}مجموع المربعات ( SOS ) إذا وُجدت كثيرات حدود{وأنا}أنا=1م{\displaystyle \{f_{i}\}_{i=1}^{m}}بحيثص=∑أنا=1موأنا2{\textstyle p=\sum _{i=1}^{m}f_{i}^{2}}. على سبيل المثال، ص=x2-4xy+7y2{\displaystyle p=x^{2}-4xy+7y^{2}} هو مجموع مربعات لأن ص=و12+و22{\displaystyle p=f_{1}^{2}+f_{2}^{2}} أين و1=(x-2y) و و2=3y.{\displaystyle f_{1}=(x-2y){\text{ and }}f_{2}={\sqrt {3}}y.} لاحظ أنه إذاص{\displaystyle p}إذا كان مجموع مربعاتص(x)≥0{\displaystyle p(x)\geq 0}للجميعx∈Rن{\displaystyle x\in \mathbb {R} ^{n}}تتوفر أوصاف تفصيلية لمجموع مربعات كثيرات الحدود . [ 5 ] [ 6 ] [ 7 ]

يمكن التعبير عن الأشكال التربيعية على النحو التالي:ص(x)=xتيسؤالx{\displaystyle p(x)=x^{T}Qx}أينسؤال{\displaystyle Q}هي مصفوفة متناظرة . وبالمثل، يمكن التعبير عن كثيرات الحدود من الدرجة  ≤  2d على النحو التالي :ص(x)=z(x)تيسؤالz(x)،{\displaystyle p(x)=z(x)^{\mathsf {T}}Qz(x),} حيث المتجهz{\displaystyle z}يحتوي على جميع أحاديات الحدود من الدرجة≤د{\displaystyle \leq d}يُعرف هذا باسم شكل مصفوفة غرام . ومن الحقائق المهمة أنص{\displaystyle p}تكون SOS إذا وفقط إذا وُجدت مصفوفة متناظرة وشبه موجبة.سؤال{\displaystyle Q}بحيثص(x)=z(x)تيسؤالz(x){\displaystyle p(x)=z(x)^{\mathsf {T}}Qz(x)}وهذا يوفر صلة بين كثيرات الحدود SOS والمصفوفات شبه المحددة الموجبة.

مشكلة التحسين

مسألة تحسين مجموع المربعات هي مسألة تحسين مخروطية بالنسبة لمخروط كثيرات حدود مجموع المربعات. وبشكل أكثر تحديدًا، بالنظر إلى متجهج∈Rن{\displaystyle c\in \mathbb {R} ^{n}}وكثيرات الحدودأك،ج{\displaystyle a_{k,j}}لك=1،...شمالs{\displaystyle k=1,\dots N_{s}}،ج=0،1،...،ن{\displaystyle j=0,1,\dots ,n}تُكتب مسألة تحسين مجموع المربعات على النحو التالي:

أقصىu∈Rنجتيuرهناً بـأك،0(x)+أك،1(x)u1+⋯+أك،ن(x)uن∈نداء استغاثة(ك=1،...،شمالs).{\displaystyle {\begin{aligned}{\underset {u\in \mathbb {R} ^{n}}{\text{maximize}}}\quad &c^{T}u\\{\text{subject to}}\quad &a_{k,0}(x)+a_{k,1}(x)u_{1}+\cdots +a_{k,n}(x)u_{n}\in {\text{SOS}}\quad (k=1,\ldots ,N_{s}).\end{aligned}}}

هنا، يرمز "SOS" إلى فئة كثيرات الحدود ذات مجموع المربعات (SOS). الكمياتu∈Rن{\displaystyle u\in \mathbb {R} ^{n}}هي متغيرات القرار. يمكن تحويل برامج SOS إلى برامج شبه محددة (SDPs) باستخدام ازدواجية برنامج SOS متعدد الحدود وتخفيف التحسين متعدد الحدود المقيد باستخدام المصفوفات شبه المحددة الموجبة ، انظر القسم التالي.

المسألة المزدوجة: التحسين متعدد الحدود المقيد

لنفترض مسألة تحسين غير خطية على النحو التالي: تقليلx∈Rنص(x)suبجهـجتتoأأنا(x)=0،أنا=1،...،م{\displaystyle {\begin{aligned}&{\underset {x\in \mathbb {R} ^{n}}{\operatorname {minimize} }}&&p(x)\\&\operatorname {subject\;to} &&a_{i}(x)=0,\quad i=1,\dots ,m\end{aligned}}}

أينص(x):Rن→R{\displaystyle p(x):\mathbb {R} ^{n}\to \mathbb {R} }هي متعددة حدود من الرتبة n، وكل منهاأأنا(x){\displaystyle a_{i}(x)}هي متعددة حدود من n متغيرًا من الدرجة 2d على الأكثر . يمكن إعادة كتابة نفس المسألة على النحو التالي:

أينx≤د{\textstyle x^{\leq d}}هونيا(د){\displaystyle n^{O(d)}}متجه ذو أبعاد n يحتوي على عنصر واحد لكل حد أحادي في x من الدرجة d على الأكثر ، بحيث يكون لكل مجموعة متعددةS⊂[ن]،|S|≤د،{\displaystyle S\subset [n],|S|\leq d,}xS=∏أنا∈Sxأنا{\textstyle x_{S}=\prod _{i\in S}x_{i}}،ج{\textstyle C}هي مصفوفة غرام p ، وأأنا{\textstyle A_{i}}هي مصفوفة غرام منأأنا{\displaystyle a_{i}}نتبنى الاتفاقية التيx∅=1{\displaystyle x_{\emptyset }=1}، بحيث يمكن تضمين المعامل الثابت في مصفوفة غرام لكثير الحدود.

هذه المسألة غير محدبة بشكل عام. يمكن محاولة تحويلها إلى مسألة محدبة باستخدام البرمجة شبه المحددة لاستبدال مصفوفة المتغيرات ذات الرتبة الواحدة.x≤د(x≤د)⊤{\displaystyle x^{\leq d}(x^{\leq d})^{\top }}بمصفوفة شبه محددة موجبةX{\displaystyle X}: نقوم بفهرسة كل حد أحادي الحجم على الأكثر2د{\displaystyle 2d}بواسطة مجموعة متعددةS{\displaystyle S}على الأكثر2د{\displaystyle 2d}المؤشرات،S⊂[ن]،|S|≤2د{\displaystyle S\subset [n],|S|\leq 2d}لكل حد أحادي من هذا القبيل، نقوم بإنشاء متغيرXS{\displaystyle X_{S}}في البرنامج، ونرتب المتغيراتXS{\displaystyle X_{S}}لتشكيل المصفوفةX∈R[ن]≤د×[ن]≤د{\textstyle X\in \mathbb {R} ^{[n]^{\leq d}\times [n]^{\leq d}}}، أينR[ن]≤د×[ن]≤د{\displaystyle \mathbb {R} ^{[n]^{\leq d}\times [n]^{\leq d}}}هي مجموعة المصفوفات الحقيقية التي يتم تحديد صفوفها وأعمدتها بمجموعات متعددة من العناصر منن{\displaystyle n}بحجم أقصىد{\displaystyle d}ثم نكتب البرنامج شبه المحدد التالي في المتغيراتXS{\displaystyle X_{S}}:

تقليلX∈R[ن]≤د×[ن]≤د⟨ج،X⟩suبجهـجتتoXيو،V=XS،تي،∀ يو،V،S،تي∈[ن]≤د،يو∪V=S∪تي⟨أأنا،X⟩=0،أنا=1،...،مX∅=1X⪰0{\displaystyle {\begin{aligned}&{\underset {X\in \mathbb {R} ^{[n]^{\leq d}\times [n]^{\leq d}}}{\operatorname {minimize} }}&&\langle C,X\rangle \\&\operatorname {subject\;to} &&X_{U,V}=X_{S,T},\quad \forall \ U,V,S,T\in [n]^{\leq d},U\cup V=S\cup T\\&&&\langle A_{i},X\rangle =0,\quad i=1,\dots ,m\\&&&X_{\emptyset }=1\\&&&X\succeq 0\end{aligned}}}

حيث C هي مصفوفة غرام من p وأأنا{\textstyle A_{i}}هي مصفوفة غرام منأأنا{\textstyle a_{i}}يضمن القيد الأول أن تكون قيمة الحد الأحادي الذي يظهر عدة مرات داخل المصفوفة متساوية في جميع أنحاء المصفوفة، ويتم إضافته لجعل المصفوفةX{\displaystyle X}احترام نفس التناظرات الموجودة في المصفوفةx≤د(x≤د)⊤{\displaystyle x^{\leq d}(x^{\leq d})^{\top }}.

الازدواجية

يمكن للمرء أن يأخذ البرنامج الثنائي للبرنامج شبه المحدد أعلاه ويحصل على البرنامج التالي:

تقليلy∈Rم′y0suبجهـجتتoج-y0هـ∅-∑أنا∈[م]yأناأأنا-∑S∪تي=يو∪VyS،تي،يو،V(هـS،تي-هـيو،V)⪰0{\displaystyle {\begin{aligned}&{\underset {y\in \mathbb {R} ^{m'}}{\operatorname {minimize} }}&&y_{0}\\&\operatorname {subject\;to} &&C-y_{0}e_{\emptyset }-\sum _{i\in [m]}y_{i}A_{i}-\sum _{S\cup T=U\cup V}y_{S,T,U,V}(e_{S,T}-e_{U,V})\succeq 0\end{aligned}}}

لدينا متغيرy0{\displaystyle y_{0}}بما يتوافق مع القيد⟨هـ∅،X⟩=1{\displaystyle \langle e_{\emptyset },X\rangle =1}(أينهـ∅{\displaystyle e_{\emptyset }}هي المصفوفة التي تحتوي على جميع عناصرها على أصفار باستثناء العنصر المفهرس بواسطة(∅،∅){\displaystyle (\varnothing ,\varnothing )}), متغير حقيقيyأنا{\displaystyle y_{i}}لكل قيد متعدد الحدود⟨X،أأنا⟩=0s.ت.أنا∈[م]،{\displaystyle \langle X,A_{i}\rangle =0\quad s.t.i\in [m],}ولكل مجموعة من المجموعات المتعددةS،تي،يو،V⊂[ن]،|S|،|تي|،|يو|،|V|≤د،S∪تي=يو∪V{\displaystyle S,T,U,V\subset [n],|S|,|T|,|U|,|V|\leq d,S\cup T=U\cup V}لدينا متغير مزدوجyS،تي،يو،V{\displaystyle y_{S,T,U,V}}بالنسبة لقيد التناظر⟨X،هـS،تي-هـيو،V⟩=0{\displaystyle \langle X,e_{S,T}-e_{U,V}\rangle =0}يضمن قيد شبه التحديد الإيجابي ما يلي:ص(x)-y0{\displaystyle p(x)-y_{0}}هو مجموع مربعات كثيرات الحدود علىأ⊂Rن{\displaystyle A\subset \mathbb {R} ^{n}}: من خلال توصيف المصفوفات شبه الموجبة، لأي مصفوفة شبه موجبةسؤال∈Rم×م{\textstyle Q\in \mathbb {R} ^{m\times m}}يمكننا أن نكتبسؤال=∑أنا∈[م]وأناوأنا⊤{\textstyle Q=\sum _{i\in [m]}f_{i}f_{i}^{\top }}للمتجهاتوأنا∈Rم{\textstyle f_{i}\in \mathbb {R} ^{m}}وبالتالي بالنسبة لأيx∈أ⊂Rن{\textstyle x\in A\subset \mathbb {R} ^{n}}، ص(x)-y0=ص(x)-y0-∑أنا∈[م′]yأناأأنا(x)منذ x∈أ=(x≤د)⊤(ج-y0هـ∅-∑أنا∈[م′]yأناأأنا-∑S∪تي=يو∪VyS،تي،يو،V(هـS،تي-هـيو،V))x≤دبالتناظر=(x≤د)⊤(∑أناوأناوأنا⊤)x≤د=∑أنا⟨x≤د،وأنا⟩2=∑أناوأنا(x)2،{\displaystyle {\begin{aligned}p(x)-y_{0}&=p(x)-y_{0}-\sum _{i\in [m']}y_{i}a_{i}(x)\qquad {\text{since }}x\in A\\&=(x^{\leq d})^{\top }\left(C-y_{0}e_{\emptyset }-\sum _{i\in [m']}y_{i}A_{i}-\sum _{S\cup T=U\cup V}y_{S,T,U,V}(e_{S,T}-e_{U,V})\right)x^{\leq d}\qquad {\text{by symmetry}}\\&=(x^{\leq d})^{\top }\left(\sum _{i}f_{i}f_{i}^{\top }\right)x^{\leq d}\\&=\sum _{i}\langle x^{\leq d},f_{i}\rangle ^{2}\\&=\sum _{i}f_{i}(x)^{2},\end{aligned}}}

حيث حددنا المتجهاتوأنا{\textstyle f_{i}}بمعاملات متعددة حدود من الدرجة على الأكثرد{\displaystyle d}وهذا يُعطي برهانًا باستخدام مجموع المربعات على أن القيمةص(x)≥y0{\textstyle p(x)\geq y_{0}}زيادةأ⊂Rن{\displaystyle A\subset \mathbb {R} ^{n}}.

ويمكن تطبيق ما سبق على المناطق أيضاًأ⊂Rن{\displaystyle A\subset \mathbb {R} ^{n}}تُعرَّف بواسطة متباينات متعددة الحدود.

التسلسل الهرمي لمجموع المربعات

تُعرف التسلسلات الهرمية لمجموع المربعات (SOS hierarchy)، والمعروفة أيضًا باسم تسلسلات لاسير الهرمية، بأنها تسلسلات هرمية من التقريبات المحدبة ذات قوة متزايدة وتكلفة حسابية متزايدة. لكل عدد طبيعيد∈شمال{\textstyle d\in \mathbb {N} }يُعرف الاسترخاء المحدب المقابل باسمد{\textstyle d}المستوى th أود{\textstyle d}الجولة رقم - من التسلسل الهرمي لمنظمة SOS.1{\textstyle 1}الجولة الأولى، عندماد=1{\textstyle d=1}، يتوافق مع برنامج شبه محدد أساسي ، أو مع تحسين مجموع المربعات على كثيرات الحدود من الدرجة على الأكثر2{\displaystyle 2}لتعزيز البرنامج المحدب الأساسي عند1{\textstyle 1}المستوى الأول من التسلسل الهرمي إلىد{\textstyle d}في المستوى -th، تُضاف متغيرات وقيود إضافية إلى البرنامج لكي يأخذ البرنامج في الاعتبار كثيرات الحدود من الدرجة d على الأكثر2د{\displaystyle 2d}.

يستمد التسلسل الهرمي SOS اسمه من حقيقة أن قيمة دالة الهدف عندد{\textstyle d}المستوى رقم n محدود ببرهان مجموع المربعات باستخدام كثيرات حدود من الدرجة n على الأكثر2د{\textstyle 2d}عن طريق الثنائية (انظر "الثنائية" أعلاه). وبالتالي، فإن أي برهان مجموع المربعات الذي يستخدم كثيرات حدود من الدرجة على الأكثر2د{\textstyle 2d}يمكن استخدامها لتقييد القيمة المستهدفة، مما يسمح بإثبات الضمانات المتعلقة بمدى إحكام الاسترخاء.

بالإضافة إلى نظرية بيرغ، يُشير هذا إلى أنه عند إجراء عدد كافٍ من الجولات، يصبح التقريب دقيقًا للغاية على أي فترة محددة. وتنص نتيجة بيرغ [ 8 ] [ 9 ] على أنه يمكن تقريب كل متعددة حدود حقيقية غير سالبة ضمن فترة محدودة بدقةε{\textstyle \varepsilon }على تلك الفترة بمجموع مربعات كثيرات الحدود الحقيقية ذات درجة عالية بما فيه الكفاية، وبالتالي إذايابج(x){\textstyle OBJ(x)}هي قيمة الهدف متعددة الحدود كدالة للنقطةx{\textstyle x}، إذا كانت المتباينةج+ε-يابج(x)≥0{\textstyle c+\varepsilon -OBJ(x)\geq 0}ينطبق على الجميعx{\textstyle x}في المنطقة محل الاهتمام ، يجب أن يكون هناك برهان مجموع المربعات لهذه الحقيقة. اختيارج{\textstyle c}لكي تكون القيمة الدنيا للدالة الهدف على المنطقة الممكنة ، نحصل على النتيجة.

التكلفة الحسابية

عند تحسين دالة فين{\textstyle n}المتغيرات،د{\textstyle d}يمكن كتابة المستوى رقم n من التسلسل الهرمي كبرنامج شبه محدد علىنيا(د){\textstyle n^{O(d)}}المتغيرات، ويمكن حلها في وقتنيا(د){\textstyle n^{O(d)}}باستخدام طريقة القطع الناقص .

تحسين مجموع مربعات هيرميت

متعددة الحدود الهرميتية هي دالة لـن{\displaystyle n}المتغيرات المركبةz1،...،zن{\displaystyle z_{1},\dots ,z_{n}}ومقترناتهاz1*،...،zن*{\displaystyle z_{1}^{*},\dots ,z_{n}^{*}}والتي تأخذ قيمًا حقيقية فقط لجميع الأعداد المركبةz{\displaystyle z}يمكن أيضًا النظر في استرخاءات البرمجة شبه المحددة القائمة على مجموع المربعات الهيرميتية (HSOS).ز1*ز1+⋯+زك*زك{\displaystyle g_{1}^{*}g_{1}+\dots +g_{k}^{*}g_{k}}حيث كلزأنا{\displaystyle g_{i}}هي متعددة حدود في المتغيرات فقطz1،...،zن{\displaystyle z_{1},\dots ,z_{n}}وليس مرافقاتها. تتقارب البرامج شبه المحددة الناتجة إلى الحل الأمثل الحقيقي بشكل تقاربي في جميع الحالات ذات السلوك الجيد، وتختزل إلى حساب أكبر القيم الذاتية للمصفوفات المعطاة صراحةً، كما لاحظ بوتينار لأول مرة. [ 10 ]

أدوات البرمجيات

انظر أيضاً

مراجع

  1. ↑ مجموع المربعات  : النظرية والتطبيقات  : دورة قصيرة من الجمعية الأمريكية للرياضيات، مجموع المربعات  : النظرية والتطبيقات، 14-15 يناير 2019، بالتيمور، ماريلاند . باريلو، بابلو أ.؛ توماس، ريخا ر. بروفيدنس، رود آيلاند: الجمعية الأمريكية للرياضيات. 2020. ISBN 978-1-4704-5025-0. OCLC 1157604983 . {{cite book}}صيانة CS1: أخرى ( رابط )
  2. ↑ تان، و.، باكارد، أ.، 2004. " البحث عن دوال ليابونوف للتحكم باستخدام برمجة مجموع المربعات ". في: مؤتمر أليرتون حول الاتصالات والتحكم والحوسبة . الصفحات 210-219.
  3. ↑ تان، و.، توبكو، يو.، سيلر، ب.، بالاس، ج.، باكارد، أ.، 2008. تحليل إمكانية الوصول والكسب المحلي بمساعدة المحاكاة للأنظمة الديناميكية غير الخطية . في: وقائع مؤتمر IEEE للتحكم واتخاذ القرارات. الصفحات 4097-4102.
  4. ↑ أ. تشاكرابورتي، ب. سيلر، و ج. بالاس، " حساسية وحدات التحكم في الطيران F/A-18 لوضع الورقة الساقطة: تحليل غير خطي "، مجلة AIAA للتوجيه والتحكم والديناميكيات، المجلد 34 العدد 1 (2011)، الصفحات 73-85.
  5. ↑ باريلو، ب.، (2000) البرامج شبه المحددة المهيكلة وطرق الهندسة شبه الجبرية في المتانة والتحسين . أطروحة دكتوراه، معهد كاليفورنيا للتكنولوجيا.
  6. ↑ باريلو، ب. (2003) " استرخاءات البرمجة شبه المحددة للمسائل شبه الجبرية ". البرمجة الرياضية ، السلسلة ب 96 (2)، 293-320.
  7. ↑ لاسير، ج. (2001) " التحسين العالمي باستخدام كثيرات الحدود ومسألة العزوم ". مجلة SIAM للتحسين ، 11 (3)، 796-817.
  8. ↑ بيرغ، كريستيان (1987). "مسألة العزوم متعددة الأبعاد وشبه المجموعات" . في: لاندو، هنري ج. (محرر). العزوم في الرياضيات . وقائع ندوات في الرياضيات التطبيقية. المجلد 37. الصفحات 110-124 . doi : 10.1090/psapm/037/921086 . ISBN   9780821801147.
  9. ↑ لاسير، ج. (2007-01-01). "تقريب مجموع المربعات لكثيرات الحدود غير السالبة" . مجلة SIAM Review . 49 (4): 651–669 . arXiv : math/0412398 . Bibcode : 2007SIAMR..49..651L . doi : 10.1137/070693709 . ISSN 0036-1445 . 
  10. ↑ بوتينار، ميهاي (2012). "الفصل 9: مجاميع المربعات الهرميتية: القديم والجديد". التحسين شبه المحدد والهندسة الجبرية المحدبة . فيلادلفيا، بنسلفانيا: جمعية الرياضيات الصناعية والتطبيقية. ص 407-446. doi : 10.1137/1.9781611972290.ch9 . ISBN  978-1-61197-228-3.