Solving the metric nearness problem: methods and results (2025)
- Authors:
- Autor USP: GUIZARDI, JÚLIA DEMORI - IME
- Unidade: IME
- Sigla do Departamento: MAP
- DOI: 10.11606/D.45.2025.tde-31072025-192457
- Subjects: ALGORITMOS DE APROXIMAÇÃO; APROXIMAÇÃO NUMÉRICA
- Keywords: Algencan; Dykstra; Metric nearness problem; Problema da aproximação métrica; Aproximação métrica
- Agências de fomento:
- Language: Inglês
- Abstract: O Problema da Aproximação Métrica consiste em encontrar a matriz de distâncias mais próxima, usando a norma \ell_p, para uma matriz de dissimilaridade dada de forma que as propriedades métricas, particularmente as desigualdades triangulares, sejam satisfeitas. Este problema pode ser aplicado em diversos contextos, incluindo processamento de imagens, agrupamento de dados e localização de sensores (quando restrições adicionais são acrescentadas), onde os dados fornecidos possuem ruídos ou estão incompletos e precisam ser corrigidos. Este trabalho oferece estudos tanto teóricos quanto práticos do problema. A formulação do problema é apresentada sob as normas \ell_, \ell_ e \ell_{\infty}. Dois métodos de otimização numérica são estudados e aplicados: o método de Lagrangiano Aumentado via Algencan e o método de projeção de Dykstra, que pode ser especificamente programado para este problema. Ambos são aplicados às três normas. Otimizações foram implementadas para lidar com o grande número de restrições, aproveitando de padrões no algoritmo. Diversos experimentos foram conduzidos em conjuntos de dados sintéticos e reais para avaliar o desempenho computacional e a precisão numérica. O problema com a norma \ell_ foi especialmente adaptado ao Algencan devido à sua estrutura não linear, enquanto o método de Dykstra mostrou desempenho superior em conjuntos de grande escala devido à implementação específica que gera baixos requisitos de memória. Em casos lineares, com as normas\ell_ e \ell_{\infty}, também foi realizada uma comparação com o método Simplex. Os resultados revelam que o método de Dykstra, quando aplicado corretamente, pode resolver problemas com até 10^ restrições
- Imprenta:
- Data da defesa: 04.06.2025
- Este periódico é de acesso aberto
- Este artigo NÃO é de acesso aberto
-
ABNT
GUIZARDI, Júlia Demori. Solving the metric nearness problem: methods and results. 2025. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2025. Disponível em: https://www.teses.usp.br/teses/disponiveis/45/45132/tde-31072025-192457/. Acesso em: 24 fev. 2026. -
APA
Guizardi, J. D. (2025). Solving the metric nearness problem: methods and results (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://www.teses.usp.br/teses/disponiveis/45/45132/tde-31072025-192457/ -
NLM
Guizardi JD. Solving the metric nearness problem: methods and results [Internet]. 2025 ;[citado 2026 fev. 24 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45132/tde-31072025-192457/ -
Vancouver
Guizardi JD. Solving the metric nearness problem: methods and results [Internet]. 2025 ;[citado 2026 fev. 24 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45132/tde-31072025-192457/
Informações sobre o DOI: 10.11606/D.45.2025.tde-31072025-192457 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
