Limits and improvements on searching and optimization: from one dimensional problems to multi-objective optimization

Abstract

Esta tese apresenta uma série de melhorias em quatro métodos clássicos de busca empregados para resolver quatro problemas bem estabelecidos. Os métodos aprimorados e seus problemas correspondentes são: (i) o método da bissecção para problemas de busca de raízes; (ii) o algoritmo de busca binária para procura em listas discretas; (iii) a técnica de back-tracking para buscas inexatas do tipo Armijo; e (iv) o método de otimização utilizando a direção de maior descida para problemas multi-objetivo. Diferentes tipos de melhorias são produzidas em cada instância que, de forma geral, produzem uma redução no número de chamadas à função externa que está sendo procurada. No entanto, todas as quatro melhorias propostas têm uma coisa em comum: as garantias de pior caso dos nossos métodos sempre apresentam uma melhoria em relação ao estado da arte e, quando o estado da arte já apresenta um desempenho de pior caso ótimo, então, os nossos métodos apresentam um desempenho médio ou desempenho assintótico aprimorados em relação ao estado da arte. Neste sentido, os métodos que propomos são melhorias estritas sobre as soluções clássicas, obtidas sem suposições adicionais sobre os problemas considerados e nem com custos adicionais escondidos. O manuscrito começa com uma ampla introdução que discute a importância dos problemas considerados e as soluções clássicas empregadas em vários campos diferentes. As principais contribuições são dadas no quatro capítulos subsequentes. Cada capítulo corresponde a uma resultado publicado (ou em vias de ser publicado) com a adição de material exclusivo à tese intimamente relacionados com os quatro problemas considerados. No sexto e último capítulo, apontamos as possíveis ramificações das descobertas aqui delineadas, que apresentam potencial para desenvolvimentos futuros.