Algoritmos que buscam soluções para problemas de otimização são o coração do raciocínio da máquina. Novos resultados revelam limites surpreendentes.
Nossas vidas são uma sucessão de problemas de otimização. Eles ocorrem quando buscamos o trajeto mais rápido do trabalho para casa ou tentamos equilibrar custo e qualidade em uma ida à loja, ou mesmo quando decidimos como passar o tempo livre limitado antes de dormir.
Esses cenários e muitos outros podem ser representados como um problema de otimização matemática. Tomar as melhores decisões é uma questão de encontrar as soluções ideais. E para um mundo mergulhado em otimização, dois resultados recentes fornecem boas e más notícias.
Em um artigo publicado em agosto de 2020, Amir Ali Ahmadi da Universidade de Princeton e seu ex-aluno, Jeffrey Zhang, que agora está na Carnegie Mellon University, estabeleceram que para alguns problemas de otimização quadrática – em que pares de variáveis podem interagir – é computacionalmente inviável para encontre até mesmo as soluções ideais localmente de maneira eficiente.
Mas então, dois dias depois, Zhang e Ahmadi divulgaram um segundo artigo com uma conclusão positiva. Eles provaram que sempre é possível identificar rapidamente se um polinômio cúbico – que pode apresentar interações de três vias entre variáveis – tem um mínimo local e descobrir se tem.
Os limites não são o que seus descobridores esperavam.
“Eu não teria pensado que algo mágico acontecesse com cúbicos, o que tornaria seus mínimos locais fáceis de encontrar”, disse Ahmadi.
Em conjunto, os resultados estabelecem dois marcadores importantes no estudo da complexidade computacional, provando que certos tipos de problemas são fáceis de resolver enquanto outros são necessariamente difíceis.
Eles também fornecem novas proteções para pesquisadores interessados na otimização em uma variedade de campos, de finanças a sistemas autônomos.
Life Into Math
Suponha que você seja o responsável por uma fábrica de automóveis que fabrica apenas dois modelos, o Cheapo e o Deluxe. O Deluxe é vendido por mais que o Cheapo, custa mais para fabricar e ocupa mais tempo na linha de produção. Quantos de cada a fábrica deve construir?
Esse dilema se traduz em um problema de otimização polinomial.
Para realizar essa tradução, divida o problema em três elementos distintos. Existem todas as variáveis quantificáveis esperando para serem otimizadas – como o número de carros que você deve produzir – restrições, como orçamentos e capacidade de produção, e então algo chamado de função objetivo, que é a soma de como cada variável o leva em direção ao seu objetivo ou longe disso.
“A função objetivo pega as variáveis de decisão como entrada e cospe um número”, disse Ahmadi. “Isso é algo que sempre queremos minimizar ou maximizar”.
Nosso exemplo de fator de carro é um problema de otimização simples. Conforme descrevemos, estamos assumindo que nenhuma das variáveis interage entre si, o que significa que podem ser empacotadas em uma função linear. Mas a maioria dos problemas do mundo real são mais complicados. A matemática que os descreve também.
Por exemplo, imagine que você está tentando localizar o hub ideal para uma companhia aérea. Cada aeroporto tem seu próprio valor inerente (contribuições lineares) do tráfego ou do custo do aeroporto. Mas então os termos quadráticos capturam o efeito da escolha de pares de aeroportos que interagem entre si de maneiras específicas: se você tem muito tráfego saindo de Los Angeles, se beneficiará mais em emparelhá-lo com um hub de São Francisco.
E é claro que os problemas podem ser ainda mais complicados do que isso. As interações de três vias entre as variáveis requerem funções cúbicas mais complexas.
Cada aumento na complexidade das funções permite modelar uma gama mais ampla de problemas. Mas essa complexidade tem um custo – não há garantia de que você ainda será capaz de calcular as soluções ideais.
Problema ideal
A teoria de otimização moderna desenvolvida durante a Segunda Guerra Mundial, quando um cientista chamado George Dantzig desenvolveu um procedimento para encontrar soluções para problemas de otimização linear. Seu trabalho pioneiro ajudou o Departamento de Defesa dos EUA a tomar decisões informadas sobre tudo, desde a aquisição de aviões até o transporte de suprimentos para o exterior.
Nas décadas seguintes, os pesquisadores seguiram seu exemplo, desenvolvendo algoritmos mais rápidos para encontrar soluções ideais para problemas cada vez mais complicados.
Mas, na década de 1980, esses avanços atingiram uma barreira inamovível. Os pesquisadores provaram que não existe um algoritmo rápido para resolver problemas de otimização. Eles estabeleceram que essas questões são fundamentalmente complexas demais para permitir isso.
Então, para onde você vai se as soluções ideais estão fora de alcance? Você pode pesquisar soluções aproximadas ou soluções ideais “localmente”, como são conhecidas.
As soluções localmente ideais podem não representar o melhor resultado possível, mas são melhores do que quaisquer soluções semelhantes. Eles são maneiras “boas o suficiente” de tomar decisões, como quantos de cada carro fabricar, que não podem ser melhorados por pequenos ajustes em algumas das variáveis. Apenas uma grande reorganização poderia levar ao melhor resultado absoluto, mas para grandes problemas, tal reorganização é computacionalmente intensiva.
Diante de tudo isso, desde o início da década de 1990, os pesquisadores têm tentado determinar se existe um método rápido para encontrar soluções ideais localmente. Em dois casos importantes, Ahmadi e Zhang finalmente descobriram a resposta.
Más notícias para quadráticos
Quando os pesquisadores desejam determinar se um problema é computacionalmente difícil de resolver, eles normalmente o equiparam a alguma outra questão cuja complexidade eles já conhecem. Se você sabe que o Problema A é intratável e pode mostrar que resolver o Problema B forneceria uma maneira de resolver A, aí está a sua prova.
“Isso deve significar que o problema B que tive não é fácil”, disse Zhang.
Em seu primeiro artigo, Ahmadi e Zhang combinaram o desafio da otimização quadrática – na qual pares de variáveis interagem – com algo chamado de problema de conjunto estável máximo, um problema famoso (e comprovadamente) difícil de resolver.
Um “conjunto estável” é qualquer lista de nós em um gráfico em que não haja dois nós diretamente vinculados. O problema do conjunto estável máximo pede para encontrar o maior tal conjunto de um gráfico. Mesmo que você só queira saber se existe um conjunto estável de um determinado tamanho, é computacionalmente complexo determinar a resposta.
Em junho passado, Ahmadi e Zhang reformularam o problema de conjuntos estáveis máximos como um caso especial de busca por soluções ótimas localmente. Eles criaram um método para representar a questão do conjunto estável como um problema de otimização quadrática. Encontrar um conjunto estável de um certo tamanho tornou-se uma questão de encontrar soluções localmente ótimas para esse problema de otimização.
E como eles já sabiam que não havia uma maneira rápida de encontrar esses conjuntos estáveis, eles sabiam que não havia uma maneira rápida de resolver esse problema. Isso significa que soluções localmente ótimas são tão difíceis de encontrar para esses tipos de problemas quanto soluções realmente ótimas – uma correspondência surpreendente.
“Intuitivamente, deve ser mais fácil. O surpreendente é que eles mostram que é difícil”, disse Monique Laurent do CWI, o instituto nacional de pesquisa para matemática e ciência da computação na Holanda.
Boas notícias sobre cúbicos
Ahmadi e Zhang descartaram a existência de um algoritmo eficiente que sempre encontra soluções ótimas localmente para alguns problemas de otimização quadrática. Ao mesmo tempo, eles queriam saber: eles poderiam fazer isso para problemas de otimização cúbica que carregam a condição simplificadora de que eles não incorporam restrições?
Polinômios cúbicos são importantes de muitas maneiras práticas. Eles fornecem uma estrutura matemática para pensar sobre as interações de terceira ordem entre as variáveis. O aumento da clareza pode melhorar enormemente as ferramentas, como aquelas usadas para mineração de texto, onde você deseja que os algoritmos extraiam significado de conjuntos de big data.
Por exemplo, imagine que você coloca um bloco de texto em um computador e pede a ele para determinar do que se trata o texto. O computador observa que a palavra “maçã” aparece com frequência. Mas sem mais informações, o assunto ainda é ambíguo.
“Pode ser a fruta. Pode ser a empresa”, disse Anima Anandkumar, do California Institute of Technology.
Saber que tanto “maçã” quanto “laranja” aparecem deixaria você mais confiante, mas ainda assim você pode estar errado (a Orange também é uma empresa). Um terceiro termo, como “melão”, introduz uma relação cúbica e pode permitir que você conclua com segurança que o texto está falando sobre produtos.
Mas a clareza adicional traz complexidade adicional – e é por isso que Zhang inicialmente não teve muitas esperanças.
“Quando entrei no problema dos mínimos locais cúbicos, na verdade esperava que fosse intratável”, disse ele.
A partir do início de 2019, ele explorou diferentes maneiras de abordar o problema. Ele ficou preso até que Ahmadi sugeriu que ele tentasse uma técnica chamada soma de quadrados, que Ahmadi havia usado anteriormente para resolver outros problemas de otimização.
Um Futuro Mais Brilhante
“Soma de quadrados” refere-se à ideia de que alguns polinômios podem ser representados como a soma do quadrado de outros polinômios. Por exemplo, 2×2 + 16x + 34 = (x + 5)² + (x + 3)².
A perspectiva da soma dos quadrados revela imediatamente as propriedades do polinômio com o qual você começou. Quadrados de números reais não podem ser negativos, então se você pode expressar um polinômio como uma soma de quadrados – e há uma maneira rápida de verificar se você pode – você provou que sempre produz um valor não negativo. Essa abordagem não funciona, no entanto, em problemas de otimização quadrática com restrições, razão pela qual Ahmadi e Zhang não puderam tirar proveito dela em seu trabalho quadrático.
Mas para problemas de otimização cúbica sem restrições, a soma dos quadrados torna-se um teste prático para encontrar soluções mínimas ideais localmente. Imagine o gráfico de uma função polinomial como uma curva flutuando acima do eixo horizontal. Seu ponto baixo corresponde a um determinado arranjo de variáveis.
Um algoritmo rápido pode percorrer uma série de entradas, testando repetidamente se o polinômio é uma soma de quadrados. Ao fazer isso, o algoritmo arrasta a curva para baixo de forma que apenas toque o eixo e quase não seja positivo. Nesse ponto, outro algoritmo rápido pode informar as coordenadas do ponto baixo de forma eficiente.
A descoberta de Zhang e Ahmadi veio quando eles descobriram que a busca por soluções localmente ideais de funções cúbicas pode ser feita encontrando pontos baixos de certos polinômios com o teste de soma dos quadrados.
No gráfico de um polinômio cúbico como x³ + 1, uma extremidade sempre vai para o infinito negativo. Portanto, cúbicos nunca podem ser não negativos em todos os lugares ou uma soma de quadrados. Mas Ahmadi e Zhang descobriram uma maneira de focar exclusivamente na parte do gráfico que se curva para cima. E é aí que eles aplicaram o teste da soma dos quadrados.
“Para cúbicos, podemos sempre arrastar nossa função para onde quisermos”, disse Zhang.
O resultado resolve uma importante questão teórica sobre a dificuldade de encontrar soluções localmente ótimas de funções cúbicas. Ahmadi e Zhang estão agora tentando aumentar seu valor prático atualizando um algoritmo amplamente usado para que possa trabalhar com relações cúbicas em vez de apenas quadráticas. Isso tornaria o programa menos instável e poderia levar a um melhor desempenho para uma série de tarefas de aprendizado de máquina.
“Se eles conseguirem fazer esse trabalho”, disse Laurent, “isso pode ser muito útil”.
Publicado em 02/11/2021 09h23
Artigo original:
- https://www.quantamagazine.org/surprising-limits-discovered-in-quest-for-optimal-solutions-20211101/
Estudo original: