Implementación de un Método de Programación Semidefinida Usando Computación Paralela

Abstract

En el presente trabajo se estudió y rediseñó una implementación existente del algoritmo Filter-SDP, el cual resuelve problemas de programación semidefinida no lineal de la forma:

donde f : Rn → R, h : Rn → Rp y G : Rn → Sm son funciones de clase C2 y Sm

denota el espacio lineal de las matrices simétricas de m×m dotado del producto interno A·B = . El algoritmo resuelve en cada iteración una aproximación local representada por un problema de programación semidefinida lineal, y adicionalmente

se utiliza un esquema de penalización multi-objetivo, en el cual se minimiza la función

objetivo y una función de mérito utilizando un filtro.

Se estudió la introducción de cálculo paralelo en partes específicas del algoritmo, con el objetivo de disminuir el tiempo de ejecución. Se reimplementó el algoritmo utilizando el lenguaje C y la librería de cálculo paralelo MPI. Esa nueva implementación se comparó con un desarrollo ya existente, realizado sobre la plataforma MATLAB, y se midió su speedup en los problemas más pesados de una batería de tests escogida. Como apoyo al desarrollo del algoritmo, se diseñaron nuevas fases de restauración sobre la plataforma MATLAB, con el objetivo de mejorar la calidad de las soluciones obtenidas. Se diseñaron 4 nuevos métodos para la fase de restauración del algoritmo, cuyas principales áreas de influencia son la restauración inexacta, el diseño de controladores retroalimentados de salida estática y el posicionamiento de polos.

Dentro de los resultados obtenidos, se logró visualizar las ventajas de la nueva implementación con respecto al desarrollo ya existente, así como demostrar el beneficio que se obtiene en el speedup para problemas pesados. También se realizó una comparación entre los métodos diseñados para la fase de restauración, con la cual se llegó a conclusiones que pueden abrir nuevas áreas de investigación y trabajo a futuro.

Finalmente, se aprendió a utilizar una herramienta de álgebra lineal que funciona sobre ambientes de cálculo paralelo, ScaLAPACK, y se perfeccionó el proceso de desarrollo de software que ya se tenía sobre este tipo de plataformas.