Condições de Karush-Kuhn-Tucker

Em otimização, as Condições de Karush-Kuhn-Tucker (também conhecidas como Condições de Kuhn-Tucker ou condições KKT) são condições de primeira ordem para que uma solução de um problema de programação não linear seja ótima, desde que valham condições chamadas de condições de qualificação ou, em inglês, constraint qualifications. Permitindo restrições de desigualdade, as condições KKT generalizam, na programação não linear, o método de multiplicadores de Lagrange, que permite somente restrições de igualdade. O sistema de equações e inequações correspondente às condições KKT em geral não é resolvido diretamente, exceto em alguns casos especiais onde uma solução pode ser obtida analiticamente. Nos demais casos, diversos algoritmos de otimização podem ser usados para resolver numericamente o sistema.

As condições KKT foram originalmente nomeadas após Harold W. Kuhn e Albert W. Tucker, que primeiro publicaram essas condições em 1951.^[1] Porém, estudiosos posteriores descobriram que as condições necessárias para esse problema já haviam sido ditadas por William Karush em sua tese de mestrado em 1939.^[2][3]

O problema

Seja o seguinte problema de otimização não-linear (também conhecido como PNL):

${\displaystyle (PNL){\begin{cases}\min \limits _{x}&f(x)\\{\text{sujeito a}}&g_{i}(x)\leq 0\\&h_{j}(x)=0\end{cases}}}$

onde

${\displaystyle x\in \mathbb {R} ^{n}}$ é a variável de otimização,

${\displaystyle f(x)}$ é a função a ser minimizada (chamada também de função objetivo),

${\displaystyle g_{i}(x)}$, com ${\displaystyle i=1,2,...,m}$ são as restrições de desigualdade,

${\displaystyle h_{j}(x)}$, com ${\displaystyle j=1,2,...,l}$ são restrições de igualdade,

sendo ${\displaystyle m}$ e ${\displaystyle l}$ as quantidades de restrições de desigualdade e igualdade, respectivamente.

Condições necessárias

Seja um PNL definido como na seção acima. Seja também o operador Lagrangeano ${\displaystyle L:\mathbb {R} ^{n}\times \mathbb {R} ^{m}\times \mathbb {R} ^{l}\rightarrow \mathbb {R} }$ definido como:

${\displaystyle L(x,\mu ,\lambda )=f(x)+\sum _{i=1}^{m}\mu _{i}g_{i}(x)+\sum _{j=1}^{l}\lambda _{j}h_{j}(x)}$

Suponha que a função objetivo ${\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ e as restrições ${\displaystyle g_{i}:\,\!\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ e ${\displaystyle h_{j}:\,\!\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ sejam continuamente diferenciáveis em um ponto ${\displaystyle x^{*}}$.

Se ${\displaystyle x^{*}}$ é um mínimo local para ${\displaystyle f}$ e o PNL satisfaz algumas condições de regularidade então existem constantes ${\displaystyle \mu _{i}}$ com ${\displaystyle i=1,2,...,m}$ e ${\displaystyle \lambda _{j}}$ com ${\displaystyle j=1,2,...,l}$, chamadas de multiplicadores KKT tais que^[4]:

Estacionariedade

${\displaystyle \nabla f(x^{*})+\sum _{i=1}^{m}\mu _{i}\nabla g_{i}(x^{*})+\sum _{j=1}^{l}\lambda _{j}\nabla h_{j}(x^{*})=0}$ ^{[Demonstração 1][5]}

Folga complementar

${\displaystyle \mu _{i}g_{i}(x^{*})=0}$ para todo ${\displaystyle i=1,2,...,m}$ ^{[Demonstração 2][5]}

Viabilidade primal

${\displaystyle g_{i}(x^{*})\leq 0}$ para todo ${\displaystyle i=1,2,...,m}$

${\displaystyle h_{j}(x^{*})=0}$ para todo ${\displaystyle j=1,2,...,l}$^[5]

Viabilidade dual

${\displaystyle \mu _{i}\geq 0}$ para todo ${\displaystyle i=1,2,...,m}$^[5]

As restrições ${\displaystyle g_{i}(x)\,}$ em que ${\displaystyle g_{i}(x^{*})=0\,}$ são chamadas restrições ativas em ${\displaystyle x^{*}}$.

No caso particular em que ${\displaystyle m=0}$, isto é, não há nenhuma restrição de desigualdade, as condições KKT se transformam nas condições de Lagrange e os multiplicadores KKT são chamados multiplicadores de Lagrange.

Se algumas das funções não são diferenciáveis, versões subdiferenciáveis das condições KKT estão disponíveis.^[6]

Condições suficientes

Em alguns casos, as condições necessárias são também suficientes para otimalidade, mas em geral, isso não ocorre e informações adicionais são necessárias, como as condições suficientes de segunda ordem. Para funções suaves, essas condições envolvem as segundas derivadas, o que explica seu nome.

As condições necessárias são suficientes para otimalidade se a função objetivo ${\displaystyle f}$ de um problema de maximização é uma função côncava, as restrições de desigualdade ${\displaystyle g_{j}}$ são funções convexas continuamente diferenciáveis e as restrições de igualdade ${\displaystyle h_{i}}$ são funções afim.

H.D. Martin provou em 1985 que a ampla classe de funções em que as condições KKT garantem a otimalidade global é chamada funções invexas tipo 1.^[7][8]

Condições suficientes de segunda ordem

Para problemas não-lineares suaves, uma condição suficiente de segunda ordem é dada como segue:

Considere ${\displaystyle x^{*}}$, ${\displaystyle \lambda ^{*}}$, ${\displaystyle \rho ^{*}}$ que achem um mínimo local usando as condições KKT. Com ${\displaystyle \rho ^{*}}$ tal que a complementaridade estrita é mantida em ${\displaystyle x^{*}}$ (i.e. todo ${\displaystyle \rho _{i}>0}$), então para todo ${\displaystyle s\neq 0}$ tal que

${\displaystyle \left[{\frac {\delta g(x^{*})}{\delta x}},{\frac {\delta h(x^{*})}{\delta x}}\right]^{T}s=0}$

A seguinte equação deve se manter: ${\displaystyle s'\nabla _{xx}^{2}L(x^{*},\lambda ^{*},\rho ^{*})s\geq 0}$

Se a condição acima é satisfeita estritamente, a função é estritamente restrita a um mínimo local.

Demonstrações

Referências