Motivação intuitiva para atualização do BFGS

15

Estou dando uma aula de pesquisa de análise numérica e buscando motivação para o método BFGS para alunos com formação / intuição limitada em otimização!

J k ( → x k - → x k - 1 ) = f ( → x k ) - f ( → x k - 1 )__Jk-Jk-1 1__Para2Jk(x→k-x→k-1 1)=f(x→k)-f(x→k-1 1)

As derivações das atualizações do BFGS parecem muito mais envolvidas e obscuras! Em particular, eu gostaria de não assumir a priori que a atualização deve ser de nível 2 ou assumir uma forma específica. Existe uma pequena motivação de aparência variada para a atualização do BFGS Hessian como a de Broyden?

optimization iterative-method nonlinear-programming Justin Solomon
fonte
4
Se você permitir uma atualização arbitrária, poderá usar o Hessian completo no método de Newton. Uma grande vantagem computacional de uma atualização de baixa classificação é que ela permite atualizar a fatoração do Hessian aproximado muito rapidamente.
Brian Borchers 12/09

Respostas:

12

A derivação do BFGS é mais intuitiva quando se considera (estritamente) funcionais de custo convexos:

No entanto, algumas informações básicas são necessárias: Suponha que alguém deseje minimizar uma função convexa Digamos que exista uma solução aproximada . Então, aproxima-se o mínimo de f pelo mínimo da expansão truncada de Taylor f (x_k + p) \ approx f (x_k) + \ nabla f (x_k) ^ Tp + \ frac {1} {2} p ^ TH ( x_k) p. \ quad (*) Ou seja, procura-se p tal que (*) seja mínimo e defina x_ {k + 1}: = x_k + p . Computar o gradiente de (*) - "em relação a p " - e defini-lo como zero fornece a relação x k f f ( x k + p ) ≈ f ( x k ) + ∇ f ( x k ) T p + 1

f(x)→minx∈Rn.
xkfp ( ∗ ) x k + 1 : = x k + p ( ∗ ) p H ( x k ) [ x k + 1 - x k ] = ∇ f ( x k + 1 ) - ∇ f ( x k ) ,
f(xk+p)≈f(xk)+∇f(xk)Tp+1 12pTH(xk)p.(∗)
p(∗)xk+1 1: =xk+p(∗)p
H(xk)[xk+1 1-xk]=∇f(xk+1 1)-∇f(xk),
onde H é o 'jacobiano do gradiente' ou a matriz hessiana.

Como o cálculo e a inversão do Hessian são caros ...

... uma resposta curta

(cf. atualização de Broyden) pode ser que a atualização BFGS Hk+1 1-1 1 minimize

__Hk-1 1-H-1 1__W
em uma norma Frobenius ponderada e escolhida de maneira inteligente, sujeito a
  1. H[xk+1 1-xk]=∇f(xk+1 1)-∇f(xk) - é para isso que se precisa - e
  2. HT=H , porque o Hessiano é simétrico.

Então a escolha do peso em como o inverso do Hessiano médio , cf. aqui para a declaração, mas sem prova, fornece a fórmula de atualização do BFGS (com ).W__H__W: =__W1 1/2HW1 1/2__F G: =∫0 01 1H(xk+τp)dταk=1 1

Os principais pontos são:

  • Procura-se aproximar a solução dos custos reais pela solução para uma aproximação quadrática
  • A computação do hessiano e seu inverso são caros. Um prefere atualizações simples.
  • A atualização é escolhida ideal para o inverso e não para o hessiano real.
  • O fato de se tratar de uma atualização de nível 2 é uma consequência da escolha específica dos pesos na norma Frobenius.

Uma resposta mais longa deve incluir como escolher os pesos, como fazer isso funcionar para problemas não-convexos (onde aparece uma condição de curvatura que requer uma escala da direção de pesquisa ) e como derivar a fórmula real da atualização. Uma referência está aqui (em alemão).p

Jan
fonte
Muito obrigado, isso é ótimo (e mais ou menos o que eu esperava com base na discussão em Nocedal & Wright). A única questão que resta é: por que escolhemos e a norma como fazemos? Eu entendo que isso tem a ver com unidades, mas existem muitas opções potenciais de e normas que fazem isso. WW
23613 Justin Solomon
Sim, verdade. Bem, eu não sei. Uma resposta é que ela fornece a fórmula de atualização simples de calcular e que funciona bem. Historicamente, essa abordagem da atualização - minimizando a diferença na atualização - era a de Shanno. Foi um árbitro (Goldfarb) que descobriu que uma determinada escolha dos pesos leva à fórmula de Broyden e Fletcher. Veja esta tese de doutorado Desenvolvimento histórico do método secante BFGS ... para as intuições dos desenvolvedores do BFGS. No entanto, todas as três abordagens são bastante abstratas.
Janeiro
11
Interessante, obrigado pela orientação! Meu artigo atual (com alguns erros de matemática que precisam de ajuda) está aqui: graphics.stanford.edu/courses/cs205a-13-fall/assets/notes/… (se você quiser crédito por sua ajuda, fico feliz em fornecê-lo - envie-me um e-mail com as informações de contato adequadas)
Justin Solomon
@jan Por que sua equação e não Não é a condição secante fornecida por , onde . Obrigado!
H(xk)[xk+1 1-xk]=∇f(xk+1 1)-∇f(xk)
H(xk+1 1)[xk+1 1-xk]=∇f(xk+1 1)-∇f(xk)?
Hk+1 1sk=yksk=xk+1 1-xk,yk=∇fk+1 1-∇fk
22417 Jeff Faraci