O problema matemático clássico se manifesta no mundo real

Cem anos atrás, o grande matemático David Hilbert fez uma pergunta de pesquisa no campo da matemática pura. Desenvolvimentos recentes na teoria da otimização levam o trabalho de Hilbert ao mundo dos robomobiles

Muito antes que os robôs pudessem correr e os carros pudessem dirigir, os matemáticos consideravam uma simples questão matemática. Finalmente, eles resolveram o problema e o deixaram de lado - sem poder saber que o objeto de sua curiosidade matemática se manifestaria em máquinas de um futuro distante.

O futuro chegou. Como resultado do novo trabalho de Amir Ali Ahmadi e Aniruda Majumara da Universidade de Princeton, o problema clássico da matemática pura está pronto para fornecer uma prova de ferro de que drones e robomobiles automáticos não colidirão com árvores ou taxiarão na pista que se aproxima.

"Existe uma garantia total e 100% demonstrável de que seu sistema" pode evitar colisões, disse Georgina Hall , uma estudante de Princeton que colaborou com Ahmadi neste trabalho.

Amir Ali Ahmadi, professor de Princeton

A garantia é obtida em um local inesperado - em um problema matemático conhecido como " soma dos quadrados ". Foi colocado em 1900 pelo grande matemático David Hilbert. Ele perguntou se certas equações sempre podem ser expressas como a soma de dois termos separados, cada um dos quais ao quadrado.

Os matemáticos responderam à pergunta de Hilbert algumas décadas depois. Então, quase 90 anos depois, cientistas e engenheiros da computação descobriram que essa propriedade matemática - a expressibilidade de uma equação em termos da soma dos quadrados - ajuda a resolver muitos problemas reais que eles gostariam de resolver.

"Muita matemática clássica do século 19 é usada no que faço, juntamente com matemática computacional muito moderna", disse Ahmadi.

No entanto, assim que os pesquisadores perceberam que a soma dos quadrados poderia ajudar a responder a muitos tipos de perguntas, eles tiveram problemas ao aplicar essa abordagem. O novo trabalho elimina um dos maiores problemas desse tipo, forçando a antiga questão matemática a resolver algumas das questões tecnológicas mais importantes do nosso tempo.

Positivo garantido

O que significa que uma certa quantidade é a soma dos quadrados? Pegue o número 13. Essa é a soma de dois quadrados - 2 ² e 3 ² . O número 34 é a soma de 3 ² e 5 ² .

Em vez de números, a pergunta de Hilbert - 17 dos 23 problemas que ele propôs no início do século 20 - lida com polinômios como 5x ² + 16x + 13. Esses polinômios às vezes também podem ser representados como somas de quadrados. Por exemplo, 5x ² + 16x + 13 pode ser reescrito como (x + 2) ² + (2x + 3) ² .

Quando uma expressão é a soma dos quadrados, você sabe que é sempre positiva (todos os números [reais] ao quadrado dão um número positivo ou zero, e a soma dos números positivos é positiva). Hilbert queria saber se isso funciona da outra maneira: todos os polinômios não negativos podem ser expressos como a soma dos quadrados das funções racionais. Em 1927, o matemático Emil Artin provou que a hipótese de Hilbert era verdadeira.

Essa relação é bastante útil. Se você receber um polinômio complexo, com dezenas de variáveis ​​elevadas ao mais alto grau, é bastante difícil determinar imediatamente se é sempre negativo. “Alguns polinômios são obviamente não negativos, outros não. É difícil testá-los quanto à não-negatividade ", disse Ahmadi.

Mas assim que você mostrar que esse polinômio pode ser expresso em termos da soma dos quadrados, a não-negatividade será simplesmente uma conseqüência disso. "A soma dos quadrados fornece um belo certificado de positividade", disse Pablo Parrilo , cientista da computação e engenheiro do Instituto de Tecnologia de Massachusetts, envolvido em trazer a questão da soma dos quadrados para o mundo das aplicações.

Saber que um polinômio em particular é sempre não negativo pode parecer trivialidade matemática. Mas cem anos depois que Hilbert fez sua pergunta, a não negatividade dos polinômios acabou sendo a resposta para os problemas aplicados que afetam a todos nós.

Melhor maneira

A soma dos quadrados encontra o mundo real no campo da otimização. A teoria da otimização está preocupada em encontrar a melhor maneira de fazer algo enquanto estiver dentro das restrições - por exemplo, encontrar a melhor rota para começar a trabalhar, dado o estado da estrada e a parada necessária que você precisa fazer ao longo do caminho. Tais cenários geralmente podem ser reduzidos a polinômios. Nesses casos, é possível resolver ou "otimizar" o cenário, localizando o valor mínimo que o polinômio assume.

Encontrar o mínimo de um polinômio com muitas variáveis ​​é uma tarefa difícil. Não existe um algoritmo simples no livro para calcular o valor mínimo de polinômios complexos; além disso, eles são difíceis de construir em um gráfico.

Georgina Hall

Como o valor mínimo de um polinômio é difícil de calcular diretamente, os pesquisadores fazem suposições sobre esse valor por outros métodos. É aqui que a não-negatividade entra em jogo, e a questão de saber se um polinômio é a soma dos quadrados. "Garantir a não negatividade é a essência de todos os problemas de otimização", disse Reha Thomas, matemático da Universidade de Washington.

Uma maneira de encontrar o valor mínimo é fazer a pergunta: qual valor máximo pode ser subtraído de um polinômio não negativo para que ele não se torne negativo em algum momento? Para responder à pergunta, é necessário verificar vários valores - é possível subtrair 3 para que não se torne negativo? E 4? E 5? Repetindo o procedimento, em cada etapa você precisa saber se o polinômio permanece não negativo. Isto é verificado através da possibilidade de sua expressão como a soma dos quadrados.

“A pergunta que precisa ser feita é“ o polinômio não é negativo? ”O problema é que, com um grande número de variáveis, é difícil responder a essa pergunta, disse Ahmadi. "Portanto, usamos a soma dos quadrados como um substituto para a não-negatividade."

Assim que os pesquisadores tomam conhecimento do mínimo - o valor ideal do polinômio - eles podem usar outros métodos para determinar os parâmetros de entrada que levam a esse valor. No entanto, para que a não-negatividade ajude a resolver problemas de otimização, você precisa encontrar uma maneira de calcular rapidamente se um polinômio é expresso em termos da soma dos quadrados. E para que os pesquisadores pudessem fazer isso, levou 100 anos a partir do momento em que Hilbert fez a pergunta.

Quebrando o problema

O 17º problema de Hilbert mudou-se do mundo da matemática pura para o plano aplicado por volta do ano 2000. Foi então que vários pesquisadores criaram um algoritmo para verificar se um polinômio pode ser representado em termos da soma dos quadrados. Eles chegaram a esse ponto resolvendo o problema do quadrado por meio de "programação semi-definida ", graças ao qual os computadores são capazes de lidar com essa tarefa. Isso possibilitou que pesquisadores de áreas como ciência da computação e engenharia usassem as possibilidades da não-negatividade para direcionar suas pesquisas para maneiras ótimas de resolver problemas.

Aniruda Majumdar

Porém, a programação semi-definida tem uma grande limitação: trabalha lentamente em grandes tarefas e é incapaz de processar alguns dos polinômios mais complexos pelos quais os pesquisadores estão particularmente interessados. A programação semi-definida pode ser usada para decompor na soma dos quadrados tais polinômios que consistem em não mais do que uma dúzia de variáveis ​​elevadas a uma potência não superior a 6. Polinômios que descrevem problemas complexos de engenharia - por exemplo, garantindo que o robô permaneça de pé - podem insira 50 variáveis, ou até mais do que isso. Um programa pode mastigar esse polinômio até o final dos tempos e ainda não fornecer a soma dos quadrados.

Em um artigo publicado on-line em junho passado, Ahmadi e Majumdar explicam como contornar o trabalho lento da programação semi-definida. Em vez de tentar encontrar a decomposição na soma dos quadrados com um único programa lento, eles mostram como você pode fazer isso com uma solução
seqüências de tarefas mais simples, que serão muito mais rápidas de calcular.

Tarefas desse tipo são chamadas de "lineares" e foram desenvolvidas na década de 1940 para resolver problemas de otimização relacionados a questões militares. Os programas de linha agora são bem compreendidos e resolvidos rapidamente. Em um novo artigo, Ahmadi e Majumdar mostram que é possível resolver muitos programas lineares conectados (ou, em alguns casos, um tipo diferente de problema, um programa de cone de segunda ordem) e combinar os resultados para obter algo quase tão bom quanto a resposta , que poderia fornecer um programa para programação semi-definida. Como resultado, os engenheiros têm uma nova ferramenta prática que eles podem usar para verificar a não-negatividade e encontrar rapidamente a decomposição na soma dos quadrados.

"Estudamos vários problemas de robótica e teoria de controle e mostramos que a qualidade das soluções resultantes é útil para uso prático e que elas são muito mais rápidas de calcular", disse Majumdar.

Prova de segurança

Velocidade de decisão é tudo, se você estiver em um robomóvel. Em tal situação, o polinômio pode atuar como uma barreira matemática criada em torno de obstáculos nos quais você não deseja colidir - se puder ser calculado com rapidez suficiente.

Imagine um exemplo simples: um carro robótico em um estacionamento gigante. Não há nada no estacionamento, exceto um estande de segurança no outro extremo. Sua tarefa é programar a máquina para que nunca caia neste estande.

Nesse caso, você pode puxar a grade para o estacionamento. Em seguida, faça um polinômio que use pontos na grade como entrada. Verifique se os valores do polinômio no local da máquina são negativos e se o valor no local do estande da proteção é positivo.

Em alguns conjuntos de pontos entre o carro e o estande, o polinômio passará de menos para mais. Como seu carro só pode ser localizado onde o polinômio é negativo, esses pontos desempenharão o papel de uma parede.

“Se você começar de um certo lugar, o robô não cruzará a linha atrás da qual o obstáculo está. Isso fornece evidências formais de evitar colisões ”, afirmou Ahmadi.

Obviamente, será inconveniente se essa parede estiver no meio do caminho entre a máquina e o estande. É necessário construir um polinômio para que a parede rodeie o obstáculo o mais firmemente possível. Esta opção protegerá o estande e dará ao carro muito espaço para movimentação.

Na prática, é necessário minimizar o valor - a distância entre a parede e a caixa - para que você precise mudar o gráfico do polinômio e ver até que ponto ele pode ser movido até passar de menos para mais. Isso é obtido verificando se o polinômio permanece a soma dos quadrados.

O estacionamento quase vazio é uma coisa. Mas em cenários realistas de controle de uma máquina, seus sensores constantemente detectam novos obstáculos em movimento - carros, bicicletas, crianças. Cada vez que um novo obstáculo aparece ou um conhecido se move, a máquina precisa construir novos polinômios complexos que envolvam esses obstáculos. São muitas verificações da quantidade de quadrados que devem ser executados em tempo real.

Há sete anos, outro par de pesquisadores já imaginava que essas técnicas para trabalhar com polinômios poderiam ser usadas para separar os robomobiles e os locais onde não deveriam cair. Mas naquela época, o poder dos computadores transformou essa idéia em um sonho.

A nova abordagem de Ahmadi e Majumdar abre uma nova maneira de conduzir essa computação instantânea. Portanto, se e quando os robomobiles puderem se mover com segurança pelo mundo, podemos agradecer ao Google e à Tesla - assim como Hilbert por isso.