البرمجة التربيعية (QP)

البرمجة التربيعية هي صنف المسائل min (1/2) x^T Q x + c^T x s.t. Ax ≤ b, x ≥ 0 في الصورة القياسية، حيث Q ∈ R^(n×n) مصفوفة متماثلة، c ∈ R^n الحد الخطي، والقيود خطية مثل LP. تتحدد طبيعة المسألة بإشارة Q: (1) إذا كانت Q شبه معرفة موجبة فإن QP محدبة وشروط KKT لازمة وكافية للأمثلية، وتحل في زمن متعدد الحدود بطرق النقطة الداخلية أو المجموعة النشطة (أثبت Kozlov و Tarasov و Khachiyan 1979 قابلية حل QP المحدبة في زمن متعدد الحدود)؛ (2) إذا كانت Q غير معرفة فالمسألة غير محدبة و NP-صعبة عموماً (Sahni 1974). الصياغة الكلاسيكية هي نموذج Markowitz (1952) للمتوسط-التباين لاختيار المحفظة: min (1/2) x^T Σ x s.t. μ^T x ≥ R, Σ x_i = 1, x ≥ 0 — Σ مصفوفة التباين المشترك، μ متجه العائد المتوقع، R العائد المستهدف؛ تُرسم الجبهة الكفؤة بتغيير R. حصل Markowitz على جائزة نوبل في الاقتصاد عام 1990 عن هذا العمل. QP أيضاً أساس تدريب آلات متجهات الدعم (Cortes و Vapnik 1995)، التحكم التنبؤي بالنموذج (MPC)، المربعات الصغرى المقيدة، البرمجة التربيعية المتسلسلة (SQP، الحلقة الداخلية للتحسين غير الخطي، Wilson 1963 / Han 1976 / Powell 1978)، وتحسين المسارات. الخوارزميات: طور Wolfe (1959) و Beale (1959) مبادئ المجموعة النشطة؛ وتسود الحلولَ العملية طرق النقطة الداخلية تنبؤ-تصحيح (منطق Mehrotra 1992 الموسع إلى QP) وطرق المجموعة النشطة (أبناء عمومة سمبلكس LP).