kReese.net

وكون Karush - - تاكر (KKT) الشروط, يشار إليها أحيانا على أنها شروط كوهن ، تاكر, هي الشروط التي مشكلة البرمجة الخطية لتلبية الحاجة من أجل أن تكون مثالية. وتمتد الشروط KKT طريقة مضاعفات لاغرانج من خلال السماح لمعوقات عدم المساواة, خلافا لمضاعفات لاغرانج التي تسمح فقط القيود المساواة.

دعونا نتأمل مشكلة التحسين غير الخطية:

تصغير $f(x)$
رهنا: $g_{i}(x)\leq 0 \\ h_{j}(x) = 0$

وسوف نترك $x^{*}$ تمثل نقطة الحد الأدنى النسبي لمشكلتنا, الذي يرضي أيضا بعض مؤهلات القيد. مع هذا, ثم يمكننا أن نفترض أن كل عنصر يوجد متجه $\lambda_j \left ( j = 1, \ldots, l \right )$ , حيث ل يمثل عدد من المعوقات المساواة, و $\mu_i\left ( i = 1, \ldots, m \right )$ , حيث م يمثل عدد من المعوقات عدم المساواة. هذه الثوابت, $\lambda_j$ و $\mu_i$ , وتسمى مضاعفات KKT.

من أجل أن الظروف KKT الذي سيعقد في مشكلة البرمجة الخطية (NLP), ثم يجب أن تتحقق كل واحد من الشروط الثلاثة [1-4]. وتكرر الجدوى البدائية ما هي المشكلة ولايات, أن عدم المساواة والقيود على المساواة $x^*$ يجب الوفاء بها من أجل أن يكون الحل الأمثل لمشكلة:

$\left.\begin{matrix} h\left ( x^* \right )=0\\ g\left ( x^* \right )\leq0 \end{matrix}\right\} \textrm{primal feasibility (PF)}$

ومن المعروف أن الشرط الثاني كشرط جدوى المزدوجة. في هذه الحالة دول, بدلا verbosely, أن كل عنصر في $\mu_i$ يجب أن تكون أكبر من الصفر, وأنه يجب أن stationarity للمشكلة تكون مساوية 0.

$\left.\begin{matrix} \bigtriangledown f\left ( x^* \right ) + \sum_{i=1}^{m}\lambda_{i}\bigtriangledown h_{i}\left ( x^* \right ) + \sum_{j=1}^{l}\mu_{j}\bigtriangledown g_{j}\left ( x^* \right ) = 0\\ \lambda_i \in \mathbb{R}\\ \mu_i \geq 0 \end{matrix}\right\}\textrm{dual feasibility (DF)}$

وstationarity من المشكلة هو:

$\bigtriangledown f\left ( x^* \right ) + \sum_{i=1}^{m}\lambda_{i}\bigtriangledown h_{i}\left ( x^* \right ) + \sum_{j=1}^{l}\mu_{j}\bigtriangledown g_{j}\left ( x^* \right ) = 0$

في حين أن الاثنين الآخرين هي ببساطة الظروف التي ل و م يجب أن تفي لكي $x^*$ وكأنه الحل الأمثل.

ومن المعروف أن الشرط الثالث يجب أن تتحقق وبطئ الحركة التكميلية. هذا الشرط الدول ببساطة أن لكل مو القيد وعدم المساواة في كل منها, يجب على المنتج من اثنين في النتيجة صفر:

$\mu_i g_{i} \left ( x^* \right ) = 0$

عند هذه الشروط الثلاثة هي في, لدينا مع الظروف KKT وحلنا, $x^*$ , هو الحل الأمثل لمشكلة NLP. هناك ربما اكثر من واحد س في المساحة التي تستوفي الشروط. أي نقطة في الفضاء مشكلة حيث كل عنصر من عناصرلوم, بحيث tuple (س, ل, م) ويطلق على تلبية الشروط KKT نقاط KKT. ويمكن الاطلاع على الاشتقاق من هذه القيود في [1,2]

القيد المؤهلات

كما ذكر سابقا, النقاط التي نحن بحاجة لاختبار التأهيل تلبية بعض من أجل أن تكون وجهة نظر. الأكثر المؤهل القيد معروفة هي قيد التأهيل الاستقلال الخطي (LICQ), التي تنص على أنه ببساطة $h_{j}(x^*)$ و $g_{i}(x^*)$ تكون مستقلة عن الآخر خطيا عند نقطة $x^*$ . مؤهلات القيد Mangasarian - Fromovitz (MFCQ) الدول بالمثل LICQ مع إضافة إيجابية يجري lineraly مستقلة في $x^*$ . [5]

هناك عقبة أخرى التصفيات لكن ذلك استرخاء LICQ. يمكن استخدامها في تصفيات القيد سلاتر في مشاكل محدبة. إذا كان هناك علامة X هذه النقطة التي $h_{j}(x^*) =$ و $g_{i}(x^*) < 0$ ط للجميع,ي النشطة في $x^*$ , ثم الشرط يحمل لائحة. [5,6]

أنواع أخرى من التصفيات القيد موجودة, ولكن هؤلاء الثلاثة يبدو أن الأكثر شيوعا في التأهل KKT.

[1] كوهن, H. وتكر, أ., “البرمجة الخطية” وقائع الندوة بيركلي 2 1951, ص. 481-492.
[2] Karush, دبليو., “الحدود الدنيا من وظائف العديد من المتغيرات وعدم المساواة مع القيود الجانبية”. ماجستير. أطروحة, جامعة. of Chicago, شيكاغو, و, 1939.
[3] كوهن, م. “نظرية Karush - كوهن ، تاكر”, الإنترنت: http://smp.if.uj.edu.pl/~kopiec/MT/Materialy/KarushKuhnTucker.pdf, CDSEM المملكة. مانهايم, 2006.
[4]McCarl, باء. وSpreen, ت., “الشروط الأمثل لاخطية”, CH. 12, الرياضي برمجة تطبيق استخدام نظم الجبرية. الإنترنت: http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/thebook.pdf
[5]Eustaquio, آر. كاراس, البريد. وريبيرو, أ. المؤهل القيد للبرمجة الخطية, تقرير التكنولوجيا, جامعة. بارانا.
[6] وصول, D. وZalinescu, جيم. “على ضرورة تأهيل بعض شروط القيد في برمجة محدب”, مجلة التحليل محدب, 11 (1), 2004. ص 95-110.

وعلوم الحاسب الآلي ومجلة تدريس

المشاركات الأخيرة

Karush - كوهن ، تاكر الشروط

القيد المؤهلات