Otimização convexa

Pré-requisitos: Este artigo irá usar alguma matemática avançada, nomeadamente cálculo uni e multivariável. Adicionalmente, é útil conhecer alguns conceitos de álgebra linear, como o conceito de matriz e multiplicação de matrizes.

Por otimização normalmente entende-se problemas no seguinte formato:

• Input: uma função $f$ que mapeia objetos de um conjunto $S$ qualquer em números reais;
• Output: um elemento $x_0 \in S$ que minimize (ou maximize) $f$, ou seja, $f(x_0) \leq f(x), \forall x \in S$ (ou $f(x_0) \geq f(x), \forall x \in S$);

Existem imensos problemas interessantes em ciência de computadores podem ser escritos como um problema de otimização, ainda que nem sempre seja útil fazê-lo.

Para contextualizar, vejamos um problema, que já devem ter ouvido falar, escrito neste formato:

• Input: Seja $T$ um conjunto de pontos em duas dimensões (em $\mathbb{R}^2$), $S$ o conjunto de pares de pontos em $T$, ou seja, $S = \{(p_1, p_2) : p_1, p_2 \in T\}$ e $f((p_1, p_2)) = ||p_1 p_2||_2$ (distância entre os dois pontos);
• Output: o par de pontos $(p_1, p_2)$ que minimiza $f((p_1, p_2))$;

Já devem ter reparado que este é o problema clássico do pair de pontos mais próximo (closest pair) que é possível resolver em $O(|T|)$.

Normalmente escrever um problema neste formato não significa que conseguimos extrair uma solução mais eficiente que a trivial (tentar todos os pontos em $S$). Claramente para o exemplo anterior esta formulação não nos ajuda em nada. Porém, se assumirmos que a função $f$ segue algumas propriedades, podemos obter alguma informação importante que pode levar a uma solução mais eficiente.

Tipicamente, o conjunto $S$ é um subconjunto de $\mathbb{R}^n$, para um valor qualquer de $n$, ou seja, é um subconjunto de $n$ dimensões reais. No resto deste artigo vamos assumir que $S$ é sempre deste formato.

Convexidade de funções e conjuntos

Provavelmente já ouviram falar de funções convexas. Um conceito que é ensinado em matemática do ensino secundário é que uma função de $\mathbb{R}$ em $\mathbb{R}$ duas vezes diferenciável é localmente convexa num ponto se a sua segunda derivada nesse ponto for não negativa e globalmente convexa se for localmente convexa para todos os pontos. Vamos ver como é que esta noção é generalizável para funções em $\mathbb{R}^n$ (assim como outras definições) e como é que este conceito se aplica a conjuntos.

Vamos começar por ler o seguinte artigo:

Como já devem ter retirado do artigo, se uma função $f$ for convexa então os seus mínimos locais são mínimos globais. Por mínimo local entendemos, por exemplo para uma função de $\mathbb{R}$ em $\mathbb{R}$, os pontos de derivada 0, enquanto que um mínimo global é um ponto $x$ que minimiza $f(x)$. Isto significa que podemos usar uma técnica greedy muito simples para tentar resolver problemas com esta característica: se caminharmos no domínio da função (em $S$) e encontrarmos pontos sucessivos com valores de $f$ a diminuir, estamos a caminhar para o mínimo global.

Método do gradiente

Vamos considerar o seguinte problema: temos uma função $f$ de $\mathbb{R}^n$ em $\mathbb{R}$ e $S = \mathbb{R}^n$, qual o ponto que minimiza $f$?

Com o conhecimento que adquirimos na secção anterior, podemos agora estudar um método para resolver aproximadamente o problema anterior chamado "método do gradiente". Por aproximadamente significa que vamos obter uma solução que está próxima da solução ótima.

Muito resumidamente, primeiro começamos num ponto aleatório $x_0$ de $\mathbb{R}^n$. De seguida, procuramos um ponto $x_1$ que esteja próximo de $x_0$ e que para o qual se tenha: $f(x_1) < f(x_0)$. Para tal, podemos usar o gradiente de $f$ em $x_0$. Finalmente, repetimos esta operação um conjunto de vezes.

A explicação mais completa e formal encontra-se neste artigo:

Apesar de ser um método aparentemente muito simples, há imenso a dizer sobre ele. Podemos estudar a sua convergência para diferentes regimes de $f$, podemos estudar como escolher a constante de salto, entre outras coisas.

Método de Newton

Veremos agora um método semelhante ao anterior, mas que normalmente obtém uma melhor taxa de convergência: o método de Newton. Este método também se pode estudar em $\mathbb{R}^n$, como fizemos com o método do gradiente, mas para simplificar vamos fazê-lo apenas em $\mathbb{R}$. Para tal, consultem o artigo seguinte:

Como puderam ver, este método é ligeiramente diferente, pois permite-vos calcular zeros de funções. Na verdade é possível modificá-lo para encontrar mínimos também, mas omitimos essa modificação para simplificar.

Aplicação em concursos

É difícil arranjar exemplos simples de problemas onde estes conceitos sejam aplicados. Muito dificilmente algo como os métodos mencionados são aplicados num problema em concursos, mas as ideias de como identificar e usar convexidade para resolver problemas são úteis.

Um bom problema em que isto foi aplicado é o problema Aliens, do segundo dia da IOI 2016. Este problema é bastante difícil, foi o mais difícil de 2016, tendo apenas um 100. Por isso não é muito fácil de entender a solução para 100. Ainda assim, esta é baseada em observar que uma certa função relevante ao problema é convexa e usar isso para descobrir o seu mínimo (através de pesquisa binária).

O exemplo mais comum de problemas em que convexidade é uma propriedade importante são certos problemas que admitem uma solução de programação dinâmica. Por exemplo, considerem a seguinte formulação de programação dinâmica:

$$dp[i] = \min_{j < i} \{dp[j] + b[j] \cdot a[i]\}$$

A solução óbvia para este problema é uma solução $O(n^2)$, mas se tivermos a seguinte propriedade sobre $a$ e $b$: $b[j] \geq b[j + 1]$ e $a[i] \leq a[i + 1]$ então podemos resolver este problema em $O(n)$! Isto utiliza um truque chamado Convex Hull Optimization, que também era útil para o problema de IOI anterior. Visto que este é um conceito avançado, fica reservado para um artigo futuro.

Aplicação em ciência de computadores

Uma pequena nota final sobre este tema no âmbito mais geral do que concursos. Uma das razões para estudar este tipo de propriedades de problemas de otimização é que vários problemas de aprendizagem de máquina (machine learning) e inteligência artificial podem ser escritos neste formato e assim estudados neste contexto. Visto que não é um tema relevante para concursos não nos iremos estender muito sobre ele, mas um facto engraçado é que usando apenas o método do gradiente é possível escrever um classificador de dígitos simples, ou seja, um programa que dado uma imagem de um dígito escrito manualmente, identifica que dígito é.