نظرة عامة شاملة حول شروط كاروش كوهن تاكر

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

min⁡ f(x)

تخضع إلى

gi(x) - bi ≥ 0 , i=1,…,k

gi(x) - bi = 0 , i=k+1,…,m

هناك أربعة شروط KKT لبداية مثلى :

1. القيود المجدية:

gi(x*) - bi

2. لا يوجد هبوط ممكن:

f(x*) - Σi=1,m λi* ∇gi(x*) = 0∇

3. الركود التكميلي:

λi*(gi(x*) - bi) = 0

4. مضاعفات لاجرانج إيجابية:

λi* ≥ 0

يشير رمز النجمة (*) إلى القيم المثلى.

ينطبق شرط الجدوى (1) على كل من قيود المساواة وعدم المساواة، بمجرد إثبلت نه يجب عدم انتهاك القيود في الظروف المثلى.

شرط التدرج (2) يضمن عدم وجود اتجاه ممكن يمكن أن يحسن الدالة الهدف.

الشرطين الأخيرين (3 و 4) مطلوبين في حالة وجود قيود عدم المساواة وأن مضاعفات لاجرانج تكون موجبة في حالة القيد النشط (=0) وتساوي صفر في حالة القيد الغير نشط (>0).

تشكل شروط KKT (Karush-Kuhn-Tucker) العمود الفقري للبرمجة الخطية وغير الخطية فتمثل الأسس النظرية للعديد من الخوارزميات، نذكر منها على وجه الخصوص خوارزمية كارماركر وطريقة السيمبلكس. كما هي:



ضرورية وكافية لتحقيق الإستمثال في البرمجة الخطية.

ضرورية وكافية لتحقيق الأمثلية المحدبة، مثل تصغير المربع الأقل في الانحدار الخطي.

ضرورية لتحقيق الأمثل في مشكلة الإستمثال غير المحدبة، مثل تدريب نموذج التعلم العميق.