شروط كاروش كوهن تاكر
هذه مقالة غير مراجعة. (مارس 2022) |
في الإستمثال الرياضي، تعتبر شروط كاروش كوهن تاكر (KKT)[1]، المعروفة أيضا باسم شروط كوهن تاكر، هي اختبارات مشتقة أولى (تسمى أحيانا الشروط الضرورية من الدرجة الأولى) لإيجاد حل في البرمجة غير الخطية يكون هو الأمثل، شريطة استيفاء بعض شروط الانتظام والسماح بقيود عدم المساواة المفروضة على دالة الهدف، فإن نهج 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) العمود الفقري للبرمجة الخطية وغير الخطية فتمثل الأسس النظرية للعديد من الخوارزميات، نذكر منها على وجه الخصوص خوارزمية كارماركر وطريقة السيمبلكس. كما هي:
- ضرورية وكافية لتحقيق الإستمثال في البرمجة الخطية.
- ضرورية وكافية لتحقيق الأمثلية المحدبة، مثل تصغير المربع الأقل في الانحدار الخطي.
- ضرورية لتحقيق الأمثل في مشكلة الإستمثال غير المحدبة، مثل تدريب نموذج التعلم العميق.
افترض أن fو g دالتان قابلتان للإشتقاق باستمرار. افترض أننا نريد إيجاد القيم القصوى والدنيا لـ f الخاضعة للقيود: g(x,y)=c (حيث c ثابتة إلى حد ما). في حالة حدوث حد أقصى أو أدنى، يجب أن يحدث في مكان يكون فيه تدرج f وتدرج نقطة g في نفس الاتجاهين أو عكسهما. لذلك يجب أن يكون تدرج g أحد مضاعفات تدرج f. للعثور على القيمتين العظمى والصغرى (إن وجدت)، نقوم فقط بحل جملة المعادلات الناتجة عنها
f = λ∇g∇, و g(x,y)= c
أين λ هو ثابت التناسب. ستكون القيم القصوى والدنيا من بين حلول نظام المعادلات هذا.
شروط KKT للبرمجة الخطية مع قيود عدم المساواة
عدلmin cx
s. t. Ax ≥ b
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
w ≥ 0
حسب تعريف المشكلة، لدينا الاستنتاج التالي:
w*A ≤ c ⇒ w*Ax* ≤ cx* ⇒ w*b ≤ w*Ax* ≤ cx
حيث *w و *x هما الحل الأمثل المزدوج والحل البدائي الأمثل تباعا.
لأن فجوة الازدواجية هي صفر بالنسبة للمشكلة الخطية، لدينا:
w* b=w*Ax* ⇒ w* (Ax*-b)=0
وهو شرط الركود التكميلي في المشكلة البدائية.
شروط KKT للبرمجة الخطية مع قيود المساواة
عدلmin cx
s.t. Ax = b
x ≥ 0
يكون x هو الحل الأمثل للمشكلة المذكورة أعلاه إذا وفقط إذا كان الشرطين (4) و (6) محققحين
Ax = b , x ≥ 0 (4)َ
λA + v = c , v ≥ 0 (5)
vx = 0 (6)
(IV) min f(x)
s.t. gi(x) ≤ 0
hi(x) = 0
شروط KKT : الشروط (7)-(9) ضرورية لكي يكون x الحل الأمثل للمشكلة السابقة (IV). إذا كان (IV) محدب، (7) - (9) تصبح شروط كافية.
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).
أولا، شرط الركود التكميلي لقيود عدم المساواة gi(x) ≤ 0، يتوافق مع الشرط (3) في المشكلةII))
Ax ≥ b, x≥0 (1)
λA + v = c, λ≥0,v≥0 (2)
λ(Ax - b) = 0, vx=0 (3)
أخيرًا، (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∇
ومن الجدير بالذكر، أو قد تكون لاحظت بالفعل، إذا كانت قيود عدم المساواة في المشكلة من الشكل "≥"، ثم مضاعفات لاجرانج المقابلة غير إيجابية. بدلا من ذلك، يمكنك أيضا تغيير شرط الأمر الأول إلى الصيغة التالية للاحتفاظ بها غير سالبة.
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
λi ≥ 0
وتعرف الدالة الهدف للمشكلة المزدوجة أيضا باسم الدالة المزدوجة للاجرانجيان. تذكر أن مشتقة من الدرجة الأولى من دالة لاجرنج، جنبا إلى جنب مع مجموعتين من القيود، هي الجدوى المزدوجة وشروط الركود التكميلية للحالة غير الخطية.
حتى الآن، قمنا بمراجعة شروط KKT لمختلف المشاكل. وفي حين أن شروط الجدوى الأولية بديهية تماما، فإن الأسئلة تطرح حول كيفية تفسير الجدوى المزدوجة والركود التكميلي على النحو الأمثل.
الازدواجية
عدليمكن تقديم مشكلة الإستمثال من منظورين، المشكلة الأولية أو المشكلة المزدوجة. في بعض الأحيان، يمكن حل المشكلة بطريقة أكثر فاعلية في تنسيقها المزدوج على عكس تنسيقها الأولي.
بالنسبة لمشكلة التصغير، فإن أي حل ممكن في نسخته المزدوجة يوفر حدًا أدنى لحل الإصدار الأولي. ومن ثم، يُعرف الفرق بين الحل الأمثل المزدوج والحل الأمثل الأساسي باسم فجوة الازدواجية.
فجوة الازدواجية
عدلبالنظر إلى الإمكانية الأولية لـ x والعملية المزدوجة u ،v ، فإن الكمية f(x)-g(u,v) تسمى فجوة الازدواجية بين x و u ، v. لاحظ ذلك f(x)-f* ≤ f(x)-g(u,v)
فإذا كانت فجوة الازدواجية صفرية، فإن x هي البدائية المثلى (وبالمثل،u ،v هي المزدوجة المثلى). من وجهة نظر خوارزمية، يوفر معيار التوقف: إذا.
ε≥f(x)-g(u,v)
ثم نحن مضمونون بأن:
f(x) - f* ≤ ε
مفيد جدا، لا سيما بالاقتران مع الأساليب التكرارية.
لمحة تاريخية
عدلفي صيف عام 1950، أثناء ندوة بيركلي الثانية حول الإحصاء الرياضي والاحتمالية، التي عقدت في بيركلي، كاليفورنيا، ألقى عالم رياضيات من جامعة برينستون، ألبرت دبليو تاكر، والذي كان يعرف كاختصاصي في الهندسة المطاطية، كلمة بعنوان «البرمجة الغير خطية» التي كانت تستند إلى عمل مشترك بينه وعالم رياضيات هارولد دبليو كوهن، الذي كان قد أنهى للتو رسالة الدكتوراه في جامعة برينستون. نُشرت المحادثات في وقائع المؤتمر، وللمرة الأولى ظهر اسم «البرمجة الغير خطية» - العنوان الذي اختاره كوهن وتاكر لمنشورهما.[4]
قدم كوهن وتاكر مشكلة البرمجة غير الخطية وأثبتا المبرهنه الرئيسية للنظرية - ما يسمى بنظرية «كوهن - تاكر»، التي تعطي الشروط الضرورية لوجود حل أمثل لمشكلة البرمجة غير الخطية. كانت الإنطلاقة لهته النظرية مشهورة للغاية، ولم يمض وقت طويل على نشرها حتى بدأ الناس يتحدثون عنها على أنها نظرية كوهن تاكر.
ولكن من الواضح أن كوهن وتاكر لم يكونا الأولين في إثبات ذلك. في الكتب المدرسية الحديثة حول البرمجة الغير خطية، غالبًا ما تكون هناك حاشية سفلية تخبرنا أن ويليام كاروش أثبت النظرية في عام 1939 في أطروحة الماجستير الخاصة به من جامعة شيكاغو[5]، وأن فريتز جون اشتق تقريبًا النتيجة نفسها في ورقة نُشرت في عام 1948 في مجموعة مقالات بمناسبة عيد ميلاد ريتشارد كورانت الستين.[6]
مراجع
عدل- ^ Kjeldsen, T. H. (2000). A contextualized historical analysis of the Kuhn–Tucker theorem in nonlinear programming: the impact of World War II. Historia mathematica, 27(4), 331-361.
- ^ 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. نسخة محفوظة 2018-04-18 على موقع واي باك مشين.
- ^ Kuhn, H. W., and A. W. Tucker. "Proceedings of 2nd berkeley symposium." (1951): 481-492.
- ^ Kuhn, Harold W. "Being in the right place at the right time." Operations Research 50.1 (2002): 132-134.
- ^ Karush, William. "Minima of functions of several variables with inequalities as side constraints." M. Sc. Dissertation. Dept. of Mathematics, Univ. of Chicago (1939).
- ^ John, Fritz. "Extremum problems with inequalities as subsidiary conditions, Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948." (1948): 187-204.
