Alternativas para Busca Linear em Métodos de Otimização sem Derivadas

Alisson Lucas de Souza; André Luís Machado Martinez; Vitória Moraes Zonfrilli

doi:10.20906/CPS/SICITE2015-0244

Resumo

Neste trabalho, apresentamos resultados iniciais obtidos no estudo dos métodos de otimização sem derivadas que utilizam busca linear, dando ênfase na análise dos métodos de minimização unidimensional. Os métodos de otimização sem derivadas, como o próprio nome indica, são aqueles que não utilizam derivadas em nenhum de seus passos. Vale ressaltar que a proposta de otimização sem derivadas não é desenvolver um algoritmo que supere os métodos clássicos que computam derivadas, no entanto, como uma das razões, é a aplicabilidade em problemas que têm como função objetivo um arquivo executável cujo código não está acessível ao usuário, conhecidos como caixas-pretas. Há uma classe especial de algoritmos sem derivadas que merece destaque, que é a de métodos de Busca Linear. Estes métodos consideram o problema min f(x), sujeita a x ∈ R, onde f: R → R. Então, partindo de um ponto inicial x_0, é necessária a determinação de um passo α que tomado em uma direção de descida d ∈ R consigamos verificarmos em qual vizinhança a função oferece maior decréscimo. Com isso, a cada iteração, esses parâmetros nos direcionam mais próximos da solução do problema. Ao longo do trabalho estudamos os conceitos básicos de otimização, por meio de leitura e demonstrações de proposições e teoremas, bem como um estudo mais detalhado dos métodos de Busca Linear. Para determinar o valor de α usa-se um método de minimização unidimensional, então surgiu a necessidade de encontrar o melhor método para aplicação nos métodos de otimização sem derivada. Para análise e comparação, foram escolhidos os métodos da Seção Áurea, que é baseado no número de ouro: (√5- 1)/2 ≅ 0,618, e Interpolação Quadrática, que se aproveita do fato de que um polinômio normalmente fornece uma boa aproximação para a forma de f(x) na busca da solução. O estudo teórico foi feito em forma de pesquisa em livros recomendados de otimização e, para os testes numéricos, criamos seus algoritmos manualmente e implementamos no software MATLAB.

Palavras-chave: Seção Áurea; Interpolação Quadrática; Otimização; Métodos sem Derivadas