# Different behaviour of Newton's method for finding minimum of a function

Given the following function of two variables

$$f(x, y) = 2x^2 − 2xy + y^2 + 2x − 2y$$

I wanted to use Newton's method to find a minimum of this function. I started from $(x_1, y_1) = (0, 0)$ and applied the following formula

$$x_{k+1} = x_k - \alpha \left(\nabla(f(x_k)^{2}\right)^{-1} \nabla(f(x_k))$$

where

$$\alpha = \frac{\nabla(f(x_k))^{T} \nabla(f(x_k))}{\nabla(f(x_k))^{T}(\nabla(f(x_k)^{2})\nabla(f(x_k)) }$$

I obtained $(x_2, y_2) = \left(0, \frac{1}{5}\right)$ and $(x_3, y_3) = \left(0, 0\right)$. So I decided to check by induction if in general we have $(x_{2k}, y_{2k}) = \left(0, \frac{1}{5}\right)$ and $(x_{2k+1}, y_{2k+1}) = (0, 0)$. It turns out that this is true, so I will never obtain a minimum for $k \rightarrow \infty$. Can anyone explain me this strange behaviour of this method.

• I just ran my variant of Newton Method Search to find a minimum starting at $(x, y) = (0, 0)$, and it produced a local min at $$(x, y) = (0, 1)$$ I then verified this result using another tool and it produced the same result. What code are you using? – Moo Oct 27 '17 at 16:55
• I did not use any code. I just calculated it analytically. I wanted to find general formula for $x_k$ and it turned out that using this method and using quadratic approximation of step size $\alpha$ I obtained a sequence which is not convergent. I heard that Newton's method in some cases is not good choice. I wonder why in my choice it gives me only two different points. – MathMen Oct 27 '17 at 17:11

$f(0,1)=-1$.

We'll prove that it's a minimal value.

Indeed, we need to prove that $$2x^2+y^2-2xy+2x-2y\geq-1$$ or $$2x^2-2(y-1)x+y^2-2y+1\geq0$$ or $$x^2+(x-y+1)^2\geq0.$$ Done!

• I'm sorry, but minimum of this function is: $f(0, 1) = -1$. – MathMen Oct 27 '17 at 17:19
• @MichaelRozenberg: The function you wrote is incorrect. – Moo Oct 27 '17 at 17:21
• I fixed. Thanks guys! – Michael Rozenberg Oct 27 '17 at 17:25
• I know that this is minimum of this function. My question is: Why Newton's method which generates me a sequence of solutions does not converge to the true solution. – MathMen Oct 27 '17 at 17:27

You simply have an error in your calculations.

$(x_3,y_3) = (0,9/25)$ and not $(0,0)$.

Incidentally, I'm not sure where you got the formula for $\alpha$. In traditional Newton's method you would use $\alpha=1$, in which case Newton's method converges in one step (not surprising at all, given that your objective function is quadratic...)

With your value of $\alpha$, Newton's method will still converge, but very slowly.

• Thank you very much!!! I have another question: In which cases Newton's method converges in one step? Is it always true for quadratic functions? – MathMen Oct 27 '17 at 20:05
• Yes. At each step, Newton's Method forms a quadratic approximation to the objective and finds the global minimum of the quadratic. If the objective is already a (bowl-shaped) quadratic, the approximation is perfect and the first step finds the global minimum of the objective. – eric_kernfeld Oct 27 '17 at 21:30