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 ${𝐱}_0$  visando alcançar um ponto de mínimo de $F$, consideramos a sucessão definida por ${𝐱}_0,{𝐱}_1,{𝐱}_2,\dots$ onde a pesquisa linear é dada pela direção de descida ${𝐝}_n$

${𝐱}_{n+1}={𝐱}_n+{\omega }_n{𝐝}_n$.

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

${𝐝}_n=-\mathrm{\nabla }F({𝐱}_n)$

ficando a iteração definida por

${𝐱}_{n+1}={𝐱}_n-{\omega }_n\mathrm{\nabla }F({𝐱}_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({𝐱}_n-\omega \mathrm{\nabla }F({𝐱}_n))$

notando que ${𝐱}_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 ${𝐱}_0$
• Ciclo em $n$
  • calcula-se a direção de descida ${𝐝}_n=-\mathrm{\nabla }F({𝐱}_n)$
  • define-se a função $g(\omega )=F({𝐱}_n+\omega {𝐝}_n)$
  • determina-se ${\omega }_n$ = arg min${}_{\omega >0}g(\omega )$
    • (por pesquisa exata ou inexata)
  • define-se ${𝐱}_{n+1}={𝐱}_n+{\omega }_n{𝐝}_n$
• Até que $||\mathrm{\nabla }F({𝐱}_{n+1})||<ϵ$
  • (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.

Equações diferenciais ordinárias

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

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

$\{\begin{array}{ccc}{v}^{\prime }(t)& =& -\mathrm{\nabla }F(v(t))\\ v(0)& =& x_0\end{array}.(*)$

Pode-se mostrar que a única solução $v(t)$ dessa equação é tal que $F(v(t))$ é decrescente, enquanto $\mathrm{\nabla }F(v(t))\ne 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)=\mathrm{\nabla }F(x).$

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

$\{\begin{array}{ccc}Jg(u(t))u^{\prime }(t)& =& -g(u(t))\\ u(0)& =& x_0\end{array}(**)$,

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

$\varphi (u(t))=\frac{\Vert g(u(t)){\Vert }^2}{2}$

decresce, enquanto $\mathrm{\nabla }F(u(t))\ne 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.Predefinição:Referências