Hongbo Sun يقترح خوارزمية للمتباينات التغايرية: 6400 مسألة ودقة 1e-5

قدّم Hongbo Sun خوارزمية عامة للمتباينات التغايرية (VI) لا تحتاج إلى رتابة التطبيق. تعمل الطريقة مع تطبيقات مستمرة اعتباطية على نطاقات متعددة الوجوه، وتضمن تقاربًا خطيًا عامًا. هذا التقارب دقيق للحلول غير المنحلة، أما للحلول المنحلة فيمكن بلوغ أي دقة محددة مسبقًا. وفي 6400 مسألة عشوائية بأبعاد تصل إلى 1024، انخفضت الفجوة إلى ما دون 1e-5 في كل حالة.

لماذا ما زالت المتباينات التغايرية تُعدّ مسألة صعبة

تتطلب المتباينة التغايرية إيجاد نقطة في المجموعة الممكنة لا يعطي فيها حقل الاتجاهات تحسنًا في أي اتجاه ممكن. وتندرج تحت هذه الصيغة مسائل الأمثلة ومسائل التكامل والمسائل السرجية وتوازنات الألعاب. ولهذا تظهر VI باستمرار حيث يحسّن عدة مشاركين أهدافًا مختلفة في وقت واحد، كما في صيغ minimax والأنظمة متعددة الوكلاء.

تكمن المشكلة في أن ضمانات معظم الطرق الكلاسيكية تعتمد على الرتابة أو شروط قريبة منها. وبدونها تبدأ الخوارزميات بالدوران في حلقات أو بالتباعد. وفي الملخص يصف المؤلف نفسه تطوير خوارزميات عامة بضمانات تقارب عامة بأنه مسألة قديمة لم تُحل بعد.

الحزمة الليفية بدل التعامل اليدوي مع الشذوذ

تقوم الطريقة على path-following: يُبحث عن الحل بتتبع مسار مستمر ينطلق من نقطة بداية بسيطة. ونقطة الضعف في هذا النهج معروفة: ففي النقاط الشاذة تنهار الضمانات، وقد يصل المسار إلى طريق مسدود.

يحوّل Sun أولًا VI العامة إلى VI ملساء على المبسّط. ثم يصف مجموعة حلول نظام KKT ذي النقطة الثابتة بوصفها حزمة ليفية فوق المبسّط، ويسميها «fixed-point bundle». وتفصل هندسة الحزمة بين نوعين من الحركة: على القاعدة وعلى الألياف. وبفضل ذلك تتسع خطة واحدة لثلاثة أمور تُحَلّ عادة كلٌّ على حدة:

• اختيار نقطة البداية؛
• الحركة نفسها على طول المسار؛
• تجاوز النقاط الشاذة.

في النقطة الشاذة تنتقل الخوارزمية ببساطة على طول الليف إلى نقطة غير منحلة وتواصل الطريق من هناك.

ما الذي أظهرته التجارب

أُجري الاختبار على مسائل مولَّدة عشوائيًا. أبرز المعطيات:

• عدد الحالات: 6400؛
• أقصى بُعد: 1024؛
• الدقة المحققة: فجوة دون 1e-5 في جميع الحالات؛
• التقارب للحلول غير المنحلة: خطي عام ودقيق؛
• التقارب للحلول المنحلة: خطي عام حتى أي دقة محددة مسبقًا؛
• افتراضات الرتابة أو الخصائص المشابهة: غير مطلوبة؛
• مجال التعريف: متعددات الوجوه التي تُختزل إلى مبسّط؛
• الكود والبيانات: github.com/shb20tsinghua/FiberBundle_VI؛
• الورقة اللاحقة: arXiv:2609.16158، حيث وُسّع الإطار ليشمل جداءات المبسّطات لحساب توازنات ناش.

ويستحق مؤشر «في كل حالة» الانتباه. فبالنسبة إلى خوارزمية بلا افتراضات بنيوية، يكتسب غياب الإخفاقات على هذا العدد من المسائل العشوائية أهمية عملية تفوق أهمية السرعة على الأمثلة المريحة.

أين يفيد هذا وما الذي يجب فحصه

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

المستودع مفتوح، لذا فإن أول ما ينبغي للممارسين فعله هو تشغيل الطريقة على مسائلهم المهيكلة الخاصة. تُظهر الحالات العشوائية الاستقرار جيدًا، لكنها لا تغني عن الاختبار على بيانات حقيقية تكون لتطبيقاتها بنيتها الخاصة. كما ينبغي فحص كيف تنمو كلفة الخطوة عند أبعاد تتجاوز 1024، وكيف تتصرف الخوارزمية عند متطلبات دقة عالية جدًا في الحلول المنحلة. أما التطوير اللاحق فقد حُدّد بالفعل: التوسعة إلى جداءات المبسّطات ستفتح الطريق إلى حساب توازنات ناش في الألعاب متعددة المشاركين.