طرق التدرج المنخفضة الرتبة للتفاصيل القابلة للتوسع في الأمثلية شبه المحددة

ننظر في عدة فئات من مسائل الأمثلية شبه المحددة الهامة جدًا التي تنطوي على كل من دالة هدف محدبة (إما سلسة أو غير سلسة) وقيود خطية أو غير خطية سلسة ومحدبة إضافية، التي تتواجد بكثرة في الإحصائيات، التعلم الآلي، الأمثلية التوافقية، ومجالات أخرى. نركز على إعدادات عالية الأبعاد ومعقولة حيث تمكّن المشكلة من الحصول على حل منخفض الرتبة يلبي أيضًا شرط التوافقية منخفض الرتبة. نقدم عدة نتائج نظرية تثبت أنه، في ظل هذه الظروف، تتقارب طريقة التدرج الشهيرة، عند بدء التشغيل بالقرب من حل مثالي مزدوج، إلى حل مشكلة الأمثلية المقيدة بمعدلات تقاربها القياسية، باستخدام فقط تحلل القيم الفردية المنخفضة الرتبة (SVD) لإسقاطها على مخروط شبه المحدد الإيجابي، بدلاً من التحلل الكامل الرتبة المكلف حسابيًا المطلوب في أسوأ الحالات. تدعم منهجيتنا تجارب عددية أجريت باستخدام مجموعة بيانات من حالات Max-Cut.