Constrained Multiobjective Derivative-free Optimization

Abstract

The present work focus on multiobjective derivative-free optimization, proposing strate- gies to address constrained problems. For that, a direct multisearch method that combines a filter-based strategy with an inexact restoration phase, DMS-FILTER-IR, was developed. In this approach, feasibility is treated as an additional component of the objective function that must be minimized. The inexact restoration step attempts to generate new feasible points, thereby prioritizing feasibility, a requirement for the strong performance of any filter approach. Theoretical results are provided, analyzing the different types of sequences of points generated by the new algorithm, and numerical experiments on a set of nonlinearly constrained biob- jective problems are reported, stating the good algorithmic performance of the proposed approach. The filter approach reformulates the original problem by aggregating the constraint violations into an additional objective function component, thereby increasing the number of objectives by one. From a theoretical point of view, DMS-FILTER-IR was developed for continuous constrained multiobjective optimization with an arbitrary number of objectives. However, when the original problem has three or more objectives, the increase of this number caused by the use of the filter, originates a many-objective optimization problem. Thus, strategies to address many-objective optimization problems are also investigated. Based on reduction approaches, employing correlation or sketching techniques, we propose a new variant of DMS, namely DMS-Reduction. This reduction method aims to tackle large problems by decreasing both the number of objective function components and the number of problem variables. Reducing the number of components of the objective function to be optimized at each iteration, has the additional benefit of potentially conducting to a reduction in the number of variables to be optimized, since there could be the case that not all variables are related to the objective function components selected. We detail the proposed algorithm and report a large set of numerical experiments that demonstrate the potential of this approach in addressing many-objective optimization problems. A different way of addressing constraints is resorting to penalization techniques. We investigate the use of a logarithmic barrier technique, both in single and multiobjective derivative-free optimization. For single-objective optimization, we propose the joint use of a mixed penalty-logarithmic barrier method and direct search. A merit function is employed in which the set of inequality constraints is divided into two groups: one is treated with a logarithmic barrier approach, while the other, together with the equality constraints, is addressed using a penalization term. This strategy is incorporated into a generalized pattern search method, enabling the effective handling of general nonlinear constraints. Convergence to KKT-stationary points is established under continuous differ- entiability assumptions, without requiring any form of convexity. Numerical experiments demonstrate the robustness, efficiency, and overall effectiveness of the proposed method, when compared with state-of-the-art solvers. The logarithmic barrier approach is then ex- tended to the multiobjective setting via LOG-DMS, demonstrating improved exploration of the Pareto front under inequality constraints. Comparative experiments indicate that LOG-DMS outperforms traditional DMS and DMS-FILTER-IR in terms of hypervolume metrics. Overall, the contributions of this thesis not only advance the theoretical understanding of constrained derivative-free optimization methods but also provide practical, competitive algorithms for solving optimization problems.

O presente trabalho centra-se na otimização multiobjetivo sem derivadas, propondo estratégias para abordar problemas com restrições. Para tal, foi desenvolvido um método de pesquisa múltipla direta, DMS-FILTER-IR, que combina uma estratégia baseada em filtro com uma fase de restauração inexata. Nesta abordagem, a viabilidade é tratada como uma componente adicional da função objetivo que deve ser minimizada. A etapa de restauração inexata procura gerar novos pontos admissíveis, priorizando assim a admissibilidade, um requisito para o forte desempenho de qualquer abordagem de filtro. São apresentados resultados teóricos, analisando os diferentes tipos de sequências de pontos geradas pelo novo algoritmo, e são relatados ex- perimentos numéricos num conjunto de problemas biobjetivo com restrições não lineares, evidenciando o bom desempenho algorítmico da abordagem proposta. A abordagem baseada em filtro reformula o problema original ao agregar as violações das restrições em uma componente adicional da função objetivo, aumentando assim o número de objetivos em um. Do ponto de vista teórico, o DMS-FILTER-IR foi desenvolvido para a otimização multiobjetivo contínua com restrições, com um número arbitrário de objetivos. No entanto, quando o problema original tem três ou mais objetivos, o aumento deste número causado pelo uso do filtro origina um problema de otimização com muitos objetivos. Assim, estratégias para abordar problemas de otimização com muitos objetivos também são investigadas. Com base em abordagens de redução, empregando técnicas de correlação ou esboço, propomos uma nova variante do DMS, nomeadamente o DMS-Reduction. Este método de redução tem como objetivo resolver problemas de grande dimensão, diminuindo tanto o número de componentes da função objetivo quanto o número de variáveis do problema. Reduzir o número de componentes da função objetivo a ser otimizado em cada iteração tem o benefício adicional de, potencialmente, conduzir a uma redução no número de variáveis a serem otimizadas, uma vez que pode acontecer que nem todas as variáveis estejam relacionadas com os componentes da função objetivo selecionados. Detalhamos o algoritmo proposto e relatamos um vasto conjunto de experimentos numéricos que demonstram o potencial desta abordagem na resolução de problemas de otimização com muitos objetivos. Uma forma diferente de tratar as restrições é recorrer a técnicas de penalização. Investi- gamos o uso de uma técnica de barreira logarítmica, tanto na otimização sem derivadas de objetivo único quanto multiobjetivo. Para a otimização com um único objetivo, propomos o uso conjunto de um método misto de penalização e barreira logarítmica com a pesquisa direta. Utiliza-se uma função mérito na qual o conjunto de restrições de desigualdade é dividido em dois grupos: um é tratado com uma abordagem de barreira logarítmica, enquanto o outro, juntamente com as restrições de igualdade, é abordado através de um termo de penalização. Esta estratégia é incorporada num método de pesquisa em padrão generalizada, permitindo o tratamento eficaz de restrições não lineares. A convergência para pontos estacionários de KKT é estabelecida sob pressupostos de diferenciabilidade contínua, sem exigir qualquer forma de convexidade. Experimentos numéricos demons- tram a robustez, eficiência e eficácia global do método proposto, quando comparado com solucionadores de última geração. A abordagem de barreira logarítmica é, a seguir, estendida ao contexto multiobjetivo através do LOG-DMS, demonstrando uma exploração melhorada da frente de Pareto sob restrições de desigualdade. Experimentos comparativos indicam que o LOG-DMS supera o DMS tradicional e o DMS-FILTER-IR em termos de métricas de hipervolume. De forma geral, as contribuições desta tese não só avançam a compreensão teórica dos métodos de otimização sem derivadas com restrições, como também fornecem algoritmos práticos e competitivos para a resolução de problemas de otimização.