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

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

\bigskip
----------------------------------\\
{\bf Notes:}
\begin{enumerate}
\item
Please explain your answers and proofs carefully. A yes
or no does not constitute a valid answer; nor does a numerical value
with no explanation constitute a valid answer.
\item
Please pick up your copy of the survey paper on unconstrained
optimization at the zerox room on the fifth floor of MC.
\item
Questions and comments can  be posed on the newsgroup uw.co.co367.
\end{enumerate}
----------------------------------\\
\end{flushleft}

\begin{enumerate}
\item
{\bf MATLAB}
\begin{enumerate}
\item
\begin{enumerate}
\item
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 will demonstrate 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
Submit a contour plot of the banana function for variable values between
$-4,+4.$
\item
How many iterations did the minimization take for: steepest descent; simplex
search; Broyden-Fletcher-Golfarb-Shanno; Davidon-Fletcher-Powell;
Levenberg-Marquardt? (Please specify which line search you used.)
\item
Write a program that minimizes the banana function using steepest
descent but reduces the objective value that was obtained by optdemo by
at least half. (Hint: 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 toolbox; cd optim. In particular, there is an m-file
called bandemo.m. You will also need to change the options variable
before the minimization function is called.
In matlab, enter ~~~help foptions.)
\end{enumerate}
\end{enumerate}
\end{enumerate}

\item
(Text: Problem 2, page 31)\\
Classify the following matrices according to whether they are positive
or negative definite or semidefinite or indefinite:
\begin{enumerate}
\item
\[
\left(
\begin{array}{rrr}
1 & 0 & 0\\
0 & 3 & 0\\
0 & 0 & 5
\end{array}
\right).
\]
\item
\[
\left(
\begin{array}{rrr}
-1 & 0 & 0\\
0 & -3 & 0\\
0 & 0 & -2
\end{array}
\right).
\]
\item
\[
\left(
\begin{array}{rrr}
7 & 0 & 0\\
0 & -8 & 0\\
0 & 0 & 5
\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
(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
(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
(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
(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
Show that a quadratic function $f(x)$ of $n$ variables is convex if and
only if the corresponding $n \times n$ symmetric
matrix $A$ is positive semidefinite, and is strictly convex if $A$ is
positive definite.
\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}
\end{enumerate}
\end{document}