Usuário:Lechatjaune/Método de Newton em otimização

Introdução

Em matemática, o método de Newton é um método iterativo para encontrar raízes de equações. Na sua otimização, o método de Newton é especializado para encontrar pontos estacionários de funções diferenciáveis, que são os zeros da função derivada. Engenheiros, economistas, cientistas e matemáticos, precisam, frequentemente, encontrar valores máximos e mínimos de funções, por isso a Otimização do Método de Newton é amplamente utilizada em situações práticas do dia-a-dia destes profissionais, como por exemplo, investimento de capitais de empresas ou o movimento de um objeto na direção de uma fonte de calor (trajetórias de mísseis), dentre outras aplicações. Para entendermos a otimização do método de Newton precisamos iniciar com uma breve introdução sobre Gradiente,Hessiano e Jacobiana.

Gradiente

No cálculo vetorial, podemos definir gradiente como um vetor que indica a direção e o sentido em que uma função cresce mais rapidamente, muito útil para encontrarmos valores máximos e mínimos de uma função. O gradiente de uma função escalar $f(x_{1},x_{2},\cdots ,x_{n})$ é dado por:

$\nabla f=\left\langle {\frac {\partial f}{\partial x_{1}}},{\frac {\partial f}{\partial x_{2}}},\cdots ,{\frac {\partial f}{\partial x_{n}}}\right\rangle$

Para todo campo escalar $f$ diferenciável em função do espaço cartesiano ${\vec {x}}=\left\langle x,y,z\right\rangle$ temos que:

$\nabla f=\left\langle {\frac {\partial f}{\partial x}},{\frac {\partial f}{\partial y}},{\frac {\partial f}{\partial z}}\right\rangle$

Hessiana

A matriz hessiana de uma função $f$ de $n$ variáveis é a matriz quadrada $(nxn)$ das derivadas parciais de segunda ordem da função. Sua utilidade se dá na identificação das concavidades das funções.

Definição Matemática:

Em linguagem matemática	Em Português	Exemplo: função com n=2: $f(\mathbf {x} )=f\left({x_{1}},{x_{2}}\right)=2{x_{1}}{x_{2}}^{3}$
${\frac {\partial f}{\partial {x_{1}}}}$	derivada parcial de primeira ordem da função "f" em relação a uma variável ${x_{1}}$	${\frac {\partial f}{\partial {x_{1}}}}={\frac {\partial \left(2{x_{1}}{x_{2}}^{3}\right)}{\partial {x_{1}}}}=2{x_{2}}^{3}$
${\frac {\partial }{\partial {x_{1}}}}\left({\frac {\partial f}{\partial {x_{2}}}}\right)={\frac {\partial ^{2}f}{\partial {x_{1}}\,\partial {x_{2}}}}$	A derivada da derivada (=derivada de segunda ordem): primeiro tomou-se a derivada da função "f" em relação à variável ${x_{1}}$ e depois derivou-se esta derivada em relação à variável ${x_{2}}$	${\frac {\partial ^{2}f}{\partial {x_{1}}\,\partial {x_{2}}}}$$={\frac {\partial \left(2{x_{2}}^{3}\right)}{\partial \partial {x_{2}}}}$$=6{x_{2}}^{2}$

Se todas as derivadas parciais de "f" existirem, então a matriz hessiana de f é a matriz quadrada das derivadas de segunda ordem de f

$H\left[f({x_{1}},{x_{2}},{x_{3}},...,x_{n})\right]={\begin{bmatrix}{\frac {\partial ^{2}f}{\partial {x_{1}}^{2}}}&{\frac {\partial ^{2}f}{\partial {x_{1}}\,\partial {x_{2}}}}&\cdots &{\frac {\partial ^{2}f}{\partial {x_{1}}\,\partial x_{n}}}\\\\{\frac {\partial ^{2}f}{\partial {x_{2}}\,\partial {x_{1}}}}&{\frac {\partial ^{2}f}{\partial {x_{2}}^{2}}}&\cdots &{\frac {\partial ^{2}f}{\partial {x_{2}}\,\partial x_{n}}}\\\\\vdots &\vdots &\ddots &\vdots \\\\{\frac {\partial ^{2}f}{\partial x_{n}\,\partial {x_{1}}}}&{\frac {\partial ^{2}f}{\partial x_{n}\,\partial {x_{2}}}}&\cdots &{\frac {\partial ^{2}f}{\partial x_{n}^{2}}}\end{bmatrix}}$

Matriz Jacobiana

A matriz jacobiana é formada pelas derivadas parciais de uma função vetorial.

Definição:

Em linguagem matemática	Em Português
${\begin{bmatrix}{\frac {\partial F_{1}}{\partial x_{1}}}&\cdots &{\frac {\partial F_{1}}{\partial x_{n}}}\\\vdots &\ddots &\vdots \\{\frac {\partial F_{m}}{\partial x_{1}}}&\cdots &{\frac {\partial F_{m}}{\partial x_{n}}}\end{bmatrix}}$	Matriz de m linhas e n colunas. A primeira linha representa as derivadas parciais da função $F_{1}$ em relação a todos os x (de x1 a xn). A segunda linha representa as derivadas parciais de $F_{2}$ (também em relação a todos os x), e assim por diante, até a linha de número m, que representa as derivadas parciais de $F_{m}$ em relação a todos os xs.

O método

O método de Newton é uma tentativa de construir uma sequência xn a partir de uma estimativa inicial x0 que convirja para x*tal que f’(x*)=0. O ponto x* é chamado de ponto estacionário f(.). O termo de segunda ordem da expansão de Taylor fT(x) da função f(.) em torno de xn, onde deltax=x-xn, é:

$\displaystyle f_{T}(x_{n}+\Delta x)=f_{T}(x)=f(x_{n})+f'(x_{n})\Delta x+{\frac {1}{2}}f''(x_{n})\Delta x^{2}$, e atinge o seu extremo quando a sua derivada em relação a (deltax) é igual a zero. Ou seja, quando (delta x) resolve a equação linear:

$\displaystyle f'(x_{n})+f''(x_{n})\Delta x=0.$.

Considerando-se que todos os termos da equação tenham coeficientes constantes.

Assim, desde que f(x) seja uma função duas vezes diferenciável aproximada pela expansão de segunda ordem de Taylor com um x0 escolhido suficientemente perto de x* a sequência xn é definida por: $\Delta x=x-x_{n}=-{\frac {f'(x_{n})}{f''(x_{n})}}$

$x_{n+1}=x_{n}-{\frac {f'(x_{n})}{f''(x_{n})}},\ n=0,1,\dots$ irá convergir para uma raiz de f '(x), ou seja, x * para o qual f' (x *) = 0

Observação: Só lembrando que nem sempre o método irá convergir para o extremo da função. Ou seja, depende do ponto de partida.

Interpretação Geométrica

Em cada iteração f(x) se aproxima de uma função quadrática em torno de xn e, em seguida, dá um passo em direção ao máximo ou mínimo dessa função. Em dimensões superiores pode ser também um ponto de sela.

Dimensões superiores

Em dimensões superiores podemos substituir a derivada pelo gradiente $\nabla f(\mathbf {x} )$ e a segunda derivada pelo inverso da matriz Hessiana $Hf(\mathbf {x} )$, obtendo:

$\mathbf {x} _{n+1}=\mathbf {x} _{n}-[Hf(\mathbf {x} _{n})]^{-1}\nabla f(\mathbf {x} _{n}),\ n\geq 0.$

Geralmente modifica-se o Método de Newton para incluir um passo $\gamma >0$ ao invés de $\gamma =1$:

$\mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma [Hf(\mathbf {x} _{n})]^{-1}\nabla f(\mathbf {x} _{n}).$

Isto é feito para assegurar que as Condições de Wolfe estão garantidas em cada passo $\mathbf {x} _{n}\to \mathbf {x} _{n+1}$ da iteração. Se esse for o caso, o Método de Newton converge muito rapidamente para um máximo ou mínimo local.

Uma outra abordagem

Algumas vezes, encontrar o inverso da Hessiana em dimensões elevadas não é tarefa fácil. Nesses casos é melhor calcular o vetor $\mathbf {p} _{n}=[Hf(\mathbf {x} _{n})]^{-1}\nabla f(\mathbf {x} _{n})$ que soluciona o sistema de equações lineares:

$[Hf(\mathbf {x} _{n})]\mathbf {p} _{n}=\nabla f(\mathbf {x} _{n})$

Esse sistema pode ser resolvido utilizando métodos iterativos. No entanto, muitos desses métodos se aplicam somente para certos tipos de equações, como a fatoração de Cholesky, onde o gradiente conjugado só vai funcionar se $[Hf(\mathbf {x} _{n})]$ for uma matriz definida positiva. Embora isso possa parecer uma limitação, alguma vezes é útil, como no caso de estarmos estudando um problema de minimização e se $[Hf(\mathbf {x} _{n})]$ não for positiva, as iterações irão convergir para um ponto de sela e não um ponto de mínimo.

Métodos semi-Newton

Existem vários métodos de "semi-Newton", onde uma aproximação para a Hessiana é construída a partir de mudanças no seu gradiente. Uma delas é o algoritmo de Levenberg-Marquartd (que utiliza uma Hessiana aproximada) que adiciona uma matriz identidade ponderada para a Hessianas $\mu \mathbf {I}$, as iterações vão ter um passo ${\frac {1}{\mu }}$. Isso resulta numa convergência mais lenta, mas mais confiável que a Hessiana. com ponderação modificada a cada iteração, conforme necessário. Para grandes e pequenos Hessianos

Máximos e Mínimos de uma função

Partindo do Método de Newton generalizado para sistemas, temos:

$x^{[}n+1]=x^{(}n)-JF^{-}1(x^{n})F(x^{n}),n>=0$

$x^{0}=dadoincial$

Desejamos calcular os pontos de máximo da função :$f(x,y)$

Primeiramente devemos plotar o gráfico com as curvas de nível da função;

Depois disso, devemos determinar o gradiente da função; :$\nabla f=\left\langle {\frac {\partial f}{\partial x}},{\frac {\partial f}{\partial y}}\right\rangle =F(x,y)$

No próximo passo, obtemos a Jacobiana; :$JF(x,y)$

Agora é só aplicar o Método de Newton Generalizado para sistemas.  :$(x,y)=(x,y)-F(x,y)/JF(x,y)$

Ver também

• Gradiente
• Hessiano
• Matriz_Jacobiana
• Método de Newton

Bibliografia

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. pp. xiv+490. ISBN 3-540-35445-X. MR 2265882. doi:10.1007/978-3-540-35447-5 

Nocedal, Jorge & Wright, Stephen J. (1999). Numerical Optimization. Springer-Verlag. ISBN 0-387-98793-2.

BURDEN, L. Richard. FAIRES, Douglas. J. Análise Numérica. 8ª Ed. São Paulo: Cengage Learning, 2008. ISBN 978-85-221-0601-1