{"id":181,"date":"2015-07-18T13:58:11","date_gmt":"2015-07-18T13:58:11","guid":{"rendered":"https:\/\/mgric.wordpress.com\/?p=181"},"modified":"2015-11-05T00:45:46","modified_gmt":"2015-11-05T00:45:46","slug":"gradient-search-methods-newton-raphson-method-i-have-aspart-2as","status":"publish","type":"post","link":"https:\/\/marcelloricottone.com\/blog\/2015\/07\/18\/gradient-search-methods-newton-raphson-method-i-have-aspart-2as\/","title":{"rendered":"Gradient Search Methods: Newton-Raphson Method Part 2"},"content":{"rendered":"

Last post we got an idea of how Newton-Raphson works (and how similar it is to the one dimensional version). Here we will explore step by step how the algorithm works and how quickly it arrives to our minimum. \u00a0We will be using the same function as before so we can compare how quickly the method descends. Here is our function in both a surface plot and a contour plot as a reminder. (f(x,y) = \u00a0x^2 -x+cos(y+x)+y^2<\/p>\"Screen\"Screen
\n<\/a><\/p>As you can see it is a relatively simple surface and convex. In order to use Newton Raphson, we need to take both the gradient and the hessian of our function. A quick mathematics reminder, The gradient is the vector which contains first derivatives of the function with respect to each of its variables. Below you can see a general case for the gradient as well our specific gradient for this function.<\/p>\"Screen<\/a><\/p>As I mentioned last post we also need the equivalent of the second derivative for newton-raphson. This takes the form of the hessian. Another quick mathematics reminder, the Hessian is the square matrix consisting of all the second derivatives of our function. The Hessian exhaustively takes the derivatives of the function with respect to one variable an d the second derivative with respect to every variable again. To clarify this i have left the general case below along with our specific case.<\/p>\"Screen<\/a><\/p>Note that the Hessian above is a square matrix (it always should be). The second check that has to be made is to ensure that the Hessian is invertible. Since we are dealing with matrix we cannot “divide” matrices, we must use the inverse of the Hessian instead. This comes into play with our iterative step. Now to start our method we need an initial point, we are going to use the same one as we did with Steepest Descent (8,8). \u00a0With these values we calculate our Hessian and Gradient which gives us the following. \"ScreenWe now take the inverse of the Hessian and then find our next point. The iterative equation is listed below as well as the output.<\/p>\"Screen<\/a><\/p>Our new point was a considerable decrease from our starting point. We repeat the above steps until we reach our stopping conditions which I set as our normal tolerance limits. I allowed the method to iterate until these conditions were met. The steps are outlined in the plot below.<\/p>\"Screen<\/a><\/p>The graph above looks similar to our dynamic steepest descent. As you can see the method was very direct. Taking only 5 iterations our method produces a minimum of (0.9987,0.4987). This is pretty much dead on to the actual minimum of our function. Newton Raphson makes quick work of the minimization. Next post we will look at the limitations of this method. Code below.<\/p>-Marcello<\/p>\n

\n\n%newton raphson in  dimensions\n%f(x,y) =  x^2 -x+cos(y+x)+y^2\n\nx=zeros(2,7);\nz=zeros(1,7);\n\nx(1,1)=8; %initial guess\nx(2,1)=8;\n\n\ntol(1)=1;\ntol(2)=2;\n\ni=2;\n\n\nwhile tol(1) >0.0001 && tol(2) > 0.0001 %stop conditions\n\n    %gradients\n    dx1 = -1+2*x(1,i-1)-sin(x(1,i-1)+x(2,i-1)); %gradient dx\n    dx2 = 2*x(2,i-1) - sin(x(1,i-1)+x(2,i-1)); %gradient dy\n\n    g=[dx1,dx2]';%gradient matrix\n    \n    %hessian\n    ddx1= 2 - cos(x(1,i-1)+x(2,i-1)); % sames as ddx2\n    dx1dx2= -cos(x(1,i-1)+x(2,i-1)); % same as dx2dx1\n\n    h =[ddx1 dx1dx2;dx1dx2,ddx1]; %hessian matrix\n    \n    x(:,i) = x(:,i-1)-hg;\n    \n    \n    tol(1) = abs(x(1,i)-x(1,i-1)); %tolerance calc\n    tol(2) = abs(x(2,i)-x(2,i-1));\n\n    z(i) =x(1,i)^2 -x(1,i)+cos(x(2,i)+x(1,i))+x(2,i)^2; % function eval\n\n    i=i+1;\nend\n\n\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Last post we got an idea of how Newton-Raphson works (and how similar it is to the one dimensional version). Here we will explore step by step how the algorithm works and how quickly it arrives to our minimum. \u00a0We will be using the same function as before so we can compare how quickly the… <\/p>\n
Read more Gradient Search Methods: Newton-Raphson Method Part 2<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,5,2],"tags":[],"class_list":{"0":"post-181","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-allposts","7":"category-gsm","8":"category-opt","9":"entry"},"_links":{"self":[{"href":"https:\/\/marcelloricottone.com\/blog\/wp-json\/wp\/v2\/posts\/181","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/marcelloricottone.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/marcelloricottone.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/marcelloricottone.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/marcelloricottone.com\/blog\/wp-json\/wp\/v2\/comments?post=181"}],"version-history":[{"count":1,"href":"https:\/\/marcelloricottone.com\/blog\/wp-json\/wp\/v2\/posts\/181\/revisions"}],"predecessor-version":[{"id":288,"href":"https:\/\/marcelloricottone.com\/blog\/wp-json\/wp\/v2\/posts\/181\/revisions\/288"}],"wp:attachment":[{"href":"https:\/\/marcelloricottone.com\/blog\/wp-json\/wp\/v2\/media?parent=181"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/marcelloricottone.com\/blog\/wp-json\/wp\/v2\/categories?post=181"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/marcelloricottone.com\/blog\/wp-json\/wp\/v2\/tags?post=181"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}