\hfill \thepage} %} \input{tcilatex} \begin{document} \vspace{1pt}Newton's Method Author: Robert Beezer History: 1999/03/31\qquad First version. \ For \ Chong/Zak Chapter 9 \vspace{1pt} \subsubsection{Newton's Method} \subsubsection{\protect\vspace{1pt}} \begin{enumerate} \item Suppose \ $f:R^{n}\rightarrow R$ \ has two derivatives (gradient and Hessian). \ Then the Taylor series expansion, about $x^{(k)}$ \ to second-order is \[ g(x)=f\left( x^{(k)}\right) +\nabla f\left( x^{(k)}\right) \left( x-x^{(k)}\right) +\frac{1}{2}\left( x-x^{(k)}\right) F\left( x^{(k)}\right) \left( x-x^{(k)}\right) \approx f\left( x\right) \] Use this to approximate the curve given by \ $f$.\bigskip \item Minimizing \ $g(x)$ \ proceeds by setting its gradient to the zero vector and solving, to establish critical points: \[ \nabla g(x)=\nabla f\left( x^{(k)}\right) +F\left( x^{(k)}\right) \left( x-x^{(k)}\right) \] \[ \nabla g(x)=0\Rightarrow x=x^{(k)}-\left( F\left( x^{(k)}\right) \right) ^{-1}\nabla f\left( x^{(k)}\right) \] So iteratively, we use the recurrence \[ x^{\left( k+1\right) }=x^{(k)}-\left( F\left( x^{(k)}\right) \right) ^{-1}\nabla f\left( x^{(k)}\right) \] \bigskip \item This should look a lot like the single variable case, when the matrix inverse is viewed as ``being in the denominator.'' \ Notice that we have given little thought to whether or not the critical points are actually minimizers (of the quadratic approximation, or the original function). \end{enumerate} \vspace{1pt} \vspace{1pt} \subsubsection{Example} \vspace{1pt} \begin{enumerate} \item (Peressini/Sullivan/Uhl \ Exercise 3.4) \ Minimize \ $% f(x_{1},x_{2})=2x_{1}^{4}+x_{2}^{2}-4x_{1}x_{2}+5x_{2}$ \ starting at \ $% x^{(0)}=(0,0)$. \ $g(x_{1},x_{2})=\left( \begin{array}{r} 8x_{1}^{3}-4x_{2} \\ 2x_{2}-4x_{1}+5 \end{array} \right) $ $F(x_{1},x_{2})=\left( \begin{array}{rr} 24x_{1}^{2} & -4 \\ -4 & 2 \end{array} \right) $ $\allowbreak $ $t(x_{1},x_{2})=\left( \begin{array}{r} x_{1} \\ x_{2} \end{array} \right) -\left( \begin{array}{cc} \frac{1}{8\left( 3x_{1}^{2}-1\right) } & \frac{1}{4\left( 3x_{1}^{2}-1\right) } \\ \frac{1}{4\left( 3x_{1}^{2}-1\right) } & \frac{3}{2}\frac{x_{1}^{2}}{% 3x_{1}^{2}-1} \end{array} \right) g(x_{1},x_{2})$ \ the gruesome matrix is the general inverse of the Hessian. \item First iteration: $\ F(0,0)=\allowbreak \left( \begin{array}{cc} 0 & -4.0 \\ -4.0 & 2.0 \end{array} \right) $, \ $t(0,0)\allowbreak \allowbreak =\allowbreak \left( \begin{array}{c} 1.\,\allowbreak 25 \\ 0 \end{array} \right) \allowbreak $, \ $f(1.25,0)=\allowbreak 4.\,\allowbreak 882\,812\,5$ \item Second iteration: $\ F(1.25,0)=\allowbreak \left( \begin{array}{cc} 37.\,\allowbreak 5 & -4.0 \\ -4.0 & 2.0 \end{array} \right) $, \ $t(1.25,0)\allowbreak \allowbreak \allowbreak =\allowbreak \left( \begin{array}{c} .\,\allowbreak 720\,338\,983\,\allowbreak 1 \\ -1.\,\allowbreak 059\,322\,034 \end{array} \right) \allowbreak $, \ $f(.\,\allowbreak 720\,338\,983\,\allowbreak 1,-1.\,\allowbreak 059\,322\,034)=\allowbreak -.\,\allowbreak 583\,673\,138\,\allowbreak 1$ \item Third iteration: $\ F(.\,\allowbreak 720\,338\,983\,\allowbreak 1,-1.\,\allowbreak 059\,322\,034)\allowbreak =\allowbreak \left( \begin{array}{cc} 12.\,\allowbreak 453\,318\,01 & -4.0 \\ -4.0 & 2.0 \end{array} \right) \allowbreak $, \ $t(.\,\allowbreak 720\,338\,983\,\allowbreak 1,-1.\,\allowbreak 059\,322\,034)\allowbreak \allowbreak \allowbreak =\allowbreak \left( \begin{array}{c} -.\,\allowbreak 902\,606\,333\,\allowbreak 4 \\ -4.\,\allowbreak 305\,212\,667 \end{array} \right) \allowbreak $, \ \ $f(-.\,\allowbreak 902\,606\,333\,\allowbreak 4,-4.\,\allowbreak 305\,212\,667)=\allowbreak -17.\,\allowbreak 207\,389\,81\allowbreak $ \item Fourth iteration: $\ F(-.\,\allowbreak 902\,606\,333\,\allowbreak 4,-4.\,\allowbreak 305\,212\,667)=\allowbreak \left( \begin{array}{cc} 19.\,\allowbreak 552\,756\,63 & -4.0 \\ -4.0 & 2.0 \end{array} \right) \allowbreak $, \ $t(-.\,\allowbreak 902\,606\,333\,\allowbreak 4,-4.\,\allowbreak 305\,212\,667)\allowbreak \allowbreak \allowbreak =\allowbreak \left( \begin{array}{c} -1.\,\allowbreak 884\,020\,297 \\ -6.\,\allowbreak 268\,040\,593 \end{array} \right) \allowbreak $, \ \ $f(-1.\,\allowbreak 884\,020\,297,-6.\,\allowbreak 268\,040\,593)\allowbreak =\allowbreak -14.\,\allowbreak 089\,971\,24\allowbreak $ \item From here Newton's method continues towards the true zero of the gradient at \ $(-5.26,-1.38)$. \ A couple more iterations yield pretty good accuracy. \ This yields a minimum (confirmed graphically) of $% f(-1.380408,-5.260817)=\allowbreak -20.\,\allowbreak 414\,1\allowbreak $. \end{enumerate} \vspace{1pt} Problem: \ Minimize \ $x_{1}^{4}+2x_{1}^{2}x_{2}^{2}+x_{2}^{4}$ \ by applying four iterations of Newton's Method starting at \ $(1,2)$. Can you now surmise the minimizer, and prove that it is really a minimum of the function? \end{document} %%%%%%%%%%%%%%%%%%%%%%% End /document/chap9.tex %%%%%%%%%%%%%%%%%%%%%%%