Newton's Method for Multivariable Optimization

[00:00:01]in this lecture we will be studying Newton's method for nonlinear optimization first let's remind ourselves of how Newton's method works for a function of a single variable so solving equations is often difficult or even impossible to do analytically we have a theorem from Abel in the early 1800s that says there is no formula giving the solution of an arbitrary polinomial equation of degree 5 or higher in terms of algebraic combinations of its coefficients in this case think of something like the quadratic formula for a general quadratic polinomial we have a formula that finds a solution of that quadratic set equal to zero but once we get to higher degree equations or to just equations in general Beyond pols we don't necessarily have that method for finding an analytic solution one class of methods to numerically approximate solutions to this type of problem are called iterative Methods and the idea here is we have a function and we want to find a root of this function so we want to solve F ofx equal zero and we want to generate a sequence of guesses that converge to the solution that we seek R so in here by R we mean that r is the root of f a root of F and we Define what we mean by convergence a sequence of approximations converges to the number R provided that we can make the nth entry in this sequence as close to r as we desire simply by choosing n sufficiently large so by going far enough down the list mathematically this means for any Epsilon greater than than Z there exists an n in the counting number so think of an n as an index in the sequence such that the difference the magnitude of the difference between that nth term in the sequence and that solution R is smaller than Epsilon once you're past that capital N in the list Newton's method is such an iterative method and and so in Newton's method our goal is to approximate this root of the function f ofx Newton's method uses a tangent line approach so Newton's method is for functions where we actually can calculate a derivative so let's think about the tangent line at this point xot F of xot so let's form the tangent line if we draw it we will get something like this so this is our tangent line at the point x knot F of xot we know that the slope of that tangent line is fr Prime of X knot to write down the equation of that tangent line we use our point slope formula now we know that y not is f of xot but the slope will be frime of xot so putting that all together we have y minus F ofx knot equals frime of xot * x - x what Newton's method does is starting with this xot as our initial guess for this root we form this tangent line and our next guess defined as X1 will be the root of that tangent line so how do we find the root of that tangent line given that we have the equation for the tangent line here well we note that at that roote the yalue for that tangent line is zero so we plug in zero and we seek the x coordinate associated with this y equals z value what we have here is going to be one form of how we write down Newton's method and the other we solve for that X so notice solving for that X we can divide both sides by frime of xot as long as frime of xot is non zero and so we get negative f ofx knot / frime of xot is equal to x - xot solving for x we have xal negative f ofx knot over frime of xot plus X knot and this x is what we just found here and we're calling X1 and we're using a superscript because we are working in the next slide with functions of several variables and we use the subscript to denote which entry of our Vector X that we are speaking of so the superscript in parenthesis tells us which iteration we are on note that we have this written here so this is this is now for the N plus first x given the previous guess xn so this is what we Define to be the Newton method sequence and the idea here is you can iterate this so what we would do for the next guess is we would use this X1 go up here find the tangent line and then find its x intercept and you can see graphically that we would be honing in on this root r a couple subtleties it's important to recognize that there are situations where Newton method does not converge and if it does converge it will converge to a solution of f ofx equals z but it also depends heavily on the initial guess so with this depiction here we have our horizontal axis here and we can see that if you start with an initial guess here we expect to hone in on this route but if we were to start with an initial guess over here we should expect to hone in on this route here so our initial guess does play a role so often times with Newton's method your initial guess is something that you you use information about the function that you already have to make some type of in intelligent initial guess so it's it's critical to recognize that for any iterative method you have to start somewhere so you have to have some initial guess now we want to use Newton's method for functions of n variables and we're really setting up for optimization so first we want to talk about a slightly different setting that we're used to we're going to talk about a function G from RN to RN and it's important to recognize the range here is RN so this is a vector valued function G it takes in a vector as input and gives a vector as output and we're setting up to solve the system g ofx equals the Z Vector it's a little more natural to look at it this way G of X here gives you an N Vector G1 of X G2 of X GN of X where each one of those individual G sub I these go from RN to R1 so each entry here when you give it an X is a scalar and our goal is to solve this system of equations starting with some initial guess X knot so that's a a vector as an initial guess and what we do is extend the Newton method that we just looked at to a vector version so this was one way that we could write down Newton's method for a function of a single variable and now we write that in this Vector form so instead of f of xn we'll have G1 of XK then here we have the gradient of G1 of XK dotproduct XK + 1 - XK that's the analog of this equal to zero and we have this equation for each of these equations coming from G so we have an equation like this for G1 we have an equation like this for G2 up to an equation like this for GN and the idea there is that instead of taking a tangent line and finding its root we are looking at the tangent hyperplanes for each one of these components of G we know when we're working in higher Dimensions like this that this here G1 of XK is the scaler the gradient of G1 evaluated at XK remember we know XK so this is is just a vector of numbers XK is a vector of numbers that's our previous guess XK + 1 is the unknown so this is a scalar plus some linear combination of the entries of XK + 1 equals z this is a hyper plane in our n plus1 dimensional space the key is that we are solving n of these simultaneously to see what this is graphically consider the case where n equals 2 our hyper planes in this case are just planes so this would be say the first such plane well the first such plane being equal to zero will give you this entire line in the X1 X2 plane what about the second plane maybe it look something like this that plane being equal to zero gives us this entire line in the X1 X2 plane but the key is that we are solving them simultaneously as long as these planes are not parallel these planes in the X1 X2 plane intersect in a point and this is the point we seek this is what we mean by solving these simultaneously so for some notation let's let this be a matrix so notice G and the gradient are both bold the idea being that's different how we usually write traditional gradient as a vector this is just special notation for the Jacobian matrix of G of X and so the Jacobian matrix of G of X just means that entry i j of this Jacobian is the partial derivative of GI with respect to XJ so it's a matrix of all of these first order derivatives for our Vector valued function G if we put all of that together that system of equations can be written as that Jacobian matrix times XK + 1 - XK equals g of XK this collapses all n of those equations into one Matrix Vector multiplication equation if we can invert this Jacobian matrix we can multiply both sides of this equation by that inverse and solve for XK + 1 if this is not invertible we say that the sequence is undefined and so the idea here is you can't have two parallel hyperplanes that come out of that system that way you get one point where all of the these equations are satisfied and notice we do write both versions because when you get into high Dimensions often times you're not just calculating the inverse of the Jacobian matrix like this you need to do some things in linear algebra that are a little more clever depending on the structure of the Jacobian this defines our Newton method sequence when we are working in n-dimensional space like this for a vector value function G so it's important to recognize again G has a domain of RN and a range of RN well the natural question to ask now is how does this relate to optimization we're minimizing a function f ofx our objective function is going from RN to R so why are we looking at this case where the range is RN and the reason comes down to our first order necessary conditions for our minimization problem and recall if f ofx is twice differentiable our first order necessary conditions for a local minimizer is that the gradient of f is equal to the zero vector and what we will do is set the gradient of f to be equal to G of x in the previous theorem so think about what the gradient of f ofx is the gradient of f ofx takes in an X which is in RN and then gives us a vector in RN the gradient is a a vector in RN so we simply go back here and our G will be replaced with the gradient of F and we seek a solution to the gradient of f equals the zero Vector we see here when we make that change the gradient of f plays the role of G but that means if we take another derivative here the Jacobian of G will be the hessen of f so we go back into that Newton method equation and we replace our G's with the radiant of F and we replace our Jacobian with the hessen of F and we now have our Newton method sequence for minimizing our function f ofx and so now we have our theorem here for that type of minimization and it simply is what we just wrote with G replaced by gradient of F and the Jacobian of G replaced by the hessen of f this defines our Newton method for nonlinear optimization and just like before it may not converge it's sensitive to your choice of initial guess and it's meant to hone in on points that satisfy the first order necessary condition of the gradient of f ofx being equal to the zero vector and remember that that will pick up on local Minima local Maxima and saddle points but nonetheless this gives us a way to numerically approximate points X that satisfy those first order necessary conditions for a minimizer if you have a nice situation where you know your f is convex remember those first order necessary conditions become sufficient as well and so for a convex problem Newton's method is only going to hone in on minimizers global minimizers if it's converging it's important to recognize that this is a really important line search method for optimization many optimization routines will use this as a sub routine so understanding how Newton's method works really is critical to understand how we find minimizers of optimization problems and remember when you're working with high-dimensional problems we are typically not doing some type of analytic solution we are understanding the properties of our objective function and then using iterative methods to try to find a solution numerically and this is the classic such method so we will see this in action in an example in a subsequent lecture but again it's important to recognize that Newton's method is is one of the most important methods in nonlinear optimization