En optimización del Newton paso es $-\nabla^2f(x)^{-1}\nabla f(x)$. Alguien podría ofrecer una explicación intuitiva de ¿por qué la dirección de Newton es una dirección de búsqueda buena? Por ejemplo se me ocurre de gradiente más escarpado decente como una bola rodando por una colina (en tres dimensiones), estoy luchando para pensar en una analogía similar para la dirección de Newton.
Respuestas
¿Demasiados anuncios?
El método de Newton en la optimización hace que un local aproximación cuadrática de la función que se basa en la información desde el punto actual y, a continuación, salta a la mínima de aproximación.
Imagínese el montaje un poco cuadrática de la superficie de una parábola a su superficie en el punto actual y, a continuación, ir a la mínima de la aproximación para encontrar el siguiente punto. Encontrar la dirección hacia el mínimo de la aproximación cuadrática es lo que están haciendo cuando usted resolver, $(f'')^{-1}f'$.
Pensando en esta imagen, también puede ver por qué el método de Newton puede converger a una silla de montar o un máximo en algunos casos. Si los autovalores de Hesse son mixtos o negativos - en los casos en que el local de la aproximación cuadrática es un revés paraboloid, o silla de montar.
littleO
Puntos
12894
En el método de Newton seleccionamos $\Delta x$ lo que $\nabla f(x_k + \Delta x) \approx 0$. Tenga en cuenta que $\nabla f(x_k + \Delta x) \approx \nabla f(x_k) + \nabla^2 f(x_k) \Delta x$. El parámetro igual a $0$ y $\Delta x$ de problemas nos da el paso de Newton.
Otro punto de vista es para empezar\begin{equation} f(x_k + \Delta x) \approx f(x_k) + \langle \nabla f(x_k), \Delta x \rangle + \frac12 \langle \Delta x, \nabla^2 f(x_k) \Delta x \rangle. \end{ecuación } minimizando el lado derecho con respecto a los $\Delta x$ nos da el paso de Newton.
par
Puntos
5570
El método de Newton para encontrar los ceros de una función de $f$ es de la siguiente manera $$ x_{n+1}=x_{n}-\frac{f\left(x_{n}\right)}{f^{\prime}\left(x_{n}\right)}. $$ Por lo suficientemente bueno $f$ y el valor inicial $x_{0}$, obtenemos que $$ f\left(\lim_{n\rightarrow\infty}x_{n}\right)=0. $$ La animación en https://en.wikipedia.org/wiki/Newton's_method es particularmente agradable y le ayudará a entender lo que está sucediendo.
El método de Newton en la optimización es el mismo procedimiento aplicado a $f^{\prime}$, por lo que $$ x_{n+1}=x_{n}-\frac{f^{\prime}\left(x_{n}\right)}{f^{\prime\prime}\left(x_{n}\right)}. $$ Esto nos permite encontrar $$ f^{\prime}\left(\lim_{n\rightarrow\infty}x_{n}\right)=0. $$ En particular, $x_{n}\rightarrow x$ es un punto crítico.
