kReese.net

Karush-Kuhni-Tuckeri (EZ) tingimused, mõnikord nimetatakse Kuhni-Tuckeri tingimused, tingimustel, et Mittelineaarne Programmeerimine probleem vaja täita, et olla optimaalne. KKT tingimused laiendab meetod Lagrange'i kutsumine võimaldades ebavõrdsus piirangud, erinevalt Lagrange Multipliers mis lubavad üksnes võrdõiguslikkuse piirangud.

Mõelgem mittelineaarne optimeerimise probleem:

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

Me anname $x^{*}$ esindama suhteline minimaalne punkt meie probleem, mis vastab ka mõned piirang kvalifikatsioon. Selle, siis võime eeldada, et iga element eksisteerib vektor $\lambda_j \left ( j = 1, \ldots, l \right )$ , kus l esindab paljud võrdõiguslikkuse piirangud, ja $\mu_i\left ( i = 1, \ldots, m \right )$ , kus m esindab mitmeid ebavõrdsus piirangud. Need konstandid, $\lambda_j$ ja $\mu_i$ , kutsutakse KKT kutsumine.

Selleks, et KKT tingimused, mis toimub mittelineaarne programmeerimise probleem (NLP), seejärel iga kolme tingimust peavad olema täidetud [1-4]. Primal teostatavusuuring kordab, milles probleem riigid, et ebavõrdsuse ja võrdõiguslikkuse piirangud $x^*$ peavad olema täidetud selleks, et probleem olla optimaalne:

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

Teine tingimus on tuntud kui dual teostatavuse tingimus. Selles seisukorras riigid, pigem verbosely, et iga element $\mu_i$ peab olema suurem kui null, ja et stationarity probleemi peab olema võrdne 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 on probleemi:

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

Kuigi teised kaks on lihtsalt tingimusi, mis l ja m peavad täitma, et $x^*$ optimaalseks.

Kolmas tingimus, mis tuleb täita tuntakse täiendav lõtvus. See seisund lihtsalt, et iga mu ja vastava ebavõrdsus piirang, Toodete kahest tulemusena peaks null:

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

Kui need kolm tingimust on täidetud, oleme kohtunud KKT tingimused ja meie lahendus, $x^*$ , on optimaalne lahendus NLP probleem. Seal võibolla rohkem kui üks x ruumis, mis vastavad tingimused. Mis tahes punkt probleem ruum, kus iga elementljam, selline, et korteež (x, l, m) rahuldada KKT tingimused on kutsutud KKT võrra. Tuletamine neid piiranguid võib leida [1,2]

Constraint Kvalifikatsioonikeskus

Nagu eespool mainitud, punktid, mida me katsetame vaja täita mõned kvalifikatsiooni selleks käsk pidada. Kõige tuntum piirang Kvalifikatsioon Linear Independence piirang Kvalifikatsioonikeskus (Licq), mis lihtsalt, et $h_{j}(x^*)$ ja $g_{i}(x^*)$ on lineaarselt sõltumatud teistest punktis $x^*$ . Mangasarian-Fromovitz piirang kvalifikatsioon (MFCQ) riike sarnaselt LICQ, lisaks on positiivse lineraly sõltumatu juures $x^*$ . [5]

Siiski on muudest piirangutest täpsustus, mis lõõgastavad LICQ. Slater piirang täpsustava saab kasutada kumer probleeme. Kui on olemas punkti x, nii et $h_{j}(x^*) =$ ja $g_{i}(x^*) < 0$ iga i,j aktiivsem $x^*$ , siis kiltkivi seisund omab. [5,6]

Muud tüüpi piirangu täpsustus siiski olemas, Kuid need kolm tunduvad olevat kõige enam levinud KKT kvalifikatsioon.

[1] Kuhn, H. ja Tucker, A., “Mittelineaarne Programmeerimine” Proceedings of the 2. Berkeley sümpoosion 1951, pp. 481-492.
[2] Karush, W., “Miinimumid ülesanded mitme muutuja koos ebavõrdsuse poole kitsendustega”. M. Sc. Väitekiri, Univ. of Chicago, Chicago, Il, 1939.
[3] Kuhn, M. “Karush-Kuhni-Tuckeri theorema”, Internet: http://smp.if.uj.edu.pl/~kopiec/MT/Materialy/KarushKuhnTucker.pdf, CDSEM Uni. Mannheim, 2006.
[4]McCarl, B. ja Spreen, T., “Mittelineaarsete Optimization tingimused”, Ch. 12, Applied Mathematical programmeerimine kasutades Algebraic Systems. Internet: http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/thebook.pdf
[5]Eustaquio, R. Karas, E. ja Ribeiro, A. Constraint kvalifitseerimine Mittelineaarne Programmeerimine, Tech Report, Univ. Parana.
[6] Saabuma, D. ja Zalinescu, C. “Vajalikkuse kohta mõned Constraint Kvalifikatsioonikeskus Tingimused Kumer Programming”, Journal of Kumer Analysis, 11 (1), 2004. pp 95-110.

Computer Science and Teaching Journal

Viimased postitused

Karush-Kuhni-Tuckeri tingimused

Constraint Kvalifikatsioonikeskus