Método de Newton em otimização

Uma comparação entre o método do gradiente (verde) e método de Newton (vermelho) para minimizar uma função (considerando passos pequenos). O método de Newton utiliza informações de curvatura (ou seja, a segunda derivada) para seguir uma rota mais direta.

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, essa sequência converge 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})+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})}}.$

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}+t)\approx f(x_{k})+f'(x_{k})\,t+{\frac {1}{2}}\,f''(x_{k})\,t^{2}.$

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áximo ou mínimo 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 (ou estritamente côncavas), além de pontos de mínimo e 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 ótimo 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 {h} =-[\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 {h}$ como a solução do sistema de equações lineares correspondente:

$[\mathbf {f''} (\mathbf {x_{k}} )]\,\mathbf {h} =-\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}} )$ é uma matriz definida positiva.

Portanto, se o problema abordado tiver uma matriz hessiana indefinida matriz 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. Nesses casos, o Método de Newton fornecerá pontos de sela dos paraboloides ajustados (ao invés de mínimos ou máximos).

Existem também vários métodos quase-Newton, onde 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 negativo 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, ${\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 original, traz algumas ressalvas:

1. Não pode ser usado se a matriz hessiana for singular.
2. Pode convergir para um ponto de sela ao invés de para um mínimo local (caso a matriz hessiana seja inversível, mas indefinida, com autovalores negativos e positivos).
3. 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).

Veja também

• Método quase-Newton
• Gradiente descendente
• Algoritmo de Gauss-Newton
• Algoritmo de Levenberg-Marquardt
• Região de confiança
• Otimização

Referências

• Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. [S.l.]: Dover Publishing. ISBN 0-486-43227-0 
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Numerical optimization: Theoretical and practical aspects. Col: Universitext Second revised ed. of translation of 1997 French ed. Berlin: Springer-Verlag. ISBN 3-540-35445-X. MR 2265882. doi:10.1007/978-3-540-35447-5 
• Fletcher, Roger (1987). Practical Methods of Optimization 2nd ed. New York: John Wiley & Sons. ISBN 978-0-471-91547-8 
• Givens, Geof H.; Hoeting, Jennifer A. (2013). Computational Statistics. Hoboken, New Jersey: John Wiley & Sons. pp. 24–58. ISBN 978-0-470-53331-4 
• Nocedal, Jorge; Wright, Stephen J. (1999). Numerical Optimization. [S.l.]: Springer-Verlag. ISBN 0-387-98793-2 
• Kovalev, Dmitry; Mishchenko, Konstantin. «Stochastic Newton and cubic Newton methods with simple local linear-quadratic rates». arXiv:1912.01597 [cs.LG] 

Links externos

• Korenblum, Daniel (29 de agosto de 2015). «Newton-Raphson visualization (1D)». Bl.ocks. ffe9653768cb80dfc0da