Método do gradiente

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

${\displaystyle \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

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

ficando a iteração definida por

${\displaystyle \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 ${\displaystyle \omega _{n}}$ a ser considerado na iteração.

Há duas abordagens possíveis:

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

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

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

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

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

Equações diferenciais ordinárias

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

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

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

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

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

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

${\displaystyle g(x)=\nabla F(x).}$

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

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

em que

${\displaystyle Jg(x)=HF(x)}$,

é a matriz Jacobiana de ${\displaystyle g(x)}$ e ${\displaystyle HF(x)}$ é a matriz Hessiana de ${\displaystyle F(x)}$.

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

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

decresce, enquanto ${\displaystyle \nabla F(u(t))\neq 0}$^[2].

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

Notas e Referências