Departamento de Computación

En un gran número de aplicaciones prácticas se requiere la optimización simultánea de varios objetivos. Dado que los criterios a optimizar suelen ser contradictorios, no resulta sorprendente que estos problemas posean un conjunto de soluciones (denominado conjunto de Pareto) en lugar de un óptimo absoluto. Además, bajo ciertas condiciones se tiene que dicho conjunto es típicamente un objeto suave (similar a una superficie o sólido). Por consiguiente, a fin de facilitar la toma de decisiones, nuestra meta es obtener una representación finita del conjunto de Pareto. Alternativamente, se pudiera restringir la búsqueda a una zona especifíca en situaciones en las que el conjunto de interés sea excesivamente grande. En esta tesis se propone un nuevo método predictor corrector para resolver problemas de optimización multi-objetivo mediante técnicas de continuación. El algoritmo, denominado Pareto Tracer, fue diseñado para trazar la curva (u objeto dimensional) de soluciones de Pareto (locales) en problemas con un número arbitrario de objetivos. Adicionalmente, Pareto Tracer es capaz de lidiar con restricciones tanto de caja como de igualdad mediante una modificación del método de Newton utilizado como corrector. Se proponen además dos variantes basadas respectivamente en métodos quasi-Newton y de gradiente descendiente que no requieren el uso de segundas derivadas. El desempeño de la nueva propuesta se discute primero teóricamente y luego se demuestra en varios ejemplos de prueba.

Abstract

In many real-world applications the problem arises that several objectives have to be optimized concurrently leading to a multi-objective optimization problem. Since these goals are typically contradictory, it comes as no surprise that the solution set, the so called Pareto set, of such problems does in general not consist of one single solution but rather of an entire set of optimal points. Moreover, under some mild conditions, this set is typically a smooth manifold (like a surface or solid). For the decision maker it is hence desired to obtain a suitable nite size representation of the optimal set, or to explore (locally) the possibilities around a given solution in situations where the entire Pareto set is too large. In this thesis, we devise a novel predictor corrector method to address multiobjective optimization problems by continuation. The algorithm, Pareto Tracer, is capable to trace the manifold of (local) Pareto solutions of a problem with in principle any number of objectives. Our proposal can cope with box and equality constraints for which a Newton-like method was designed to deal with restrictions. Furthermore, two Hessian-free realizations of the Pareto Tracer were developed based respectively on quasi-Newton and gradient descent approaches. We discuss the algorithm rst theoretically and demonstrate further on its strength on several examples.