C&O 367, 2001
Assignment 1

Due on Thursday, Jan. 18 (at start of class)
Instructor H. Wolkowicz

-----------------
Notes:

Questions and comments can be posed on the newsgroup uw.co.co367.

-----------------

1. MATLAB
   1. Matlab appears to be on all the Solaris systems in the undergrad environment, e.g. hermite and magnus. Enter the command matlab to start up the matlab session. Then enter
      help optim
      You will see a list of the optimization functions that are available with the optimization toolkit.
   2. Now try the command
      optdemo
      This will bring up a menu. You can try the four choices. The first choice is a tutorial. This demonstrates several of the optimization functions.
   3. The second choice in the optdemo is the minimization of the banana function or Rosenbrock's function. This is a classical example of a function with a narrow valley that exhibits ``very'' slow convergence for steepest descent type methods. Try out several methods to minimize this function.
      1. (5 marks) Submit a contour plot of the banana function for variable values between $-4,+4.$
      2. (10 marks) How many function evaluations did the minimization take for: steepest descent; simplex search; Broyden-Fletcher-Golfarb-Shanno; Davidon-Fletcher-Powell; Levenberg-Marquardt? (Please specify the line search you used.)
   Note: You can modify the matlab programs. You can see what the matlab routines are doing by looking at the matlab m-files. To do this change directory using: cd /software; cd matlab; cd distribution; cd toolbox; cd optim. In particular, there is an m-file called bandemo.m.

2. (15 marks) Classify the following matrices according to whether they are positive or negative definite or semidefinite or indefinite:
   1. 
      
      $$\left( \begin{array}{rrr} 9 & 0 & 0\\ 0 & 4 & 0\\ 0 & 0 & 5 \end{array}\right).$$
      
      

   2. 
      
      $$\left( \begin{array}{rrr} 1 & 0 & 0\\ 0 & -9 & 0\\ 0 & 0 & -2 \end{array}\right).$$
      
      

   3. 
      
      $$\left( \begin{array}{rrr} -1 & 0 & 0\\ 0 & -8 & 0\\ 0 & 0 & -5 \end{array}\right).$$
      
      

   4. 
      
      $$\left( \begin{array}{rrr} 14 & 11 & 15\\ 11 & 9 & 12\\ 15 & 12 & 18 \end{array}\right).$$
      
      

   5. 
      
      $$\left( \begin{array}{rrr} 3 & 1 & 2\\ 1 & 5 & 3\\ 2 & 3 & 7 \end{array}\right).$$
      
      

   6. 
      
      $$\left( \begin{array}{rrr} -4 & 0 & 1\\ 0 & -3 & 2\\ 1 & 2 & -5 \end{array}\right).$$
      
      

   7. 
      
      $$\left( \begin{array}{rrr} 2 & -4 & 0\\ -4 & 8 & 0\\ 0 & 0 & -3 \end{array}\right).$$
      
      

3. (20 marks) (Text: Problem 7, page 32)
   Use the principal minor criteria to determine (if possible) the nature of the critical points of the following functions:
   1. 
      
      $$f(x_1,x_2) = x_1^3 + x_2^3 - 3x_1 - 12 x_2 + 20.$$
      
      

   2. 
      
      $$f(x_1,x_2,x_3) = 3x_1^2 + 2x_2^2 +2x_3^2+ 2x_1x_2 + 2x_2x_3 + 2x_1x_3.$$
      
      

   3. 
      
      $$f(x_1,x_2,x_3) = x_1^2 + x_2^2 + x_3^2 - 4x_1 x_2.$$
      
      

   4. 
      
      $$f(x_1,x_2) = x_1^4 + x_2^4 - x_1^2 - x_2^2 + 1.$$
      
      

   5. 
      
      $$f(x_1,x_2) = 12x_1^3 -36x_1x_2 -2x_2^3 +9x_2^2 - 72 x_1 + 60x_2 +5.$$
      
      

4. (10 marks) (Text: Problem 16, page 33)
   1. Show that no matter what value of $a$ is chosen, the function
      
      $$f(x_1,x_2) = x_1^3 -3ax_1x_2 + x_2^3$$
      
      
      has no global maximizers.
   2. Determine the nature of the critical points of this function for all values of $a$.
5. (15 marks) (Text: Problem 3, page 77)
   A quadratic function in $n$ variables is any function defined on $\Re^n$ which can be expressed in the form
   
   $$f(x) = a + b^tx + x^tAx,$$
   
   
   where $a \in \Re,~b \in \Re^n,$ and $A$ is an $n \times n$ symmetric matrix.
   1. Show that the function $f(x)$ defined on $\Re^2$ by
      
      $$f(x_1,x_2) = (x_1 -x_2)^2 + (x_1 +2x_2+1)^2 - 8x_1x_2$$
      
      
      is a quadratic function of two variables by finding the appropriate $a,b,A.$
   2. Compute the gradient $\nabla f(x)$ and Hessian $\nabla^2 f(x)$ of the quadratic function in 5a and express these in terms of $a,b,A.$
   3. If $f(x)$ is a quadratic function of $n$ variables such that the corresponding matrix $A$ is positive definite, show that $0 = 2Ax +b$ has a unique solution and that this solution is the strict global minimizer of $f(x).$