Homework 3- Nonlinear equations and optimization

Written Part Due: Tuesday, March 4, 2003, 11AM
Programming Part Due: Thursday, March 6, 2003


1. Written problems chapter 5, Heath text. 5.1, 5.2, 5.3, 5.4, 5.10, 5.13.

2. Written problems chapter 6, Heath text.  6.3,  6.4, 6.8.

3. Programming Assignment.

This assignment is to write a program  to minimize a function of more than one variable. We will again experiment with making robust software, and testing each module separately. It is important to design testers that exercise all features of the code, including test cases that lead the program to (graceful) failure.

(a) Write a program that performs unsafeguarded Newton's method to find the minimum of the function

    f(x,y) = g(x^2 + a(y - b sin(c x))^2)
with a=2,b=1, and c=1.  Here, the function g(t) = e^t - 1/(1+t^2). Use your Cholesky routine from the last homework to solve the linear equations.  You should try initial guesses close and far from the solution (which is x=y=0).  With a good initial guess you should see quadratic convergence to the minimum. With a poor initial guess you should see wild behavior or termination with (graceful) failure.

(b) Add two safeguards to the program in part (a). First check that the Newton step is a descent direction (in other words, ensure that the Hessian is positive definite. If not, use the modified Cholesky decomposition. (If you have extra time you could also experiment with using the Identity matrix Hessian, which gives a method called steepest descent.) Second, you should do a line search to make sure the step you make is not crazy. You can do this as in the notes -that is, given a direction p, and a current iterate x, find a real number t so that x+t p gives a lower function value.The value t=1 is the Newton step, but far from the solution, this might be too large or too small. The algorithm for this is in the supplementary notes p. 4. Try your program on the more difficult function with a=30, b=1 and c=6, starting from the initial guess (x,y) = (3,1). Make a contour plot of the objective function showing the minimization iterates.

To Hand In:
   email: code to sen212@nyu.edu. Put all email in one tar or zip file, with all codes. Make sure your name is on top of file, even if your tar file is named using your actual name.
   hand in:  copy of code, written analysis and explanation and sample output  (for grader to use for comparison), including graphs.