Sensibilidade do BFGS às aproximações Hessianas iniciais

9

Estou tentando implementar o método Broyden-Fletcher-Goldfarb-Shanno para encontrar o mínimo de uma função. Preciso de duas suposições iniciais & e uma aproximação inicial da Matriz Hessiana . Os únicos requisitos que encontro para são que, se o Hessian é definido simétrico positivo, também deve . Olhando para a Wikipedia, vejo que uma aproximação inicial típica é (a matriz de identidade). Essa sempre é uma boa inicial ? Existe alguma razão para eu querer escolher outra coisa que não ? Outras opções de B, que satisfazem as mesmas propriedades da matriz, afetariam bastante a convergência do método? x1x0B0B0B0B0=IB0I

Paulo
fonte

Respostas:

6

Se você tem uma aproximação Hessian justificada, é melhor usá-lo em vez do arbitrária .B0=I

Edit: A lógica é que, se você começar perto da solução , a taxa inicial de convergência é (para qualquer ) passo linear com um fator de convergência -se for para alguma correção classificação da matriz de identidade. Assim, tentar fazer isso pequeno é muito valioso. (Isso é equivalente a pré-condicionar o sistema.) O fator de convergência melhora com o tempo e, finalmente, se aproxima de zero (convergência superlinear), mas em muitos problemas reais (especialmente os de alta dimensão), nunca se faz iterações suficientes para alcançar o regime superlinear. Assim, a velocidade inicial é bastante importante.xr>0r+1r+1q=B01f(x)G<1rG

Um caso importante é ao resolver problemas de mínimos quadrados não lineares (minimizar ), em que a aproximação de Gauss-Newton do Hessiano inicial pode ser calculado sem a necessidade de segundas derivadas. Seu uso torna o método BFGS afim invariável, ou seja, invariante sob transformações lineares de como o método de Newton, que geralmente é muito benéfico.F(x)22B0=F(x0)TF(x0)x

Outro caso importante é quando você resolve uma sequência de problemas relacionados. Freqüentemente, reiniciar o solucionador com a aproximação final do problema anterior do Hessian reduz significativamente o número de iterações necessárias.

Arnold Neumaier
fonte
Se se espera que o hessiano seja definido positivo simétrico, qualquer matriz definida positiva simétrica ainda levará à convergência, mas a taxa de convergência se baseia em quão assemelha ao hessiano? B0B0
Paul
Não, eventualmente, o BFGS esquece a matriz inicial; portanto, a convergência como sempre tem a mesma ordem. Mas é claro que isso não é interessante porque você nunca executa infinitamente muitos passos. k
Wolfgang Bangerth
@ Paul: Veja minha edição.
Arnold Neumaier