Método do gradiente
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Gradient_descent.svg/350px-Gradient_descent.svg.png)
O método do gradiente (ou método do máximo declive) é um método numérico usado em otimização. Para encontrar um mínimo (local) de uma função usa-se um esquema iterativo, onde em cada passo se toma a direção (negativa) do gradiente, que corresponde à direção de declive máximo. Pode ser encarado como o método seguido por um curso da água, na sua descida pela força da gravidade.
Descrição
Começando com um vetor inicial visando alcançar um ponto de mínimo de , consideramos a sucessão definida por onde a pesquisa linear é dada pela direção de descida
- .
No caso do método do gradiente a condição de descida verifica-se tomando
ficando a iteração definida por
- .
Pesquisa exata e inexata
Um dos problemas habituais nos métodos de pesquisa linear é determinar o passo a ser considerado na iteração.
Há duas abordagens possíveis:
- Pesquisa exata - onde será o valor otimal numa otimização unidimensional.
- Pesquisa inexata - onde será apenas um valor aproximado.
Isto tem que ser feito a cada passo, pelo que a Pesquisa Exata pode ser incomportável em tempo computacional, sendo preferível usar uma Pesquisa Inexata.
No caso da pesquisa exata, procura-se o ponto de mínimo de uma nova função
notando que está fixo e apenas está a variar.
Se for possível encontrar esse ponto de mínimo, então obtemos:
- arg min
por exemplo, calculando os zeros da derivada da função g.
Sendo moroso ou impraticável minimizar g considera-se um valor aproximado, dado por exemplo pelo Critério de Wolfe, que é um dos critérios mais usados na pesquisa inexata.
Algoritmo
Um algoritmo em pseudo-código pode definir-se assim:
- Define-se o vector inicial
- Ciclo em
- calcula-se a direção de descida
- define-se a função
- determina-se = arg min
- (por pesquisa exata ou inexata)
- define-se
- Até que
- (onde , pequeno, define o critério de paragem)
Solução de um sistema linear
O método do gradiente pode ser usado para resolver sistemas lineares, usando minimização quadrática, i.e. usando o método dos mínimos quadrados.
Fórmulas explícitas para encontrar o passo ótimo podem ser encontradas neste caso.[1]
Equações diferenciais ordinárias
Seja , uma função dada, em que e .
Supondo que a função possua derivada contínua, podemos considerar a equação diferencial ordinária
Pode-se mostrar que a única solução dessa equação é tal que é decrescente[2], enquanto . Na verdade é a curva na direção de maior decrescimento de , iniciando em
O uso do método de Euler para determinar uma aproximação a solução (da equação ) é equivalente ao método do gradiente (quando o tamanho de passo é variável).
Observamos que o ponto de mínimo de é um ponto crítico dessa função. Por isso, podemos procurar os pontos de mínimo de por meio das soluções da equação , em que
Isso pode ser feito resolvendo a equação diferencial ordinária
,
em que
,
é a matriz Jacobiana de e é a matriz Hessiana de .
Pode-se mostrar, sob certas condições, que a única solução dessa equação é tal que que
decresce, enquanto [2].
O uso do método de Euler para determinar uma aproximação para , com tamanho de passo , é equivalente ao método de Newton para otimização.
Notas e Referências
- ↑ David G. Luenberger, Yinyu Ye: Linear and Nonlinear Programming. International Series in Operations Research & Management Science. Volume 116. Springer (2008) [Basic Descent Methods, pág 215]
- ↑ a b Ferreira, José Claudinei (2021). «QUANDO OS MÉTODOS DE EULER E DE NEWTON COINCIDEM» (PDF). Revista Matemática Universitária (1): 34–46. doi:10.21711/26755254/rmu20213. Consultado em 26 de dezembro de 2022