Método do gradiente

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)

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 $\mathbf {x} _{0}$  visando alcançar um ponto de mínimo de $F$, consideramos a sucessão definida por $\mathbf {x} _{0},\mathbf {x} _{1},\mathbf {x} _{2},\dots$ onde a pesquisa linear é dada pela direção de descida $\mathbf {d} _{n}$

$\mathbf {x} _{n+1}=\mathbf {x} _{n}+\omega _{n}\mathbf {d} _{n}$.

No caso do método do gradiente a condição de descida verifica-se tomando

$\mathbf {d} _{n}=-\nabla F(\mathbf {x} _{n})$

ficando a iteração definida por

$\mathbf {x} _{n+1}=\mathbf {x} _{n}-\omega _{n}\nabla F(\mathbf {x} _{n})$.

Pesquisa exata e inexata

Um dos problemas habituais nos métodos de pesquisa linear é determinar o passo $\omega _{n}$ a ser considerado na iteração.

Há duas abordagens possíveis:

• Pesquisa exata - onde $\omega _{n}$ será o valor otimal numa otimização unidimensional.
• Pesquisa inexata - onde $\omega _{n}$ 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

$g(\omega )=F(\mathbf {x} _{n}-\omega \nabla F(\mathbf {x} _{n}))$

notando que $\mathbf {x} _{n}$ está fixo e apenas $\omega >0$ está a variar.

Se for possível encontrar esse ponto de mínimo, então obtemos:

$\omega _{n}=$ arg min$_{\omega >0}\,g(\omega )$

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 $\mathbf {x} _{0}$
• Ciclo em $n$
  • calcula-se a direção de descida $\mathbf {d} _{n}=-\nabla F(\mathbf {x} _{n})$
  • define-se a função $g(\omega )=F(\mathbf {x} _{n}+\omega \mathbf {d} _{n})$
  • determina-se $\omega _{n}$ = arg min$_{\omega >0}\,g(\omega )$
    • (por pesquisa exata ou inexata)
  • define-se $\mathbf {x} _{n+1}=\mathbf {x} _{n}+\omega _{n}\mathbf {d} _{n}$
• Até que $||\nabla F(\mathbf {x} _{n+1})||<\epsilon$
  • (onde $\epsilon$, 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.

Equações diferenciais ordinárias

Seja $F(x)$, uma função dada, em que $x\in \mathbb {R} ^{m}$ e $F(x)\in \mathbb {R}$.

Supondo que a função $F(x)$ possua derivada contínua, podemos considerar a equação diferencial ordinária

${\begin{cases}v'(t)&=&-\nabla F(v(t))\\v(0)&=&x_{0}\end{cases}}.\qquad \qquad (*)$

Pode-se mostrar que a única solução $v(t)$ dessa equação é tal que $F(v(t))$ é decrescente, enquanto $\nabla F(v(t))\neq 0$. Na verdade $v(t)$ é a curva na direção de maior decrescimento de $F(x)$, iniciando em $x_{0}.$

O uso do método de Euler para determinar uma aproximação a solução $v(t)$ (da equação $(*)$) é equivalente ao método do gradiente (quando o tamanho de passo é variável).

Observamos que o ponto de mínimo de $F(x)$ é um ponto crítico dessa função. Por isso, podemos procurar os pontos de mínimo de $F(x)$ por meio das soluções da equação $g(x)=0$, em que

$g(x)=\nabla F(x).$

Isso pode ser feito resolvendo a equação diferencial ordinária

${\begin{cases}Jg(u(t))u'(t)&=&-g(u(t))\\u(0)&=&x_{0}\end{cases}}\qquad \qquad (**)$,

em que

$Jg(x)=HF(x)$,

é a matriz Jacobiana de $g(x)$ e $HF(x)$ é a matriz Hessiana de $F(x)$.

Pode-se mostrar, sob certas condições, que a única solução $u(t)$ dessa equação $(**)$ é tal que que

$\phi (u(t))={\frac {\|g(u(t))\|^{2}}{2}}$

decresce, enquanto $\nabla F(u(t))\neq 0$.

O uso do método de Euler para determinar uma aproximação para $u(t)$, com tamanho de passo $h=1$, é equivalente ao método de Newton para otimização.