Por favor, use este identificador para citar o enlazar este ítem: http://repositoriodigital.uns.edu.ar/handle/123456789/3723
Título : El método del gradiente espectral proyectado acelerado mediante paralelismo : aplicaciones a ingeniería de procesos
Autor(es) : Ardenghi, Juan Ignacio
Director(es) : Brignole, Nélida Beatriz
Vazquez, Gustavo E.
Palabras clave : Ciencias de la Computación; Procesamiento paralelo; Optimización matemática; Algoritmos; Ingeniería de procesos
Resumen : En el área de Ingeniería de Procesos abundan los problemas de optimización no lineales. En busca de formulaciones más realistas ha aumentado la exigencia de un modelado riguroso. Como complejidades incorporadas, al aumento de la cantidad de variables continuas y restricciones no lineales se le suman la presencia de variables binarias. En muchos casos los problemas se resuelven mediante la relajación de variables y condiciones, así generando subproblemas no lineales cuya resolución se realiza a través de aproximaciones lineales y cuadráticas. La pregunta formulada en esta tesis es la siguiente ¿Podemos lograr eficiencia sin tener que relajar el problema? Es decir ¿podemos conseguir soluciones del modelo original en tiempos razonables? En esta tesis proponemos explotar el Método del Gradiente Espectral Proyectado (SPG) mediante su refundación a partir del paradigma paralelo. El SPG es un método de optimización global no monótono para problemas de programación no lineal, con características diferentes a las exhibidas por los métodos clásicos de gradiente proyectado. La no monotonicidad y una elección particular de la longitud del paso permiten aprovechar situaciones especiales que se presentan en muchos problemas, acelerando la convergencia con mínimos costos de almacenamiento de datos. Entre sus características más atractivas aparece su bajo costo en operaciones: SPG no calcula matrices hessianas ni resuelve sistemas lineales. SPG sólo utiliza productos matriz vector y una estrategia de búsqueda lineal no monótona para garantizar convergencia global. Combinado con un esquema de Lagrangiano Aumentado, el método se muestra como una herramienta muy prometedora para el abordaje de problemas muy exigentes en cuanto a esfuerzo computacional y eficiencia. Sus puntos débiles se encuentran en el requerimiento de muchas búsquedas lineales para obtener un nuevo iterado, y en la necesidad de una buena aproximación del gradiente cuando éste no está disponible en forma analítica. En problemas de aplicaciones industriales estos dos aspectos pueden devenir en verdaderos cuellos de botella del algoritmo. En consecuencia, el bajo costo aritmético por iteración no se ve reflejado en el tiempo total de resolución. El auge del desarrollo en la programación en paralelo hace que este paradigma se presente como un recurso que ofrece una gran oportunidad para superar estos inconvenientes. El objetivo de esta tesis fue el desarrollo y análisis del desempeño de una versión eficiente del algoritmo SPG programado en paralelo, asumiendo desconocimiento de expresiones analíticas de la función objetivo o de los gradientes. Este escenario a menudo se presenta en los problemas de optimización en ingeniería de procesos con gran cantidad de variables y restricciones no lineales. La nueva versión del algoritmo SPG genera una sucesión de iterados que es alternativa a la que genera la versión secuencial lo que lo hace más competitivo, pero manteniendo la robustez de convergencia que posee el método SPG original. Se desarrollaron e implementaron dos versiones del algoritmo paralelo: una fue concebida para ejecutarse eficientemente sobre una arquitectura distribuida mediante pasaje de mensajes sobre una red de área local estándar, y la otra fue diseñada para ejecutarse sobre una arquitectura de memoria local compartida. La experimentación numérica se realizó sobre un cluster de 8 procesadores y en una computadora multicore de 12 núcleos. Se demostró en forma teórica la eficiencia esperada. Además, hemos contrastado estos desarrollos teóricos con resultados empíricos obtenidos en algunos problemas de diseño relacionados a plantas de procesos industriales, ubicando así a este resolvedor paralelo como una herramienta competitiva frente a los resolvedores clásicos de paquetes comerciales.
There are many nonlinear optimization problems in the area of Process Engineering. In the search of more realistic formulations the need of more rigorous modeling has grown. The presence of binary variables, the increasing amount of continuous variables and nonlinear constraints count among the incorporated complexities. In many cases the problems are solved by relaxing variables and conditions, thus generating nonlinear subproblems whose resolution is carried out through linear and quadratic approximations. The question posed in this thesis is the following: Can we achieve efficiency without having to relax the problem? I mean: Can we get the original model solutions in reasonable time? In this thesis we propose to exploit the Spectral Projected Gradient method (SPG) by its relaunching from the parallel paradigm. SPG is a non-monotone global optimization method for nonlinear programming problems, its features being different from those exhibited by the classical projectedgradient methods. The non-monotonicity and a particular choice of the step length allow to exploit special situations that arise in many problems, accelerating the convergence with minimal data-storage costs. Its low operating cost features among its most attractive attributes SPG neither calculates Hessian matrices nor solves linear systems. SPG just performs matrix vector products and a non-monotone line-search strategy in order to ensure global convergence. When combined with an Augmented Lagrangian scheme, the method looks like a promising tool for addressing demanding problems in terms of computational effort and efficiency. Its weaknesses lie in the requirement of too many line-searches for a new iterate, and in the need for a good approximation of the gradient when it is not available in analytical form. In industrial application these two mentioned aspects may become real bottlenecks in the algorithm. In consequence, the low arithmetic cost per iteration is not reflected in the total elapsed time of resolution. The boom development in parallel programming presents this paradigm as a resource that provides a great opportunity to overcome these drawbacks. The goal of this thesis was the development and analysis of the performance of an efficient version of the SPG algorithm programmed in parallel, assuming lack of knowledge about the analytical expressions of the objective function or gradients. This scenario often appears in process engineering optimization problems with many variables and non-linear constraints. The new version of the SPG algorithm generates a sequence of iterates that is alternative to the one generated by the sequential version. In this way, the proposed version becomes more competitive, while maintaining the robustness of the original method. Two versions of the parallel algorithm were developed and implemented: one of them was conceived to run efficiently on a distributed architecture by using message passing on a standard local area network, and another one was designed to run on a shared local-memory architecture. The numerical experiments were performed on a cluster of 8 processors and a 12-core multicore computer. We have proved the expected efficiency theoretically. Besides, we have contrasted these theoretical developments with empirical results in some design problems related to industrial plants processes. thus placing this parallel solver as a competitive tool against classical commercial packages.
URI : http://repositoriodigital.uns.edu.ar/handle/123456789/3723
Aparece en las colecciones: Tesis de postgrado

Ficheros en este ítem:
Fichero Tamaño Formato  
Tesis_doctoral_Juan_I_Ardenghi.pdf2,72 MBAdobe PDFVisualizar/Abrir


Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.