El método de Newton en dimensiones superiores explicó

Question

Estoy estudiando sobre el método de Newton y tengo la sola dimensión caso perfectamente, pero multidimensional de la versión me hace la pregunta...

En Wikipedia método de Newton en las dimensiones superiores se define como:

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

Donde $\textbf{x}_n$ $p$- dimensiones del vector en $n$th iteración, $[Hf(\textbf{x}_n)]^{-1}$ es la inversa de la matriz Hessiana de la función de $f(\textbf{x})$ $\textbf{x}_n$ $\nabla f(\textbf{x}_n)$ es el gradiente de la función de $f(\textbf{x})$$\textbf{x}_n$. Que es:

$$\left( \begin{array}{c} x_1^{(n+1)} \\ x_2^{(n+1)} \\ \vdots \\ x_p^{(n+1)} \end{array} \right) = \left( \begin{array}{c} x_1^{(n)} \\ x_2^{(n)} \\ \vdots \\ x_p^{(n)} \end{array} \right) - \left( \begin{array}{cccc} \frac{\partial^2f}{\partial x_1^2}(\textbf{x}_n) & \dots & \dots &\frac{\partial^2f}{\partial x_p\partial x_1}(\textbf{x}_n)\\ \frac{\partial^2f}{\partial x_1\partial x_2}(\textbf{x}_n) & \ddots & \vdots & \vdots\\ \vdots & \vdots & \vdots & \vdots\\ \frac{\partial^2f}{\partial x_1\partial x_p}(\textbf{x}_n) & \dots & \dots & \frac{\partial^2f}{\partial x_p^2}(\textbf{x}_n) \end{array} \right)^{-1}\left( \begin{array}{c} \frac{\partial f}{\partial x_1}(\textbf{x}_n) \\ \frac{\partial f}{\partial x_2}(\textbf{x}_n) \\ \vdots \\ \frac{\partial f}{\partial x_p}(\textbf{x}_n) \end{array} \right)$$

Ahora mi pregunta es: "¿Qué es la intuición detrás de esta fórmula?" Esto se asemeja de alguna manera el gradiente algoritmo de descenso, pero a la inversa de la de Hess es como si viniera de la chistera :S ¿alguien me da un tipo similar de la prueba como se da aquí en el caso unidimensional:

¿Por qué el método de Newton trabajo?

¿Por qué el estado de Hesse? Por qué su inversa?! :) La intuición de la fórmula?

Gracias por la ayuda :) P. S. I aquí es la página llegué a la fórmula anterior:

http://en.wikipedia.org/wiki/Newton%27s_method_in_optimization#Higher_dimensions

Tenga en cuenta también que en mi notación de la topscript en el $x_i$s no significa exponente, es sólo una iteración de la etiqueta...

Answer 1

Voy a asumir que estamos tratando de minimizar una dos veces continuamente derivable la función $f$ definido en $\mathbb R^p$.

Queremos encontrar a $x$ tal que $\nabla f(x) = 0$.

Dado $x_n$, lo ideal sería encontrar a $\Delta x$ tal que $\nabla f(x_n + \Delta x) = 0$. En lugar de satisfacer este requisito exactamente (que probablemente sería demasiado difícil), que en lugar de utilizar la aproximación \begin{equation*} \nabla f(x_n + \Delta x) \approx \nabla f(x_n) + Hf(x_n) \Delta x. \end{ecuación*} Ajuste el lado derecho igual a $0$ nos da \begin{equation*} \Delta x = -Hf(x_n)^{-1} \nabla f(x_n). \end{ecuación*} Podemos tener la esperanza de que $x_{n+1} = x_n + \Delta x$ se una mejora en $x_n$.

Answer 2

Aquí es otra interpretación del método de Newton que me gusta bastante.

El método de Newton toma la información que se sabe de la función en un punto dado (valor de gradiente y de Hesse), hace una aproximación cuadrática de la función, y minimiza esa aproximación.

Más concretamente, supongamos $x_n$ es dado, $g = \nabla f(x_n)$, e $H = \nabla^2 f(x_n)$. La aproximación cuadrática de $f$ $x_n$ es una función cuadrática $h(x)$ tal que $h(x_n) = f(x_n)$, $\nabla h(x_n) = g$ y $\nabla^2 h(x_n) = H$. Resulta que $$ h(x) = \frac 12(x - x_n)^T H (x - x_n) + g^T (x - x_n) + f(x_n). $$ Esta función tiene un único mínimo global si y sólo si $H$ es positiva definida. Este es el requisito para el método de Newton para trabajar. Asumiendo $H$ es positiva definida, el mínimo de $h$ se consigue en $x^*$ tal que $\nabla h(x^*) = 0$. Desde $$ \nabla h(x) = H(x - x_n) + g, $$ llegamos $x^* = x_n - H^{-1}g$.

Answer 3

La Arpillera es simplemente el de mayores dimensiones de la generalización de la derivada segunda, y multiplicar por su inverso es el no-conmutativa de la generalización de la división por $f''$ en el caso unidimensional. No sé si es razonable intentar un argumento geométrico a lo largo de la línea de su enlace para el doble de la generalización a la optimización y a $n$ dimensiones: mejor, solo tienes que buscar una prueba real.

Podría ser menos confuso si usted mira la de mayores dimensiones método de Newton para las raíces, antes de que para la optimización. Esa es la "sistemas no lineales de ecuaciones" en la Wikipedia. Hubbard y Hubbard, el libro de álgebra lineal, cálculo multivariable, y formas diferenciales tiene el mejor tratamiento de la multivariante método de Newton sé.