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):

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

onde

x\in \mathbb {R} ^{n}

é a variável de otimização,

f(x)

é a função a ser minimizada (chamada também de função objetivo),

g_{i}(x)

, com

i=1,2,...,m

são as restrições de desigualdade,

h_{j}(x)

, com

j=1,2,...,l

são restrições de igualdade,

sendo $m$ e $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 $L:\mathbb {R} ^{n}\times \mathbb {R} ^{m}\times \mathbb {R} ^{l}\rightarrow \mathbb {R}$ definido como:

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 $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 continuamente diferenciáveis em um ponto $x^{*}$ .

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

Estacionariedade

\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

\mu _{i}g_{i}(x^{*})=0

para todo

i=1,2,...,m

^{[Demonstração 2]}^[5]

Viabilidade primal

g_{i}(x^{*})\leq 0

para todo

i=1,2,...,m

h_{j}(x^{*})=0

para todo

j=1,2,...,l

^[5]

Viabilidade dual

\mu _{i}\geq 0

para todo

i=1,2,...,m

^[5]

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

No caso particular em que $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 $f$ de um problema de maximização é uma função côncava, as restrições de desigualdade $g_{j}$ são funções convexas continuamente diferenciáveis e as restrições de igualdade $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 $x^{*}$ , $\lambda ^{*}$ , $\rho ^{*}$ que achem um mínimo local usando as condições KKT. Com $\rho ^{*}$ tal que a complementaridade estrita é mantida em $x^{*}$ (i.e. todo $\rho _{i}>0$ ), então para todo $s\neq 0$ tal que

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

A seguinte equação deve se manter: $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

↑ Se $x^{*}$ é um minimizador local para $f$ (e consequentemente para $L$ ), então o gradiente de $L$ deve ser nulo em $x^{*}$ . Isto é:
$\nabla L(x^{*},\mathbf {\mu } ,\mathbf {\lambda } )=0$

$f(x^{*})+\sum _{i=1}^{m}\mu _{i}g_{i}(x^{*})+\sum _{j=1}^{l}\lambda _{j}h_{j}(x^{*})=0$
↑
Com as suposições e resultados da primeira condição de KKT obtém-se que:
- $\nabla f(x^{*})=0$ (o gradiente da função objetivo no mínimo local é nulo) e;
- $\sum _{j=1}^{l}\lambda _{j}h_{j}(x^{*})=0$ (por conta da viabilidade primal).
Portanto:
- $f(x^{*})+\sum _{i=1}^{m}\mu _{i}g_{i}(x^{*})+\sum _{j=1}^{l}\lambda _{j}h_{j}(x^{*})=0\rightarrow \sum _{i=1}^{m}\mu _{i}g_{i}(x^{*})=0$
Como $g_{i}(x^{*})\leq 0$ $g_{i}(x^{*})\leq 0$ e $\mu _{i}\geq 0$ $\mu _{i}\geq 0$ (viabilidade dual), $\mu _{i}g_{i}(x^{*})\leq 0$ $\mu _{i}g_{i}(x^{*})\leq 0$ para todo $i=1,2,...,m$ $i=1,2,...,m$ .
Logo, $\sum _{j=1}^{l}\lambda _{j}h_{j}(x^{*})=0$ $\sum _{j=1}^{l}\lambda _{j}h_{j}(x^{*})=0$ só é verdadeiro se $\mu _{i}g_{i}(x^{*})=0$ $\mu _{i}g_{i}(x^{*})=0$ para todo $i=1,2,...,m$ $i=1,2,...,m$ .

Referências

↑ Kuhn, H. W.; Tucker, A. W. (1951). «Nonlinear programming». Proceedings of 2nd Berkeley Symposium. Berkeley: University of California Press. pp. 481–492
↑ W. Karush (1939). «Minima of Functions of Several Variables with Inequalities as Side Constraints». Dept. of Mathematics, Univ. of Chicago, Chicago, Illinois. M.Sc. Dissertation
↑ Kjeldsen, Tinne Hoff (2000). «A contextualized historical analysis of the Kuhn-Tucker theorem in nonlinear programming: the impact of World War II». Historia Math. 27 (4): 331–361. MR 1800317. doi:10.1006/hmat.2000.2289
↑ «The Karush-Kuhn-Tucker Theorem» (PDF). Consultado em 11 de março de 2008. Arquivado do original (PDF) em 10 de junho de 2007
↑ ^a ^b ^c ^d Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization (PDF) (em inglês). Cambridge, United Kingdom: Cambridge University Press. pp. 225, 243. ISBN 978-0-521-83378-3. Consultado em 8 de abril de 2017
↑ Ruszczyński, Andrzej (2006). Nonlinear Optimization. Princeton, NJ: Princeton University Press. ISBN 978-0691119151. MR 2199043
↑ Martin, D. H. (1985). «The Essence of Invexity». J. Optim. Theory Appl. 47 (1): 65–76. doi:10.1007/BF00941316
↑ Hanson, M. A. (1999). «Invexity and the Kuhn-Tucker Theorem». J. Math. Anal. Appl. 236 (2): 594–604. doi:10.1006/jmaa.1999.6484

[5] Se $x^{*}$ é um minimizador local para $f$ (e consequentemente para $L$ ), então o gradiente de $L$ deve ser nulo em $x^{*}$ . Isto é:
$\nabla L(x^{*},\mathbf {\mu } ,\mathbf {\lambda } )=0$

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

[7] Com as suposições e resultados da primeira condição de KKT obtém-se que:
$\nabla f(x^{*})=0$ (o gradiente da função objetivo no mínimo local é nulo) e;

$\sum _{j=1}^{l}\lambda _{j}h_{j}(x^{*})=0$ (por conta da viabilidade primal).
Portanto:
$f(x^{*})+\sum _{i=1}^{m}\mu _{i}g_{i}(x^{*})+\sum _{j=1}^{l}\lambda _{j}h_{j}(x^{*})=0\rightarrow \sum _{i=1}^{m}\mu _{i}g_{i}(x^{*})=0$
Como $g_{i}(x^{*})\leq 0$ e $\mu _{i}\geq 0$ (viabilidade dual), $\mu _{i}g_{i}(x^{*})\leq 0$ para todo $i=1,2,...,m$ .
Logo, $\sum _{j=1}^{l}\lambda _{j}h_{j}(x^{*})=0$ só é verdadeiro se $\mu _{i}g_{i}(x^{*})=0$ para todo $i=1,2,...,m$ .

[3] $\nabla f(x^{*})=0$ (o gradiente da função objetivo no mínimo local é nulo) e;

[4] $\sum _{j=1}^{l}\lambda _{j}h_{j}(x^{*})=0$ (por conta da viabilidade primal).

[5] $f(x^{*})+\sum _{i=1}^{m}\mu _{i}g_{i}(x^{*})+\sum _{j=1}^{l}\lambda _{j}h_{j}(x^{*})=0\rightarrow \sum _{i=1}^{m}\mu _{i}g_{i}(x^{*})=0$

[1] Kuhn, H. W.; Tucker, A. W. (1951). «Nonlinear programming». Proceedings of 2nd Berkeley Symposium. Berkeley: University of California Press. pp. 481–492

[2] W. Karush (1939). «Minima of Functions of Several Variables with Inequalities as Side Constraints». Dept. of Mathematics, Univ. of Chicago, Chicago, Illinois. M.Sc. Dissertation

[3] Kjeldsen, Tinne Hoff (2000). «A contextualized historical analysis of the Kuhn-Tucker theorem in nonlinear programming: the impact of World War II». Historia Math. 27 (4): 331–361. MR 1800317. doi:10.1006/hmat.2000.2289

[4] «The Karush-Kuhn-Tucker Theorem» (PDF). Consultado em 11 de março de 2008. Arquivado do original (PDF) em 10 de junho de 2007

[CO-6] Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization (PDF) (em inglês). Cambridge, United Kingdom: Cambridge University Press. pp. 225, 243. ISBN 978-0-521-83378-3. Consultado em 8 de abril de 2017

[8] Ruszczyński, Andrzej (2006). Nonlinear Optimization. Princeton, NJ: Princeton University Press. ISBN 978-0691119151. MR 2199043

[9] Martin, D. H. (1985). «The Essence of Invexity». J. Optim. Theory Appl. 47 (1): 65–76. doi:10.1007/BF00941316

[10] Hanson, M. A. (1999). «Invexity and the Kuhn-Tucker Theorem». J. Math. Anal. Appl. 236 (2): 594–604. doi:10.1006/jmaa.1999.6484

[1]

[2]

[3]

[4]

[Demonstração 1]

[5]

[Demonstração 2]

[6]

[7]

[8]