Constructing a newton sequence

Question

How may I construct the newton sequence for the following:

$(1) f(x_1,x_2) = x_1^4 + 2x_1^2x_2^2 + x_2^4$ with $x_0 = (1,1)$ and $x_0 = (1,0)$

$(2) f(t) = t^4 - 32t^2$ and $t_0 = 1$

To find $x_{k+1}$ do I need to use $\nabla^2f(x_k)(x_{k+1}-x_k) = - \nabla f(x_k)$

For finding the $x_{k+1}$ terms? If so, how would I go about solving that equation?

Answer 1

For the first question, we are given an $f(x_1, x_2)$ and asked to find the minimum using Newton's method with starting points $X_0 = (x_1, x_2) = (1, 1)$ and $x_0 = (1, 0)$ as:

$$\tag 1 f(x_1, x_2) = x_1^4 + 2x_1^2x_2^2 + x_2^4$$

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(x_1,x_2) = \begin{bmatrix} \dfrac{\partial f}{\partial x_1} \\ \dfrac{\partial f}{\partial x_2} \end{bmatrix} = \begin{bmatrix} 4 x_1^3 + 4 x_1 x_2^2 \\ 4 x_1^2 x_2 + 4 x_2^3 \end{bmatrix}$$

$$J(x_1,x_2) = \begin{bmatrix} \dfrac{\partial^2 f}{\partial x_1^2} & \dfrac{\partial^2 f}{\partial x_1 \partial x_2} \\ \dfrac{\partial^2 f}{\partial x_2 \partial x_1} & \dfrac{\partial^2 f}{\partial x_2^2} \end{bmatrix} = \begin{bmatrix} 12 x_1^2 + 4 x_2^2 & 8 x_1 x_2 \\ 8 x_1 x_2 & 4 x_1^2 + 12 x_2^2 \end{bmatrix}$$

The iterates are:

• $X_0 = \begin{bmatrix} 1.0 \\ 1.0 \end{bmatrix}$
• $X_1 = \begin{bmatrix} 0.666667 \\ 0.666667 \end{bmatrix}$
• $X_2 = \begin{bmatrix} 0.444445 \\ 0.444445 \end{bmatrix}$
• $X_3 = \begin{bmatrix} 0.296297 \\ 0.296297 \end{bmatrix}$
• $\ldots$
• $X_n = \begin{bmatrix} 0. \\ 0. \end{bmatrix}$

A plot shows:

You try for $X_0 = (1, 0)$.

For the second problem, we can use Newton's method to find the minimum of a function. We need to derive a function $h(t)$ that has a root at the point where $f(t)$ achieves its minimum.

Write down the formula for Newton’s method applied to $h(t)$.

$$h(t) = f'(t) = 4t^3 - 64 t$$

Use Newton's Method to find the root (you should verify what you get as critical points with $h''(t)$, where you can also use Newton's Method):

$$t_{n+1} = t_n - \dfrac{h(t_n)}{h'(t_n)} = t_n - \dfrac{4t_n^3-64t_n}{12t_n^2-64}$$

• $t_0 = 1.0$
• $t_1 = -0.153846$
• $\ldots$
• $t_n = 0$

A plot shows:

We can see that using $t_0 = 1$, we found the local max. Had we chosen a better starting value, like $t_0 = 5$ or $t_0 = -5$, we would have landed on either of those two global minimum ($t = \pm 4$). I assume your problem likely meant local max for this part of the problem.