كفاءة طرق التقريب العشوائي للإحداثيات على تحسينات تركيبية غير قابلة للفصل

تناقش هذه الورقة مشاكل التحسين المركب التي يكون فيها دالة الهدف مكونة من مجموع طرفين؛ الأول له تدرج مستمر ليبشيتش على طول الأبعاد الفرعية العشوائية وقد يكون غير مقعر، بينما الطرف الثاني بسيط وقابل للاشتقاق ولكنه ربما غير مقعر وغير قابل للفصل. في هذه الإعدادات، نصمم طريقة تقارب إحداثيات عشوائية تأخذ في الاعتبار الشكل المركب غير القابل للفصل لدالة الهدف. يحقق هذا الخوارزم سرعة التوسع من خلال بناء نموذج تقريب محلي للدالة غير القابلة للفصل في كل تكرار على طول بعد عشوائي بأبعاد يحددها المستخدم. نحدد تقنيات فعالة لاختيار الأبعاد الفرعية العشوائية، مما يحقق تنفيذًا بتكلفة منخفضة لكل تكرار، كما يحقق أيضًا معدلات تقارب سريعة. نقدم تحليلًا احتماليًا لأسوأ حالة معقدة لطريقة التقريب العشوائية لدينا في إعدادات مقعرة وغير مقعرة؛ على وجه الخصوص، نثبت حدودًا بفرصة عالية على عدد التكرارات قبل تحقيق مثالية معينة. تؤكد النتائج العددية الواسعة أيضًا على كفاءة خوارزمنا. التمويل: تم دعم هذا العمل من قبل منح النرويج 2014-2021 منحة ELO-Hyp 24/2020؛ Unitatea Executiva pentru Finantarea Invatamantului Superior، a Cercetarii، Dezvoltarii si Inovarii منح PN-III-P4-PCE-2021-0720، L2O-MOC، رقم 70/2022؛ ومشروع ITN-ETN TraDE-OPT الممول من برنامج البحث والابتكار Horizon 2020 التابع للاتحاد الأوروبي بموجب اتفاقية منحة Marie Skłodowska-Curie رقم 861137.