Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm studying about Newton's method and I get the single dimension case perfectly, but the multidimensional version makes me ask question...

In Wikipedia Newton's method in higher dimensions is defined as:

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

Where $\textbf{x}_n$ is the $p$-dimensional vector at $n$th iteration, $[Hf(\textbf{x}_n)]^{-1}$ is the inverse of the Hessian matrix of the function $f(\textbf{x})$ at $\textbf{x}_n$ and $\nabla f(\textbf{x}_n)$ is the gradient of the function $f(\textbf{x})$ at $\textbf{x}_n$. That is:

$$\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)$$

Now my question is: "What is the intuition behind this formula?" This resembles somehow the gradient descent algorithm, but the inverse of the Hessian is like it came from the magician's hat :S Can somebody give me a similar kind of proof as is given here on the one-dimensional case:

Why does Newton's method work?

Why the Hessian? Why its inverse?! :) Intuition of the formula?

Thank you for any help :) P.S. I here is the page I got the formula above:

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

Note also that in my notation the topscript in the $x_i$s doesn't mean exponent, it's just an iteration label...

share|improve this question

3 Answers 3

up vote 6 down vote accepted

I'll assume we're trying to minimize a twice continuously differentiable function $f$ defined on $\mathbb R^p$.

We wish to find $x$ such that $\nabla f(x) = 0$.

Given $x_n$, we would ideally like to find $\Delta x$ such that $\nabla f(x_n + \Delta x) = 0$. Rather than satisfying this requirement exactly (which would probably be too difficult), we instead use the approximation \begin{equation*} \nabla f(x_n + \Delta x) \approx \nabla f(x_n) + Hf(x_n) \Delta x. \end{equation*} Setting the right hand side equal to $0$ gives us \begin{equation*} \Delta x = -Hf(x_n)^{-1} \nabla f(x_n). \end{equation*} We can hope that $x_{n+1} = x_n + \Delta x$ will be an improvement on $x_n$.

share|improve this answer
2  
Note that Newton's method in optimization simply solves $\nabla f(x) = 0$, using Newton's method for solving nonlinear equations. –  littleO Aug 2 '13 at 10:49
1  
+1 Thank you for your help :) –  jjepsuomi Aug 2 '13 at 11:19

Here is another interpretation of Newton's method that I rather like.

Newton's method takes the known information of the function at a given point (value, gradient and Hessian), makes a quadratic approximation of that function, and minimizes that approximation.

More specifically, suppose $x_n$ is given, $g = \nabla f(x_n)$, and $H = \nabla^2 f(x_n)$. The quadratic approximation of $f$ at $x_n$ is a quadratic function $h(x)$ such that $h(x_n) = f(x_n)$, $\nabla h(x_n) = g$ and $\nabla^2 h(x_n) = H$. It turns out that $$ h(x) = \frac 12(x - x_n)^T H (x - x_n) + g^T (x - x_n) + f(x_n). $$ This function has a unique global minimum if and only if $H$ is positive definite. This is the requirement for Newton's method to work. Assuming $H$ is positive definite, the minimum of $h$ is achieved at $x^*$ such that $\nabla h(x^*) = 0$. Since $$ \nabla h(x) = H(x - x_n) + g, $$ we get $x^* = x_n - H^{-1}g$.

share|improve this answer
    
+1 Thank you for your help :) –  jjepsuomi Aug 2 '13 at 11:20

The Hessian is simply the higher-dimensional generalization of the second derivative, and multiplying by its inverse is the non-commutative generalization of dividing by $f''$ in the one-dimensional case. I don't know if it's reasonable to try a geometric argument along the line of your link for the double generalization to optimization and to $n$ dimensions: better to just look up an actual proof.

It might be less confusing if you look at the higher-dimensional Newton's method for roots, before that for optimization. That's the "nonlinear systems of equations" section on Wikipedia. Hubbard and Hubbard's book on linear algebra, multivariable calculus, and differential forms has the best treatment of multivariate Newton's method I know.

share|improve this answer
1  
+1 Thank you for your help @Kevin Carlson –  jjepsuomi Aug 2 '13 at 10:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.