الطرق العددية المثلى لحل البرمجة شبه المحددة لمسائل NP-Hardness
Numerical Optimization Methods for Solving the Semidefinite Programming of NP-Hardness Problems
- الباحث
- أحمد حسن حميد محمود
- المشرف
- أحمد صباح أحمد الجيلاوي
- الجامعة
- جامعة بابل
- الكلية / القسم
- كلية التربية للعلوم الصرفة / الرياضيات
- الشهادة
- دكتوراه
- السنة
- 2022
- لغة الرسالة
- انكليزي
- الكلمات المفتاحية
- Semidefinite Programming ; NP-Hard Problems ; Numerical Optimization ; Optimization Methods
الملخص
تركز هذه الأطروحة على حل مشكلة NP-hard (غير الحتمية متعددة الحدود) باستخدام متغير واسع النطاق. حيث أن مشكلة K-CLUSTER (البحث عن الرسم البياني الفرعي الأكثر كثافة لحجم ثابت ع1) بحدود شبه غير محددة هي مشكلة NP- الكلاسيكية للتحسين التوافقي وقد ثبت أنها مشكلة NP-Hardness في تجميع الرسم البياني . تولد الاستراتيجية علاقة جيدة مع القيمة المثلى للمشكلة الأصلية. تم تطوير طريقة لاغرائج المعزز كبديل لطريقة penalty ، وتم تطوير تقنية هجينة تتغير بين الطريقتين بناءً على قيمة المعلمة. تم اختبار النموذج الجديد باستخدام العديد من الرسوم البيانية من مكتبة Cus ،Big Mac تم استخدام لغة جوليا للحصول على النتائج. يتفوق نهجنا الجديد على أساليب penalty من Cue السرعة والمتانة. أخيرًا ٠ أظهرت خصائص التقارب النظرية للخوارزمية المقترحة أنها التقنية المفضلة لحل توسيع البرمجة شبه المحددة للمسائل تنائية التفرع التربيعية.
Abstract
The dissertation focus on NP-hard problem (non deterministic polynomial time) with large scale variable. Whereas, the K-CLUSTER PROBLEM (search for a densest subgraph of fixed size k) with semidefinite bounds which is a classical NP-hard problem in combinatorial optimization and has been demonstrated to be an NP-Hardness problem in graph clustering. The strategy was generates a good bound to the original problem’s optimum value. The augmented Lagrangian method has been developed as a replacement for the penalty method. As well as, a hybrid technique that changes between the two ways has been developed based on the value of the parameter. The new model was tested using many graphs from the Biq Mac library, where the Julia language was applied to obtain the results. A novel approach outperforms the penalty methods in terms of speed and robustness. Finally, the theoretical convergence properties of the proposed algorithm were demonstrating that it is the technique of choice for solving the semidefinite relaxations of binary quadratic problems.
طلب نسخة من الملف
الملفات غير منشورة على الموقع. اترك بياناتك وسيتواصل معك موظفو قسم الشؤون الثقافية والفنون لإرسال النسخة مجاناً.