# Método de Newton em otimização

Em cálculo numérico, o método de Newton (também chamado de Newton-Raphson) é um método iterativo para encontrar as raízes de uma função diferenciável f, que são soluções para a equação f (x) = 0 . Dessa forma, pode-se aplicar o método de Newton à derivada f ′ de uma função f duas vezes diferenciável para encontrar as raízes da derivada (soluções para f ′(x) = 0), também conhecidas como pontos críticos de f. Essas soluções podem ser mínimos, máximos ou pontos de sela. Isto é relevante nos problemas de otimização, nos quais se deseja encontrar mínimos (ou máximos) de uma função objetivo.

## Método de Newton

No contexto da otimização, o método de Newton pode ser usado para minimizar funções estritamente convexas, ou para maximizar funções estritamente côncavas. Consideremos primeiro o caso de funções de uma única variável real. Em seguida, consideraremos o caso de funções multivariáveis, mais geral e mais útil na prática.
Dada uma função duas vezes diferenciável $f:\mathbb {R} \to \mathbb {R}$, buscamos resolver o problema de otimização irrestrito:
$\min _{x\in \mathbb {R} }f(x).$
O método de Newton tenta resolver este problema construindo uma sequência $\{x_{k}\}$ a partir de uma estimativa inicial (ponto de partida) $x_{0}\in \mathbb {R}$. Se a função é estritamente convexa, isto é, se sua segunda derivada é sempre positiva, espera-se que essa sequência convirja para um minimizador $x^{*}$ de $f$. Em cada iteração, a função é aproximada por seu polinômio de Taylor de segunda ordem, em torno do ponto atual $x_{k}$:
$f(x_{k}+t)\approx f(x_{k})+f'(x_{k})\,t+{\frac {1}{2}}\,f''(x_{k})\,t^{2}.$
O próximo termo da sequência, $x_{k+1}$, é definido de modo a minimizar esta aproximação quadrática em $t$. Quando a função é convexa, essa expressão define uma parábola convexa, que possui um único ponto de mínimo. Ele pode ser obtido igualando a zero a derivada da expressão em relação a $t$:
$f'(x_{k})+f''(x_{k})\,t^{*}=0\;{\Leftrightarrow }\;t^{*}=-{\frac {f'(x_{k})}{f''(x_{k})}};$
$x_{k+1}=x_{k}+t^{*}=x_{k}-{\frac {f'(x_{k})}{f''(x_{k})}}.$

## Interpretação geométrica

A interpretação geométrica do método de Newton é que, a cada iteração, equivale ao ajuste de uma parábola ao gráfico de $f(x)$, em torno do valor atual $x_{k}$, tendo a mesma inclinação (primeira derivada) e curvatura (segunda derivada) da função original naquele ponto. Então, move-se até o mínimo (ou máximo) dessa parábola. Em dimensões superiores, faz-se o ajuste de um paraboloide à curva da função original, seguindo o mesmo procedimento. Em dimensões superiores, caso o método seja aplicado a funções que não sejam estritamente convexas nem estritamente côncavas, além de pontos de mínimo ou de máximo, os pontos de derivada nula do paraboloide ajustado podem corresponder a pontos de sela. Observe que se $f$ for uma função quadrática, então o ponto crítico (mínimo, máximo ou ponto de sela) exato é encontrado em uma única iteração.

## Dimensões superiores

O esquema iterativo acima pode ser generalizado para $d>1$ dimensões substituindo a derivada pelo vetor gradiente$(\mathbf {f'} (\mathbf {x} )=\mathbf {\nabla f} (\mathbf {x} )=\mathbf {g_{f}} (\mathbf {x} )\in \mathbb {R} ^{d})$, e o inverso da segunda derivada pela inversa da matriz hessiana $(\mathbf {f''} (\mathbf {x} )=\mathbf {\nabla ^{2}f} (\mathbf {x} )=\mathbf {H_{f}} (\mathbf {x} )\in \mathbb {R} ^{d\times d})$. Obtém-se assim o esquema iterativo:
$f(\mathbf {x_{k}} +\mathbf {t} )\approx f(\mathbf {x_{k}} )+[\mathbf {f'} (\mathbf {x_{k}} )]^{T}\,\mathbf {t} +{\frac {1}{2}}\,\mathbf {t} ^{T}\,[\mathbf {f''} (\mathbf {x_{k}} )]\,\mathbf {t} \,{;}$
$\mathbf {f'} (\mathbf {x_{k}} )+[\mathbf {f''} (\mathbf {x_{k}} )]\,\mathbf {t^{*}} =\mathbf {0} \Leftrightarrow \mathbf {t^{*}} =-[\mathbf {f''} (\mathbf {x_{k}} )]^{-1}\,\mathbf {f'} (\mathbf {x_{k}} )\,;$
$\mathbf {x_{k+1}} =\mathbf {x_{k}} -[\mathbf {f''} (\mathbf {x_{k}} )]^{-1}\,\mathbf {f'} (\mathbf {x_{k}} )\;.$
Frequentemente, o método de Newton é modificado para incluir um pequeno tamanho de passo $0<\gamma \leq 1$ em vez de $\gamma =1$:
$\mathbf {x_{k+1}} =\mathbf {x_{k}} -\gamma \,[\mathbf {f''} (\mathbf {x_{k}} )]^{-1}\,\mathbf {f'} (\mathbf {x_{k}} )\;.$
Isso geralmente é feito para garantir que as condições de Wolfe (ou a condição de Armijo) sejam satisfeitas em cada iteração do método. Para tamanhos de passo menores que 1, o método é frequentemente chamado de método de Newton relaxado ou amortecido.

## Convergência

Se $f:\mathbb {R} ^{d}\to \mathbb {R}$ for uma função fortemente convexa com hessiana Lipschitz contínua, então, dado um ponto $\mathbf {x_{0}}$ suficientemente próximo da solução única $\mathbf {x^{*}} =\arg \min f(\mathbf {x} )$, a sequência $\{\mathbf {x_{0}} ,\mathbf {x_{1}} ,\mathbf {x_{2}} ,\dots \}$, gerada pelo método de Newton, converge para a $\mathbf {x^{*}}$, com uma taxa de convergência quadrática.

## Calculando a direção de Newton

Computar a inversa da hessiana em dimensões altas para calcular a direção de Newton $\mathbf {t^{*}} =-[\mathbf {f''} (\mathbf {x_{k}} )]^{-1}\,\mathbf {f'} (\mathbf {x_{k}} )$ pode ser uma operação computacionalmente onerosa. Nesses casos, em vez de inverter diretamente a matriz, pode-se calcular o vetor $\mathbf {t^{*}}$ como a solução do sistema de equações lineares correspondente,
$[\mathbf {f''} (\mathbf {x_{k}} )]\,\mathbf {t^{*}} =-\mathbf {f'} (\mathbf {x_{k}} )\,,$
que pode ser resolvido por diversos métodos, diretos ou iterativos. Parte desses métodos são aplicáveis apenas a certos tipos de equações, por exemplo, a fatoração de Cholesky e o método do gradiente conjugado só podem ser usados se $\mathbf {f''} (\mathbf {x_{k}} )$ for uma matriz definida positiva.
Portanto, se o problema abordado tiver uma matriz hessiana indefinida (o que ocorre se a função não for nem estritamente convexa, nem estritamente côncava), métodos mais gerais devem ser usados para solucionar os sistemas lineares, por exemplo, a fatoração LU. Nestes casos, o método de Newton fornece pontos de sela dos paraboloides ajustados (ao invés de mínimos ou máximos).
Existem também vários métodos quase-Newton, nos quais uma aproximação para a matriz hessiana (ou diretamente para sua inversa) é construída avaliando mudanças no gradiente.
Se a hessiana estiver próxima de uma matriz singular, quer dizer, se seu número de condicionamento for elevado demais, a resolução numérica do sistema linear (em aritmética de ponto flutuante) pode produzir resultados muito imprecisos e o processo iterativo pode divergir. Nesses casos, algumas estratégias podem ser adotadas. Pode-se, por exemplo, modificar a hessiana adicionando uma matriz de correção $\mathbf {B_{k}}$ de modo a fazer $\mathbf {f''} (\mathbf {x_{k}} )+\mathbf {B_{k}}$ definida positiva. Uma abordagem é definir $\mathbf {B_{k}}$ de forma que todo autovalor menor ou igual a zero da matriz hessiana original seja transformado num pequeno valor positivo $\epsilon >0$.
Uma abordagem explorada no algoritmo Levenberg-Marquardt (que usa uma matriz hessiana aproximada) é adicionar à hessiana uma matriz proporcional à matriz identidade, μI{\textstyle \mu \, \mathbf {I} }, com o coeficiente $\mu$ ajustado a cada iteração conforme necessário. Para um valor $\mu$ elevado (comparado com a ordem de grandeza dos autovalores da hessiana), o método de Newton se degenera no método de gradiente descendente, com tamanho de passo $1/\mu$.

## Algumas ressalvas

O método de Newton, em sua versão mais básica, traz algumas ressalvas:
* Não pode ser usado se a matriz hessiana for singular.
* Pode convergir para um ponto de sela ao invés de para um mínimo local (caso a matriz hessiana seja invertível, mas indefinida, com autovalores negativos e positivos).
* Pode não convergir se condições mínimas não forem satisfeitas (grau de convexidade da função a ser minimizada, proximidade do ponto de partida a um ótimo local, tamanho de passo suficientemente pequeno).