Descida de gradiente e descida de gradiente conjugada

11

Para um projeto, tenho que implementar esses dois métodos e comparar o desempenho deles em diferentes funções.

Parece que o método do gradiente conjugado se destina a resolver sistemas de equações lineares de

Ax=b

Onde A é uma matriz n por n simétrica, definida positiva e real.

Por outro lado, quando leio sobre a descida do gradiente, vejo o exemplo da função Rosenbrock , que é

f(x1,x2)=(1x1)2+100(x2x12)2

A meu ver, não posso resolver isso com um método de gradiente conjugado. Ou eu sinto falta de alguma coisa?

Philipp
fonte

Respostas:

14

A descida gradiente e o método do gradiente conjugado são ambos algoritmos para minimizar funções não lineares, ou seja, funções como a função Rosenbrock

f(x1,x2)=(1x1)2+100(x2x12)2

ou uma função quadrática multivariada (neste caso, com um termo quadrático simétrico)

f(x)=12xTATAxbTAx.

xdnf(x)αx

minf(x)

Ambos os métodos começam com um palpite inicial, e, em seguida, calculam a próxima iteração usando uma função do formuláriox0

xi+1=xi+αidi.

Em palavras, o próximo valor de é encontrado iniciando no local atual e movendo-se na direção de busca por alguma distância . Nos dois métodos, a distância a mover pode ser encontrada por uma pesquisa de linha (minimize sobre ). Outros critérios também podem ser aplicados. Onde os dois métodos diferem está na escolha de . Para o método de gradiente, . Para o método do gradiente conjugado, o procedimento de Grahm-Schmidt é usado para ortogonalizar os vetores de gradiente. Em particular, , mas é igualxxidiαif(xi+αidi)αididi=f(xi)d0=f(x0)d1f(x1) menos a projeção do vetor em modo que . Cada vetor gradiente subsequente é ortogonalizado em relação a todos os anteriores, o que leva a propriedades muito boas para a função quadrática acima.d0(d1)Td0=0

A função quadrática acima (e formulações relacionadas) também é de onde vem a discussão da resolução de usando o método do gradiente conjugado, uma vez que o mínimo desse é alcançado no ponto que .Ax=bf(x)xAx=b

Elaine Hale
fonte
9

Nesse contexto, os dois métodos podem ser considerados problemas de minimização da função: Quando é simétrico, então é minimizado quando .

ϕ(x)=12xTAxxTb
AϕAx=b

A descida do gradiente é o método que procura iterativamente por um minimizador, olhando na direção do gradiente. O gradiente conjugado é semelhante, mas também é necessário que as direções da pesquisa sejam ortogonais entre si, no sentido de que .piTApj=0i,j

Bill Barth
fonte