kReese.net

Den Karush-Kuhn-Tucker (KKT) vilkår, undertiden benævnt Kuhn-Tucker betingelser, er betingelserne, at en ikke-lineær programmering problem, skal opfylde for at være optimal. Den KKT betingelser udvider metoden til Lagrange multiplikatorer ved at tillade ulighed begrænsninger, i modsætning til den Lagrange multiplikatorer, som kun tillader lighed begrænsninger.

Lad os betragte en ikke-lineær optimering problem:

Minimer $f(x)$
omfattet af: $g_{i}(x)\leq 0 \\ h_{j}(x) = 0$

Vi vil lade $x^{*}$ udgør en relativ mindst for vores problem, som også opfylder nogle tvang kvalifikation. Med denne, så kan vi antage, at for hvert element der findes en vektor $\lambda_j \left ( j = 1, \ldots, l \right )$ , hvor den repræsenterer antallet af lighed begrænsninger, og $\mu_i\left ( i = 1, \ldots, m \right )$ , hvor m repræsenterer antallet af ulighed begrænsninger. Disse konstanter, $\lambda_j$ og $\mu_i$ , kaldes KKT multiplikatorer.

For at KKT betingelser, som skal afholdes i en ikke-lineær programmering problem (NLP), så hver af de tre betingelser skal være opfyldt [1-4]. Den Primal feasibility gentager, hvad problemet stater, , at ulighed og lighed begrænsninger på $x^*$ skal være opfyldt, for det problem at være optimal:

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

Den anden betingelse er kendt som den dobbelte feasibility tilstand. I denne tilstand stater, snarere verbosely, at ethvert element i $\mu_i$ skal være større end nul, og at stationaritet af problemet skal være lig med 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)}$

Den stationaritet af problemet er:

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

Mens de to andre er simpelthen forhold, der l og m skal opfylde, for at $x^*$ være optimal.

Den tredje betingelse, der skal opfyldes, er kendt som et supplement slaphed. Denne betingelse blot, at for hver MU og dets respektive ulighed tvang, produktet af de to skal resultere i nul:

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

Når disse tre betingelser er opfyldt, vi har mødt de KKT betingelser og vores løsning, $x^*$ , er en optimal løsning for NLP problemet. Der måske mere end én x i det rum, som opfylder betingelserne. Ethvert punkt i problemet rum, hvor ethvert element aflogm, sådan, at tuple (x, l, m) opfylder KKT betingelser kaldes KKT punkter. Udledningen af disse begrænsninger kan findes i [1,2]

Constraint Kvalifikationer

Som tidligere nævnt, de punkter, vi tester nødt til at møde nogle kvalifikationer, for det punkt, der skal overvejes. Den mest kendte begrænsning Kvalifikation er den lineære Independence begrænsning Kvalifikation (Licq), der blot hedder, at $h_{j}(x^*)$ og $g_{i}(x^*)$ er lineært uafhængige fra de øvrige i punkt $x^*$ . Den Mangasarian-Fromovitz begrænsning kvalifikation (MFCQ) stater Tilsvarende LICQ med tilføjelse af at være positiv-lineraly uafhængig på $x^*$ . [5]

Der er dog andre begrænsninger qualifiers at slappe af LICQ. Den Slater begrænsning kvalifikationskamp kan bruges i konveks problemer. Hvis der findes et punkt x, således at $h_{j}(x^*) =$ og $g_{i}(x^*) < 0$ for alle i,j aktive i $x^*$ , så skifer tilstand besidder. [5,6]

Andre typer af tvang kvalifikationskampe findes, men disse tre synes at være de mest almindeligt anvendte i KKT kvalifikation.

[1] Kuhn, H. og Tucker, A., “Nonlinear Programming” Afvikling af 2. Berkeley Symposium 1951, pp. 481-492.
[2] Karush, W., “Minima for funktioner af flere variable med uligheder Side begrænsninger”. M. Sc. Dissertation, Univ.. af Chicago, Chicago, Den, 1939.
[3] Kuhn, M. “Den Karush-Kuhn-Tucker theorema”, Internet: http://smp.if.uj.edu.pl/~kopiec/MT/Materialy/KarushKuhnTucker.pdf, Uni CDSEM. Mannheim, 2006.
[4]McCarl, B. og Spreen, T., “Nonlinear Optimization Betingelser”, Ch. 12, Anvendt Matematisk programmering med algebraiske systemer. Internet: http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/thebook.pdf
[5]Eustaquio, R. Karas, E. og Ribeiro, En. Constraint Kvalifikation til Nonlinear Programming, Tech Rapport, Univ.. of Parana.
[6] Arrive, D. og Zalinescu, C. “Om nødvendigheden af nogle Constraint Kvalifikation Forholdene i Konveks Programmering”, Journal of Konveks Analyse, 11 (1), 2004. pp 95-110.

En Computer Science and Teaching Tidende

Seneste indlæg

Karush-Kuhn-Tucker betingelser

Constraint Kvalifikationer