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.   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, neste trabalho apresentamos uma relaxação convexa para o problema original, baseada em programação semidefinida, que permite a determinação de bons pontos iniciais para o método local.    Experimentos numéricos mostram que a abordagem proposta é eficiente e capaz de recuperar, a partir de dados experimentais, estruturas proteicas com centenas de átomos em poucos minutos e com qualidade razoável.