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.
| Identifer | oai:union.ndltd.org:uns.edu.ar/oai:repositorio.bc.uns.edu.ar:123456789/3723 |
| Date | 20 May 2014 |
| Creators | Ardenghi, Juan Ignacio |
| Contributors | Brignole, Nélida Beatriz, Vazquez, Gustavo E. |
| Publisher | Universidad Nacional del Sur |
| Source Sets | Universidad Nacional del Sur |
| Language | Spanish |
| Detected Language | Spanish |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0031 seconds