Abrir menu principal
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çãoEditar

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 inexataEditar

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.

AlgoritmoEditar

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 linearEditar

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]