kReese.net

Karush-Kuhn-Tucker (EZ) warunki, czasami określane jako Kuhn-Tucker warunkach, są warunki, które Nieliniowa problem programowania muszą spełniać, aby być optymalne. W KKT warunki rozszerza metodę mnożników Lagrange'a poprzez umożliwienie ograniczenia nierówności, w przeciwieństwie do mnożnikami Lagrange'a co tylko pozwalają ograniczenia równości.

Rozważmy problem optymalizacji nieliniowej:

Zminimalizować $f(x)$
z zastrzeżeniem: $g_{i}(x)\leq 0 \\ h_{j}(x) = 0$

Poinformujemy $x^{*}$ stanowią względną punktu minimum dla naszego problemu, który spełnia również pewne kwalifikacje więzów. Z tego, wtedy możemy założyć, że dla każdego elementu istnieje wektor $\lambda_j \left ( j = 1, \ldots, l \right )$ , gdzie l oznacza liczbę ograniczeń równości, i $\mu_i\left ( i = 1, \ldots, m \right )$ , gdzie m oznacza liczbę ograniczeń nierówności. Te stałe, $\lambda_j$ i $\mu_i$ , nazywane są KKT mnożniki.

W celu dla KKT warunkach, które odbędą się w nieliniowym problemem programowania (NLP), wówczas każdy z trzech warunków musi być spełniony [1-4]. Pierwotnej potwierdza wykonalności na czym polega problem stanowiący, że nierówność i równość ograniczenia dotyczące $x^*$ muszą być spełnione, aby tego problemu jest optymalny:

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

Drugi warunek jest znany jako podwójnego warunku wykonalności. W tym stanie państwa, raczej Szerzej, że każdy element w $\mu_i$ musi być większa od zera, i że stacjonarność problemu musi być równa 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)}$

Stacjonarność problemu jest:

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

Natomiast dwa pozostałe są po prostu warunki, które l i m musi spełnić, aby $x^*$ za optymalny.

Trzeci warunek, który musi być spełniony jest znany jako uzupełniający bierności. Warunek ten stwierdza jedynie, że dla każdego MU a jego odpowiednim ograniczeniem nierówność, produktów z nich powinno doprowadzić do zera:

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

Kiedy te trzy warunki są spełnione, spotkaliśmy się z KKT warunki i nasze rozwiązanie, $x^*$ , jest optymalnym rozwiązaniem problemu NLP. Nie może więcej niż jeden x w przestrzeni, które spełniają warunki. Dowolny punkt w przestrzeni problemu, gdzie każdy elementlim, takie, że krotka (x, l, m) spełniają warunki KKT są nazywane KKT punkty. Wyprowadzenie tych ograniczeń można znaleźć w [1,2]

Kwalifikacje więzów

Jak wspomniano wcześniej, punkty, które testujemy muszą spełniać pewne kwalifikacje, aby punkt mógł być uznany. Najbardziej znanym Kwalifikacje ograniczeniem jest liniowa Kwalifikacje ograniczenie Niepodległości (LICQ), który po prostu, że $h_{j}(x^*)$ i $g_{i}(x^*)$ są liniowo niezależne od siebie w punkcie $x^*$ . Mangasarian-Fromovitz kwalifikacja ograniczenie (MFCQ) stwierdza, podobnie LICQ z dodatkiem jest pozytywny-lineraly niezależny w $x^*$ . [5]

Istnieją jednak inne eliminacje ograniczenie, że złagodzenie LICQ. Kwalifikator ograniczenie Slater może być stosowany w wypukłych problemów. Jeśli istnieje punkt x taki, że $h_{j}(x^*) =$ i $g_{i}(x^*) < 0$ dla wszystkich i,j aktywny w $x^*$ , następnie stan łupek trzyma. [5,6]

Inne rodzaje eliminacji przymusu istnieją, ale te trzy wydają się najczęściej używane w KKT kwalifikacji.

[1] Kuhn, H. i Tucker, A., “Programowania nieliniowego” Materiały z 2 Sympozjum Berkeley 1951, pp. 481-492.
[2] Karush, W., “Minima z funkcji wielu zmiennych z nierównościami jak ujemne skutki”. M.Sc. Rozprawa, Univ. of Chicago, Chicago, Il, 1939.
[3] Kuhn, M. “Karush-Kuhn-Tucker twierdzenie”, Internet: http://smp.if.uj.edu.pl/~kopiec/MT/Materialy/KarushKuhnTucker.pdf, CDSEM University. Mannheim, 2006.
[4]McCarl, B. i Spreen, T., “Nieliniowe Warunki optymalizacji”, Ch. 12, Stosowane programowanie matematyczne Korzystanie algebraicznych systemów. Internet: http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/thebook.pdf
[5]Eustachy, R. Karas, To. i Ribeiro, A. Kwalifikacje Ograniczenie dla programowania nieliniowego, Tech Report, Univ. Parana.
[6] Przybyć, D. i Zalinescu, C. “O konieczności pewnych warunkach Kwalifikacyjnych przymusu w Convex Programowanie”, Journal of Convex Analysis, 11 (1), 2004. pp 95-110.

Informatyka i Nauczanie Dz.

Najnowsze posty

Karush-Kuhn-Tucker Warunki

Kwalifikacje więzów