Métodos de otimização sem derivadas baseado em direções aleatórias

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

doi:10.20906/CPS/SICITE2015-0306

Resumo

Neste trabalho, é apresentado um estudo teórico sobre do Algoritmo de Direções Aleatórias, este algoritmo se destaca por ser uma opção de método de otimização sem derivada. Esses métodos sem derivadas, como o próprio indica, não calculam nem utilizam derivadas em nenhum de seus passos. A proposta de otimização sem derivada não é desenvolver algoritmos que superem os tradicionais que computam derivadas, mas sim, resolver os problemas onde as derivadas não estão disponíveis. Há uma classe especial de algoritmos que não utilizam derivadas em nem nenhum de seus passos, que merece destaque, que é a de métodos de Busca Linear. Este método considera o problema min f(x), sujeita a x ∈ ℝ, onde f : ℝ → ℝ . Partindo de um ponto inicial x0 é necessário a determinação de uma direção de descida d ∈ ℝ, para verificar em qual vizinhança a função tem maior decréscimo, direcionando, a cada iteração, mais próximo da solução do problema. Para determinar a direção de descida d ∈ ℝ, os autores do Algoritmo propõem uma busca de direções que são geradas aleatoriamente a cada iteração. O Algoritmo de Direções Aleatórias foi proposto em 2008 em um trabalho de Diniz-Ehrhardt, Martínez e Raydan. Baseados em algumas técnicas derivative-free da literatura, os autores construíram um método globalmente convergente com estratégia de busca linear não monótona. Esse é um grande diferencial do trabalho, por permitir acréscimo na função objetivo, que eventualmente pode utilizar inclusive direção de subida. É visível que a ideia de gerar direções aleatórias para obter a direção de busca foi bastante inovadora, uma vez que ele foi o primeiro método a utilizar direções aleatórias, porém o desempenho apresentado pelo algoritmo foi bastante modesto. Vale ressaltar que, o Algoritmo a cada iteração gera uma direção aleatória havendo assim a possibilidade de diferentes resultados, a cada vez que aplicamos o algoritmo.

Palavras-chave: Algoritmo de Direções Aleatórias; Métodos sem derivadas; Otimização