As condições de Karush-Kuhn-Tucker (KKT) são condições necessárias de otimalidade para problemas de programação não-linear com restrições de igualdade e desigualdade.
Problema geral
Min f(x)
s.a. gᵢ(x) ≤ 0, i = 1, ..., m
hⱼ(x) = 0, j = 1, ..., p
Se x* é um mínimo local e se se verificam certas condições de regularidade (qualificação das restrições), então existem multiplicadores λᵢ ≥ 0 e μⱼ tais que as condições KKT se satisfazem.
Condições KKT
- Estacionaridade: ∇f(x*) + Σλᵢ∇gᵢ(x*) + Σμⱼ∇hⱼ(x*) = 0
- Admissibilidade primal: gᵢ(x*) ≤ 0 e hⱼ(x*) = 0
- Admissibilidade dual: λᵢ ≥ 0
- Complementaridade: λᵢ · gᵢ(x*) = 0 para cada i
A condição de complementaridade significa que para cada restrição de desigualdade, ou a restrição está ativa (gᵢ = 0) ou o multiplicador é nulo (λᵢ = 0).
Exemplo simples
Min f(x₁,x₂) = x₁² + x₂²
s.a. x₁ + x₂ ≥ 1 (g₁: −x₁ − x₂ + 1 ≤ 0)
x₁, x₂ ≥ 0
Lagrangiana: L = x₁² + x₂² + λ(−x₁ − x₂ + 1)
Condições KKT:
- ∂L/∂x₁ = 2x₁ − λ = 0 → x₁ = λ/2
- ∂L/∂x₂ = 2x₂ − λ = 0 → x₂ = λ/2
- Complementaridade: λ(−x₁ − x₂ + 1) = 0
- λ ≥ 0, −x₁ − x₂ + 1 ≤ 0
Se λ > 0 → restrição ativa: x₁ + x₂ = 1 e x₁ = x₂ → x₁* = x₂* = 0,5, λ* = 1. Verificação: f(0,5; 0,5) = 0,5 (mínimo).
Quando as KKT são suficientes
Para problemas convexos (f convexa, gᵢ convexas, hⱼ afins), as condições KKT são necessárias e suficientes para otimalidade global. Para problemas não convexos são apenas necessárias e pode existir mais do que um ponto que as satisfaça.