Entendendo Convexo e Não Convexo na Prática
A diferença entre problemas convexos e não convexos é uma daquelas coisas que todo mundo lê em livro didático mas só entende mesmo quando perde horas rodando uma otimização que simplesmente não converge. O conceito básico é simples. Uma função é convexa se o segmento de linha entre dois pontos quaisquer do gráfico nunca fica acima da curva. Isso implica que qualquer mínimo local é também mínimo global. Problemas convexos são previsíveis nessa direção. Problemas não convexos não têm essa propriedade. Eles podem ter múltiplos mínimos locais, pontos de sela, platôs e outros comportamentos que fazem algoritmos baseados em gradiente pararem em lugares errados. A maioria dos problemas reais de engenharia e aprendizado de máquina são não convexos. Isso não significa que sejam impossíveis, só significa que você precisa ser mais cuidadoso com o que está fazendo.
O que define convexo e não convexo
Para conjuntos, a definição é geométrica. Um conjunto é convexo se, para quaisquer dois pontos pertencentes a ele, toda a linha reta que os conecta também pertence ao conjunto. Uma bola é convexa. Um anel não é. Para funções, a definição exige que a matriz hessiana seja semidefinida positiva em todo o domínio — ou seja, todos os autovalores da Hessiana sejam maiores ou iguais a zero. Se algum autovalor for negativo em qualquer ponto, a função não é convexa naquele ponto. A regra prática que uso no dia a dia é mais simples do que verificar autovalores. Para funções univariadas, basta checar se a segunda derivada é sempre não negativa. Para funções bivariadas ou multivariadas, construo a Hessiana e verifico a condição de Sylvester — todos os menores principais lider devem ser positivos. Na prática, eu faço isso no papel apenas para funções simples. Para funções mais complexas, uso o CVXPY com verificações de disciplina geométrica, que checam automaticamente se a composição preserva a convexidade.
Aqui vai um detalhe que pouca gente menciona: a composição de funções convexas nem sempre preserva convexidade. Se f é convexa e decrescente e g é convexa, então f(g(x)) pode very não ser convexa. Isso quebrou meu pipeline uma vez em um problema de diseño de filtros, onde eu estava minimizando uma norma sobre uma transformação logarítmica dos parâmetros. O problema parecia convexo à primeira vista, mas a composição quebrava a propriedade. A solução foi reparametrizar usando variáveis w = log(x) e reformular toda a expressão original.
Como resolver na prática
Para problemas convexos, a abordagem padrão é usar um solver de programação convexa. No ecossistema Python, o CVXPY é a biblioteca mais usada. Ele usa disciplina geométrica para verificar convexidade automaticamente antes mesmo de enviar o problema para o solver. Se algo não for convexo, o CVXPY levanta uma exceção antes de você gastar tempo esperando por uma solução que não existe no sentido desejado. O CVXOPT lida com problemas quadráticos e lineares, enquanto o SCS resolve problemas de cone geral. Para programação linear pura, o método simplex é o padrão histórico. Ele nada mais é do que um algoritmo que caminha pelos vértices do politopo viável até encontrar o ótimo. Existe também os métodos de ponto interior, que são mais robustos para problemas de grande escala. O interior-point method do Gurobi ou do MOSEK resolve problemas de programação linear com milhares de variáveis em segundos. Para problemas de programação quadrática convexa, o qpOASES e o OSQP são boas escolhas.
Aqui vai algo contra-intuitivo sobre convexidade: problemas convexos de grande escala nem sempre são fáceis. Quando você tem mais de 100 mil variáveis, até mesmo um solver de ponto interior pode ficar lento porque a fatoração da matriz Hessiana é computacionalmente cara. Nesse regime, métodos escalonados como o ADMM (Alternating Direction Method of Multipliers) costumam ser mais eficientes. O ADMM decompõe o problema em subproblemas menores que podem ser resolvidos paralelamente. Eu usei ADMM para um problema de estimação de matriz de covariância com 50 mil variáveis onde um solver direto travava. Para problemas não convexos, o cenário é diferente. Gradientes descendentes com inicializações múltiplas são a ferramenta mais comum. O truque é rodar o otimizador várias vezes a partir de pontos iniciais diferentes e escolher o melhor resultado. Redes neurais são o exemplo clássico — a função de perda é altamente não convexa, mas em prática os mínimos locais que encontramos são bons o suficiente porque a paisagem de perda em altas dimensões tem uma estrutura especial. Muitos dos chamados mínimos locais na verdade são apenas pontos de sela com curvatura quase nula em algumas direções.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Pegadinhas comuns que todo mundo encontra
A primeira pegadinha é assumir que uma função é convexa porque parece "suave". Funções suaves podem ser profundamente não convexas. A função de Rosenbrock, f(x,y) = (1-x)² + 100(y-x²)², é um caso famoso. Ela é diferenciável infinitas vezes, mas tem um vale estreito e curvo que faz algoritmos de otimização patrulharem por aí sem encontrar o mínimo facilmente. Se você está testando um novo otimizador, rode ele na Rosenbrock primeiro. A segunda pegadinha é a questão das restrições. Um problema pode ter uma função objetivo convexa, mas restrições não convexas, e o problema inteiro deixa de ser convexo. Por exemplo, restringir variáveis a estarem fora de uma bola (uma região não convexa) já quebra a convexidade do problema. Já vi gente levar horas tentando resolver um problema assim como se fosse convexo porque a função objetivo era quadrática.
A terceira pegadinha, e essa é mais sutil, é a numérica. Problemas convexos mal condicionados podem fazer solvers retornarem soluções com erro numérico significativo. A condição da matriz Hessiana, medida pelo número de condição, é o indicador principal. Se o número de condição estiver acima de 10, confie pouco no resultado. Na prática, eu já vi o solver do SCS entregar resíduos de 1e-4 para um problema que teoricamente deveria ter convergido para 1e-8, só porque a escala das variáveis estava desbalanceada. Reescalar as variáveis resolveu.
Quando convexo falha completamente
Não adianta ter toda a teoria se o problema não for realmente convexo. Se você aplicar um solver de programação convexa em um problema não convexo, o resultado é inútil. O solver vai encontrar um mínimo local e dizer que é ótimo, mas vai haver um mínimo melhor em algum outro lugar da paisagem de perda. Esse é o risco principal de confiar demais em frameworks que assumem convexidade. Para contornar isso, algumas abordagens úteis incluem relaxações convexas. Você transforma o problema não convexo em um problema convexo aproximado, resolve o problema relaxado, e depois tenta recuperar uma solução factível para o original. Isso funciona bem para problemas de otimização combinatória com restrições específicas. Outro caminho é o branch-and-bound para problemas mistos inteiros convexos (MINLP), que é o que solvers como o BONMIN e o BARON fazem. É mais lento, mas garante optimalidade global dentro de uma tolerância especificada.
Se o seu problema é estritamente não convexo e de larga escala, talvez você precise abrir mão da garantia de optimalidade global e usar métodos heuristicos. Algoritmos genéticos, simulated annealing e particle swarm optimization são opções. Eles não garantem o ótimo, mas em muitos casos práticos de engenharia, uma boa solução viável é suficiente. Eu já resolvi um problema de escalonamento de produção com 200 variáveis inteiras e 50 restrições não lineares usando um híbrido de GRASP com busca local. Levei duas horas para implementar e o solver direto levaria dias se existisse.
Convexo e não convexo: resumo operacional
A verificação prática de convexidade começa com a Hessiana. Se você consegue demonstrar que a Hessiana é semidefinida positiva em todo o domínio da função, o problema é convexo. Caso contrário, é não convexo. Para funções compostas, verifique as regras de composição — soma preserva convexidade, composição com função afim preserva convexidade, mas composição geral não preserva. Para problemas com restrições, verifique tanto a função objetivo quanto as regiões viáveis definidas pelas restrições. O conselho que eu daria é: verifique a convexidade antes de gastar tempo rodando o solver. Um cheque rápido com o Disciplined Convex Programming do CVXPY pode economizar horas de debug. Se o problema for convexo, use um solver de ponto interior para o melhor desempenho. Se for não convexo, considere relaxações ou métodos heurísticos dependendo do tamanho e da estrutura do seu problema específico.
