En diversas aplicaciones prácticas cada vez es más frecuente la presencia de problemas de optimización que involucran variables que deben tomar valores discretos. Debido a su naturaleza combinatoria, los problemas de optimización discretos presentan por lo general una complejidad computacional exponencial, y por tanto son mucho más complicados de resolver que los problemas continuos. El trabajo descrito en esta tesis se ha centrado en el estudio y solución al problema de encontrar el punto de una retícula más cercano a un punto dado. Dicho problema puede originarse, entre otras múltiples aplicaciones prácticas, en la detección de señales en sistemas de comunicaciones inalámbricos MIMO (Multiple Input - Multiple Output).
Los problemas de optimización discretos no pueden abordarse con métodos de convergencia rápida basados en derivadas. En su lugar, la solución se obtiene mediante métodos como Ramificación y Poda, programación dinámica y búsquedas heurísticas. El trabajo presentado ha consistido, en primer lugar, en realizar un amplio estudio del estado del arte de los métodos de Búsqueda Directa (que son métodos de optimización no basados en derivadas) y de los métodos Sphere-Decoding (pertenecientes al esquema de Ramificación y Poda). En segundo lugar, se ha abordado la paralelización de estos métodos dirigida a distintas arquitecturas, bien sea arquitecturas con memoria compartida, memoria distribuida y esquemas híbridos; además de explorar, en el caso de la Búsqueda Directa, variantes asíncronas de paralelización.
Adicionalmente se proponen mejoras en los propios algoritmos secuenciales. Se diseñaron e implementaron diversas variantes de métodos de Búsqueda Directa, las cuales tuvieron buenos resultados en la resolución del Problema Inverso Aditivo de Valores Singulares, pues lograron converger y obtener mejor precisión en la solución que los métodos basados en derivadas tipo Newton. / Trujillo Rasúa, RA. (2009). Algoritmos paralelos para la solución de problemas de optimización discretos aplicados a la decodificación de señales [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/7108 / Palancia
| Identifer | oai:union.ndltd.org:upv.es/oai:riunet.upv.es:10251/7108 |
| Date | 11 February 2010 |
| Creators | Trujillo Rasúa, Rafael Arturo |
| Contributors | Vidal Maciá, Antonio Manuel, García Mollá, Víctor Manuel, Universitat Politècnica de València. Departamento de Sistemas Informáticos y Computación - Departament de Sistemes Informàtics i Computació |
| Publisher | Universitat Politècnica de València |
| Source Sets | Universitat Politècnica de València |
| Language | Spanish |
| Detected Language | Spanish |
| Type | info:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/acceptedVersion |
| Source | Riunet |
| Rights | http://rightsstatements.org/vocab/InC/1.0/, info:eu-repo/semantics/openAccess |
Page generated in 0.0024 seconds