A carregar...
Publicação
Trust-region Methods for Multiobjective Derivative-free Optimization
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 4.94 MB | Adobe PDF |
Autores
Orientador(es)
Resumo(s)
Multiobjective optimization is an interdisciplinary field with diverse applications in
science, engineering, environment, finance, medicine, and many other domains. As
objective function components often conflict with each other, finding a single point that
simultaneously minimizes all function components becomes impossible. Instead, the
solution lies in the Pareto front, which represents a set of nondominated points.
This thesis proposes an algorithmthatemploys a trust-region approach to approximate
the set of Pareto critical points in multiobjective optimization problems. Initially, the
algorithm utilizes derivative information from the objective function to compute Taylor
models that provide approximations for the different components of it. Subsequently, the
algorithm will be adapted to handle multiobjective derivative-free optimization problems,
where derivative information is not accessible.
The primary objective of this algorithm is to achieve a comprehensive, densely populated,
and uniformly distributed approximation of the complete Pareto front. This is
accomplished through an iterative process consisting of two main steps: the extreme
point step and the scalarization step. These steps are performed alternately throughout the
algorithm’s execution.
During the extreme point step, the algorithm expands the approximation to the Pareto
front by moving towards its extreme points. These extreme points correspond to the
individual minimization of each objective function component. On the other hand, the
scalarization step focuses on reducing gaps along the Pareto front by solving suitable
scalarization problems.
The scalarization step incorporates a pivotal additional step, referred to as the middle
point step. This step plays an important role in determining the initial points for solving
the scalarization problems. The significance of this step in ensuring the high performance
of the algorithm is substantiated through numerical results.
The algorithm proposed in this thesis incorporates a meticulous approach to managing
the limited evaluations of objective functions. It is specifically designed to address
scenarios where the evaluation of objective functions is computationally expensive and
the budget for such evaluations is restricted. This approach maximizes the quality of the obtained approximation to the Pareto front, allowing for a more accurate representation
of the optimal trade-off solutions in multiobjective optimization problems with expensive
and limited function evaluations.
The thesis provides a detailed and comprehensive analysis of the convergence properties
of the proposed method under the scenario where derivative information of the
objective function is available and utilized. The analysis aims to thoroughly understand
and evaluate the behavior of the algorithm as it iteratively advances toward the Pareto
critical points during the optimization process.
The results of numerical experiments are reported, to illustrate the effectiveness
and robustness of the proposed approach. These experiments are designed with two
main purposes. The first goal is to demonstrate the essentiality of each key algorithmic
feature in achieving optimal performance by this approach. Secondly, the performance
of this algorithm is compared against a state-of-the-art multiobjective derivative-based
optimization solver, which inherently attempts to generate approximations of the complete
Pareto front for a given problem.
In the second phase of the thesis, following the initial algorithm, we further modify
it to compute an approximation of the complete Pareto front in multiobjective derivativefree
optimization problems. In this scenario, the objective functions are assumed to
be expensive black-box functions, where derivatives are not available and cannot be
estimated. The modified algorithm is specifically adapted to fully accommodate the
absence of derivatives.
To approximate the objective function components, the modified algorithm incorporates
various strategies to navigate the challenges posed by the absence of derivatives. It
employs a technique based on polynomial interpolation and minimum Frobenius norm
approaches to compute high-quality models that approximate the objective function
components.
The convergence analysis for the derivative-free version of the algorithm is conducted.
Extensive efforts are devoted to examining the convergence properties of the algorithm,
specifically considering the challenge of lacking derivative information.
Detailed numerical results are presented, demonstrating the notable performance
of the modified algorithm compared to state-of-the-art multiobjective derivative-free
optimization solvers, which also aim to approximate complete Pareto fronts.
A otimização multiobjetivo é um campo interdisciplinar com diversas aplicações em ciência, engenharia, ambiente, finanças, medicina e em muitos outros domínios. Como as componentes da função objetivo frequentemente estão em conflito entre si, encontrar um único ponto que minimize simultaneamente todas as componentes da função torna-se impossível. Em vez disso, a solução do problema consiste na determinação da frente de Pareto, que representa um conjunto de pontos não dominados. Esta tese propõe um algoritmo que utiliza uma abordagem baseada em regiões de confiança para aproximar o conjunto de pontos de Pareto críticos, em problemas de otimização multiobjetivo. Inicialmente, o algoritmo utiliza informação acerca das derivadas da função objetivo para calcularmodelos deTaylorque constituem aproximações das suas diferentes componentes. Posteriormente, o algoritmo será adaptado para lidar com problemas de otimização multiobjetivo sem derivadas, onde a informação acerca das derivadas não está acessível. O objetivo principal deste algoritmo é determinar uma aproximação completa, densamente populada e uniformemente distribuída da fronteira de Pareto. Tal é alcançado por meio de um processo iterativo composto por dois passos principais: o passo de ponto extremo e o passo de escalarização. Estes passos são realizados alternadamente, durante a execução do algoritmo. No passo de ponto extremo, o algoritmo expande a aproximação da frente de Pareto, movendo-se em direção aos seus pontos extremos. Esses pontos correspondem à minimização individual de cada componente da função objetivo. Por outro lado, o passo de escalarização concentra-se na redução de hiatos ao longo da frente de Pareto, por meio da resolução de problemas de escalarização adequados. O passo de escalarização incorpora uma etapa adicional fundamental, designada por passo de ponto médio. Esse passo desempenha um papel importante na determinação dos pontos iniciais para a resolução dos problemas de escalarização. O algoritmo proposto nesta tese incorpora uma abordagem meticulosa para gerir as avaliações limitadas das funções objetivo. É especificamente desenhado para lidar com cenários em que a avaliação das funções objetivo é computacionalmente dispendiosa e o orçamento para tais avaliações é limitado. Esta abordagem maximiza a qualidade da aproximação obtida para a frente de Pareto, permitindo uma representação mais precisa das soluções ótimas de compromisso em problemas de otimização multiobjetivo com avaliação dispendiosa e limitada das funções. Atese providencia uma análise detalhada e abrangente das propriedades de convergência do método proposto, no cenário em que a informação acerca das derivadas da função objetivo está disponível e é utilizada. A análise tem como objetivo compreender e avaliar detalhadamente o comportamento do algoritmo à medida que avança iterativamente, durante o processo de otimização, em direção aos pontos de Pareto críticos. Os resultados da experimentação numérica são relatados para ilustrar a eficácia e a robustez da abordagem proposta. Essas experiências são delineadas com dois objetivos principais. O primeiro, é demonstrar a necessidade de cada elemento estrutural do algoritmo na obtenção de um desempenho ideal por meio desta abordagem. Em segundo lugar, o desempenho do algoritmo é comparado com um código bem estabelecido de otimização multiobjetivo baseado em derivadas, que inerentemente gera aproximações completas da frente de Pareto para um certo problema. Na segunda parte da tese, seguindo a estrutura algorítmica inicial, são introduzidas modificações que permitam determinar uma aproximação à frente de Pareto completa em problemas de otimização multiobjetivo sem derivadas. Neste cenário, assume-se que as funções objetivo são dispendiosas, do tipo caixa-preta, não estando as derivadas disponíveis, nem podendo ser estimadas. O algoritmo modificado é especificamente adaptado para acomodar a ausência de derivadas. Para aproximar as componentes da função objetivo, o algoritmo modificado incorpora diversas estratégias para lidar com os desafios impostos pela ausência de derivadas. Técnicas de interpolação polinomial e abordagens de norma de Frobenius mínima são usadas para calcular modelos de alta qualidade que aproximam as componentes da função objetivo. A análise de convergência para a versão sem derivadas do algoritmo é conduzida. Esforços extensivos são dedicados a examinar as propriedades de convergência do algoritmo, considerando especificamente o desafio da falta de informação acerca das derivadas. Resultados numéricos detalhados são apresentados, demonstrando o bom desempenho do algoritmo modificado por comparação com códigos de otimização multiobjetivo sem derivadas bem estabelecidos, que também procuram aproximar frentes de Pareto completas.
A otimização multiobjetivo é um campo interdisciplinar com diversas aplicações em ciência, engenharia, ambiente, finanças, medicina e em muitos outros domínios. Como as componentes da função objetivo frequentemente estão em conflito entre si, encontrar um único ponto que minimize simultaneamente todas as componentes da função torna-se impossível. Em vez disso, a solução do problema consiste na determinação da frente de Pareto, que representa um conjunto de pontos não dominados. Esta tese propõe um algoritmo que utiliza uma abordagem baseada em regiões de confiança para aproximar o conjunto de pontos de Pareto críticos, em problemas de otimização multiobjetivo. Inicialmente, o algoritmo utiliza informação acerca das derivadas da função objetivo para calcularmodelos deTaylorque constituem aproximações das suas diferentes componentes. Posteriormente, o algoritmo será adaptado para lidar com problemas de otimização multiobjetivo sem derivadas, onde a informação acerca das derivadas não está acessível. O objetivo principal deste algoritmo é determinar uma aproximação completa, densamente populada e uniformemente distribuída da fronteira de Pareto. Tal é alcançado por meio de um processo iterativo composto por dois passos principais: o passo de ponto extremo e o passo de escalarização. Estes passos são realizados alternadamente, durante a execução do algoritmo. No passo de ponto extremo, o algoritmo expande a aproximação da frente de Pareto, movendo-se em direção aos seus pontos extremos. Esses pontos correspondem à minimização individual de cada componente da função objetivo. Por outro lado, o passo de escalarização concentra-se na redução de hiatos ao longo da frente de Pareto, por meio da resolução de problemas de escalarização adequados. O passo de escalarização incorpora uma etapa adicional fundamental, designada por passo de ponto médio. Esse passo desempenha um papel importante na determinação dos pontos iniciais para a resolução dos problemas de escalarização. O algoritmo proposto nesta tese incorpora uma abordagem meticulosa para gerir as avaliações limitadas das funções objetivo. É especificamente desenhado para lidar com cenários em que a avaliação das funções objetivo é computacionalmente dispendiosa e o orçamento para tais avaliações é limitado. Esta abordagem maximiza a qualidade da aproximação obtida para a frente de Pareto, permitindo uma representação mais precisa das soluções ótimas de compromisso em problemas de otimização multiobjetivo com avaliação dispendiosa e limitada das funções. Atese providencia uma análise detalhada e abrangente das propriedades de convergência do método proposto, no cenário em que a informação acerca das derivadas da função objetivo está disponível e é utilizada. A análise tem como objetivo compreender e avaliar detalhadamente o comportamento do algoritmo à medida que avança iterativamente, durante o processo de otimização, em direção aos pontos de Pareto críticos. Os resultados da experimentação numérica são relatados para ilustrar a eficácia e a robustez da abordagem proposta. Essas experiências são delineadas com dois objetivos principais. O primeiro, é demonstrar a necessidade de cada elemento estrutural do algoritmo na obtenção de um desempenho ideal por meio desta abordagem. Em segundo lugar, o desempenho do algoritmo é comparado com um código bem estabelecido de otimização multiobjetivo baseado em derivadas, que inerentemente gera aproximações completas da frente de Pareto para um certo problema. Na segunda parte da tese, seguindo a estrutura algorítmica inicial, são introduzidas modificações que permitam determinar uma aproximação à frente de Pareto completa em problemas de otimização multiobjetivo sem derivadas. Neste cenário, assume-se que as funções objetivo são dispendiosas, do tipo caixa-preta, não estando as derivadas disponíveis, nem podendo ser estimadas. O algoritmo modificado é especificamente adaptado para acomodar a ausência de derivadas. Para aproximar as componentes da função objetivo, o algoritmo modificado incorpora diversas estratégias para lidar com os desafios impostos pela ausência de derivadas. Técnicas de interpolação polinomial e abordagens de norma de Frobenius mínima são usadas para calcular modelos de alta qualidade que aproximam as componentes da função objetivo. A análise de convergência para a versão sem derivadas do algoritmo é conduzida. Esforços extensivos são dedicados a examinar as propriedades de convergência do algoritmo, considerando especificamente o desafio da falta de informação acerca das derivadas. Resultados numéricos detalhados são apresentados, demonstrando o bom desempenho do algoritmo modificado por comparação com códigos de otimização multiobjetivo sem derivadas bem estabelecidos, que também procuram aproximar frentes de Pareto completas.