Método BFGS

Um Estudo Comparativo entre as Buscas Armijo e Wolfe na Minimização da Função de Rosenbrock

Abstract

Os métodos quase-Newton buscam alcançar as boas taxas de convergência do método de Newton, mas sem a necessidade de fazer cálculos de segundas derivadas e inversões de matrizes. Essas operações demandam um alto custo computacional, o que pode diminuir o desempenho do método. Nesse contexto destacamos o método Broyden-Fletcher-Goldfarb-Shanno (BFGS) que caracteriza-se por construir aproximações para as inversas das matrizes hessianas. Formalmente, esse método pode ser organizado como o algoritmo a seguir. No passo 5 do algoritmo acima o comprimento de passo α_k é determinado por uma busca linear. Neste trabalho analisaremos o método BFGS equipado com as buscas de Armijo e Wolfe. A busca de Armijo determina α_k > 0 tal que f(x^k + α_kd^k) ≤ f(x^k) + σα_k⟨f'(x^k), d^k⟩, onde σ ∈ (0, 1/2). Observamos que essa busca é bem definida, ou seja, dada uma direção de descida d^k, sempre existe α_k > 0 que satisfaz a desigualdade (1). Além disso ressaltamos que essa busca garante um decrescimento da sequência {f(x^k)}. A busca de Wolfe é caracteriza pela introdução de um critério de curvatura na busca de Armijo, essa busca determina o maior real postivo α_k > 0 que satisfaz f(x^k + α_kd^k) ≤ f(x^k) + σ₁α_k⟨f'(x^k), d^k⟩ e ⟨f'(x^k + α_kd^k), d^k⟩ ≥ σ₂⟨f'(x^k), d^k⟩, onde 0 < σ₁ < σ₂ < 1/2. Para os testes numéricos, consideramos o problema de minimizar a função f: Rⁿ → R conhecida como função de Rosenbrock. Para esse problema, utilizamos o método BFGS equipado com as regras de Armijo e Wolfe com o objetivo de estudar o desempenho de cada uma dessas buscas. Nossos testes consideraram o tempo de CPU e o número de iterações como fatores de comparação entre as buscas. O método foi implementado utilizando a linguagem de programação Julia. Os códigos estão disponíveis livremente no endereço https://github.com/petimatematica/bfgs. Nos testes do BFGS com Armijo, consideramos σ = 0,4 e para os testes com Wolfe consideramos σ₁ = 0,3 e σ₂ = 0,4. Para cada n ∈ {10, 20, ..., 90, 100} foram tomados 10 chutes iniciais aleatoriamente escolhidos. Os testes mostraram que o método BFGS, equipado com a busca de Wolfe, apresentou melhor desempenho em relação ao mesmo método com busca de Armijo no número de iterações. Por outro lado, no tempo de CPU, o método com busca de Wolfe teve resultados ligeiramente melhores. No entanto, essa diferença não foi significativa. [...]