Condições de Karush-Kuhn-Tucker

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Na matemática, as Condições de Karush-Kuhn-Tucker (também conhecidas por Kuhn-Tucker ou por condições KKT) são condições necessárias para que uma solução em problemas de programação não-linear seja ótima, dado que ela satisfaz determinadas condições de regularidade. Elas são uma generalização do método dos multiplicadores de Lagrange.

O problema[editar | editar código-fonte]

Seja o seguinte problema de otimização não-linear:

 \min\limits_{x}\;\; f(x)
 \mbox{sujeito a: }
\begin{array}{ccc} g_i(x) &\le& 0 \\ h_j(x) &=& 0 \end{array}

em que f(x) é uma função a ser minimizada (chamada, neste contexto, de função objetivo), g_i (x)\ (i = 1, \ldots,m) são restrições de desigualdade h_j (x)\ (j = 1,\ldots,l) são restrições de igualdade, sendo m e l a quantidade de restrições de desigualdade e igualdade, respectivamente.

As condições necessárias para se resolver este problema foram inicialmente publicadas na Tese de Mestrado de William Karush[1] , mas elas tornaram-se conhecidas depois de apresentadas por Harold W. Kuhn e Albert W. Tucker.[2]


Searchtool.svg
Esta página ou secção foi marcada para revisão, devido a inconsistências e/ou dados de confiabilidade duvidosa. Se tem algum conhecimento sobre o tema, por favor verifique e melhore a consistência e o rigor deste artigo. Pode encontrar ajuda no WikiProjeto Matemática.

Se existir um WikiProjeto mais adequado, por favor corrija esta predefinição. Este artigo está para revisão desde dezembro de 2009.

Condições necessárias[editar | editar código-fonte]

Seja x* um mínimo local que satisfaz determinadas condições de regularidade (listadas abaixo), e que, numa vizinhança de x*, a função objetivo f : \mathbb{R}^n \rightarrow \mathbb{R} e as restrições g_i : \,\!\mathbb{R}^n \rightarrow \mathbb{R} e h_j : \,\!\mathbb{R}^n \rightarrow \mathbb{R} sejam de classe C1 (ou seja, diferenciáveis e as derivadas parciais são contínuas).

Então existem constantes \mu_i\ (i = 1,\ldots,m) e \lambda_j\ (j = 1,...,l) tais que: [3]

\nabla f(x^*) + \sum_{i=1}^m \mu_i \nabla g_i(x^*) + \sum_{j=1}^l \lambda_j \nabla h_j(x^*) = 0,
\mu_i \ge 0\ (i = 1,\ldots,m)
g_i(x^*) \le 0, \mbox{ para todo } i = 1, \ldots, m
 h_j(x^*) = 0, \mbox{ para todo } j = 1, \ldots, l
\mu_i g_i (x^*) = 0\; \mbox{ para todo }\; i = 1,\ldots,m.

Diz-se que as restrições g_i(x)\, em que g_i(x^*) = 0\, são restrições ativas.

Exemplo[editar | editar código-fonte]

Consideremos o problema de determinar o ponto no espaço de três dimensões mais próximo da origem, que tenha coordenadas não-negativas e que pertença ao plano z = 4x + 3y - 24\,. É fácil ver que este plano corta o plano z = 0\, na linha 4x + 3y = 24\,, e que ele sobe a partir daí, portanto a solução minimizadora deve estar localizada nesta linha.

Resolvendo o problema por KKT:

  • f(x,y,z) = x^2 + y^2 + z^2\, - função objetivo
  • h(x,y,z) = 4 x + 3y - z - 24\,
  • g_1(x,y,z) = -x\,
  • g_2(x,y,z) = -y\,
  • g_3(x,y,z) = -z\,

Portanto as condições KKT se escrevem:

  • 2x  - \mu_1 + 4 \lambda = 0\,
  • 2y  - \mu_2 + 3 \lambda = 0\,
  • 2z  - \mu_3 - \lambda = 0\,
  • \mu_1 \ge 0\,
  • \mu_2 \ge 0\,
  • \mu_3 \ge 0\,
  • -x \le 0\,
  • -y \le 0\,
  • -z \le 0\,
  • 4 x + 3 y - z - 24 = 0\,
  •  \mu_1 x = 0\,
  •  \mu_2 y = 0\,
  •  \mu_3 z = 0\,

Das relações  \mu_1 x = 0\, e  \mu_2 y = 0\,, suponha-se que x = y = 0\,. Neste caso, temos que z = -24\,, contradizendo z \ge 0\,.

Supondo x = 0\,, portanto, conclui-se que \mu_2 = 0\,, mas isto junto com 2x - \mu_1 + 4 \lambda = 0\, e 2y  - \mu_2 + 3 \lambda = 0\, conclui que 0 \le \mu_1/4 = \lambda = -2y/3 \le 0, ou seja, y = 0\, (contradição).

Analogamente, com y = 0\, conclui-se a contradição x = 0\,.

Portanto, o único resultado possível para  \mu_1 x = 0\, e  \mu_2 y = 0\, é o caso \mu_1 = \mu_2 = 0\,.

Deste modo, \lambda <0\,, logo por 2z  - \mu_3 - \lambda = 0\,, temos que \mu_3 = 2z - \lambda > 2z \ge 0\,, portanto, como \mu_3 > 0\, de  \mu_3 z = 0\, temos que z = 0\,.

Finalmente, eliminando do sistema as variáveis que são zero (z, &mu1 e &mu2), chega-se ao sistema:

  • 2x  + 4 \lambda = 0\,
  • 2y  + 3 \lambda = 0\,
  • - \mu_3 - \lambda = 0\,
  • 4 x + 3 y = 24\,

Cuja solução (x, y, \lambda, \mu_3) = (96/25, 72/25, -48/25, 48/25)\, satisfaz às inequações iniciais.

Logo, a resposta é o ponto (x,y,z) = (96/25, 72/25, 0)\,.

Referências

  1. "".. Disponível em http://wwwlib.umi.com/dxweb/details?doc_no=7371591 (com o pagamento de uma taxa)
  2. Kuhn, H. W.; Tucker, A. W. (1951). "Nonlinear programming". Proceedings of 2nd Berkeley Symposium: 481-492, Berkeley: University of California Press. 
  3. The Karush-Kuhn-Tucker Theorem. Visitado em 2008-03-11.

Outras referências[editar | editar código-fonte]

  • J. Nocedal, S. J. Wright, Numerical Optimization. Springer Publishing. ISBN 978-0-387-30303-1.
  • Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
  • R. Andreani, J. M. Martínez, M. L. Schuverdt, On the relation between constant positive linear dependence condition and quasinormality constraint qualification. Journal of Optimization Theory and Applications, vol. 125, no2, pp. 473–485 (2005).
  • Jalaluddin Abdullah, Optimization by the Fixed-Point Method, Version 1.97. [1].