Otimização Convexa

O que é otimização convexa?

Otimização convexa (convex optimization) é o estudo de problemas de otimização em que a função objetivo (objective function) é convexa (convex) e o conjunto viável (feasible set) (as restrições (constraints)) é convexo. Esses problemas são “especiais” porque estão entre as poucas classes amplas de problemas de otimização nas quais podemos fazer garantias fortes e globais:

  • Qualquer mínimo local (local minimum) é um mínimo global (global minimum).
  • Sob condições brandas, o ótimo global é único (por exemplo, com convexidade forte (strong convexity)).
  • Há algoritmos bem compreendidos com garantias de convergência (convergence guarantees).
  • Restrições e dualidade (duality) frequentemente têm interpretações claras e solucionadores eficientes.

Em inteligência artificial (AI) e aprendizado de máquina (machine learning), a otimização convexa sustenta muitos modelos “clássicos” (por exemplo, regressão linear (linear regression), regressão logística (logistic regression) com regularização convexa (convex regularization), máquinas de vetores de suporte (support vector machines)) e fornece ferramentas essenciais para raciocinar sobre otimização — mesmo quando o treinamento de redes profundas (deep networks) modernas é não convexo (non-convex).

Este artigo foca nos fundamentos da convexidade e por que problemas convexos tendem a ser excepcionalmente bem-comportados.

A forma padrão de otimização convexa

Uma forma comum é:

[ \min_{x \in \mathbb{R}^n} ; f(x) \quad \text{s.t.} \quad g_i(x) \le 0 ; (i=1,\dots,m), ;; Ax=b ]

Isso é um problema de otimização convexa se:

  • (f) é convexa
  • cada função de restrição de desigualdade (g_i) é convexa (então ({x : g_i(x)\le 0}) é convexo)
  • restrições de igualdade são afins (affine) (isto é, (Ax=b))

Para mais sobre restrições e condições de otimalidade, veja Otimização com Restrições.

Conjuntos convexos: a geometria por trás da convexidade

Um conjunto (C \subseteq \mathbb{R}^n) é convexo se, para quaisquer dois pontos (x, y \in C) e qualquer (\theta \in [0,1]),

[ \theta x + (1-\theta) y \in C. ]

Interpretação: se você escolhe quaisquer dois pontos viáveis, então todo o segmento de reta entre eles também é viável.

Exemplos de conjuntos convexos

  • Semiespaços (half-spaces): ({x : a^\top x \le b})
  • Subespaços afins (affine subspaces): ({x : Ax=b})
  • Bolas euclidianas (Euclidean balls): ({x : |x|_2 \le r})
  • Politopos (polytopes) (interseção de um número finito de semiespaços): comuns em programação linear (linear programming)
  • Cone semidefinido positivo (positive semidefinite cone): ({X \succeq 0}) em programação semidefinida (semidefinite programming)

Exemplos de conjuntos não convexos

  • Dois aglomerados separados (regiões viáveis desconectadas)
  • Conjuntos com “buracos” (por exemplo, uma coroa circular/anel)
  • Restrições inteiras (por exemplo, (x \in {0,1}^n))

Regiões viáveis não convexas criam “armadilhas” nas quais uma busca local pode ficar presa longe do ótimo global.

Funções convexas: objetivos “arqueados para cima”

Uma função (f:\mathbb{R}^n \to \mathbb{R}) é convexa se, para quaisquer (x,y) e (\theta\in[0,1]),

[ f(\theta x + (1-\theta)y) \le \theta f(x) + (1-\theta) f(y). ]

Isso diz: o valor da função em um ponto interpolado não é pior do que a interpolação dos valores da função. Geometricamente, a corda entre ((x,f(x))) e ((y,f(y))) fica acima do gráfico.

Caracterização de primeira ordem (caso diferenciável)

Se (f) é diferenciável, convexidade é equivalente a:

[ f(y) \ge f(x) + \nabla f(x)^\top (y-x) ]

Interpretação: o hiperplano tangente em (x) é um subestimador global (global underestimator) de (f). Essa propriedade é central para algoritmos de otimização e demonstrações.

Caracterização de segunda ordem (caso duas vezes diferenciável)

Se (f) é duas vezes diferenciável, então (f) é convexa sse:

[ \nabla^2 f(x) \succeq 0 \quad \text{para todo } x ]

isto é, a Hessiana (Hessian) é semidefinida positiva (positive semidefinite) em todo lugar.

Convexidade forte (por que acontecem unicidade e taxas rápidas)

(f) é (\mu)-fortemente convexa ((\mu)-strongly convex) se:

[ f(y) \ge f(x) + \nabla f(x)^\top (y-x) + \frac{\mu}{2}|y-x|_2^2. ]

Convexidade forte implica:

  • um minimizador global único
  • geometria melhor condicionada (sem vales planos)
  • convergência mais rápida para muitos métodos (por exemplo, taxas lineares para descida do gradiente sob suavidade)

Por que problemas convexos são especiais

1) Mínimos locais são mínimos globais

Em problemas não convexos, você pode ter:

  • mínimos locais
  • pontos de sela
  • platôs planos
  • muitas bacias desconectadas

Em otimização convexa, se (x^*) é localmente ótimo, então ele deve ser globalmente ótimo. Isso simplifica drasticamente teoria e prática: você pode usar métodos locais (como algoritmos baseados em gradiente) com confiança de que “ficar preso” não significa perder uma solução melhor em outro lugar.

2) Condições de otimalidade são limpas e verificáveis

Para problemas convexos sem restrições e diferenciáveis:

[ \nabla f(x^*) = 0 \quad \Longleftrightarrow \quad x^* \text{ é globalmente ótimo}. ]

Para problemas com restrições, as condições de Karush–Kuhn–Tucker (KKT) tornam-se não apenas necessárias, mas (sob condições brandas) suficientes — uma das principais razões pelas quais a otimização convexa com restrições é tratável. Veja Otimização com Restrições.

3) Dualidade é poderosa (e frequentemente exata)

Problemas convexos frequentemente têm lacunas de dualidade (duality gaps) pequenas ou nulas, isto é, o ótimo do problema primal (primal) é igual ao ótimo do problema dual (dual) sob condições como a condição de Slater (Slater’s condition). A dualidade fornece:

  • formas alternativas de resolver problemas
  • certificados de otimalidade
  • intuições sobre regularização e restrições (por exemplo, multiplicadores de Lagrange (Lagrange multipliers) como “preços”)

4) Algoritmos têm garantias de convergência global

Muitos algoritmos — descida do gradiente (gradient descent), métodos acelerados (accelerated methods), métodos de ponto interior (interior-point methods), métodos proximais (proximal methods) — vêm com garantias explícitas como:

  • convergência para o ótimo global
  • taxas como (O(1/k)), (O(1/k^2)), ou convergência linear (linear convergence) sob convexidade forte

Isso contrasta fortemente com a otimização não convexa geral (por exemplo, em aprendizado profundo), onde as garantias são mais fracas e frequentemente focam na convergência para pontos estacionários (stationary points).

Para métodos baseados em gradiente em contextos de AM, veja Descida do Gradiente e, para treinamento com gradientes ruidosos, veja Otimização Estocástica.

Objetivos convexos canônicos em aprendizado de máquina

Muitos objetivos de AM amplamente usados são convexos nos parâmetros do modelo.

Mínimos quadrados (regressão linear)

Dada a matriz de dados (X \in \mathbb{R}^{N\times d}) e alvos (y \in \mathbb{R}^N), a perda quadrática (squared loss) é:

[ \min_w ;; \frac{1}{2}|Xw - y|_2^2. ]

  • Quadrática convexa em (w)
  • Fortemente convexa se (X^\top X) tem posto completo (full rank) (ou com regularização (L_2))

Regressão de crista (ridge regression) adiciona ( \frac{\lambda}{2}|w|_2^2 ), melhorando o condicionamento e garantindo convexidade forte mesmo se (X) for deficiente em posto.

Regressão logística (classificação convexa)

A regressão logística binária minimiza a log-verossimilhança negativa (negative log-likelihood):

[ \min_w \sum_{i=1}^N \log(1+\exp(-y_i w^\top x_i)) + \lambda |w|_2^2 ]

A perda logística (logistic loss) é convexa em (w), e adicionar regularização (L_2) tipicamente torna o problema fortemente convexo.

Máquinas de Vetores de Suporte (perda hinge)

Uma forma primal comum:

[ \min_w \frac{1}{2}|w|2^2 + C\sum{i=1}^N \max(0, 1 - y_i w^\top x_i) ]

  • A perda hinge (hinge loss) é convexa, mas não diferenciável (linear por partes)
  • Ainda é tratável usando subgradientes (subgradients) ou solucionadores especializados

LASSO e aprendizado esparso (convexo, mas não suave)

[ \min_w \frac{1}{2}|Xw-y|_2^2 + \lambda |w|_1 ]

A norma (L_1) é convexa e incentiva esparsidade, mas é não suave (non-smooth). Isso motiva métodos de gradiente proximal (proximal gradient) e descida por coordenadas (coordinate descent).

Restrições: mantendo a viabilidade convexa

Restrições convexas aparecem naturalmente em sistemas de AM e IA:

  • Restrições de caixa (box constraints): (l \le x \le u) (por exemplo, parâmetros limitados)
  • Restrições de norma (norm constraints): (|w|_2 \le r) (regularização na forma de restrição)
  • Restrições de simplex (simplex constraints): (p_i \ge 0, \sum_i p_i = 1) (vetores de probabilidade)
  • Restrições de semidefinição positiva (positive semidefinite, PSD): (X \succeq 0) (aprendizado de kernels (kernel learning), relaxações de aprendizado de métricas (metric learning))

Uma ideia prática fundamental: muitos regularizadores podem ser expressos tanto como penalidades (penalties) quanto como restrições convexas (frequentemente equivalentes via multiplicadores de Lagrange).

Algoritmos de otimização convexa (visão prática)

Estruturas convexas diferentes sugerem solucionadores diferentes.

Descida do gradiente (convexa suave)

Para minimizar (f) convexa suave, a descida do gradiente padrão:

w = w0
for t in range(T):
    w = w - eta * grad_f(w)
  • Funciona bem quando gradientes são baratos
  • A taxa de convergência depende de suavidade e convexidade forte
  • Em AM, frequentemente usamos gradientes estocásticos; veja Otimização Estocástica

Método de Newton (suave, duas vezes diferenciável)

Usa a curvatura da Hessiana:

[ w_{t+1} = w_t - \left(\nabla^2 f(w_t)\right)^{-1}\nabla f(w_t) ]

  • Muito rápido perto do ótimo
  • Caro em altas dimensões (inversão da Hessiana), mas poderoso para problemas convexos de escala média

Gradiente proximal (composto: não suave + suave)

Muitos objetivos de AM têm a forma:

[ \min_x ; f(x) + g(x) ]

onde (f) é convexa suave e (g) é convexa, mas possivelmente não suave (por exemplo, (L_1)).

Passo de gradiente proximal:

[ x_{t+1} = \mathrm{prox}_{\eta g}(x_t - \eta \nabla f(x_t)) ]

Este é um método “coringa” para aprendizado esparso e minimização do risco empírico (empirical risk minimization, ERM) com regularização.

Métodos de ponto interior (convexa com restrições)

Para problemas com muitas restrições e dimensão moderada, métodos de ponto interior podem ser extremamente eficazes e fornecer soluções de alta precisão — especialmente em programação linear (LP), programação quadrática (QP) e alguns programas cônicos.

Exemplo prático: resolvendo um problema convexo com CVXPY

CVXPY é um pacote Python comum para especificar problemas convexos de forma declarativa (a escolha do solucionador é feita “por baixo do capô”).

Exemplo: LASSO (mínimos quadrados + penalidade (L_1))

import cvxpy as cp
import numpy as np

N, d = 200, 50
X = np.random.randn(N, d)
w_true = np.zeros(d)
w_true[:5] = np.array([2, -1.5, 0.5, 3.0, -2.0])
y = X @ w_true + 0.1 * np.random.randn(N)

w = cp.Variable(d)
lam = 0.2

objective = cp.Minimize(0.5 * cp.sum_squares(X @ w - y) + lam * cp.norm1(w))
problem = cp.Problem(objective)
problem.solve()

print("status:", problem.status)
print("objective:", problem.value)
print("nonzeros:", np.sum(np.abs(w.value) > 1e-4))

Por que isso é convexo:

  • sum_squares é quadrática convexa
  • norm1 é convexa
  • soma de funções convexas é convexa

Na prática, gradiente proximal ou descida por coordenadas pode escalar melhor do que solucionadores genéricos para (N,d) muito grandes, mas o CVXPY é excelente para correção e prototipagem.

Convexidade vs. não convexidade no aprendizado profundo moderno

A maioria dos objetivos de treinamento de redes neurais profundas é não convexa devido a:

  • composição de camadas não lineares
  • simetrias de parâmetros
  • interações multiplicativas

Então por que aprender otimização convexa em um currículo de IA?

  • Ela fornece o “caso ideal” no qual a otimização é totalmente compreendida.
  • Muitos subproblemas dentro de sistemas maiores são convexos (calibração, alguns passos de inferência, certos regularizadores, passos de projeção).
  • Ferramentas de análise convexa (dualidade, subgradientes, operadores proximais) aparecem em métodos modernos (por exemplo, modelos esparsos, predição estruturada, otimização robusta).
  • Relaxações convexas podem converter problemas combinatórios difíceis em aproximações tratáveis.

Mesmo quando a paisagem global é não convexa, o pensamento convexo ajuda você a projetar objetivos com melhor condicionamento, interpretar regularização e raciocinar sobre convergência.

Relaxações convexas: tornando problemas difíceis tratáveis

Uma estratégia comum é substituir um problema não convexo difícil por um problema convexo mais fácil de resolver.

Exemplos:

  • Substituir uma restrição não convexa por seu fecho convexo (convex hull) (o conjunto convexo mais “apertado” que a contém)
  • Usar (L_1) como substituto convexo (convex surrogate) para (L_0) (esparsidade)
  • Relaxações semidefinidas (semidefinite relaxations) para certos problemas de otimização discreta

Relaxações trocam exatidão por tratabilidade, mas frequentemente funcionam surpreendentemente bem na prática.

Armadilhas comuns e “pegadinhas”

  • Convexo em predições não é o mesmo que convexo em parâmetros.
    Uma perda pode ser convexa em (z = w^\top x), mas, uma vez que você introduz parametrização não linear (por exemplo, redes profundas), a convexidade pode desaparecer.

  • Convexo não suave ainda é convexo.
    Perda hinge e (L_1) são convexas, mas não diferenciáveis em todo lugar. A otimização se apoia em subgradientes ou passos proximais.

  • Mau condicionamento pode tornar problemas convexos difíceis numericamente.
    Mesmo que o ótimo global seja fácil “em princípio”, atributos mal escalonados ou matrizes quase singulares podem desacelerar drasticamente a convergência. Regularização e escalonamento de atributos ajudam.

  • Restrições devem preservar convexidade.
    Restrições de igualdade devem ser afins; uma restrição de igualdade não linear geralmente torna o conjunto viável não convexo.

Resumo: principais conclusões

  • Problemas de otimização convexa são aqueles com objetivos convexos e conjuntos viáveis convexos (com igualdades afins).
  • Convexidade implica uma paisagem excepcionalmente favorável: sem mínimos locais espúrios, condições fortes de otimalidade e dualidade poderosa.
  • Muitos modelos centrais de AM (mínimos quadrados, regressão logística, MVS, LASSO) são convexos e servem como exemplos fundamentais.
  • Métodos convexos fornecem tanto ferramentas práticas (solucionadores, métodos proximais) quanto ferramentas conceituais (dualidade, certificados) que continuam úteis mesmo no aprendizado profundo não convexo.

Tópicos relacionados nesta seção: Otimização com Restrições, Otimização Estocástica e métodos de otimização como Descida do Gradiente.