Over-Relaxed Projected-Forward Iterations for Cocoercive Variational Inequalities: Active-Face Spectral Tuning

ملخص تقني: التكرارات الأمامية المفرطة الاسترخاء للمتراجحات المتغيرة ذات التماسك (Cocoercive Variational Inequalities)

بيان المشكلة
تتناول الورقة البحثية مشكلة المتراجحة المتغيرة (VI): ابحث عن $p \in X$ بحيث يكون $\langle f(p), x - p \rangle \geq 0$ لكل $x \in X$، حيث $X$ هي مجموعة محدبة مغلقة غير فارغة في فضاء هيلبرت حقيقي، و $f$ مؤثر ذو تماسك (cocoercive operator). ينصب التركيز على التكرار الأمامي المسقط (المكافئ لتقسيم الأمام-الخلف للمحتوى المخروطي) المعرف عبر خريطة النقطة الثابتة $G_\gamma = P_X(I - \gamma f)$.

بينما ثبت عالمياً التقارب العالمي للتكرارات المسترخية $x_{n+1} = x_n + \lambda_n(G_\gamma x_n - x_n)$ ضمن فاصل متوسط محدد، فإن النظريات الحالية لا تحدد معلم الاسترخاء الأمثل $\lambda$ بمجرد تحديد القيود النشطة ("الوجه النشط" - active face). تبحث الورقة في كيفية اختيار $\lambda$ لتقليل نصف قطر الطيف المحلي بعد استقرار وجه الإسقاط، وتحديداً للقيود الصندوقية (box constraints).

المنهجية
يحلل المؤلفون السلوك التقاربي للتكرار تحت فرضية التكامل الصارم (strict complementarity) والقابلية للاشتقاق المحلي.

1. تحديد الوجه النهائي: تحت شرط التكامل الصارم، تحدد الخوارية المجموعة النشطة (المتغيرات عند الحدود الدنيا/العليا) والمجموعة الحرة (المتغيرات داخل الحدود تماماً) في زمن محدد. بمجرد تحديدها، يعمل مؤثر الإسقاط $P_X$ كقناع ثابت للمتغيرات النشطة وكالمتطابقة للمتغيرات الحرة.
2. الخطيّة المحلية: تشتق الورقة المشتقة الدقيقة للخريطة المسترخية $R_{\gamma, \lambda}(x) = (1-\lambda)x + \lambda P_X(x - \gamma f(x))$ عند النقطة $p$. بالنسبة للقيود الصندوقية، تأخذ هذه المشتقة $M_{\gamma, \lambda}$ شكلاً مثلثياً كتلياً:
   • الكتلة النشطة: تمتلك قيمًا ذاتية تساوي $|1 - \lambda|$.
   • الكتلة الحرة: تعتمد على جاكوبي $f$ المقيد بالمتغيرات الحرة ($J_{FF}$). إذا كان $J_{FF}$ متماثلاً وموجباً محدداً بقيم ذاتية $\theta_j$، فإن القيم الذاتية للكتلة الحرة هي $|1 - \lambda \gamma \theta_j|$.
3. تقليل الطيف: يتم التحكم في معدل التقارب المحلي بواسطة نصف قطر الطيف $\rho(M_{\gamma, \lambda})$. يصيغ المؤلفون مسألة "مينيمكس" (minimax) قياسية لتقليل الحد الأقصى $\max(|1-\lambda|, \max_j |1 - \lambda \gamma \theta_j|)$.
4. الاختيار المحمي: لضمان التقارب العالمي مع استغلال السرعة المحلية، تقترح الورقة خوارية تكيفية (الخوارية 1). تقوم هذه الخوارية بـ:
   • مراقبة نمط الوجه النشط.
     // قفل النمط بمجرد استقراره لعدد $K$ من التكرارات.
   • تقدير القيم الطيفية القصوى للكتلة الحرة.
   • حساب $\lambda^*_{loc}$ الأمثل وقصّه (clipping) ضمن فاصل المتوسط العالمي $[ \lambda_{min}, 1/\eta_\gamma - \epsilon ]$ لضمان السلامة العالمية حتى لو كان تحديد الوجه سابقاً لأوانه.

المساهمات الرئيسية
تقدم الورقة خمس مساهمات محددة:

1. الأساس العالمي: تثبت شهادة تقارب خطي عالمي حادة لخريطة الإسقاط الأمامي المسترخية تحت شرط الرتابة القوية والتماسك، لتكون بمثابة مرجع للتحليل المحلي.
2. اشتقاق ما بعد التحديد: تشتق المشتقة الدقيقة للخريطة المسترخية بعد التحديد النهائي للوجه للمؤثرات من الفئة $C^1$، مما يظهر البنية المثلثية الكتلوية التي تفصل بين الديناميكيات النشطة والحرة.
3. الاسترخاء الأمثل بصيغة مغلقة: بالنسبة للقيود الصندوقية مع جاكوبي حر متماثل وموجب محدد، يشتق المؤلفون مُقلل نصف قطر الطيف المحلي بصيغة قياسية:
   $$\lambda^*_{loc} = \frac{2}{a_\gamma + b_\gamma}$$
   حيث $a_\gamma$ و $b_\gamma$ هما الحد الأدنى والأقصى للمجموعة $\{1\} \cup \{\gamma \theta_j\}$. ويذكرون صراحةً شرط الاسترخاء المفرط الحقيقي ($\lambda^*_{loc} > 1$) وهو $a_\gamma + b_\gamma < 2$.
4. توصيف الضبط المشترك: توضح الورقة الزوج الأمثل المشترك $(\gamma, \lambda)$. وتجد نتيجة حاسمة وهي أنه إذا أمكن إعادة ضبط الخطوة الأمامية $\gamma$ بحرية بعد تحديد الوجه، فإن الخيار غير المسترخى ($\lambda=1$) مع $\gamma$ أمثل هو بالفعل أمثل محلياً. وبالتالي، فإن الاسترخاء الخارجي يكون أكثر قيمة عندما تكون $\gamma$ ثابتة، أو متحفظة، أو مقيدة عالمياً.
5. المحدد التكيفي المحمي: تُقترح خوارية عملية تقوم ديناميكياً بقفل الوجه النشط، وتقدير المعلمات الطيفية، وقص معلم الاسترخاء ضمن الفاصل الآمن عالمياً، مما يضمن عدم المساس بالتقارب العالمي أبداً.

النتائج
تؤكد التجارب العددية على اختبارات مرجعية أفينية كثيفة مكونة من 120 بُعداً ومشكلة غير خطية مكونة من 80 بُعداً النتائج النظرية:

• الخطوة الأمامية المقيدة: في اختبار مرجعي حيث ينتهك $\gamma$ الأمثل محلياً الحدود العالمية، قلل الاسترخاء المفرط التكيفي (مع $\gamma$ ثابتة) عدد التكرارات بنسبة تقارب 33% مقارنة بالطريقة غير المسترخية.
• الخطوة الأمامية القابلة لإعادة الضبط: في اختبار غير خطي حيث كان $\gamma$ الأمثل مقبولاً عالمياً، تفوق إعادة ضبط $\gamma$ (مع $\lambda=1$) على الاسترخاء المفرط باستخدام $\gamma$ متحفظة ثابتة.
• السلامة: نجحت آلية إعادة ضبط النمط في التعامل مع حالات التحديد الخاطئ العابر للوجه دون تدمير التقارب العالمي، حيث كان معلم الاسترخاء يُقص دائماً إلى الفاصل الآمن.

الأهمية والادعاءات
تضع الورقة مساهمتها بتواضع ليس كبديل لتقنيات تقدير الأداء العالمي أو كخوارزمية تسريع عامة، بل كـ قاعدة تحليلية خاصة بآلية محددة.

• النطاق: تنطبق النتائج تحديداً على المتراجحات المتغيرة ذات القيود الصندوقية مع المؤثرات ذات التماسك حيث يكون جاكوبي الوجه الحر متماثلاً وموجباً محدداً.
• دور الاسترخاء المفرط: يوضح المؤلفون أن الاسترخاء المفرط ($\lambda > 1$) ليس متفوقاً بشكل عالمي. تبرز فائدته المتميزة عندما تكون الخطوة الأمامية $\gamma$ ثابتة أو مقيدة بمتطلبات الاستقرار العالمية؛ في هذه الحالات، يعمل $\lambda$ كمتغير تحكم ضروري لتعويض $\gamma$ غير المثالية.
• القيود: يعتمد التحليل على نصف قطر الطيف (المعدل التقاربي) بدلاً من انكماش النورم في خطوة واحدة، مع الإقرار بأن عدم الطبيعية (non-normality) في المصفوفة الكاملة قد تسبب تقلبات حدودية. الحل ذو الصيغة المغلقة خاص بهندسة القيود الصندوقية.

في الختام، توفر الورقة معياراً دقيقاً لمتى يكون الاسترخاء المفرط مفيداً: إنه أداة تسريع مستهدفة لأنظمة الخطوة الأمامية الثابتة حيث لا يمكن تحسين الخطوة الأمامية محلياً، بدلاً من كونه تحسيناً عاماً لجميع طرق التقسيم.