\documentstyle[12pt]{article}
\begin{document}
\begin{center}

{\large\bf C\&O 367 \\ 
Assignment 1 
}
\end{center}
\begin{flushleft}
{\large  Due on Tuesday, Feb. 2,~~~~   Instructor H. Wolkowicz
}

\bigskip
----------------------------------\\
{\bf Notes:}
\begin{description}
\item
Questions and comments can  be posed on the newsgroup uw.co.co367.
\end{description}
----------------------------------\\
\end{flushleft}

\begin{enumerate}
\item
{\bf MATLAB}
\begin{enumerate}
\item
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
\begin{center}
help optim
\end{center}
You will see a list of the optimization functions that are available
with the optimization toolkit. 
\item
Now try the command
\begin{center}
optdemo
\end{center}
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.
\item
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.
\begin{enumerate}
\item
(5 marks)
Submit a contour plot of the banana function for variable values between
$-4,+4.$
\item
(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.)
\end{enumerate}
\end{enumerate}
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.

\item
(15 marks)
Classify the following matrices according to whether they are positive
or negative definite or semidefinite or indefinite:
\begin{enumerate}
\item
\[
\left(
\begin{array}{rrr}
9 & 0 & 0\\
0 & 4 & 0\\
0 & 0 & 5
\end{array}
\right).
\]
\item
\[
\left(
\begin{array}{rrr}
 1 & 0 & 0\\
0 & -9 & 0\\
0 & 0 & -2
\end{array}
\right).
\]
\item
\[
\left(
\begin{array}{rrr}
-1 & 0 & 0\\
0 & -8 & 0\\
0 & 0 & -5
\end{array}
\right).
\]
\item
\[
\left(
\begin{array}{rrr}
   14  & 11  & 15\\
    11 &   9  & 12\\
    15 &  12  & 18
\end{array}
\right).
\]
\item
\[
\left(
\begin{array}{rrr}
3 & 1 & 2\\
1 & 5 & 3\\
2 & 3 & 7
\end{array}
\right).
\]
\item
\[
\left(
\begin{array}{rrr}
-4 & 0 & 1\\
0 & -3 & 2\\
1 & 2 & -5
\end{array}
\right).
\]
\item
\[
\left(
\begin{array}{rrr}
2 & -4 & 0\\
-4 & 8 & 0\\
0 & 0 & -3
\end{array}
\right).
\]
\end{enumerate}
\item
(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:
\begin{enumerate}
\item
\[  f(x_1,x_2) = x_1^3 + x_2^3 - 3x_1 - 12 x_2 + 20.
\]
\item
\[  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.
\]
\item
\[  f(x_1,x_2,x_3) = x_1^2 + x_2^2 + x_3^2   - 4x_1 x_2.
\]
\item
\[  f(x_1,x_2) = x_1^4 + x_2^4 - x_1^2 - x_2^2 + 1.
\]
\item
\[  f(x_1,x_2) = 12x_1^3  -36x_1x_2 -2x_2^3 +9x_2^2 - 72 x_1 + 60x_2 +5.
\]
\end{enumerate}
\item
(10 marks)
(Text: Problem 16, page 33)
\begin{enumerate}
\item
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.
\item
Determine the nature of the critical points of this function for all
values of $a$.
\end{enumerate}
\item
(15 marks) 
(Text: Problem 31, page 36) 
\begin{enumerate}
\item
Let $A$ be an $n \times n$ symmetric matrix. Diagonalize $A$ to show
that (the Raleigh quotient)
\[
\frac{x^tAx}{||x||^2}
\]
is greater than or equal to the smallest eigenvalue of $A$ for all $x
\neq 0$ in $\Re^n$.
\item
\label{small}
Show that the quadratic form $Q_A(x) = x^tAx$ is coercive if and only if
$A$ is positive definite.
\item Conclude from \ref{small} that if 
\[ f(x) = a + b^tx + \frac 12 x^t A x
\]
is any quadratic function where $a \in \Re,~ b \in \Re^n$ and $A$ is an
$n \times n$ symmetric matrix, then $f(x)$ is coercive if and only if
$A$ is positive definite.
\end{enumerate}
\item
(15 marks)
(Text: Problem 3, page 77)\\
A {\em 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.
\begin{enumerate}
\item
\label{quad}
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.$
\item
Compute the gradient $\nabla f(x)$ and Hessian $\nabla^2 f(x)$ of the
quadratic function in \ref{quad} and express these in terms of $a,b,A.$
\item
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).$
\end{enumerate}
\item
(15 marks)
Find the gradient and Hessian of
\[ f(x) = 100(x_2-x_1^2)^2+(1-x_1)^2.   \]
Verify that $x^*=(1,1)^T$ is the minimizer.
Show that the Hessian $H(x)$
is singular if and only if $x$ satisfies the condition
\[  x_2-x_1^2=0.005.  \]
Hence show that $H(x)$ is positive definite for all $x$ such that $f(x)
< 0.0025.$

\end{enumerate}
\end{document}