Otimização Convexa — Conceitos, Métodos e Aplicações

Otimização convexa significa minimizar uma função convexa sobre um conjunto viável convexo. O principal motivo de isso ser importante é simples: se essas condições de convexidade valem, qualquer mínimo local também é um mínimo global.

Essa garantia torna esses problemas muito mais confiáveis do que problemas gerais de otimização. Ainda é preciso modelar o problema corretamente, mas, quando o modelo é convexo, você não fica procurando uma solução que só parece melhor em uma pequena vizinhança.

Uma forma comum é

$$\text{minimize } f(x)$$

sujeito a

$$g_i(x) \le 0 \quad \text{for } i=1,\dots,m, \qquad Ax=b,$$

em que $f$ e cada $g_i$ são convexas, e as restrições de igualdade são afins. Nessas condições, o conjunto viável é convexo e o problema de otimização é convexo.

Definição de Otimização Convexa

Uma função $f$ é convexa se, para quaisquer dois pontos $x$ e $y$ em seu domínio e qualquer $0 \le t \le 1$,

$$f(tx + (1-t)y) \le t f(x) + (1-t) f(y).$$

Em linguagem simples, o segmento de reta entre dois pontos do gráfico fica acima do gráfico. Em uma variável, muitas funções convexas têm formato de tigela, mas a desigualdade é o teste real.

Um conjunto é convexo se, sempre que contém dois pontos, também contém todos os pontos do segmento de reta entre eles.

Você precisa das duas partes:

• uma função objetivo convexa
• um conjunto viável convexo

Se qualquer uma dessas partes falhar, o problema pode deixar de ser convexo.

Por Que a Otimização Convexa É Mais Fácil de Analisar

A otimização costuma ser difícil porque pode haver muitos vales. Um algoritmo pode continuar melhorando a função objetivo e ainda assim parar em um ponto que é apenas localmente o melhor.

A otimização convexa elimina esse modo específico de falha. Se a função objetivo é convexa e a região viável é convexa, então um ponto que não pode ser melhorado localmente já é globalmente ótimo. É por isso que problemas convexos são importantes em estatística, aprendizado de máquina, controle e pesquisa operacional.

Isso não significa que todo problema convexo seja fácil. Alguns ainda são grandes ou computacionalmente caros. Significa que a estrutura é limpa o suficiente para que bons algoritmos possam buscar o ótimo verdadeiro em vez de ficarem presos por comportamentos locais enganosos.

Exemplo Resolvido de Otimização Convexa

Considere o problema sem restrições

$$\text{minimize } f(x) = (x-3)^2 + 2.$$

Este é um problema de otimização convexa porque $f(x)$ é uma função quadrática com coeficiente líder positivo, então ela é convexa em todos os números reais.

Para encontrar o minimizador, derive:

$$f'(x) = 2(x-3).$$

Iguale a derivada a zero:

$$2(x-3)=0 \quad \Rightarrow \quad x=3.$$

Agora avalie a função objetivo:

$$f(3) = (3-3)^2 + 2 = 2.$$

Portanto, o valor mínimo é $2$, atingido em $x=3$.

Este exemplo é simples, mas mostra a ideia principal. Quando você chega a $x=3$, não existe um vale mais baixo escondido em outro lugar.

Métodos Comuns para Otimização Convexa

O método depende da estrutura do problema.

Para problemas suaves sem restrições ou com restrições simples, métodos baseados em gradiente são comuns, porque mover-se na direção oposta ao gradiente pode reduzir a função objetivo.

Para muitos problemas convexos com restrições, métodos de ponto interior são amplamente usados porque lidam diretamente com as restrições e muitas vezes têm bom desempenho na prática.

Para problemas convexos não suaves, métodos de subgradiente ou proximais podem ser mais apropriados. A ideia importante não é a lista de algoritmos. É a garantia de que a estrutura convexa dá a esses algoritmos algo estável com que trabalhar.

Erros Comuns em Otimização Convexa

Supor Que um Gráfico Prova Convexidade

Um gráfico pode parecer em forma de tigela em uma visualização e ainda assim não ser convexo em todo o domínio ou em dimensões maiores. A definição ou regras padrão de convexidade importam mais do que um esboço.

Esquecer Que as Restrições Importam

Uma função objetivo convexa, sozinha, não basta. Se o conjunto viável não é convexo, o problema como um todo não é um problema de otimização convexa.

Tratar Todo Ponto Crítico Como Mínimo

Para uma função convexa diferenciável, um ponto com gradiente zero é um minimizador global. Sem convexidade, essa conclusão não vale em geral.

Confundir Convexo com Estritamente Convexo

Convexidade estrita é uma condição mais forte. Ela muitas vezes dá um minimizador único, enquanto a convexidade simples nem sempre garante unicidade.

Onde a Otimização Convexa É Usada

A otimização convexa aparece sempre que um problema real pode ser modelado com custos convexos e restrições convexas.

Exemplos comuns incluem ajuste por mínimos quadrados, máquinas de vetores de suporte, seleção de portfólio sob modelos convexos de risco e muitos problemas de alocação de recursos. O modelo exato importa: uma aplicação só é convexa quando a função objetivo e as restrições escolhidas realmente satisfazem as hipóteses de convexidade.

Quando a Convexidade Ajuda na Prática

A otimização convexa é especialmente útil quando você precisa de mais do que apenas um número. Muitas vezes, você quer uma garantia de que a resposta é realmente ótima para o modelo que escreveu.

Essa garantia importa em engenharia e no trabalho com dados porque separa duas perguntas:

1. Resolvemos o problema matemático corretamente?
2. O problema matemático era um bom modelo da realidade?

A convexidade ajuda muito com a primeira pergunta. Ela não resolve automaticamente a segunda.

Tente um Problema Parecido

Considere $f(x) = (x+1)^2 + 5$ e encontre seu mínimo. Depois compare com $f(x) = -(x+1)^2 + 5$, que é côncava, não convexa. Essa comparação lado a lado torna o papel da convexidade muito mais fácil de ver.

Se quiser explorar outro caso, tente montar um pequeno problema de mínimos quadrados e veja como minimizar uma função de erro convexa leva a um melhor ajuste estável.