Next, let's talk about the Newton's method. Newton's method is somewhat similar to your gradient descent, it's going to have a lot of iterations. In each iteration, it tries to move to a better point. But there is one thing different. The Gradient Descent method is a first-order method. Pretty much we always calculate the gradient and then try to move to somewhere. The first-order method is intuitive, but sometimes it may be too slow. We're not going to show you why it may be too slow. But at least one thing that is clear is that we have gradient, we have hashing, we have first-order, we have second order, but we have not used any second-order thing, when we are using the gradient descent method. Maybe we may try or a second order method, which relies on the hashing to update a solution that may be faster. Maybe we should try this, and one second order method that is very popular or very fundamental I will say, is the Newton's method. To introduce the Newton's method for nonlinear programming, we need to start by introducing the Newton's method for solving a nonlinear equation. Maybe some of you also heard about this when you were taking your calculus course. But anyway, let's try to do this. Suppose I have a function which has only one decision variable or one independent variable. Let's say this function is differentiable. We want to find x bar such that f of x bar is zero. So f is a non-linear function like this. F is a non-linear function, and we want to find a route for this nonlinear function. We are trying to solve a non-linear equation. Now our strategy is the following. Still, I'm going to start from an initial point. Then at each point x_k, I am going to consider the linear approximation of f at that particular point. Pretty much you're doing this for this function f, I'm going to create f_L of x, where L means the linear relaxation. How to do that? Well, this is pretty much the Taylor expansion you [inaudible] in your calculus course. At each point here, you will first do f of x_k, plus f prime of x_k multiplied by x minus x_k. At each point, you will first ask yourself how high is your current point? So that is your f of x_k, and then you'll have derivative. Your derivative here somehow means your slope. You'll have x minus x_k, so you are going to move to somewhere that is close to you. Then you'll know how is the impact of doing the moving, that's going to move you toward that direction by decreasing or increasing some amount. That amount is determined by the slope, and the amount you move. If you express the height of x in that way, then your f_L, of course is a linear function and it's pretty much a first order Taylor expansion at the point x_0. So as we mentioned here this is the tangent line, this one of f at x_k or the first-order Taylor expansion of f at x_k. Your f originally is nonlinear, but its first order Taylor expansion must be linear. Then what we will do is that we will solve this linear equation. We will try to make x_k plus 1 satisfying the function being zero. We don't really directly solve our non-linear problem for this nonlinear equation, maybe we don't know how to solve it but for the linear one, everything is so easy. We do that once, and then we do it twice, do it three times, four times and so on. We keep iterating this, until our f of x_k is dense than epsilon. What's that? Our f of k is pretty much our objective value, and we want to make f of x_k zero, so we would stop when this value is pretty much zero, or on the other hand, maybe some people would say, "Okay, if the difference between the x value is small enough, then we would also stop." So we have some stopping conditions, and the way that we stop is to think about, what's the current improvement? If the current improvement is already too small, then we stop. Or when we say the objective value is already close enough to what we want, then also there would be no much improvement. Then maybe we also stop. That's the way for using the Newton's method. The method invented by Newton, so using the Newton's method, we are able to solve a non-linear equation.
