kReese.net

An Karush-Kuhn-Tucker (KKT) coinníollacha, uaireanta dá ngairtear na coinníollacha Kuhn-Tucker, Is iad na coinníollacha nach mór fadhb Clárú Nonlinear chun freastal d'fhonn a bheith is fearr is féidir. Is iad na coinníollacha KKT Síneann an modh iolraitheoirí Lagrangian trí chead a thabhairt do srianta éagothroime, le hais an iolraitheoirí Lagrange a ligeann ach srianta comhionannais.

Lig dúinn machnamh ar fhadhb leas iomlán a bhaint nonlinear:

Íoslaghdaigh $f(x)$
faoi réir ag: $g_{i}(x)\leq 0 \\ h_{j}(x) = 0$

Cuirfimid in iúl $x^{*}$ ionadaíocht a dhéanamh pointe a laghad i gcoibhneas le haghaidh ár fhadhb, a chomhlíonann freisin roinnt cáilíocht shriantacht. Leis an, ansin is féidir linn glacadh leis gur le haghaidh gach gné ar ann do veicteoir $\lambda_j \left ( j = 1, \ldots, l \right )$ , i gcás ina an Is ionann líon na srianta comhionannais, agus $\mu_i\left ( i = 1, \ldots, m \right )$ , i gcás ina m Is ionann líon na srianta éagothroime. Tá na tairisigh, $\lambda_j$ agus $\mu_i$ , Tugtar iolraitheoirí KKT.

Chun na coinníollacha a bheidh ar siúl i KKT fadhb cláir nonlinear (NLP), ansin ní mór gach ceann de na trí choinníoll a chomhlíonadh [1-4]. Athluann an Féidearthachta Primal cad a deir an fhadhb, go bhfuil na srianta éagothroime agus comhionannais ar $x^*$ ní mór iad a chomhlíonadh chun an fhadhb a bheith is fearr is féidir:

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

Is é an dara coinníoll a dtugtar an coinníoll féidearthachta dé. Sa stáit coinníoll, in áit verbosely, go bhfuil gach gné i $\mu_i$ Ní mór a bheith níos mó ná nialas, agus go gcaithfidh an stationarity an fhadhb a bheith comhionann le 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)}$

Is é an stationarity na faidhbe:

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

Cé go bhfuil an dá cheann eile ach coinníollacha go l agus m Ní mór a chomhlíonadh d'fhonn $x^*$ is fearr is féidir a bheith.

Is é an tríú coinníoll nach mór a shásamh ar a dtugtar slackness comhlántach. Deir an coinníoll seo ach gur le haghaidh gach mú agus a shriantacht éagothroime faoi seach, Ba chóir an táirge ar an dá thoradh náid:

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

Nuair a bheidh na trí choinníoll go gcomhlíontar, ní mór dúinn leis na coinníollacha KKT agus ár réiteach, $x^*$ , Tá réiteach is fearr le haghaidh an fhadhb NLP. Tá b'fhéidir níos mó ná aon x sa spás freastal ar a bhfuil na coinníollacha. Aon phointe sa spás ina fhadhb gach gné delagusm, den sórt sin go bhfuil an tuple (x, l, m) na coinníollacha KKT a dtugtar pointí KKT. Is féidir le díorthú de na srianta seo a fháil i [1,2]

Cáilíochtaí shriantacht

Mar a luadh cheana, Ní mór na pointí go bhfuil muid ag tástáil chun freastal ar roinnt cáilíochta d'fhonn an pointe a bheidh le breithniú. Is é an srian Cáilíocht an chuid is mó ar eolas go maith leis an srian Cáilíocht Líneach Neamhspleáchas (LICQ), a deir go simplí go $h_{j}(x^*)$ agus $g_{i}(x^*)$ Tá líneach neamhspleách ar an taobh eile ag an bpointe $x^*$ . An cháilíocht srian Mangasarian-Fromovitz (MFCQ) Deir an dul céanna LICQ leis an Chomh maith a bheith dearfach-lineraly neamhspleách ar $x^*$ . [5]

Tá, áfach, cailitheoirí srian eile a scíth a ligean an LICQ. Is féidir leis an qualifier srian Slater a úsáid i fadhbanna a dronnach. Má ar ann do x pointe sin go $h_{j}(x^*) =$ agus $g_{i}(x^*) < 0$ do gach duine i,j gníomhach i $x^*$ , ansin tá an coinníoll sclátaí. [5,6]

Dhéanamh Cineálacha eile cailitheoirí srianta ann, ach dealraíonn sé na trí a bheith ar an chuid is mó a úsáidtear go coitianta i KKT cáilíocht.

[1] Kuhn, H. agus Tucker, A., “Clárú Nonlinear” Imeachtaí ar an 2ú Berkeley Siompóisiam 1951, pp. 481-492.
[2] Karush, W., “Minima de Feidhmeanna Athróga roinnt le Éagothroime mar Srianta Taobh”. M.Sc. Tráchtas, Univ. de Chicago, Chicago, An, 1939.
[3] Kuhn, M. “An théorème Karush-Kuhn-Tucker”, Idirlíon: http://smp.if.uj.edu.pl/~kopiec/MT/Materialy/KarushKuhnTucker.pdf, CDSEM Uni. Mannheim, 2006.
[4]McCarl, B. agus Spreen, T., “Coinníollacha Optimization Nonlinear”, Ch. 12, Cláir Fheidhmeacha Matamaitice Ag baint úsáide as Córais ailgéabracha. Idirlíon: http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/thebook.pdf
[5]Eustace, R. Karas, E. agus Ribeiro, A. Cáilíocht srian le haghaidh Chláir Nonlinear, Tech Tuarascáil, Univ. de Paraná.
[6] Teacht, D. agus Zalinescu, C. “Ar an Riachtanas ar roinnt Coinníollacha Cáilíocht Srianta i gClárú dronnach”, Journal of Anailís dronnach, 11 (1), 2004. pp 95-110.

A Eolaíocht Ríomhaireachta agus Oifigiúil Teagaisc

Poist is Déanaí

Karush-Kuhn-Tucker Coinníollacha

Cáilíochtaí shriantacht