Orientadores: Carlile Campos Lavor, Tibérius de Oliveira e Bonates / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-26T15:11:50Z (GMT). No. of bitstreams: 1 Lima_JorgeFerreiraAlencar_D.pdf: 1109545 bytes, checksum: 086223c23c920a9abe0d3661769a6a7d (MD5) Previous issue date: 2015 / Resumo: Geometria de Distâncias Euclidianas (GDE) é o estudo da geometria euclidiana baseado no conceito de distância. É uma teoria útil em diversas aplicações, onde os dados consistem em um conjunto de distâncias e as possíveis soluções são pontos em algum espaço euclidiano que realizam as distâncias dadas. O problema chave em GDE é conhecido como Problema de Geometria de Distâncias (PGD), em que é dado um inteiro K>0 e um grafo simples, não direcionado, ponderado G=(V,E,d), cujas arestas são ponderadas por uma função não negativa d, e queremos determinar se existe uma função (realização) que leva os vértices de V em coordenadas no espaço euclidiano K-dimensional, satisfazendo todas as restrições de distâncias dadas por d. Consideramos tanto problemas teóricos quanto aplicações da GDE. Em termos teóricos, demonstramos a quantidade exata de soluções de uma classe de PGDs muito importante para problemas de conformação molecular e, além disso, conseguimos condições necessárias e suficientes para determinar quando um grafo completo associado a um PGD é realizável e qual o espaço euclidiano com dimensão mínima para tal realização. Em termos práticos, desenvolvemos um algoritmo que calcula tal realização em dimensão mínima com resultados superiores a um algoritmo clássico da literatura. Finalmente, mostramos uma aplicação direta do PGD em problemas de escalonamento multidimensional / Abstract: Euclidean distance geometry (EDG) is the study of Euclidean geometry based on the concept of distance. This is useful in several applications, where the input data consists of an incomplete set of distances and the output is a set of points in some Euclidean space realizing the given distances. The key problem in EDG is known as the Distance Geometry Problem (DGP), where an integer K>0 is given, as well as a simple undirected weighted graph G=(V,E,d), whose edges are weighted by a non-negative function d. The problem consists in determining whether or not there is a (realization) function that associates the vertices of V with coordinates of the K-dimensional Euclidean space, in such a way that those coordinates satisfy all distances given by d. We considered both theoretical issues and applications of EDG. In theoretical terms, we proved the exact number of solutions of a subclass of DGP that is very important in the molecular conformation problems. Moreover, we described necessary and sufficient conditions for determining whether a complete graph associated to a DGP is realizable and the minimum dimension of such realization. In practical terms, we developed an algorithm that computes such realization, which outperforms a classical algorithm from the literature. Finally, we showed a direct application of DGP to multidimensional scaling / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

The main result of this thesis is the development of a theory of semidefinite facial reduction for the Euclidean distance matrix completion problem. Our key result shows a close connection between cliques in the graph of the partial Euclidean distance matrix and faces of the semidefinite cone containing the feasible set of the semidefinite relaxation. We show how using semidefinite facial reduction allows us to dramatically reduce the number of variables and constraints required to represent the semidefinite feasible set. We have used this theory to develop a highly efficient algorithm capable of solving many very large Euclidean distance matrix completion problems exactly, without the need for a semidefinite optimization solver. For problems with a low level of noise, our SNLSDPclique algorithm outperforms existing algorithms in terms of both CPU time and accuracy. Using only a laptop, problems of size up to 40,000 nodes can be solved in under a minute and problems with 100,000 nodes require only a few minutes to solve.

The main result of this thesis is the development of a theory of semidefinite facial reduction for the Euclidean distance matrix completion problem. Our key result shows a close connection between cliques in the graph of the partial Euclidean distance matrix and faces of the semidefinite cone containing the feasible set of the semidefinite relaxation. We show how using semidefinite facial reduction allows us to dramatically reduce the number of variables and constraints required to represent the semidefinite feasible set. We have used this theory to develop a highly efficient algorithm capable of solving many very large Euclidean distance matrix completion problems exactly, without the need for a semidefinite optimization solver. For problems with a low level of noise, our SNLSDPclique algorithm outperforms existing algorithms in terms of both CPU time and accuracy. Using only a laptop, problems of size up to 40,000 nodes can be solved in under a minute and problems with 100,000 nodes require only a few minutes to solve.