Método do gradiente
# 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 $\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.

## Notas e Referências

* ↑ 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]
* 1 2 Ferreira, José Claudinei (2021). «QUANDO OS MÉTODOS DE EULER E DE NEWTON COINCIDEM» (PDF). Revista Matemática Universitária (1): 34–46. doi:10.21711/26755254/rmu20213. Consultado em 26 de dezembro de 2022