Paralelización del Resolvedor de un Método de Optimizacion No Lineal

Abstract

En este trabajo se trata de reducir el tiempo de computo en un programa de optimización no lineal. Se utiliza el algoritmo FAIPA (Feasible Arc Interior Point Algorithm), de punto interior.
Partiendo de un punto situado en la región admisible va moviendose siempre dentro de esa región. El cálculo de la dirección de búsqueda se hace a partir de tres direcciones básicas. Cada una de estas resulta de resolver un sistema de ecuaciones algebraicas lineales. Los tres sistemas tienen la misma matriz de coeficientes, diferenciándose solo en el vector de términos independientes. El tamaño de estos sistemas es igual a la cantidad de variables de diseño más el número de restricciones. Se propone un resolvedor de tipo LDU (es decir a través de una factorización de la matriz, con L matriz triangular inferior; D matriz diagonal y U matriz triangular superior). Como es sabido la factorización insume
una cantidad de operaciones del orden del cubo del tamaño de la matriz, y las sustituciones hacia adelante y hacia atrás una cantidad de operaciones del orden del cuadrado de ese tamaño. Para reducir los tiempos de proceso, se realiza una descomposición LDU por bloques. Esto redunda en una
importante ganancia de tiempo en procesamiento secuencial. Este esquema se utiliza para hacer la resolución en paralelo.