Each question is worth 20 points.

1. The problem

   has a saddle point at the origin and two global minima at ±(1,-1). We investigate solving this problem using Newton’s method.

   1. Let x⁰ be the starting point and x¹,x²,… be the subsequent iterates. Show that x^k is on the line x₁ + x₂ = 0 for k ≥ 1, for any x⁰, provided (x₁ - x₂)²≠4∕3.
   2. Show that if we take a steplength equal to one then the algorithm converges cubically to the saddle point if |x₁ - x₂| < .
   3. Show that if we take a steplength equal to one then the algorithm converges to a global minimum if |x₁ - x₂|≥ 1.
2. Consider using a quasi-Newton approach to the problem from question 1: if the Hessian is not positive definite, approximate the inverse of the Hessian by the matrix

   Assume the algorithm starts from a nonzero point with an indefinite Hessian. Show that the algorithm eventually obtains a point with a positive definite Hessian. What can you then conclude from question 1?

3. Let (NLP) denote the nonlinear programming problem

   This problem has optimal solution x = (0,-20). One penalty function approach to this problem is to use a penalty parameter μ and solve

   

   Use AMPL and a solver on the NEOS server (or another package) to solve this problem for various values of μ. Show empirically that increasing μ by a factor of ten results in a solution to (NLP) with about one more digit of accuracy.