Bundle methods based on level sets for non-smooth optimization applied to Steiner problems

Autor: Medeiros, Jean Carlos Aparecido, 1995
Přispěvatelé: Santos, Sandra Augusta, 1964, Silva, Paulo José da Silva e, Oliveira, Welington Luis de, Universidade Estadual de Campinas. Instituto de Matemática, Estatística e Computação Científica, Programa de Pós-Graduação em Matemática Aplicada, UNIVERSIDADE ESTADUAL DE CAMPINAS
Jazyk: portugalština
Rok vydání: 2021
Předmět:
Zdroj: Biblioteca Digital de Teses e Dissertações da Universidade Estadual de Campinas (UNICAMP)
Universidade Estadual de Campinas (UNICAMP)
instacron:UNICAMP
Popis: Orientador: Sandra Augusta Santos Dissertação (mestrado) – Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica Resumo: O método de feixes em níveis tem se mostrado um algoritmo robusto para problemas de otimização não suave. Uma das vantagens da variante em níveis está no parâmetro de estabilização, que possui uma forma bem definida de atualização. Inspirados em um trabalho recente, nosso objetivo foi estudar tal método aplicado à resolução de instâncias de problemas de Steiner. Consideramos a resolução desses problemas do ponto de vista da otimização não suave, de modo a explorar suas características geométricas. A partir de uma técnica de diferenciação automática baseada em números duais, implementada em Julia, desenvolvemos um oráculo genérico, capaz de abranger diversas classes de funções. Propusemos quatro formas distintas de implementação do método de feixes em níveis, explorando a formulação primal, ou a dual equivalente, bem como o uso, ou não, da técnica de compressão do feixe. Essas quatro versões foram o principal objeto de estudo dos nossos experimentos numéricos. Com base na análise dos resultados numéricos, tivemos fortes indícios de que tanto o oráculo é uma ferramenta bastante robusta para o problema estudado, quanto as quatro versões implementadas do método de feixes em níveis são capazes de obter resultados satisfatórios, com uma pequena vantagem para as versões baseadas no problema primal, utilizando, ou não, a técnica de compressão. Abstract: Level bundle methods have proven to be robust algorithms for non-smooth optimization problems. One of the advantages of the level variant is the stabilization parameter, which has a well-defined form of updating. Inspired by a recent work, our goal was to study such a method applied to address instances of the Steiner problem. We have considered solving these problems from the non-smooth optimization perspective, in order to take advantage of their geometric features. Using an automatic differentiation technique based on dual numbers, implemented in Julia, we developed a generic oracle, capable of treating different classes of functions. We proposed four different ways of implementing the level bundle method, exploring the primal, or the dual equivalent formulation, as well as the use, or not, of the bundle compression technique. These four versions were the main object of study of our numerical experiments. Based on the analysis of the numerical results, we have noticed that, for the family of problems under consideration, not only the oracle is a very robust tool, but also the four implemented versions of the level bundle method are capable of obtaining satisfactory results, with a small advantage for the versions based on the primal problem, using or not the compression technique. Mestrado Matemática Aplicada Mestre em Matemática Aplicada CAPES 001
Databáze: OpenAIRE
Externí odkaz: