kReese.net

O Karush-Kuhn-Tucker (EZ) condições, por vezes referido como as condições de Kuhn-Tucker, são as condições que um problema de programação não-linear necessidade de cumprir, a fim de ser o ideal. O KKT condições estende o método dos multiplicadores de Lagrange, permitindo restrições de desigualdade, ao contrário do Multiplicadores de Lagrange, que só permitem restrições de igualdade.

Vamos considerar um problema de otimização não-linear:

Minimizar $f(x)$
sujeito a: $g_{i}(x)\leq 0 \\ h_{j}(x) = 0$

Vamos deixar $x^{*}$ representam um ponto mínimo relativo para o nosso problema, que também satisfaz alguma restrição de qualificação. Com este, então podemos assumir que para cada elemento existe um vetor $\lambda_j \left ( j = 1, \ldots, l \right )$ , onde o representa o número de restrições de igualdade, e $\mu_i\left ( i = 1, \ldots, m \right )$ , onde m representa o número de restrições desigualdade. Essas constantes, $\lambda_j$ e $\mu_i$ , são chamados de multiplicadores de KKT.

Para que as condições KKT a ser realizada em um problema de programação não-linear (PNL), então cada uma das três condições devem ser atendidas [1-4]. O Primal reafirma viabilidade que o problema estados, que a desigualdade e as restrições de igualdade na $x^*$ devem ser atendidos para que o problema a ser óptimo:

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

A segunda condição é conhecida como condição de viabilidade dupla. Nesta condição estados, vez com detalhes, que cada elemento em $\mu_i$ deve ser maior que zero, e que a estacionaridade do problema deve ser igual a 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)}$

A estacionaridade do problema é:

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

Enquanto os outros dois são simplesmente condições que l e m deve atender a fim de $x^*$ para ser o ideal.

A terceira condição que deve ser atendida é conhecido como slackness complementares. Esta condição indica simplesmente que para cada mu e seus respectivos restrição de desigualdade, o produto das duas deve resultar em zero:

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

Quando estas três condições forem satisfeitas, temos reunidas as condições KKT e nossa solução, $x^*$ , é uma óptima solução para o problema de PNL. Há talvez mais de uma x no espaço que satisfaçam as condições. Qualquer ponto do espaço do problema, onde cada elemento dalem, tal que a tupla (x, l, m) satisfazer as condições KKT são chamados pontos KKT. Derivação destas restrições pode ser encontrada em [1,2]

Qualificações restrição

Como mencionado anteriormente, os pontos que estamos testando necessidade de cumprir alguma qualificação para que o ponto a ser considerado. O mais Qualificação restrição bem conhecido é o de Qualificação restrição Linear Independência (Licq), que simplesmente afirma que $h_{j}(x^*)$ e $g_{i}(x^*)$ são linearmente independentes entre si no ponto $x^*$ . A qualificação restrição Mangasarian-Fromovitz (MFCQ) estados da mesma forma o licq com a adição de ser positiva lineraly independente em $x^*$ . [5]

Existem no entanto outros qualificadores restrição que relaxam o licq. O qualificador de restrição Slater pode ser usado em problemas convexos. Se existe um x tal ponto que $h_{j}(x^*) =$ e $g_{i}(x^*) < 0$ para todos os i,j ativo em $x^*$ , então a condição de ardósia detém. [5,6]

Outros tipos de restrição não existem qualificadores, mas esses três parecem ser os mais comumente usados em KKT qualificação.

[1] Kuhn, H. e Tucker, A., “Programação não-linear” Proceedings do 2 º Simpósio de Berkeley 1951, pp. 481-492.
[2] Karush, W., “Minima de Funções de Várias Variáveis com Restrições de Desigualdades como Side”. M. Sc. Dissertação, Univ. de Chicago, Chicago, O, 1939.
[3] Kuhn, M. “O Theorema Karush-Kuhn-Tucker”, Internet: http://smp.if.uj.edu.pl/~kopiec/MT/Materialy/KarushKuhnTucker.pdf, CDSEM Uni. Mannheim, 2006.
[4]McCarl, B. e Spreen, T., “Condições não-linear Otimização”, Ch. 12, Programação Matemática Aplicada Usando sistemas algébricos. Internet: http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/thebook.pdf
[5]Eustaquio, R. Karas, E. e Ribeiro, A. Qualificação restrição para Programação Não Linear, Tech Report, Univ. do Paraná.
[6] Chegar, D. e Zalinescu, C. “Sobre a necessidade de algumas condições de restrição de Qualificação em Programação Convexa”, Journal of Convex Analysis, 11 (1), 2004. pp 95-110.

A Ciência da Computação e Jornal Ensino

Mensagens recentes

Karush-Kuhn-Tucker Condições

Qualificações restrição