Métodos de otimização para o problema de geometria de distâncias intervalar

Abstract

O problema fundamental em Geometria de Distâncias consiste em determinar a posição de um conjunto de objetos utilizando apenas algumas distâncias entre pares de objetos. Este problema encontra importantes aplicações, como a determinação da estrutura de proteínas a partir de dados experimentais. Neste caso, as distâncias não são conhecidas exatamente, mas representadas por intervalos reais não-negativos, levando ao problema de Geometria de Distâncias Intervalar. Neste trabalho, focamos no problema de otimização associado e empregamos o método do Gradiente Projetado Espectral para sua resolução. Como este é um método local, apresentamos uma relaxação convexa para o problema original, baseada em programação semidefi nida, que permite a determinação de bons pontos iniciais para o método local. Experimentos numéricos mostram que a abordagem proposta é efi ciente e capaz de recuperar, a partir de dados experimentais, estruturas proteicas com centenas de átomos em poucos minutos e com qualidade razoável.