Condições KKT

As condições de Karush-Kuhn-Tucker (KKT) generalizam os multiplicadores de Lagrange para problemas com restrições de desigualdade. Elas são as condições fundamentais de otimalidade necessárias para a otimização restrita: praticamente todo algoritmo de otimização prático, do método Simplex a métodos de ponto interior a máquinas de vetores de suporte, é construído em torno de satisfazer as condições KKT.

O problema restrito geral

As condições KKT são construídas em torno desta forma geral, que permite restrições de desigualdade e de igualdade ao mesmo tempo:

\[\min_{x \in \mathbb{R}^n} f(x) \quad \text{sujeito a} \quad g_i(x) \leq 0,\; i=1,\ldots,m \quad h_j(x) = 0,\; j=1,\ldots,p\]

O Lagrangiano para este problema é:

\[\mathcal{L}(x, \mu, \lambda) = f(x) + \sum_{i=1}^m \mu_i g_i(x) + \sum_{j=1}^p \lambda_j h_j(x)\]

em que \(\mu_i \geq 0\) são os multiplicadores das restrições de desigualdade e \(\lambda_j\) (sem restrição de sinal) são os multiplicadores das restrições de igualdade.

As cinco condições KKT

Em um mínimo local \(x^*\) que satisfaz uma qualificação de restrição, existem multiplicadores \(\mu^* \geq 0\) e \(\lambda^*\) tais que:

1. Estacionariedade: \[\nabla f(x^*) + \sum_{i=1}^m \mu_i^* \nabla g_i(x^*) + \sum_{j=1}^p \lambda_j^* \nabla h_j(x^*) = \mathbf{0}\]

2. Viabilidade primal: \[g_i(x^*) \leq 0 \quad \forall i, \qquad h_j(x^*) = 0 \quad \forall j\]

3. Viabilidade dual: \[\mu_i^* \geq 0 \quad \forall i\]

4. Folga complementar: \[\mu_i^* g_i(x^*) = 0 \quad \forall i\]

Cada condição tem um papel claro:

  • Estacionariedade: o gradiente do Lagrangiano é zero. Generaliza a condição de Lagrange \(\nabla f = -\lambda \nabla g\) para desigualdades.
  • Viabilidade primal: a solução é viável. Todas as restrições são satisfeitas.
  • Viabilidade dual: os multiplicadores de desigualdade são não negativos. Isso garante que restrições de desigualdade ativas empurram a solução para dentro, não para fora.
  • Folga complementar: para cada restrição de desigualdade, ou a restrição está ativa (\(g_i(x^*) = 0\), a fronteira da restrição está justa) ou o multiplicador é zero (\(\mu_i^* = 0\), a restrição é inativa e não desempenha papel algum). Os dois não podem ser diferentes de zero simultaneamente.

Folga complementar: a condição-chave

A folga complementar é a condição KKT mais distintiva. Ela diz que uma restrição inativa (uma em que \(g_i(x^*) < 0\): a solução está estritamente dentro da região viável) não tem efeito sobre o ótimo: \(\mu_i^* = 0\) e a restrição desaparece da condição de estacionariedade.

Uma restrição ativa (\(g_i(x^*) = 0\): a solução está na fronteira) pode ter \(\mu_i^* > 0\): a restrição é vinculante e seu gradiente aparece na condição de estacionariedade com peso diferente de zero.

Dois painéis mostrando um ótimo restrito no interior (restrição inativa) e na fronteira (restrição ativa)

Esquerda: o mínimo irrestrito \((3,2)\) fica dentro do disco viável. A restrição é inativa (\(g(x^*)=3^2+2^2-16 = -7 < 0\)), então \(\mu^* = 0\) e a restrição não desempenha papel algum. Direita: o mínimo irrestrito \((5,4)\) fica fora da região viável. O ótimo restrito é a projeção sobre a fronteira do disco, em que a restrição é ativa (\(g(x^*)=0\)) e \(\mu^* > 0\).

Exemplo completo: quadrática com restrição de desigualdade

Minimizar \(f(x,y) = x^2 + y^2\) sujeito a \(g_1: x + y \geq 2\) (ou seja, \(2 - x - y \leq 0\)) e \(g_2: x \geq 0\), \(g_3: y \geq 0\).

Reescrevendo em forma padrão (\(g_i \leq 0\)): \(g_1 = 2-x-y\), \(g_2 = -x\), \(g_3 = -y\).

Lagrangiano:

\[\mathcal{L} = x^2 + y^2 + \mu_1(2-x-y) + \mu_2(-x) + \mu_3(-y)\]

Estacionariedade:

\[2x - \mu_1 - \mu_2 = 0 \implies \mu_1 + \mu_2 = 2x\]

\[2y - \mu_1 - \mu_3 = 0 \implies \mu_1 + \mu_3 = 2y\]

Por simetria (\(f\) e a restrição ativa \(x+y=2\) são simétricas), tente \(x^* = y^* = 1\).

Verificação: \(g_1 = 2-1-1=0\) (ativa), \(g_2 = -1 < 0\) (inativa, então \(\mu_2=0\)), \(g_3 = -1 < 0\) (inativa, então \(\mu_3=0\)).

Da estacionariedade com \(\mu_2=\mu_3=0\): \(\mu_1 = 2x^* = 2\). Verifique a viabilidade dual: \(\mu_1=2 > 0\). Verifique a folga complementar: \(\mu_1 g_1 = 2 \times 0 = 0\), \(\mu_2 g_2 = 0 \times (-1) = 0\), \(\mu_3 g_3 = 0 \times (-1) = 0\). Todas satisfeitas.

Solução ótima: \(x^* = y^* = 1\), \(f^* = 2\), \(\mu_1^* = 2\).

O multiplicador \(\mu_1^* = 2\) nos diz: apertar a restrição de \(x+y \geq 2\) para \(x+y \geq 2+\varepsilon\) aumenta o valor ótimo em aproximadamente \(2\varepsilon\).

Região viável para a quadrática com restrição de desigualdade com curvas de nível e ponto ótimo na restrição ativa

Suficiência: quando KKT implica otimalidade global

As condições KKT são sempre necessárias (sob uma qualificação de restrição). Elas são suficientes para a otimalidade global quando:

  • \(f\) é convexa.
  • Cada \(g_i\) é convexa (então \(g_i(x) \leq 0\) define um conjunto viável convexo).
  • Cada \(h_j\) é afim (linear).

Sob essas condições, qualquer ponto KKT é um mínimo global. Isso cobre os casos práticos mais importantes: programação linear, programação quadrática com objetivo convexo, otimização convexa de carteiras, máquinas de vetores de suporte.

Para problemas não convexos, pontos KKT podem ser mínimos locais, máximos locais, ou pontos de sela. Encontrar o mínimo global exige estrutura adicional ou métodos de busca global.

Aplicação: máquinas de vetores de suporte

As SVMs encontram o hiperplano de margem máxima que separa duas classes. O problema primal é:

\[\min_{w,b} \frac{1}{2}\|w\|^2 \quad \text{s.a.} \quad y_i(w^T x_i + b) \geq 1 \quad \forall i\]

As condições KKT dão o problema dual: apenas os vetores de suporte (pontos em que \(\mu_i > 0\), ou seja, a restrição \(y_i(w^T x_i+b) = 1\) está ativa) aparecem na solução. Pontos longe da margem têm \(\mu_i = 0\) por folga complementar e são irrelevantes. Essa esparsidade é uma consequência direta do KKT.

⚠️ As condições KKT exigem qualificação de restrição

A qualificação de restrição mais comum é a LICQ (Independência Linear): os gradientes das restrições ativas em \(x^*\) devem ser linearmente independentes. Se a LICQ falhar, os multiplicadores KKT podem não existir ou não ser únicos.

Situações comuns em que a QR pode falhar:

  • Duas restrições de desigualdade são tangentes uma à outra no ótimo.
  • Uma restrição tem gradiente nulo no ótimo.
  • Restrições ativas demais (mais de \(n\) restrições ativas em \(\mathbb{R}^n\)).

Na prática, a falha de QR é rara em problemas bem formulados. Se você suspeitar disso, verifique se os gradientes das restrições ativas são linearmente independentes no seu candidato a ótimo.

💡 Verificando as condições KKT na prática

Dado um ponto candidato \(x^*\), verifique o KKT manualmente:

  1. Verifique a viabilidade primal: todos os \(g_i(x^*) \leq 0\) e \(h_j(x^*) = 0\).
  2. Calcule \(\nabla f(x^*)\) e \(\nabla g_i(x^*)\) para as restrições ativas.
  3. Resolva o sistema linear para \(\mu_i^*\) a partir da condição de estacionariedade.
  4. Verifique a viabilidade dual: \(\mu_i^* \geq 0\) para todo \(i\).
  5. Verifique a folga complementar: \(\mu_i^* g_i(x^*) = 0\) para todo \(i\).

No R, verificação numérica de KKT após resolver com nloptr:

library(nloptr)

f      <- function(x) x[1]^2 + x[2]^2
grad_f <- function(x) c(2*x[1], 2*x[2])
g_ineq <- function(x) c(2 - x[1] - x[2], -x[1], -x[2])

res <- nloptr(x0=c(0.5, 0.5), eval_f=f, eval_grad_f=grad_f,
              eval_g_ineq=g_ineq,
              opts=list(algorithm="NLOPT_LD_SLSQP", xtol_rel=1e-8))
res$solution  # c(1, 1)