Week 2

Question 1

What is the Newton-Raphson method, and what are the steps?

Answer 1

The Newton’s method is used to find the minimum/maximum of a function.

By the Taylor expansion f(x + h) ≈ f(x) + h^T G(x) + 0,5 h^2 H(x) h =: Q(h), then minimize Q(h) with respect to h in R^d

Q’(x) = G(x) = H(x)h = 0 => H(x)h = -G(x)
set x = x + h, then repeat

Question 2

What are the disadvantages of the Newson-Rapson Method?

Answer 2

1. It requires the existence of the Hessian matrix (2nd order derivates). If Hessian exists and behave well you also need t find the inverse of the Hessian at every step.
2. A local optimum instead of a global one is found

We can use the BFGS method to approximate H^-1

Question 3

What are steps of the BFGS method?

Answer 3

• Start with k = 0 and a positive definite matrix M0, e.g. M0 = Id
• Calculate hk = -MkGk, with Gk = G(x^k)
• Update x^k+1 = x^k + hk
• Calculate qk = G(X^(k+1)) - G(x^k)

Question 4

What is the direction h of the Newton-Rapson method?

Answer 4

h = -[H(x^(k)]^-1 G(x^(k))

Question 5

What is the direction h of the BFGS method?

Answer 5

h = -MkG(x^(k))