0

I have the following function:

$f(x) = 100(x_2 - x_1^2)^2 + (1-x_1)^2$

I have to find the minimum of this function using the Newton Raphson method.

The point where I have to start is $x = [1.2$, $1.2$]

I have found a formula on the internet for this:

$ x_{k+1} = x_k - J^{-1}\cdot f(x_k)$ where $J$ is the Jacobian.

But for this problem the Jacobian matrix is a $1$x$2$ matrix, hence an inverse does not exist.

Can anybody please tell me how to solve this problem?

dreamer
  • 3,379
Nedellyzer
  • 1,174

1 Answers1

3

Hint: at a minimum of a function, the derivative is zero.

Newton-Rhapson is a root-finding algorithm, and hence is well-suited to computing zeros of functions.

Edit: You need to find the minimum. The first step of this is to find points where $\frac{\partial f}{\partial x_1}$ and $\frac{\partial f}{\partial x_2}$ are both zero.

Now you have two conditions, so you want to compute:

$$\mathbf{g}(x_1,x_2) \stackrel{\textrm{def}}{=}\begin{pmatrix} \frac{\partial f}{\partial x_1} \\ \frac{\partial f}{\partial x_2} \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}.$$

This gives you two equations with two unknowns. Now perform Newton-Raphson on $\mathbf{g}$. The "Jacobian" of $\mathbf{g}$ is the Hessian of $f$, so you'll have a matrix that looks like:

$$\begin{pmatrix} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} \\ \frac{\partial ^2 f}{\partial x_2\partial x_1} & \frac{\partial^2 f}{\partial^2 x_2}\end{pmatrix}$$

Emily
  • 35,688
  • 6
  • 93
  • 141
  • I already know that... I don't know how to do this for a function with 2 variables – Nedellyzer Dec 03 '13 at 16:32
  • 1
    Well, if you use it to compute the minimum by finding the zeros of the derivative, you won't be using the Jacobian. You'll be using the Hessian: http://en.wikipedia.org/wiki/Hessian_matrix – Emily Dec 03 '13 at 17:04
  • @Arkamis Yes, but if you use the formula for Newton Rhapson method, you get a $2X2$ matrix multiplied by $f(x)$ which is a scalar, hence matrix dimensions in total will not be correct. – Nedellyzer Dec 03 '13 at 17:41
  • $H^{-1}f(x_k)$ means the inverse of the Hessian computed from $f(x)$ at $x_k$. $Hf(x)$ is the Hessian operator applied to the function $f(x)$, resulting in a 2x2 matrix which is, in all likelihood, invertible. – Emily Dec 03 '13 at 17:57
  • @SjoerdSmaal You should peruse this Wikipedia page: http://en.wikipedia.org/wiki/Newton%27s_method_in_optimization – Emily Dec 03 '13 at 17:58