شروط كاروش كوهن تاكر
المحتويات
بدايةً، في الإستمثال الرياضي، تعتبر شروط كاروش كوهن تاكر (KKT)، المعروفة كذلك باسم شروط كوهن تاكر، هي اختبارات مشتقة أولى (تسمى أحيانا الشروط الضرورية من الدرجة الأولى) لإيجاد حل في البرمجة غير الخطية يكون هو الأمثل، شريطة استيفاء بعض شروط الانتظام والسماح بقيود عدم المساواة المفروضة على دالة الهدف، فإن نهج KKT في البرمجة غير الخطية يعمم طريقة مضاعفات لاجرانج التي لا تسمح في الأصل إلا بقيود المساواة. على غرار نهج لاجرانج، تتم إعادة صياغة مشكلة إيجاد القيمة العظمى المقيدة (التصغير) كدالة لاجرانج التي تكون نقطتها المثلى هي نقطة السرج تلعب هذه الظروف دورا مهما جدا في نظرية الإستمثال المقيدة وتطوير الخوارزمية. للحصول على مشكلة إستمثال:
- min f(x)
- تخضع إلى
- gi(x) - bi ≥ 0 , i=1,…,k
f(x) - f* ≤ ε
مفيد جدا، لا سيما بالاقتران مع الأساليب التكرارية.
فجوة الازدواجية
f(x)-f* ≤ f(x)-g(u,v)
ثم نحن مضمونون بأن:
ε≥f(x)-g(u,v)
وفي هذا الصدد، بالنظر إلى الإمكانية الأولية لـ x والعملية المزدوجة u ،v ، فإن الكمية f(x)-g(u,v) تسمى فجوة الازدواجية بين x و u ، v. لاحظ ذلك
كذلك، فإذا كانت فجوة الازدواجية صفرية، فإن x هي البدائية المثلى (وبالمثل،u ،v هي المزدوجة المثلى). من وجهة نظر خوارزمية، يوفر معيار التوقف: إذا.
f = λ∇g∇, و g(x,y)= c
- شروط KKT للبرمجة الخطية مع قيود عدم المساواة
- min cx
- s. t. Ax ≥ b
إضافةً إلى ذلك، أين λ هو ثابت التناسب. ستكون القيم القصوى والدنيا من بين حلول نظام المعادلات هذا.
الازدواجية
في هذا الإطار، بالنسبة لمشكلة التصغير، فإن أي حل ممكن في نسخته المزدوجة يوفر حدًا أدنى لحل الإصدار الأولي. ومن ثم، يُعرف الفرق بين الحل الأمثل المزدوج والحل الأمثل الأساسي باسم فجوة الازدواجية.
من جانب آخر، يمكن تقديم مشكلة الإستمثال من منظورين، المشكلة الأولية أو المشكلة المزدوجة. في بعض الأحيان، يمكن حل المشكلة بطريقة أكثر فاعلية في تنسيقها المزدوج على عكس تنسيقها الأولي.
f(x*) - Σi=1,m λi* ∇gi(x*) = 0∇
3. الركود التكميلي:
λi ≥ 0
كذلك، وتعرف الدالة الهدف للمشكلة المزدوجة كذلك باسم الدالة المزدوجة للاجرانجيان. تذكر أن مشتقة من الدرجة الأولى من دالة لاجرنج، جنبا إلى جنب مع مجموعتين من القيود، هي الجدوى المزدوجة وشروط الركود التكميلية للحالة غير الخطية.
إضافةً إلى ذلك، حتى الآن، قمنا بمراجعة شروط KKT لمختلف المشاكل. وفي حين أن شروط الجدوى الأولية بديهية تماما، فإن الأسئلة تطرح حول كيفية تفسير الجدوى المزدوجة والركود التكميلي على النحو الأمثل.
x ≥ 0
وفي هذا الصدد، يكون x هو الحل الأمثل للمشكلة المذكورة أعلاه إذا وفقط إذا كان الشرطين (1) و (3) صحققين.
- Ax ≥ b, x ≥ 0 (1)
- λA + v = c, λ ≥ 0 , v ≥ 0 (2)
- λ(Ax-b) = 0, vx = 0 (3)
- المشكلة المزدوجة هي:
- max wb
- s.t. wA ≤ c
hi(x) = 0
- Ax ≥ b, x≥0 (1)
- λA + v = c, λ≥0,v≥0 (2)
- λ(Ax - b) = 0, vx=0 (3)
- gi(x) ≤ 0, hi(x) = 0 (7)
- grad·f(x) + ∑(i=1 m)λi∇gi(x) + ∑(i=1 p)vi∇hi(x) = 0, λi ≥ 0 (8)
- λigi(x) = 0 (9)
- (7) مماثلة ل (1)، هو شرط الجدوى البدائية. دعونا نقفز إلى الشرط (9).
من جهة ثانية، أخيرًا، (8) هو شرط الجدوى المزدوج لضمان الجدوى في المشكلة المزدوجة. ليس من الصعب معرفة أن الشرط (3) في المشكلة (II) هو حالة خاصة لـ (8)، مع:
كذلك، ومن الجدير بالذكر، أو قد تكون لاحظت بالفعل، إذا كانت قيود عدم المساواة في المشكلة من الشكل "≥"، ثم مضاعفات لاجرانج المقابلة غير إيجابية. بدلا من ذلك، يمكنك كذلك تغيير شرط الأمر الأول إلى الصيغة التالية للاحتفاظ بها غير سالبة.
- [A I]=f(x)=cx ⟹ ∇f(x)=c, g(x) = [b 0]T-[A I]Tx ⟹ ∇g(x)
- مع λ و v على التوالي تمثل مضاعفات لاغرانجيان ل Ax ≥ b و x ≥ 0، لدينا:
- f(x)+∑(i=1,m)λi∇gi(x)+ ∑(i=1,p)μi∇hi(x)=0 ⇒ c-λA-v = 0 ⇒ λA+v = c∇
من جهة ثانية، شروط KKT : الشروط (7)-(9) ضرورية لكي يكون x الحل الأمثل للمشكلة السابقة (IV). إذا كان (IV) محدب، (7) - (9) تصبح شروط كافية.
إضافةً إلى ذلك، أولا، شرط الركود التكميلي لقيود عدم المساواة gi(x) ≤ 0، يتوافق مع الشرط (3) في المشكلةII))
λi*(gi(x*) - bi) = 0
4. مضاعفات لاجرانج إيجابية:
w ≥ 0
- حسب تعريف المشكلة، لدينا الاستنتاج التالي:
- w*A ≤ c ⇒ w*Ax* ≤ cx* ⇒ w*b ≤ w*Ax* ≤ cx
- حيث *w و *x هما الحل الأمثل المزدوج والحل البدائي الأمثل تباعا.
- لأن فجوة الازدواجية هي صفر بالنسبة للمشكلة الخطية، لدينا:
f(x)-∑(i=1,m)λi∇gi(x)+∑(i=1,p)μi∇hi(x) = 0∇
- المشكلة المزدوجة معطاة:
- min f(x) + ∑(i=1,m)λigi(x) + ∑(i=1,p)μihi(x)
- s.t. λigi(x) = 0
لمحة تاريخية
وفي السياق ذاته، في صيف عام 1950، أثناء ندوة بيركلي الثانية حول الإحصاء الرياضي والاحتمالية، التي عقدت في بيركلي، كاليفورنيا، ألقى عالم رياضيات من جامعة برينستون، ألبرت دبليو تاكر، والذي كان يعرف كاختصاصي في الهندسة المطاطية، كلمة بعنوان «البرمجة الغير خطية» التي كانت تستند إلى عمل مشترك بينه وعالم رياضيات هارولد دبليو كوهن، الذي كان قد أنهى للتو رسالة الدكتوراه في جامعة برينستون. نُشرت المحادثات في وقائع المؤتمر، وللمرة الأولى ظهر اسم «البرمجة الغير خطية» - العنوان الذي اختاره كوهن وتاكر لمنشورهما.
وفي هذا السياق، قدم كوهن وتاكر مشكلة البرمجة غير الخطية وأثبتا المبرهنه الرئيسية للنظرية - ما يسمى بنظرية «كوهن - تاكر»، التي تعطي الشروط الضرورية لوجود حل أمثل لمشكلة البرمجة غير الخطية. كانت الإنطلاقة لهته النظرية مشهورة للغاية، ولم يمض وقت طويل على نشرها حتى بدأ الناس يتحدثون عنها على أنها نظرية كوهن تاكر.
إضافةً إلى ذلك، ولكن من الواضح أن كوهن وتاكر لم يكونا الأولين في إثبات ذلك. في الكتب المدرسية الحديثة حول البرمجة الغير خطية، غالبًا ما تكون هناك حاشية سفلية تخبرنا أن ويليام كاروش أثبت النظرية في عام 1939 في أطروحة الماجستير الخاصة به من جامعة شيكاغو، وأن فريتز جون اشتق على وجه التقريب النتيجة نفسها في ورقة نُشرت في سنة 1948 في مجموعة مقالات بمناسبة عيد ميلاد ريتشارد كورانت الستين.
w* b=w*Ax* ⇒ w* (Ax*-b)=0
- وهو شرط الركود التكميلي في المشكلة البدائية.
- شروط KKT للبرمجة الخطية مع قيود المساواة
- min cx
- s.t. Ax = b
gi(x*) - bi
2. لا يوجد هبوط ممكن:
gi(x) - bi = 0 , i=k+1,…,m
هناك أربعة شروط KKT لبداية مثلى :
1. القيود المجدية:
x ≥ 0
وفي هذا السياق، شروط KKT لمشاكل غير خطية Kuhn, H. W., and A. W. Tucker. "Proceedings of 2nd berkeley symposium." (1951): 481-492.
كذلك، يكون x هو الحل الأمثل للمشكلة المذكورة أعلاه إذا وفقط إذا كان الشرطين (4) و (6) محققحين
- Ax = b , x ≥ 0 (4)َ
- λA + v = c , v ≥ 0 (5)
- vx = 0 (6)
s.t. gi(x) ≤ 0
(IV) min f(x)
λi* ≥ 0
يشير رمز النجمة (*) إلى القيم المثلى.
ضرورية وكافية لتحقيق الإستمثال في البرمجة الخطية.
ومن جهة أخرى، g(x,y)=c (حيث c ثابتة إلى حد ما). في حالة حدوث حد أقصى أو أدنى، يجب أن يحدث في مكان يكون فيه تدرج f وتدرج نقطة g في نفس الاتجاهين أو عكسهما. لذلك يجب أن يكون تدرج g أحد مضاعفات تدرج f. للعثور على القيمتين العظمى والصغرى (إن وجدت)، نقوم فقط بحل جملة المعادلات الناتجة عنها
ومن جهة أخرى، تشكل شروط KKT (Karush-Kuhn-Tucker) العمود الفقري للبرمجة الخطية وغير الخطية فتمثل الأسس النظرية للعديد من الخوارزميات، نذكر منها على وجه الخصوص خوارزمية كارماركر وطريقة السيمبلكس. كما هي:
وفي هذا السياق، ضرورية وكافية لتحقيق الأمثلية المحدبة، مثل تصغير المربع الأقل في الانحدار الخطي.
وفي هذا الصدد، ضرورية لتحقيق الأمثل في مشكلة الإستمثال غير المحدبة، مثل تدريب نموذج التعلم العميق.
علاوةً على ذلك، ينطبق شرط الجدوى (1) على كل من قيود المساواة وعدم المساواة، بمجرد إثبلت نه يجب عدم انتهاك القيود في الظروف المثلى.
في هذا الإطار، الشرطين الأخيرين (3 و 4) مطلوبين في حالة وجود قيود عدم المساواة وأن مضاعفات لاجرانج تكون موجبة في حالة القيد النشط (=0) وتساوي صفر في حالة القيد الغير نشط (>0).
كذلك، افترض أن fو g دالتان قابلتان للإشتقاق باستمرار. افترض أننا نريد إيجاد القيم القصوى والدنيا لـ f الخاضعة للقيود:
ومن جهة أخرى، نظرية مضاعفات لاغرانج Lagrange, Joseph-Louis. "Manière plus simple et plus générale de faire usage de la formule de l'équilibre donnée dans la section deuxième." dans Mécanique analytique 1 (1788): 77-112.
من جهة ثانية، شرط التدرج (2) يضمن عدم وجود اتجاه ممكن يمكن أن يحسن الدالة الهدف.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟