kReese.net

Karush - Kuhn - टकर (ईज़ी) शर्तों, कभी कभी Kuhn - टकर शर्तों के रूप में जाना जाता है, शर्तों रहे हैं कि एक Nonlinear प्रोग्रामिंग समस्या को पूरा करने की जरूरत है क्रम में करने के लिए इष्टतम. KKT शर्तों असमानता की कमी के लिए अनुमति देकर लाग्रंगियन मल्टीप्लायरों की विधि का विस्तार, के रूप में Lagrange, मल्टीप्लायरों जो केवल समानता की कमी की अनुमति के लिए विरोध.

हमें एक nonlinear अनुकूलन समस्या पर विचार:

न्यूनतम $f(x)$
के अधीन: $g_{i}(x)\leq 0 \\ h_{j}(x) = 0$

हम आपको सूचित करेंगे $x^{*}$ हमारी समस्या के लिए एक रिश्तेदार न्यूनतम बिंदु का प्रतिनिधित्व करते हैं, जो भी कुछ बाधा योग्यता संतुष्ट. इस के साथ, तो हम मान सकते हैं कि प्रत्येक तत्व के लिए एक वेक्टर मौजूद $\lambda_j \left ( j = 1, \ldots, l \right )$ , जहाँ l समानता की कमी की संख्या का प्रतिनिधित्व करता है, और $\mu_i\left ( i = 1, \ldots, m \right )$ , जहाँ मीटर असमानता की कमी की संख्या का प्रतिनिधित्व करता है. इन अचरों, $\lambda_j$ और $\mu_i$ , KKT मल्टीप्लायरों कहा जाता है.

KKT एक nonlinear प्रोग्रामिंग समस्या में आयोजित होने की स्थिति के लिए आदेश में (एनएलपी), तो प्रत्येक तीन शर्तों का पूरा किया जाना चाहिए [1-4]. आदि व्यवहार्यता restates समस्या क्या कहा गया है, कि पर असमानता और समानता की कमी $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^*$ , एनएलपी समस्या के लिए एक इष्टतम समाधान है. शायद एक से अधिक वहाँ एक्स अंतरिक्ष में जो शर्तों को पूरा. समस्या अंतरिक्ष में किसी भी बिंदु है, जहां के प्रत्येक तत्वएलऔरमीटर, ऐसी है कि टपल (एक्स, एल, मीटर) KKT शर्तों को संतुष्ट KKT अंक कहा जाता है. इन बाधाओं की व्युत्पत्ति में पाया जा सकता है [1,2]

बाधा योग्यता

जैसा कि पहले उल्लेख, कहते हैं कि हम परीक्षण कर रहे हैं क्रम में कुछ बिंदु पर विचार किया जा करने के लिए योग्यता को पूरा करने की आवश्यकता है. सबसे अच्छी तरह से जाना जाता बाधा योग्यता रैखिक स्वतंत्रता बाधा योग्यता है (LICQ), जो केवल कहा गया है कि $h_{j}(x^*)$ और $g_{i}(x^*)$ रैखिक बिंदु पर दूसरे से स्वतंत्र हैं $x^*$ . बाधा Mangasarian Fromovitz योग्यता (MFCQ) राज्यों पर सकारात्मक lineraly स्वतंत्र जा रहा है के अलावा के साथ इसी तरह LICQ $x^*$ . [5]

वहाँ तथापि अन्य बाधा क्वालिफायर कि LICQ आराम कर रहे हैं. स्लेटर बाधा पात्रता उत्तल समस्याओं में इस्तेमाल किया जा सकता है. अगर वहाँ एक बात है कि ऐसे एक्स मौजूद $h_{j}(x^*) =$ और $g_{i}(x^*) < 0$ मैं सभी के लिए,जम्मू में सक्रिय $x^*$ , तो स्लेट शर्त रखती है. [5,6]

बाधा क्वालिफायर के अन्य प्रकार मौजूद है, लेकिन इन तीन सबसे अधिक KKT योग्यता में इस्तेमाल होने लगते हैं.

[1] Kuhn, एच. और टकर, ए., “Nonlinear प्रोग्रामिंग” 2 बर्कले संगोष्ठी की कार्यवाही 1951, पीपी. 481-492.
[2] Karush, डब्ल्यू., “साइड प्रतिबन्ध के रूप में असमानता के साथ कई चर के कार्य के minima”. M.Sc. निबंध, Univ. of Chicago, शिकागो, Il, 1939.
[3] Kuhn, एम. “Karush Kuhn - टकर théorème”, इंटरनेट: http://smp.if.uj.edu.pl/~kopiec/MT/Materialy/KarushKuhnTucker.pdf, CDSEM विश्वविद्यालय. मेन्नहैम, 2006.
[4]McCarl, बी. और Spreen, टी., “Nonlinear अनुकूलन स्थितियां”, चौधरी. 12, एप्लाइड गणितीय बीजीय सिस्टम का प्रयोग प्रोग्रामिंग. इंटरनेट: http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/thebook.pdf
[5]युस्टैस, आर. Karas, ई. और रिबेरो, एक. Nonlinear प्रोग्रामिंग के लिए बाधा की योग्यता, टेक रिपोर्ट, Univ. Parana की.
[6] आएँ, डी. और Zalinescu, सी. “उत्तल प्रोग्रामिंग में कुछ बाधा योग्यता शर्तों की आवश्यकता”, उत्तल विश्लेषण की जर्नल, 11 (1), 2004. पीपी 95-110.

एक कंप्यूटर विज्ञान और शिक्षण जर्नल

हाल के पोस्ट

Karush Kuhn - टकर स्थितियां

बाधा योग्यता