Otimização com Restrições

Por que a otimização com restrições aparece em IA/ML

A maioria dos problemas de otimização em aprendizado de máquina (machine learning) é escrita como “minimizar uma perda”. Na prática, você frequentemente tem requisitos que a solução deve satisfazer:

  • Limites físicos ou do domínio: pesos devem ser não negativos, probabilidades devem somar 1, uma entrada de controle deve permanecer dentro de limites.
  • Validade do modelo: matrizes de covariância devem ser semidefinidas positivas, distribuições devem normalizar.
  • Segurança/equidade/robustez: restrições sobre taxas de erro entre grupos, restrições sobre a pior perda sob perturbações.
  • Restrições de recursos: orçamentos de memória/latência/energia, limites de esparsidade ou uma contagem fixa de parâmetros.

A otimização com restrições fornece uma maneira fundamentada de expressar e resolver esses problemas, e também explica vários “truques” usados em aprendizado de máquina (por exemplo, softmax para impor uma restrição de simplex, ou passos de projeção na otimização).

Este artigo foca nas ideias centrais: restrições, multiplicadores de Lagrange (Lagrange multipliers) e condições KKT (KKT conditions) — com intuição suficiente para reconhecê-las na prática moderna de IA. Para um contexto mais amplo sobre quando restrições se tornam especialmente tratáveis, veja Otimização Convexa. Para métodos iterativos sem restrições, veja Descida do Gradiente e Otimização Estocástica.

Configuração do problema e terminologia

Um problema padrão de otimização com restrições é:

[ \begin{aligned} \min_{x \in \mathbb{R}^n} \quad & f(x) \ \text{s.t.}\quad & g_i(x) \le 0 \quad (i=1,\dots,m) \ & h_j(x) = 0 \quad (j=1,\dots,p) \end{aligned} ]

  • (f(x)) é o objetivo (perda).
  • (g_i(x)\le 0) são restrições de desigualdade (por exemplo, limites, orçamentos).
  • (h_j(x)=0) são restrições de igualdade (requisitos exatos).
  • O conjunto de pontos que satisfazem todas as restrições é o conjunto factível.
  • Uma restrição é ativa em (x^\star) se ela vale com igualdade ali (por exemplo, (g_i(x^\star)=0)). Caso contrário, ela é inativa ((g_i(x^\star)<0)).

Intuição geométrica: “você não pode descer”

Na otimização sem restrições, um ótimo local (x^\star) normalmente satisfaz (\nabla f(x^\star)=0): não há direção na qual você possa se mover que diminua (f).

Com restrições, você só pode se mover dentro do conjunto factível. Em um ótimo, não há direção factível que diminua o objetivo. O gradiente (\nabla f(x^\star)) pode ser diferente de zero, mas ele deve ser “bloqueado” pelas restrições.

Essa imagem do “gradiente bloqueado” é exatamente o que os multiplicadores de Lagrange e as condições KKT formalizam.

Multiplicadores de Lagrange para restrições de igualdade

Considere o caso apenas com igualdades:

[ \min_x f(x)\quad\text{s.t.}\quad h(x)=0 ]

(Para múltiplas igualdades, trate (h(x)) como um vetor.)

Ideia central

Em um ótimo sob restrição, você fica restrito a direções tangentes à superfície da restrição. O gradiente de (f) no ótimo deve ser ortogonal a todas as direções factíveis — ou seja, ele pertence ao span dos vetores normais às restrições.

Se (h(x)=0) define uma superfície, sua direção normal é (\nabla h(x)). Assim, no ótimo:

[ \nabla f(x^\star) + \lambda \nabla h(x^\star)=0 ]

para algum escalar (\lambda) (ou vetor (\lambda) para múltiplas restrições). Esse (\lambda) é o multiplicador de Lagrange.

O Lagrangiano

Empacotamos essa condição usando o Lagrangiano (Lagrangian):

[ \mathcal{L}(x,\lambda) = f(x) + \lambda , h(x) ]

Então, as condições necessárias são:

  • Estacionariedade: (\nabla_x \mathcal{L}(x^\star,\lambda^\star)=0)
  • Factibilidade primal: (h(x^\star)=0)

Interpretação prática: multiplicadores como “preços sombra”

Em muitos problemas, (\lambda^\star) mede sensibilidade: o quanto o objetivo ótimo mudaria se você relaxasse/apertasse levemente a restrição. Em termos aproximados,

[ \lambda^\star \approx \frac{\partial f^\star}{\partial (\text{nível da restrição})} ]

Por isso os multiplicadores são chamados de “preços”: eles quantificam o valor dos recursos de restrição.

Exemplo: solução de menor norma sob uma restrição linear

Resolva:

[ \min_x \tfrac12|x|_2^2 \quad \text{s.t.}\quad a^\top x = b ]

Lagrangiano: [ \mathcal{L}(x,\lambda)=\tfrac12 x^\top x + \lambda(a^\top x - b) ]

Estacionariedade: [ \nabla_x \mathcal{L}=x+\lambda a=0 \Rightarrow x^\star=-\lambda a ]

Imponha a restrição: [ a^\top x^\star = -\lambda a^\top a = b \Rightarrow \lambda^\star = -\frac{b}{|a|^2} ]

Logo, [ x^\star = \frac{b}{|a|^2}a ]

Interpretação: dentre todos os vetores cujo produto interno com (a) é (b), o melhor é aquele alinhado com (a).

Restrições de desigualdade: por que KKT é necessário

Desigualdades introduzem um novo fenômeno: algumas restrições podem não importar no ótimo. Se (g_i(x^\star)<0), essa restrição é inativa e não deve afetar o balanço de gradientes.

É aqui que entram as condições de Karush–Kuhn–Tucker (Karush–Kuhn–Tucker, KKT). Elas estendem os multiplicadores de Lagrange ao:

  • exigir que multiplicadores de desigualdades sejam não negativos,
  • garantir que restrições inativas recebam multiplicador zero automaticamente.

Condições KKT (intuição primeiro)

Para

[ \min_x f(x)\ \ \text{s.t.}\ \ g_i(x)\le 0,\ \ h_j(x)=0 ]

defina o Lagrangiano:

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

onde:

  • (\lambda_i) são multiplicadores para desigualdades,
  • (\nu_j) são multiplicadores para igualdades.

As condições KKT são:

  1. Factibilidade primal [ g_i(x^\star)\le 0,\quad h_j(x^\star)=0 ]

  2. Factibilidade dual [ \lambda_i^\star \ge 0 ] (Apenas “empurram de volta” contra violações; não “puxam” para dentro da violação.)

  3. Folga complementar [ \lambda_i^\star, g_i(x^\star)=0 \quad \forall i ] Este é o portão lógico-chave:

    • Se (g_i(x^\star)<0) (inativa), então (\lambda_i^\star=0).
    • Se (\lambda_i^\star>0), então (g_i(x^\star)=0) (ativa).

  4. Estacionariedade [ \nabla f(x^\star) + \sum_i \lambda_i^\star \nabla g_i(x^\star) + \sum_j \nu_j^\star \nabla h_j(x^\star)=0 ]

“Restrições ativas formam a parede”

Um modelo mental útil: no ótimo, o gradiente negativo (-\nabla f) aponta na direção em que você gostaria de ir. As restrições ativas fornecem normais para fora que “sustentam” a região factível na solução. A condição de estacionariedade diz que o gradiente do objetivo é uma combinação linear dessas normais (mais as normais das restrições de igualdade).

Exemplo: restrição de limite em 1D

Minimize (f(x)=(x-3)^2) sujeito a (x\le 1).

  • Minimizador sem restrição: (x=3) (inviável).
  • Conjunto factível: ((-\infty,1]).
  • Ótimo com restrição: (x^\star=1) (a fronteira é ativa).

Escreva a restrição como (g(x)=x-1\le 0).

KKT:

  • Factibilidade primal: (1-1=0) OK.
  • Estacionariedade: (f'(x^\star)+\lambda g'(x^\star)=0). Aqui (f'(x)=2(x-3)), (g'(x)=1). Em (x^\star=1): (-4 + \lambda = 0 \Rightarrow \lambda^\star=4\ge 0).
  • A folga complementar vale pois (g(x^\star)=0).

Interpretação: o multiplicador (\lambda^\star=4) quantifica o quão fortemente a restrição está “segurando” o ótimo.

Dualidade: outra visão das restrições (e por que isso importa)

O Lagrangiano também leva ao problema dual (dual problem), que é central em muitos métodos de aprendizado de máquina (notavelmente SVMs e muitas relaxações convexas).

Defina a função dual (dual function):

[ q(\lambda,\nu) = \inf_x \mathcal{L}(x,\lambda,\nu) ]

Para restrições de desigualdade, restringimos (\lambda \ge 0). Então o problema dual é:

[ \max_{\lambda\ge 0,\nu} \ q(\lambda,\nu) ]

Fatos-chave:

  • Para qualquer (x) factível e qualquer (\lambda\ge 0), (q(\lambda,\nu)) fornece um limitante inferior para o ótimo primal (para minimização). Isso é chamado de dualidade fraca (weak duality).
  • Sob convexidade e condições de regularidade leves (por exemplo, condição de Slater), os valores ótimos primal e dual coincidem: dualidade forte (strong duality). Esta é uma razão pela qual problemas convexos com restrições são tão poderosos (veja Otimização Convexa).

Por que pessoas de ML se importam com o dual

  • O dual pode ser mais fácil de otimizar (menos variáveis, restrições mais simples).
  • O dual expõe estrutura de vetores de suporte / esparsidade (clássico em SVMs).
  • Variáveis duais têm significados interpretáveis (sensibilidades de restrição).
  • Muitos resolvedores modernos (métodos de ponto interior, métodos primal-dual) exploram a estrutura primal–dual.

Como a otimização com restrições é usada na prática de ML

1) Máquinas de Vetores de Suporte (SVM): maximização de margem com restrições

A SVM clássica de margem rígida pode ser escrita como:

[ \min_{w,b}\ \tfrac12|w|^2 \quad \text{s.t.}\quad y_i(w^\top x_i + b)\ge 1 ]

Essas são restrições de desigualdade — cada ponto de treino deve ficar fora da margem. As condições KKT explicam:

  • Apenas pontos exatamente na margem têm multiplicadores não nulos ((\lambda_i>0)): os vetores de suporte.
  • O (w) ótimo é uma combinação de vetores de suporte (via estacionariedade).

Este é um exemplo canônico de como KKT fornece insight geométrico imediato.

2) Probabilidades e o simplex: “saídas devem somar 1”

Muitos modelos exigem que (p\in\mathbb{R}^K) satisfaça:

  • (p_k \ge 0)
  • (\sum_k p_k = 1)

Em vez de resolver explicitamente problemas com restrições a cada passo, o aprendizado profundo (deep learning) tipicamente impõe a restrição por parametrização (parameterization):

  • Seja logits (z\in\mathbb{R}^K), e defina (p=\mathrm{softmax}(z)).
  • Isso transforma uma otimização sem restrições em uma com restrições de forma implícita.

Quando você precisa de restrições explícitas (por exemplo, otimizar pesos de mistura com objetivos customizados), você pode usar projeção no simplex (veja a seção de algoritmos).

3) Restrições de equidade, segurança e recursos

Exemplos:

  • Restringir métricas de disparidade entre grupos enquanto minimiza a perda.
  • Restringir a pior perda sob perturbações (otimização robusta).
  • Restringir FLOPs/latência ou impor orçamentos de esparsidade.

Isso frequentemente leva a restrições de desigualdade e se beneficia de relaxação Lagrangiana (tratar penalidades de restrição com multiplicadores aprendíveis).

4) Aprendizado por reforço: otimização de política com restrições

Em RL seguro, você pode minimizar o custo esperado sujeito a restrições sobre violações esperadas (por exemplo, custos de segurança). Uma abordagem comum usa atualizações primal-dual: atualizar parâmetros de política para reduzir custo enquanto atualiza multiplicadores para impor restrições.

Caixa de ferramentas algorítmica: como resolvemos problemas com restrições

Não existe um único melhor método; a escolha depende de convexidade, diferenciabilidade e escala.

Métodos de gradiente projetado (simples e comuns)

Para restrições da forma (x\in \mathcal{C}) (um conjunto no qual você consegue projetar), você pode fazer:

  1. Dar um passo de gradiente: (x \leftarrow x - \eta \nabla f(x))
  2. Projetar de volta: (x \leftarrow \Pi_\mathcal{C}(x))

Isso é amplamente usado para restrições de caixa, bolas de norma e o simplex de probabilidades.

Pseudocode

repeat:
    x = x - η * grad f(x)
    x = projection_C(x)
until convergence

Example: projection onto the probability simplex

import numpy as np

def project_simplex(v, z=1.0):
    """
    Euclidean projection of v onto {p: p>=0, sum(p)=z}.
    """
    v = np.asarray(v, dtype=float)
    u = np.sort(v)[::-1]
    cssv = np.cumsum(u)
    rho = np.nonzero(u * np.arange(1, len(v)+1) > (cssv - z))[0][-1]
    theta = (cssv[rho] - z) / (rho + 1.0)
    w = np.maximum(v - theta, 0.0)
    return w

Quando isso ajuda em ML?

  • Impor pesos de mistura, distribuições de atenção com restrições extras, atribuições de características com restrições, ou sempre que você precisar de restrições explícitas de simplex além de softmax.

Métodos de penalidade (transformam restrições em termos extras de perda)

Substitua o problema com restrição por:

[ \min_x\ f(x) + \mu \sum_i \max(0, g_i(x))^2 + \mu \sum_j h_j(x)^2 ]

À medida que (\mu \to \infty), violações de restrição se tornam muito caras. Métodos de penalidade são fáceis de implementar com otimizadores padrão, mas:

  • (\mu) grande pode tornar a otimização mal condicionada,
  • a solução pode permanecer levemente inviável na prática.

Métodos de barreira (ponto interior) (permanecem estritamente factíveis)

Para desigualdades (g_i(x)\le 0), adicione uma barreira como:

[ \min_x\ f(x) - \frac{1}{t}\sum_i \log(-g_i(x)) ]

Isso mantém as iterações estritamente dentro da região factível. Métodos de ponto interior são extremamente eficazes para muitos problemas convexos, tipicamente via passos de segunda ordem (Newton). Eles são menos comuns para grandes redes profundas, mas comuns em toolkits clássicos de otimização.

Lagrangiano aumentado e ADMM (frequentemente o melhor dos dois mundos)

O Lagrangiano aumentado (augmented Lagrangian) adiciona tanto multiplicadores quanto penalidades, por exemplo, para restrições de igualdade:

[ \mathcal{L}_\rho(x,\nu)= f(x) + \nu^\top h(x) + \frac{\rho}{2}|h(x)|^2 ]

Isso frequentemente melhora a estabilidade em comparação com métodos de penalidade puros e dá suporte a atualizações alternadas. ADMM (Alternating Direction Method of Multipliers) é uma variante popular que separa variáveis para lidar com objetivos/restrições compostos (útil em aprendizado esparso, problemas de consenso e cenários distribuídos).

Atualizações primal–dual (ponto de sela)

As condições KKT caracterizam um ponto de sela de (\mathcal{L}). Muitos métodos alternam:

  • descida em (x) (variáveis primais),
  • subida em (\lambda) (variáveis duais), mantendo (\lambda\ge 0).

Isso é comum em RL com restrições e em aprendizado com restrições em larga escala.

Armadilhas comuns e dicas práticas

  • A qualificação de restrições importa: as condições KKT são necessárias sob hipóteses de regularidade (por exemplo, gradientes das restrições ativas não serem degenerados). Se isso falhar, multiplicadores podem não existir ou podem não caracterizar ótimos de forma limpa.
  • Não convexidade é a norma em aprendizado profundo: KKT ainda fornece condições necessárias locais, mas a otimalidade global não é garantida. Espere mínimos locais e pontos de sela.
  • Escalar restrições muda as magnitudes dos multiplicadores: se você multiplicar uma restrição por 100, a “mesma” restrição leva a multiplicadores cerca de 1/100 do tamanho. Não compare valores de (\lambda) entre restrições com escalas diferentes sem normalização.
  • Escolha deliberadamente a estratégia de imposição:
    • Se a restrição é fácil de satisfazer via parametrização (simplex, positividade), prefira reparametrização (reparameterization) (por exemplo, softmax, softplus).
    • Se a projeção é barata, métodos projetados são diretos e robustos.
    • Se você precisa de factibilidade precisa e bom condicionamento, considere Lagrangiano aumentado / ADMM ou um resolvedor convexo.
  • Use resolvedores padrão quando possível: para problemas convexos com restrições, ferramentas no estilo de modelagem CVX (por exemplo, CVXPY) podem ser muito mais confiáveis do que truques de gradiente feitos à mão.

Resumo: o modelo mental a manter

  • Multiplicadores de Lagrange explicam restrições de igualdade: no ótimo, o gradiente do objetivo pertence ao span das normais das restrições.
  • Condições KKT estendem isso para desigualdades:
    • restrições ativas recebem multiplicadores positivos,
    • restrições inativas recebem multiplicadores zero automaticamente (folga complementar),
    • multiplicadores são não negativos e agem como “forças” ou “preços”.
  • Dualidade transforma restrições em uma maximização sobre multiplicadores e sustenta muitos métodos clássicos de ML.
  • Algoritmos variam de gradientes projetados simples a métodos sofisticados primal–dual e de ponto interior; a escolha certa depende da estrutura e da escala.

A otimização com restrições é uma das principais pontes entre “minimização de perda” e “sistemas reais”, nos quais as soluções devem obedecer a orçamentos, limites de segurança, consistência probabilística e regras do domínio.