Otimização Convexa
- Proposto por
- Stephen Boyd & Lieven Vandenberghe
- Ano
- 2004
- Tipo
- Mathematical optimization framework
- Família
- Mathematical programming
Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês
O que ele faz?
Otimização convexa é um subcampo da otimização matemática que estuda o problema de minimizar funções convexas sobre conjuntos convexos.
Formalizado e popularizado por Stephen Boyd e Lieven Vandenberghe em seu livro de 2004, o framework unifica uma ampla família de problemas — incluindo programação linear, programação quadrática, programação semidefinida e programação de cono de segunda ordem — sob um único teto teórico. Sua propriedade definidora é que qualquer solução localmente ótima é também globalmente ótima, tornando-a tratável e confiável para engenharia, estatística, aprendizado de máquina e pesquisa operacional.
A intuição por trás do método
Imagine um vale em forma de tigela: não importa onde você comece a rolar uma bola, ela sempre se acomodará no mesmo ponto mais baixo. A otimização convexa formaliza essa geometria matematicamente. A função objetivo é a tigela, a região factível é um terreno de forma convexa, e o algoritmo é a bola seguindo a inclinação. Como não há reentrâncias locais ocultas ou cristas enganosas, você tem a garantia de encontrar o verdadeiro mínimo global — tornando a abordagem fundamentalmente diferente e mais confiável do que a otimização não linear geral.
História
As bases teóricas da análise convexa remontam ao trabalho de Minkowski e Farkas no início do século XX, com a programação linear emergindo na década de 1940 através de Dantzig. Métodos de ponto interior, introduzidos por Karmarkar em 1984 e refinados ao longo da década de 1990, tornaram os programas convexos gerais computacionalmente tratáveis. O livro de Boyd e Vandenberghe de 2004 da Cambridge University Press, livremente disponível online, sintetizou décadas de resultados em um framework coerente e acessível e gerou o paradigma de programação convexa disciplinada implementado em CVX, CVXPY e ferramentas relacionadas.
Quando usar
Use otimização convexa quando o objetivo e todas as restrições puderem ser expressos ou reformulados como funções convexas. É apropriado para otimização de portfólio, regressão com regularização, fluxo de rede, máquinas de vetores de suporte e projeto de controle. As suposições chave são a convexidade do conjunto factível e do objetivo; violá-las remove a garantia de otimalidade global. Quando o problema é não convexo, considere relaxações convexas ou resolvedores não lineares locais. Prefira resolvedores de programação linear quando o problema for linear para eficiência adicional.
Limitações e considerações
- A aplicabilidade depende inteiramente de o problema poder ser formulado ou aproximado em forma convexa; muitos problemas do mundo real são inerentemente não convexos.
- Métodos de ponto interior armazenam e fatoram grandes matrizes, tornando os requisitos de memória e tempo substanciais para problemas de altíssima dimensão.
- Relaxações convexas de problemas combinatórios ou inteiros podem produzir soluções fracionárias que não são diretamente acionáveis sem heurísticas de arredondamento.
- A modelagem de problemas requer expertise: uma afirmação incorreta de convexidade remove silenciosamente as garantias teóricas enquanto o resolvedor ainda retorna uma resposta.
As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.
Pontos fortes
- Garante uma solução globalmente ótima sempre que uma formulação convexa for alcançável — sem risco de convergência para um mínimo local.
- Solucionável em tempo polinomial via métodos de ponto interior, fornecendo eficiência prática mesmo para problemas de larga escala.
- A teoria de dualidade fornece certificados de otimalidade, variáveis duais com interpretações econômicas e análise de sensibilidade sem custo adicional.
- Um rico conjunto de regras de composição (DCP) permite a verificação sistemática da convexidade e a transformação automática para a forma pronta para o resolvedor.
Aplicações
- Otimização de portfólio: minimização de variância ou CVaR sujeito a metas de retorno e restrições de alocação em finanças quantitativas.
- Aprendizado de máquina: o treinamento de máquinas de vetores de suporte, regressão lasso e ridge, e regressão logística são programas convexos canônicos.
- Processamento de sinais e imagens: compressão de sensoriamento, denoising de variação total e recuperação esparsa são formulados como programas convexos.
- Rede e alocação de recursos: roteamento ótimo, controle de potência em redes sem fio e alocação de largura de banda sob restrições de capacidade.
- Sistemas de controle: síntese de controladores H-infinito baseada em programação semidefinida e verificação de estabilidade de Lyapunov.
Como funciona
Como funciona
O analista formula o problema de decisão como um programa convexo em forma padrão: minimizar uma função objetivo convexa f0(x) sujeita a restrições de desigualdade convexa fi(x) ≤ 0 e restrições de igualdade afins Ax = b. Obter a formulação correta — escolher a representação correta das variáveis e expressar todas as restrições em forma convexa — é o primeiro passo crítico que determina se as poderosas garantias se aplicam.
Fórmula
\min_{x \in \mathcal{C}} f_0(x) \quad \text{s.t.} \quad f_i(x) \leq 0,\; i=1,\ldots,m,\; Ax = bAntes de resolver, cada função no problema é verificada como convexa, o que significa que seu epígrafo é um conjunto convexo ou, equivalentemente, satisfaz a desigualdade do ponto médio. O conjunto de regras de programação convexa disciplinada (DCP) de Boyd e Vandenberghe fornece uma maneira sistemática de confirmar a convexidade por regras de composição, para que os analistas não precisem provar a convexidade do zero para cada problema.
Fórmula
f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y), \quad \forall x,y \in \text{dom}\,f,\; \theta \in [0,1]O Lagrangiano L(x, λ, ν) é formado relaxando as restrições com multiplicadores duais. Sob a qualificação de restrição de Slater, a dualidade forte se mantém: os ótimos primal e dual coincidem e as condições KKT — estacionariedade, factibilidade primal/dual e folga complementar — são necessárias e suficientes para a otimalidade global. A dualidade também fornece certificados de otimalidade e informações de sensibilidade sobre como o ótimo muda com os dados do problema.
Fórmula
L(x,\lambda,\nu) = f_0(x) + \sum_{i=1}^{m}\lambda_i f_i(x) + \nu^T(Ax-b), \quad \lambda_i \geq 0Métodos de ponto interior, variantes de descida de gradiente ou algoritmos proximais movem-se iterativamente através do conjunto factível em direção ao ótimo. Para problemas suaves não restritos, passos de gradiente com tamanhos de passo adequados convergem em taxas conhecidas. Para problemas restritos ou estruturados, métodos de ponto interior alcançam convergência em tempo polinomial com alta precisão, e métodos de primeira ordem como ADMM escalam para instâncias muito grandes.
Fórmula
x^{(k+1)} = x^{(k)} - t_k \nabla f_0(x^{(k)}), \quad t_k > 0Erros comuns
- Assumir que um problema é convexo sem verificação formal — as regras de composição devem ser verificadas rigorosamente, não por inspeção visual do objetivo.
- Negligenciar o condicionamento numérico: problemas mal escalados fazem com que os resolvedores relatem soluções imprecisas ou infactíveis, apesar da factibilidade teórica.
- Ignorar lacunas de dualidade em resolvedores não padrão ou em configurações onde a condição de Slater falha, o que pode invalidar as afirmações de otimalidade baseadas em KKT.
- Tratar a solução de relaxação convexa como a solução do problema original quando restrições inteiras ou combinatórias foram descartadas durante a reformulação.
Perguntas frequentes
Como sei se meu problema é convexo?
Verifique se a função objetivo e cada função de restrição satisfazem a desigualdade de convexidade do ponto médio, ou verifique a convexidade usando o conjunto de regras de programação convexa disciplinada. Se cada função for construída a partir de primitivas convexas conhecidas combinadas de acordo com regras de composição que preservam a convexidade (função externa convexa não decrescente, funções internas convexas, etc.), o problema é convexo. O Capítulo 3 de Boyd e Vandenberghe fornece um extenso catálogo de funções convexas.
Qual é a diferença entre otimização convexa e programação linear?
Programação linear é um caso especial de otimização convexa onde tanto o objetivo quanto todas as restrições são funções afins (lineares). A otimização convexa é muito mais geral, englobando programas quadráticos, de cono de segunda ordem e semidefinidos. Enquanto os métodos simplex e de ponto interior resolvem programas lineares, apenas os métodos de ponto interior se estendem diretamente para a classe convexa completa.
A otimização convexa pode lidar com variáveis inteiras ou binárias?
Não diretamente — restrições inteiras tornam um problema combinatoriamente difícil e geralmente não convexo. Uma abordagem comum é resolver a relaxação convexa (descartando a integridade) para obter um limite inferior, e então aplicar branch-and-bound ou arredondamento. Resolvedores de programação mista inteira convexa combinam essas ideias, mas a garantia de otimalidade global da otimização convexa pura não se aplica mais em sua total generalidade.
Métodos relacionados
Fontes
Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
ISBN: 978-0-521-83378-3Copiado.