4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – Moo Oct 27 '17 at 16:55
  • $\begingroup$ 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. $\endgroup$ – MathMen Oct 27 '17 at 17:11
2
$\begingroup$

$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!

$\endgroup$
  • $\begingroup$ I'm sorry, but minimum of this function is: $f(0, 1) = -1$. $\endgroup$ – MathMen Oct 27 '17 at 17:19
  • $\begingroup$ @MichaelRozenberg: The function you wrote is incorrect. $\endgroup$ – Moo Oct 27 '17 at 17:21
  • $\begingroup$ I fixed. Thanks guys! $\endgroup$ – Michael Rozenberg Oct 27 '17 at 17:25
  • $\begingroup$ 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. $\endgroup$ – MathMen Oct 27 '17 at 17:27
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – MathMen Oct 27 '17 at 20:05
  • 1
    $\begingroup$ 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. $\endgroup$ – eric_kernfeld Oct 27 '17 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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