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 Predefinição:Math, que são soluções para a equação Predefinição:Math . Dessa forma, pode-se aplicar o método de Newton à derivada Predefinição:Math de uma função Predefinição:Math duas vezes diferenciável para encontrar as raízes da derivada (soluções para Predefinição:Math), também conhecidas como pontos críticos de Predefinição:Math. 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:ℝ\to ℝ$, buscamos resolver o problema de otimização irrestrito:

$\underset{x\in ℝ}{\min }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 ℝ$. 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^{\prime }(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^{\prime }(x_k)+f^{″}(x_k)t^{*}=0\iff t^{*}=-\frac{f^{\prime }(x_k)}{f^{″}(x_k)};$

$x_{k+1}=x_k+t^{*}=x_k-\frac{f^{\prime }(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$({𝐟}^{\prime }(𝐱)=\mathrm{\nabla }𝐟(𝐱)={𝐠}_{𝐟}(𝐱)\in {ℝ}^d)$, e o inverso da segunda derivada pela inversa da matriz hessiana $({𝐟}^{″}(𝐱)={\mathrm{\nabla }}^{\mathrm{𝟐}}𝐟(𝐱)={𝐇}_{𝐟}(𝐱)\in {ℝ}^{d\times d})$. Obtém-se assim o esquema iterativo:

$f({𝐱}_{𝐤}+𝐭)\approx f({𝐱}_{𝐤})+[{𝐟}^{\prime }({𝐱}_{𝐤}){]}^T𝐭+\frac{1}{2}{𝐭}^T[{𝐟}^{″}({𝐱}_{𝐤})]𝐭;$

${𝐟}^{\prime }({𝐱}_{𝐤})+[{𝐟}^{″}({𝐱}_{𝐤})]{𝐭}^{\mathbf{*}}=\mathrm{𝟎}\iff {𝐭}^{\mathbf{*}}=-[{𝐟}^{″}({𝐱}_{𝐤}){]}^{-1}{𝐟}^{\prime }({𝐱}_{𝐤});$

${𝐱}_{𝐤\mathbf{+}\mathrm{𝟏}}={𝐱}_{𝐤}-[{𝐟}^{″}({𝐱}_{𝐤}){]}^{-1}{𝐟}^{\prime }({𝐱}_{𝐤}).$

Frequentemente, o método de Newton é modificado para incluir um pequeno tamanho de passo $0<\gamma \le 1$ em vez de $\gamma =1$:

${𝐱}_{𝐤\mathbf{+}\mathrm{𝟏}}={𝐱}_{𝐤}-\gamma [{𝐟}^{″}({𝐱}_{𝐤}){]}^{-1}{𝐟}^{\prime }({𝐱}_{𝐤}).$

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:{ℝ}^d\to ℝ$ for uma função fortemente convexa com hessiana Lipschitz contínua, então, dado um ponto ${𝐱}_{\mathrm{𝟎}}$ suficientemente próximo da solução única ${𝐱}^{\mathbf{*}}=\arg \min f(𝐱)$, a sequência $\{{𝐱}_{\mathrm{𝟎}},{𝐱}_{\mathrm{𝟏}},{𝐱}_{\mathrm{𝟐}},\dots \}$, gerada pelo método de Newton, converge para a ${𝐱}^{\mathbf{*}}$, 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{*}}=-[{𝐟}^{″}({𝐱}_{𝐤}){]}^{-1}{𝐟}^{\prime }({𝐱}_{𝐤})$ pode ser uma operação computacionalmente onerosa. Nesses casos, em vez de inverter diretamente a matriz, pode-se calcular o vetor ${𝐭}^{\mathbf{*}}$ como a solução do sistema de equações lineares correspondente,

$[{𝐟}^{″}({𝐱}_{𝐤})]{𝐭}^{\mathbf{*}}=-{𝐟}^{\prime }({𝐱}_{𝐤}),$

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 ${𝐟}^{″}({𝐱}_{𝐤})$ 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 ${𝐁}_{𝐤}$ de modo a fazer ${𝐟}^{″}({𝐱}_{𝐤})+{𝐁}_{𝐤}$ definida positiva. Uma abordagem é definir ${𝐁}_{𝐤}$ de forma que todo autovalor menor ou igual a zero da matriz hessiana original seja transformado num pequeno valor positivo $ϵ>0$.

Uma abordagem explorada no algoritmo Levenberg-Marquardt (que usa uma matriz hessiana aproximada) é adicionar à hessiana uma matriz proporcional à matriz identidade, $\mu 𝐈$, 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:

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 invertí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).

Ver 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

• Predefinição:Citar livro
• Predefinição:Citar livro
• Predefinição:Citar livro
• Predefinição:Citar livro
• Predefinição:Citar livro
• Predefinição:Citar arXiv

Ligações externas

• Predefinição:Citar web