kReese.net

Karush-Kuhn-Tucker (KKT) koşullar, bazen Kuhn-Tucker koşulları olarak anılacaktır, en iyi olmak için bir Doğrusal Olmayan Programlama sorun karşılamak için gereken koşullar. KKT koşulları eşitsizlik kısıtlamaları için izin vererek, Lagrange çarpanları yöntemi uzatır., sadece eşitlik kısıtları izin Lagrange çarpanları karşı.

Bize bir doğrusal olmayan optimizasyon problemi ele alalım:

Azaltmak $f(x)$
tabi: $g_{i}(x)\leq 0 \\ h_{j}(x) = 0$

Biz izin verir $x^{*}$ sorun için göreceli bir asgari noktayı temsil, aynı zamanda bazı kısıtlama yeterlilik tatmin. Bununla birlikte, o zaman her eleman için bir vektör var olduğunu varsayabiliriz $\lambda_j \left ( j = 1, \ldots, l \right )$ , nerede l eşitlik kısıtlamaları sayısını temsil eder, ve $\mu_i\left ( i = 1, \ldots, m \right )$ , nerede m eşitsizlik kısıtlamaları sayısını temsil eder. Bu sabitler, $\lambda_j$ ve $\mu_i$ , KKT çarpanları denir..

Doğrusal olmayan programlama problemi yapılacak KKT koşulları için (NLP), sonra her üç koşulun yerine getirilmesi gerekir [1-4]. Sorunun ne devletler Primal Fizibilite tekrarlıyor, eşitsizlik ve eşitlik kısıtları $x^*$ sorun için optimal karşılanması gerekir:

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

İkinci koşul, çift fizibilite koşulu olarak bilinir. Bu durum devletler, yerine verbosely, ki her eleman $\mu_i$ sıfırdan büyük olmalıdır, ve sorunun durağanlık eşit olması gerektiğini 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)}$

Sorunun durağanlık:

$\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$

Diğer iki basitçe bu koşulları l ve m için için yerine getirmesi gereken $x^*$ optimal.

Üçüncü koşul karşılanması gereken tamamlayıcı gevşeklik olarak bilinir. Bu durum sadece her mu ve ilgili eşitsizlik kısıtı belirtmektedir, iki ürün sıfır sonuçlanması gerekiyor:

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

Bu üç koşullarında zaman, biz KKT koşulları ve çözüm var, $x^*$ , NLP sorun için optimal bir çözüm. Orada birden belki de daha fazla x koşulları karşılayan alanı. Her eleman sorunu uzayda herhangi bir yerelvem, öyle ki demet (x, l, m) KKT koşulları yerine KKT noktaları denir. Bu kısıtlamaları türetilmesi bulunabilir [1,2]

Kısıt Nitelikleri

Daha önce de belirtildiği gibi, test noktaları dikkate alınması gereken nokta için bazı yeterlilik karşılaması gerekir. En iyi bilinen kısıtlama Yeterlilik Lineer Bağımsızlık kısıtlama Yeterlilik (LICQ), sadece bu devletler $h_{j}(x^*)$ ve $g_{i}(x^*)$ noktada diğer doğrusal bağımsız $x^*$ . Mangasarian Fromovitz kısıtlama yeterlilik (MFCQ) devletlerin pozitif lineraly bağımsız olarak eklenmesi ile benzer LICQ $x^*$ . [5]

Ancak diğer kısıtlama elemelerinde LICQ dinlenmek vardır. Slater kısıtlama niteleyicisi konveks sorunları olabilir. , Böyle bir nokta x var ise, $h_{j}(x^*) =$ ve $g_{i}(x^*) < 0$ i,j aktif giriş $x^*$ , sonra barut koşulun gerçekleşmesi. [5,6]

Diğer kısıtlama elemelerinde türleri var, ancak bu üç en yaygın olarak kullanılan KKT yeterlilik gibi görünüyor.

[1] Kuhn, H. ve Tucker, A., “Doğrusal Olmayan Programlama” 2. Berkeley Sempozyumu Bildiriler Kitabı 1951, pp. 481-492.
[2] Karush, W., “Çok Değişkenli Fonksiyonlar, Minima ile Side Kısıtlar olarak Eşitsizlikler”. M. Sc. Tez, Üniversitesi. of Chicago, Chicago, Il, 1939.
[3] Kuhn, M. “Karush-Kuhn-Tucker Teoremi”, Internet: http://smp.if.uj.edu.pl/~kopiec/MT/Materialy/KarushKuhnTucker.pdf, CDSEM Krallık. Mannheim, 2006.
[4]McCarl, B. ve Spreen, T., “Doğrusal Olmayan Optimizasyon Koşulları”, Ch. 12, Cebirsel Sistemleri Uygulamalı Matematiksel Programlama. Internet: http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/thebook.pdf
[5]Eustaquio, R. Karas, E. Ribeiro ve, A. Doğrusal olmayan programlama için Constraint Elemeleri, Teknik Rapor, Üniversitesi. of Parana.
[6] Varmak, D. ve Zalinescu, C. “Konveks Programlama bazı Constraint Yeterlilik Koşulları Gerekliliği”, Konveks Analiz Dergisi, 11 (1), 2004. pp 95-110.

Bilgisayar Bilimi ve Öğretimi Dergisi

Son Mesajlar

Karush-Kuhn-Tucker koşulları

Kısıt Nitelikleri