kReese.net

Mae'r Karush-Kuhn-Tucker (EZ) amodau, cyfeirir ato weithiau fel yr amodau Kuhn-Tucker, yw'r amodau y broblem Rhaglennu aflinol angen i gwrdd er mwyn bod yn orau. Mae'r amodau KKT yn ymestyn y dull lluosyddion Lagrangian drwy ganiatáu i gyfyngiadau anghydraddoldeb, yn hytrach na'r Lluosyddion Lagrange sydd ond yn caniatáu cyfyngiadau cydraddoldeb.

Gadewch i ni ystyried yn broblem Optimization aflinol:

Lleihau'r $f(x)$
yn amodol ar: $g_{i}(x)\leq 0 \\ h_{j}(x) = 0$

Byddwn yn gadael i $x^{*}$ cynrychioli man lleiaf cymharol ar gyfer ein problem, sydd hefyd yn bodloni rhai amodau cyfyngiad. Gyda hyn, yna gallwn dybio bod ar gyfer pob elfen bod yna fector $\lambda_j \left ( j = 1, \ldots, l \right )$ , lle y cynrychioli nifer y cyfyngiadau cydraddoldeb, a $\mu_i\left ( i = 1, \ldots, m \right )$ , lle m cynrychioli nifer y cyfyngiadau anghydraddoldeb. Mae'r rhain yn Cysonion, $\lambda_j$ a $\mu_i$ , yn cael eu galw lluosyddion KKT.

Er mwyn i'r amodau KKT i'w gynnal yn broblem rhaglennu aflinol (NLP), yna rhaid i bob un o dri amodau yn cael eu diwallu [1-4]. Mae'r ailddatgan Ddichonoldeb gysefin beth yw'r broblem yn datgan, bod yr anghydraddoldeb a'r cyfyngiadau cydraddoldeb ar $x^*$ rhaid eu bodloni er mwyn i'r broblem gael ei orau:

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

Yr ail amod ei adnabod fel y cyflwr dichonoldeb deuol. Yn y cyflwr yn datgan, yn hytrach verbosely, bod pob elfen yn y $\mu_i$ Rhaid i fod yn fwy na sero, a bod yn rhaid i'r stationarity y broblem fod yn hafal i 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)}$

Mae stationarity y broblem yn:

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

Er bod y ddau arall yn syml amodau y mae'n l a m Mae'n rhaid bodloni er mwyn i $x^*$ gorau i fod yn.

Y trydydd amod y mae'n rhaid eu bodloni ei adnabod fel slackness cyflenwol. Mae'r cyflwr hwn yn syml yn datgan bod ar gyfer pob mu a'r cyfyngiad priodol anghydraddoldeb, Dylai y cynnyrch y ddau yn arwain at sero:

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

Pan fydd y tri amodau yn cael eu bodloni, rydym wedi cwrdd â'r amodau KKT a'n ateb, $x^*$ , yn ateb gorau ar gyfer y broblem NLP. Mae yna efallai mwy nag un x yn y gofod sy'n bodloni'r amodau. Unrhyw bwynt yn y gofod broblem lle mae pob elfen olam, fel bod y tuple (x, l, m) bodloni'r amodau KKT yn cael eu galw'n bwyntiau KKT. Gall tarddiad y cyfyngiadau hyn i'w gweld yn [1,2]

Cyfyngu Cymwysterau

Fel y soniwyd yn flaenorol, y pwyntiau ein bod yn profi angen i ni gwrdd â rhai cymwysterau er mwyn i'r pwynt gael ei ystyried. Y mwyaf Cymhwyster cyfyngiad adnabyddus yw Cymhwyster Annibyniaeth cyfyngiad llinol (Licq), sydd yn syml yn datgan bod $h_{j}(x^*)$ a $g_{i}(x^*)$ yn llinol annibynnol ar y llall ar bwynt $x^*$ . Mae'r cymhwyster cyfyngiad Mangasarian-Fromovitz (MFCQ) Dywed yr un modd y LICQ gan ychwanegu bod yn gadarnhaol-lineraly annibynnol yn $x^*$ . [5]

Mae yna, fodd bynnag rhagbrofol gyfyngiad arall y ymlacio y LICQ. Gall y rhagbrofol Slater cyfyngiad yn cael ei ddefnyddio mewn problemau amgrwm. Os oes yn bodoli x pwynt fel bod $h_{j}(x^*) =$ a $g_{i}(x^*) < 0$ ar gyfer yr holl ff,g weithredol yn $x^*$ , yna bydd y cyflwr llechi yn cynnal. [5,6]

Mathau eraill o rhagbrofol cyfyngiad yn bodoli, ond y tri yn ymddangos i fod y rhai mwyaf cyffredin a ddefnyddir yn y KKT cymhwyster.

[1] Kuhn, H. a Tucker, A., “Rhaglennu aflinol” Trafodion y 2 Berkeley Symposiwm 1951, tt. 481-492.
[2] Karush, W., “Minima Swyddogaethau o nifer o Newidynnau ag Anghydraddoldebau fel Cyfyngiadau Ochr”. M. Sc. Traethawd Hir, Univ. o Chicago, Chicago, Mae'r, 1939.
[3] Kuhn, M. “Mae'r theorema Karush-Kuhn-Tucker”, Rhyngrwyd: http://smp.if.uj.edu.pl/~kopiec/MT/Materialy/KarushKuhnTucker.pdf, CDSEM Uni. Mannheim, 2006.
[4]McCarl, B. a Spreen, T., “Amodau Optimization aflinol”, Ch. 12, Rhaglennu Cymhwysol Mathemategol Defnyddio Systemau Algebraidd. Rhyngrwyd: http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/thebook.pdf
[5]Eustaquio, R. Karas, Mae'n. a Ribeiro, A. Cymhwyster cyfyngiad ar gyfer Rhaglennu aflinol, Adroddiad Tech, Univ. o Paraná.
[6] Cyrraedd, D. a Zalinescu, C. “Ar y Rheidrwydd rhai Amodau Cyfyngiadau Cymhwyster mewn Rhaglennu amgrwm”, Journal of amgrwm Dadansoddi, 11 (1), 2004. tt 95-110.

Mae Cyfrifiadureg a Journal Addysgu

Swyddi diweddar

Karush-Kuhn-Tucker Amodau

Cyfyngu Cymwysterau