ملخص تقني: مجموع المربعات التفريعي (Disjunctive Sum of Squares)

بيان المشكلة

تتناول الورقة البحثية المشكلة الجوهرية المتمثلة في إثبات عدم سلبية كثيرات الحدود. فبينما تكون كثيرة الحدود $p$ غير سالبة إذا كان $p(x) \geq 0$ لجميع قيم $x \in \mathbb{R}^n$، فإن تحديد هذه الخاصية يعد عموماً مسألة صعبة حسابياً (NP-hard). إن النهج القياسي، وهو طريقة مجموع المربعات (SOS)، يثبت عدم السلبية عبر التعبير عن $p$ كمتطابقة جبرية واحدة $p(x) = \sum q_i^2(x)$. ومع ذلك، ليست كل كثيرات الحدود غير السالبة هي بالضرورة مجموع مربعات (SOS) (وهي حقيقة أثبتها هيلبرت)، وإثبات عدم السلبية لتلك التي لا تندرج تحت هذا التصنيف يتطلب عادةً ضرب $p$ في كثيرة حدود SOS ذات درجة عالية (على سبيل المثال، عبر حل أرتين لمسألة هيلبرت السابعة عشرة). يؤدي هذا إلى هويات جبرية ذات درجات أعلى بكثير من درجة كثيرة الحدود الأصلية، مما ينتج عنه برامج تحليلية شبه محددة (SDPs) تنمو بشكل أسّي في الحجم وتصبح غير قابلة للحل حاسوبياً.

السؤال المركزي الذي يحفز هذا البحث هو: هل يمكن تقليل تعقيد إثبات عدم سلبية كثيرة الحدود القائم على طريقة SOS عبر إنشاء عدة هويات جبرية بدلاً من هوية واحدة؟

المنهجية

يقدم المؤلفون مفهوم مجموع المربعات التفريعي (Disjunctive Sum of Squares). فبدلاً من الهوية العالمية الواحدة، يتم إثبات عدم السلبية عبر مجموعة من الهويات الجبرية، كل منها صالح في منطقة فرعية محددة من النطاق. هذه المناطق الفرعية تشكل تقسيماً (أو غطاءً) للفضاء، ويتم تعريفها بواسطة تفريع جبري (Algebraic Disjunction).

التعريفات الجوهرية

1. التفريع الجبري: مجموعة من كثيرات الحدود $\mathcal{D} = \{\{q_{k,j}\}\}$ بحيث يغطي اتحاد المناطق $\Omega_k = \{x \mid q_{k,j}(x) \geq 0, \forall j\}$ الفضاء $\mathbb{R}^n$.
2. إثبات مجموع المربعات التفريعي: تُعتبر كثيرة الحدود $p$ "مجموع مربعات تفريعي" بالنسبة لـ $\mathcal{D}$ إذا كان لكل منطقة $\Omega_k$ توجد كثيرات حدود SOS، وهي $s_{k,j}$، بحيث:
   $$p(x) = s_{k,0}(x) + \sum_{j=1}^{n_k} s_{k,j}(x)q_{k,j}(x) \quad \text{لكل } x \in \Omega_k.$$
   ومن الأهمية بمكان أن درجة كثيرات الحدود $s_{k,j}$ يمكن إبقاؤها منخفضة (تحديداً، محصورة في درجة $p$)، على عكس إثباتات SOS العالمية حيث يجب أن تزداد الدرجة غالباً.

الإطار النظري

تؤسس الورقة لنتيجتين نظريتين رئيسيتين، تُسميان مبرهنات الموجبية التفريقية (Disjunctive Positivstellensätze):

1. مبرهنة الموجبية التفريقية القائمة على الـ SDP (المبرهنة 1):
   لأي صيغة موجبة تماماً من الدرجة $d$، يوجد عائلة صريحة من التفريعات الجبرية (يتم إنشاؤها عبر الأغطية الكروية) بحيث تقبل $p$ إثبات مجموع مربعات تفريعي حيث تكون درجة مضاعفات الـ SOS هي $d$ كحد أقصى. وهذا يسمح بإنشاء تسلسل هرمي من الحدود الدنيا لتقليل كثيرات الحدود فوق الكرة الوحدة باستخدام الـ SDPs بحجم ثابت (مستقل عن مستوى التسلسل الهرمي).

2. مبرهنة الموجبية التفريقية الخالية من التحسين (المبرهنة 8):
   نتيجة أقوى توضح أنه لأي صيغة موجبة تماماً، توجد عائلة من التفريعات الوتدية (المخاريط متعددة الوجوه) بحيث يمكن إثبات عدم سلبية $p$ ببساطة عبر التحقق من أن معاملاتها غير سالبة بعد تغيير خطي للإحداثيات داخل كل مخروط. هذا النهج لا يتطلب برنامج تحسين (فقط برمجة خطية أو فحص مباشر للمعاملات) ولكنه قد يتطلب عدداً أكبر من المناطق مقارنة بنهج الـ SDP.

الإطار الخوارزمي

يقترح المؤلفون إطار عمل الفرع والحد (Branch-and-Bound) المكاني (SBB) للبحث تكيفياً عن هذه الإثباتات التفريقية. بدلاً من تقسيم الفضاء بشكل موحد (كما في البناءات النظرية)، تقوم الخوارزمية بما يلي:

• الحفاظ على شجرة من المناطق الفرعية (المخاريط الوتدية).
• حساب الحدود الدنيا عبر الـ SDPs (أو الفحوص الخطية) على كل منطقة فرعية.
• حساب الحدود العليا عبر الانحدار المتدرج المسقط (Projected Gradient Descent).
• التقسيم (Branching) عبر تنصيف أطول ضلع للمنطقة ذات الحد الأدنى الأصغر.
  يهدف هذا النهج التكيفي إلى إيجاد شهادات تتطلب عدداً أقل من المناطق مقارنة بالتقسيم الموحد.

المساهمات والنتائج الرئيسية

1. الضمانات النظرية

• الدرجة الثابتة: تثبت الورقة أن إثباتات مجموع المربعات التفريقية ذات الدرجة المنخفضة موجودة دائماً. درجة كثيرات حدود الـ SOS في الإثبات لا تحتاج للنمو مع مستوى التسلسل الهرمي؛ بل يمكن تثبيتها عند درجة كثيرة الحدود الأصلية.
• التقارب: يبني المؤلفون تسلسلاً هرمياً من الـ SDPs ذات قيود ثابتة الحجم يتقارب نحو الحد الأدنى العالمي لكثيرة حدود متجانسة فوق الكرة الوحدة. وقد وضعوا معدل تقارب قدره $O(1/m)$، حيث ترتبط $m$ بدقة التقسيم المكاني.
• شهادات خالية من التحسين: توفر مبرهنة الموجبية الثانية طريقة لإثبات عدم السلبية دون حل الـ SDPs، بالاعتماد على التحويلات الخطية وفحص عدم سلبية المعاملات.

2. التطبيق على التحسين المقيد

• تحسين كثيرات الحدود: من خلال دمج النهج التفريعي مع تقنية اختزال من [2]، يبني المؤلفون تسلسلاً هرمياً متقارباً من الحدود الدنيا لمسائل تحسين كثيرات الحدود العامة (POPs) فوق مجموعات شبه جبرية أساسية متراصة.
• البرمجة المتوافقة (Copositive Programming): تم تخصيص الطريقة لإثبات توافق المصفوفات (التحقق من أن $x^T Q x \geq 0$ لـ $x \geq 0$). يعرّف المؤلفون شرط "Disjunctive P+N"، حيث يتم إثبات توافق المصفوفة إذا كان من الممكن، في كل منطقة وتدية فرعية من المتجه المتعامد غير السالب، تفكيكها إلى مصفوفة موجبة محددة ومصفوفة غير سالبة. ينتج عن ذلك تسلسل هرمي كامل حيث يظل حجم قيد الـ SDP ثابتاً ($n \times n$)، على عكس التسلسلات الهرمية الحالية حيث ينمو حجم القيد بشكل متعدد الحدود مع المستوى.

3. التجارب العددية

يعرض المؤلفون تجارب عددية على:

• كثيرات الحدود غير الـ SOS: نجحت الخوارزميات في إثبات عدم سلبية كثيرات حدود كلاسيكية غير SOS (مثل Motzkin، وRobinson، وChoi-Lam، وDelzell) باستخدام عدد صغير من المناطق (غالباً أقل من 20) عبر إطار عمل SBB.
• البرامج المتوافقة: حلت الخوارزمية مسائل تربيعية غير متصلة (nonconvex) وحسبت عدد الكليكات (clique number) للرسوم البيانية (عبر مبرهنة Motzkin-Straus) في نماذج عشوائية.
• الأداء: تشير النتائج إلى أن النهج التفريعي يمكنه إثبات عدم السلبية وحل مسائل التحسين بعدد أقل بكثير من المناطق مقارنة بالتقسيم الموحد، كما تظل قيود الـ SDP قابلة للإدارة من حيث الحجم.

الأهمية والادعاءات

تدعي الورقة أن نهج مجموع المربعات التفريعي يقدم بديلاً قابلاً للتطبيق للتسلسلات الهرمية التقليدية لـ SOS عبر فصل تعقيد الإثبات (درجة كثيرات حدود الـ SOS) عن عدد الهويات الجبرية المستخدمة.

• الكفاءة الحسابية: من خلال إبقاء درجة كثيرات حدود الـ SOS منخفضة وثابتة، يظل حجم الـ SDPs الأساسية ثابتاً طوال التسلسل الهرمي، مما يتجنب "لعنة الأبعاد" المرتبطة بزيادة درجات كثيرات الحدود في طرق SOS القياسية.
• المرونة: يدعم إطار العمل كلاً من البحث القائم على الـ SDP (للحصول على حدود أدق بعدد أقل من المناطق) والبحث الخالي من التحسين (للحصول على شهادات أسرع، وإن كانت أقل دقة).
• الاكتمال: يثبت المؤلفون أن هذا النهج كامل؛ فبالنسبة لأي كثيرة حدود موجبة تماماً (أو مصفوفة متوافقة تماماً)، توجد شهادة ضمن إطار عملهم.

تختتم الورقة بالإشارة إلى أنه بينما تستخدم البناءات النظرية تقسيمات موحدة، فإن خوارزمية SBB العملية تقوم بتقسيم الفضاء تكيفياً، مما يشير إلى أن التفريعات الخاصة بكل حالة قد تقلل أكثر من عدد المناطق المطلوبة. يفتح هذا العمل آفاقاً لدمج الـ SOS التفريعي مع استغلال التشتت (sparsity) والتماثل، واستكشاف جانب العزم المزدوج لهذا الإطار.