Método do gradiente

Origem: Wikipédia, a enciclopédia livre.
Illustração do método do gradiente (as linhas em azul correspondem a curvas de nível, e as setas a vermelho correspondem a 4 iterações do método)

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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 otimal podem ser encontradas neste caso.[1]

Notas e Referências

  1. 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]