برنامج تربيعي مقيد تربيعيًا

في مجال التحسين الرياضي ، يُعدّ برنامج التحسين التربيعي المقيد تربيعيًا ( QCQP ) مسألة تحسين تكون فيها كل من دالة الهدف والقيود دوالًا تربيعية . ويأخذ الشكل التالي:

${\displaystyle {\begin{aligned}&{\text{تقليل}}&&{\tfrac {1}{2}}x^{\mathrm {T} }P_{0}x+q_{0}^{\mathrm {T} }x\\&{\text{بشرط}}&&{\tfrac {1}{2}}x^{\mathrm {T} }P_{i}x+q_{i}^{\mathrm {T} }x+r_{i}\leq 0\quad {\text{لـ }}i=1,\dots ,m,\\&&&Ax=b,\end{aligned}}}$

حيث P ₀ , ..., P _m هي مصفوفات من الرتبة n × n و x ∈ R ⁿ هو متغير التحسين.

إذا كانت المصفوفات _P₀ ، _... ، Pₘ موجبة شبه محددة ، فإن المسألة تكون محدبة . أما إذا لم تكن هذه المصفوفات موجبة ولا سالبة شبه محددة، فإن المسألة تكون غير محدبة. وإذا كانت _{المصفوفات} P₁ ، ...، Pₘ جميعها تساوي صفرًا، فإن القيود تكون خطية، _وتكون المسألة برنامجًا تربيعيًا .

يمكن حل مسألة QCQP المحدبة بكفاءة باستخدام طريقة النقطة الداخلية (في وقت متعدد الحدود)، وعادةً ما تتطلب حوالي 30-60 تكرارًا للتقارب. أما حل الحالة العامة غير المحدبة فهو مسألة صعبة من نوع NP .

لتوضيح ذلك، لاحظ أن القيدين x₁ ₍ x₁ _- 1) ≤ 0 و x₁ ( x₁ - 1) ≥ 0 يُكافئان القيد x₁ _{( x₁} - 1) = 0، والذي بدوره يُكافئ القيد x₁ ∈ {0, 1}. وبالتالي، يُمكن صياغة أي برنامج عددي ثنائي (حيث يجب أن تكون جميع المتغيرات إما 0 أو 1) كبرنامج تربيعي مقيد تربيعيًا. وبما أن البرمجة العددية الثنائية هي مسألة صعبة الحل ₍ NP _- hard) بشكل عام ، فإن QCQP هي _أيضًا مسألة صعبة الحل (NP-hard).

مع ذلك، حتى في مسائل البرمجة التربيعية المقيدة غير المحدبة، يمكن عمومًا إيجاد حل محلي باستخدام صيغة غير محدبة من طريقة النقطة الداخلية. في بعض الحالات (مثل حل مسائل البرمجة غير الخطية باستخدام منهجية البرمجة التربيعية المقيدة المتسلسلة)، تكون هذه الحلول المحلية جيدة بما يكفي لقبولها.

توجد طريقتان رئيسيتان لتخفيف مشكلة QCQP: استخدام البرمجة شبه المحددة (SDP)، واستخدام تقنية إعادة الصياغة والخطية (RLT). بالنسبة لبعض فئات مسائل QCQP (وتحديدًا مسائل QCQP ذات العناصر القطرية الصفرية في مصفوفات البيانات)، تتوفر طرق تخفيف باستخدام البرمجة المخروطية من الدرجة الثانية (SOCP) والبرمجة الخطية (LP) تُعطي نفس قيمة الهدف التي تُعطيها طريقة التخفيف باستخدام SDP. ^{[ 1 ]}

يمكن حلّ مسائل البرمجة التربيعية شبه المحددة غير المحدبة ذات العناصر غير القطرية غير الموجبة بدقة باستخدام تقنيات الاسترخاء شبه المحددة (SDP) أو البرمجة التربيعية المتدرجة (SOCP)، ^{[ 2 ]} وتوجد شروط كافية قابلة للتحقق في زمن متعدد الحدود لكي تكون تقنيات الاسترخاء شبه المحددة لمسائل البرمجة التربيعية شبه المحددة العامة دقيقة. ^{[ 3 ]} علاوة على ذلك، فقد ثبت أن فئة من مسائل البرمجة التربيعية شبه المحددة العامة العشوائية لها تقنيات استرخاء شبه محددة دقيقة باحتمالية عالية طالما أن عدد القيود لا ينمو أسرع من دالة متعددة الحدود ثابتة في عدد المتغيرات. ^{[ 3 ]}

• مسألة القطع الأقصى هي مسألة في نظرية المخططات، وهي مسألة صعبة من نوع NP. تتمثل هذه المسألة، عند إعطاء مخطط، في تقسيم رؤوسه إلى مجموعتين، بحيث تنتقل أكبر عدد ممكن من الحواف من مجموعة إلى أخرى. يمكن صياغة مسألة القطع الأقصى كمسألة QCQP، ويُوفر استرخاء SDP للمسألة الثنائية حدودًا دنيا جيدة.
• تُستخدم تقنية QCQP لضبط إعدادات الآلة بدقة في التطبيقات عالية الدقة مثل الطباعة الضوئية .

• بويد، ستيفن؛ ليفين فاندنبيرغ (2004). التحسين المحدب . كامبريدج: مطبعة جامعة كامبريدج. ISBN 978-0-521-83378-3.

• دليل تحسين NEOS: البرمجة التربيعية المقيدة ( مؤرشف بتاريخ 2013-04-02 في Wayback Machine)