convergence-divergencenewton raphsonnumerical optimizationoptimization
Lets say I have a function
$f(x) = x^TAx+b^Tx+c$
Using Newton's method to find a minimum, I get $$x_1 = x_0 + \frac{x^TAx+b^Tx+c}{f'(x)}$$
How would I prove that this converges in one iteration, regardless of initial solution ($x_0$)? Obviously the exact solution is the quadratic formula but I can't see how after just one iteration you can see that it has converged.
We are given the Rosenbrock Function, sometimes called the banana function with $a = 1, b = 100$ and asked to find the minimum using Newton's method with a starting point $X_0 = (x, y) = (1.2, 1.2)$ as:
$$f(x,y)=(1-x)^2+100(y-x^2)^2$$
Newton's method can be extended for the minimization of multivariable functions.
The iteration is given by:
$$X_{n+1} = X_n - [J_n]^{-1} \nabla f_n$$
where: $$ \nabla f = \begin{bmatrix} \dfrac{\partial f}{\partial x} \\ \dfrac{\partial f}{\partial y} \end{bmatrix} = \begin{bmatrix} 2 (1 - x) - 400 x (-x^2 + y) \\ 200 (-x^2 + y) \end{bmatrix}$$
$$J = \begin{bmatrix} \dfrac{\partial^2 f}{\partial x^2} & \dfrac{\partial^2 f}{\partial x \partial y} \\ \dfrac{\partial^2 f}{\partial y \partial x} & \dfrac{\partial^2 f}{\partial y^2} \end{bmatrix} = \begin{bmatrix} 2 + 800 x^2 + 400 (x^2 - y) & 400 x \\ -400 x & 200 \end{bmatrix}$$
The iterates are:
Here is a graphical representation of the Newton iterates:
A lot is known about fixed point iterations, and this can be applied to the case of the Newton iteration. "Just using Newton's method", you may be able to tell what happens when you start at a particular initial point, but how can you tell whether it will converge for all initial points in a certain interval? Using the theory of fixed point iterations, this may be possible.
For example, here's one of my favourite results. Say you're using Newton's method to solve $f(x) = 0$, and $x=r$ is one solution. What is the largest interval around $r$ such that if you start in that interval, Newton's method always converges to $r$? This interval will be of the form $(a,b)$, where there are just four possibilities:
Best Answer
Note that the version you wrote is Newton's method for finding the zero of a function $f$. To find the minimum of a function, we look for zeros of $\nabla f$ (the gradient of $f$). If $A$ is symmetric and positive definite, then your function $f$ is a strictly convex function and therefore a zero of $\nabla f$ will be the unique global minimizer of $f$. Therefore, if we use Newton's method to find a zero of $\nabla f$ and the scheme converges, then we have successfully minimized $f$. Now, writing Newton's method to find a zero of $\nabla f$, we obtain \begin{equation*} x_{k+1} = x_k - \nabla^2 f(x_k)^{-1} \nabla f(x_k), \end{equation*} where $\nabla^2 f$ is the Hessian of $f$. Of course, this scheme relies on the assumption that $f$ is twice differentiable and that the Hessian is nonsingular at all points $x_k$ in our sequence of iterates. For $f(x) = x^\top Ax + b^\top x + c$ with $A\succ 0$, both of these assumptions are satisfied.
Now let's prove the one-step convergence. Note that, for symmetric $A$, it holds that $\nabla f(x) = 2Ax + b$ and $\nabla^2 f(x) = 2A$. Let $x_0\in\mathbb{R}^n$. Then our first iterate becomes \begin{align*} x_1 ={}& x_0 - (2A)^{-1}(2Ax_0 + b) \\ ={}& x_0 - \frac{1}{2}A^{-1}(2Ax_0+b) \\ ={}& x_0 - x_0 - \frac{1}{2}A^{-1}b \\ ={}& -\frac{1}{2}A^{-1}b. \end{align*} We can verify that this indeed is the global minimizer by analytically minimizing $f$: \begin{equation*} \nabla f(x^*) = 2Ax^* + b = 0 \end{equation*} implies that the unique global minimizer is \begin{equation*} x^* = -\frac{1}{2}A^{-1}b = x_1. \end{equation*} Hence, the scheme converges to the global minimizer in one step.