1
$\begingroup$

I am currently trying to study the Newton's method of optimization through this wiki article http://en.wikipedia.org/wiki/Newton%27s_method_in_optimization. However, I didn't get this concept about constructing the sequence xn and approximating the objective function by a quadratic function around xn.

Can anyone provide me some good references. I mean why are are constructing that sequence xn? Any geometric visualization will be helpful I guess.

1 Answers 1

1

This is not really very difficult. The article gives the second order Taylor expansions of a twice differentiable function f. This function is quadratic in ∆x. A quadratic function will have a single extreme point where the first derivative is zero. It is either a maximum or a minimum depending on whether the coefficient of the quadratic term is positive or negative. If you start at a point xn that is reasonably close the the target point x the second order Taylor series will be a good local approximation for the function. So you set the first derivative of that function of ∆x to 0. That gives ∆x =-f'(xn)/f"(xn) and hence x-xn=-f'(xn)/f"(xn) since x-xn=∆x. So we have that to get closer to x we take xn+1 =xn-f'(xn)/f"(xn). Now expanding at the point xn+1 gives the next iteration xn+2=xn+1-f'(xn+1)/f"(xn+1).

  • 0
    Reasonably close just means close enough that the second order Taylor series approximation of the function at that point is close to the actual value of the function at that point. To use this formula you need to be starting close enough that the formula will move you in the right direction toward x. So xn needs to be close enough that the move to xn+1 gets you closer to x. This is admittedly a little vague but you can pick an epsilon to make this precise.2012-06-16