البرمجة التربيعية

كحالة خاصة عندما تكون Q متماثلة وموجبة التحديد ، فإن دالة التكلفة تختزل إلى المربعات الصغرى:

التقليل	${\displaystyle {\tfrac {1}{2}}\|R\mathbf {x} -\mathbf {d} \|^{2}}$
رهناً بـ	${\displaystyle A\mathbf {x} \preceq \mathbf {b} ,}$

حيث Q = R ^T R ينتج من تحليل Cholesky لـ Q و c = − R ^T d . وعلى العكس من ذلك، يمكن صياغة أي برنامج للمربعات الصغرى المقيدة بشكل مكافئ كمسألة برمجة تربيعية، حتى بالنسبة لمصفوفة R غير مربعة عامة .

عند تصغير دالة f في جوار نقطة مرجعية x₀ _، تُعيّن Q إلى مصفوفة هيسيان الخاصة بها H ( f ( x₀ ₎ ) ، وتُعيّن c إلى تدرجها ∇f ( x₀ ₎ . ويمكن صياغة مسألة برمجة ذات صلة، وهي البرمجة التربيعية المقيدة تربيعيًا ، بإضافة قيود تربيعية على المتغيرات.

تُعدّ البرمجة التربيعية بسيطةً للغاية عندما تكون Q موجبة التحديد ولا توجد سوى قيود المساواة؛ أي أن عملية الحل خطية. وباستخدام مُضاعِفات لاغرانج والبحث عن القيمة القصوى لدالة لاغرانج، يُمكن إثبات أن حل المسألة ذات قيود المساواة هو

${\displaystyle {\text{تقليل}}\quad {\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x} }$

${\displaystyle {\text{subject to}}\quad E\mathbf {x} =\mathbf {d} }$

يُعطى بواسطة النظام الخطي

${\displaystyle {\begin{bmatrix}Q&E^{\top }\\E&0\end{bmatrix}}{\begin{bmatrix}\mathbf {x} \\\lambda \end{bmatrix}}={\begin{bmatrix}-\mathbf {c} \\\mathbf {d} \end{bmatrix}}}$

حيث λ هي مجموعة من معاملات لاغرانج التي تخرج من الحل جنبًا إلى جنب مع x .

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

إذا لم تربط القيود المتغيرات ببعضها بإحكام شديد، فإنّ أحد الحلول البسيطة نسبيًا هو تغيير المتغيرات بحيث تُلبّى القيود بشكل مطلق. على سبيل المثال، لنفترض أن d = 0 (التعميم إلى قيمة غير صفرية أمرٌ سهل). بالنظر إلى معادلات القيود:

${\displaystyle E\mathbf {x} =0}$

أدخل متغيرًا جديدًا y معرفًا بواسطة

${\displaystyle Z\mathbf {y} =\mathbf {x} }$

حيث يكون بُعد y هو x ناقص عدد القيود. ثم

${\displaystyle EZ\mathbf {y} =\mathbf {0} }$

وإذا تم اختيار Z بحيث يكون EZ = 0، فإن معادلة القيد ستتحقق دائمًا. ويتطلب إيجاد Z إيجاد الفضاء الصفري لـ E ، وهو أمر بسيط نسبيًا اعتمادًا على بنية E. وبالتعويض في الصيغة التربيعية، نحصل على مسألة تصغير غير مقيدة.

${\displaystyle {\tfrac {1}{2}}\mathbf {x} ^{\top }Q\mathbf {x} +\mathbf {c} ^{\top }\mathbf {x} \quad \ضمنا \quad {\tfrac {1}{2}}\mathbf {y} ^{\top }Z^{\top }QZ\mathbf {y} +\left(Z^{\top }\mathbf {c} \right)^{\top }\mathbf {y} }$

الحل الذي يُعطى بالصيغة التالية:

${\displaystyle Z^{\top }QZ\mathbf {y} =-Z^{\top }\mathbf {c} }$

في ظل شروط معينة على Q ، ستكون المصفوفة المختزلة Z ^T QZ موجبة التحديد. من الممكن كتابة صيغة معدلة لطريقة التدرج المترافق تتجنب الحساب الصريح لـ Z. ^{[ 5 ]}

بالنسبة لـ Q الموجبة المحددة ، تكون مسألة التصغير محدبة . لذا، يمكن استخدام طريقة القطع الناقص لحل المسألة في وقت متعدد الحدود (ضعيف) . وقد تم إثبات ذلك صراحةً في عام 1979 من قبل كوزلوف وتاراسوف وخاشيان. ^{[ 6 ]}

يقدم كل من Ye وTse ^{[ 7 ]} خوارزمية ذات زمن متعدد الحدود، وهي امتداد لخوارزمية Karmarkar من البرمجة الخطية إلى البرمجة التربيعية المحدبة. في نظام يحتوي على n متغيرًا و L بتًا للإدخال، تتطلب خوارزميتهم O(L n) تكرارًا، يمكن تنفيذ كل منها باستخدام O(L n ³ ) عملية حسابية، ليصبح إجمالي تعقيد زمن التشغيل O( L ² n ⁴ ).

يقدم كابور وفيديا ^{[ 8 ]} خوارزمية أخرى تتطلب O( L * log L * n ^3.67 * log n ) من العمليات الحسابية.

عندما لا تكون Q موجبة التحديد (أي أن المسألة غير محدبة)، فإن البرمجة التربيعية تُصنف ضمن مسائل NP-صعبة . إحدى طرق إثبات ذلك هي استخدام نظرية موتزكين-ستراوس . ^{[ 9 ]} تنص هذه النظرية على أنه لأي رسم بياني غير موجه G ، فإن برنامجًا تربيعيًا معينًا مرتبطًا بـ G له قيمة عظمى تعتمد على عدد الزمر في G. يُعد حساب عدد الزمر في الرسم البياني مسألة NP-صعبة معروفة؛ لذا، فإن حل البرنامج التربيعي يُصنف أيضًا ضمن مسائل NP-صعبة. بعض الحالات الخاصة المهمة تُصنف أيضًا ضمن مسائل NP-صعبة.

• أثبت ساهني ^{[ 10 ]} صعوبة NP في حالة كون Q سالبة التحديد (لها n من القيم الذاتية السالبة)؛
• أثبت باردالوس وفافاسيس ^{[ 11 ]} صعوبة NP (قوية) عندما يكون للدالة Q قيمة ذاتية سالبة واحدة على الأقل . وقد حققا ذلك من خلال إظهار اختزال من مسألة الزمرة إلى برنامج تربيعي محدد بمتغيرات w ، x₁ ... xₙ _{، y₁ ،} y₂ ... _yₙ ( _{n-1)، n} ، z ودالة هدف z - w² ^. وأثبتا أن الرسم البياني المدخل يحتوي على زمرة بحجم k، إذا وفقط إذا كان للبرنامج التربيعي المقابل حل بقيمة صفر.

علاوة على ذلك، فإن إيجاد نقطة كاروش-كون-تاكر لبرنامج تربيعي غير محدب هو أمر صعب من نوع CLS. ^{[ 12 ]}