kReese.net

На Karush-Кун-Такер (KKT) услови, понекогаш се нарекува како Кун-Такер услови, се услови кои на нелинеарни програмерски проблем треба да се исполнат со цел да биде оптимална. На KKT услови се протега на метод на Lagrangian мултипликатори со дозволување за нееднаквост ограничувања, што е спротивно на Лагранж мултипликатори кои само што им овозможуваат еднаквоста ограничувања.

Дозволете ни да се сметаат за нелинеарна оптимизација проблем:

Спушти $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 )$ , каде m го претставува бројот на нееднаквост ограничувања. Овие константи, $\lambda_j$ и $\mu_i$ , се нарекуваат KKT множители.

Во цел за KKT услови да се одржи во нелинеарни програмерски проблем (НЛП), тогаш секој од трите услови мора да бидат исполнети [1-4]. Исконската Физибилити Повторно што е проблемот држави, дека нееднаквост и еднаквост ограничувања на $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$

Додека другите две се едноставно услови кои L и m мора да ги исполни со цел за $x^*$ да се оптимално.

Третиот услов мора да се исполнат е познат како комплементарни slackness. Оваа состојба едноставно наведува дека за секоја општини и нејзините нееднаквост Ограничување, производ на две треба да резултира со нула:

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

Кога овие три услови се во, имаме со KKT услови и нашето решение, $x^*$ , е оптимално решение за проблемот НЛП. Има можеби и повеќе од една x во просторот, кои ги исполнуваат условите. Било која точка во проблемот простор каде секој елемент наLиm, така што торка (x, L, m) задоволи KKT услови се нарекуваат KKT поени. Изведување на овие ограничувања може да се најде во [1,2]

Ограничување на квалификации

Како што споменавме претходно, точки кои сме тестирање треба да се исполнат некои квалификации, со цел за момент да се смета. Најпознати ограничување квалификација е линеарна независност ограничување квалификација (LICQ), која едноставно вели дека $h_{j}(x^*)$ и $g_{i}(x^*)$ се линеарно независно од другите во точка $x^*$ . На Mangasarian-Fromovitz ограничување квалификација (MFCQ) држави слично на LICQ со тоа да се биде позитивен lineraly независни во $x^*$ . [5]

Постојат меѓутоа други пречка квалификациите што релаксира LICQ. На ограничувањето Слејтер квалификациите може да се користи во конвексен проблеми. Ако постои точка таква што x $h_{j}(x^*) =$ и $g_{i}(x^*) < 0$ за сите јас,ѕ активни во $x^*$ , тогаш чеша состојба има. [5,6]

Други видови на ограничување квалификациите не постојат, но овие три се чини дека се еден од најчесто користените во KKT квалификација.

[1] Кун, H. и Такер, А, “Нелинеарни Програмирање” Зборник на трудови на 2 Беркли симпозиум 1951, п.п.. 481-492.
[2] Karush, В., “Минимум на функции од повеќе променливи со нееднаквости како страна ограничувања”. М-р. Дисертација, Univ. во Чикаго, Чикаго, На, 1939.
[3] Кун, М. “На Karush-Кун-Такер теорема”, Интернет: http://smp.if.uj.edu.pl/~kopiec/MT/Materialy/KarushKuhnTucker.pdf, CDSEM Кралство. Манхајм, 2006.
[4]McCarl, Б. и Spreen, Т, “Нелинеарни оптимизација Услови”, Канал. 12, Применета Математичка програмирање со користење Алгебарски системи. Интернет: http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/thebook.pdf
[5]Eustaquio, Р. Karas, Е. Рибеиро и, А. Ограничување на квалификации за нелинеарна Програмирање, Техника Злоупотреба, Univ. на Парана.
[6] Пристигнете, D. и Zalinescu, C. “На потребата од некои Ограничување услови за квалификација во конвексен Програмирање”, Весник на конвексни анализа, 11 (1), 2004. п.п. 95-110.

Компјутерски науки и настава весник

Последни пораки

Karush-Кун-Такер Услови

Ограничување на квалификации