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

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

\bigskip
\end{flushleft}

\begin{enumerate}
\item
Compute the first three terms of Steepest Descent for the function
\[
        f(x,y) = 4x^2 - 4xy + 2y^2,
\]
using the starting point $(2,3)$.
\item
Consider the function $f(t) = 1 - t e^{-t}$.  Find the acceptable range
of $t$
in the Goldstein-Wolfe-Armijo conditions for $ \rho = .1$ and
$\sigma = .25$.
\item
Let $\{ v_1, v_2, \ldots, v_n \}$ denote the eigenvectors of an $n
\times n$ symmetric positive definite matrix $Q$, and consider the
problem
\[
        \min_x  f(x) = \frac 12 x^T Q x - b^T x.
\]
For initial point $x_0$ let $x_k$ be generated by Steepest Descent with
exact line search.  Let $\nabla f(x_0) = \sum_j \alpha_j v_j$, and let $M
=
\mbox{span}\,\{v_i \mid \alpha_i \neq 0\}$.  Show that $\nabla f(x_k) \in M$ for
all
$k$.  Find the rate of convergence for the sequence $x_k$.

\item
Let $f \in C^2$ and let the sequence $x_k$
be defined by Newton's Method, that is
$x_{k+1} = x_k + v_k$ where $v_k$ solves
\begin{equation} \label{e:newton}
        \nabla^2 f(x_k) v_k = -\nabla f(x_k).
\end{equation}
\begin{enumerate}
\item
Show that if $\nabla^2 f(x_k)$ is positive definite,
then $v_k$ is a direction of descent
for $f$ at $x_k$.
\item
Show, by finding examples, that $v_k$ may or may not be a direction of
descent when $\nabla^2 f(x_k)$ is not positive definite.
\item
Find an example showing that even if the Newton direction $v_k$ is a
direction of descent, we may have $f(x_{k+1}) > f(x_k)$.
\end{enumerate}
\item
Consider Rosenbrock's test function
\[
f(x) = 100(x_2-x_1^2)^2+(1-x_1)^2.
\]
Find the minimum point for this function
from the initial estimate $x^{(1)} = (-1~1)^T$.
Use the matlab package and use the following three methods:
\begin{enumerate}
\item
Newton with approximate linesearch,
\item
quasi-Newton with BFGS update with approximate linesearch,
\item
steepest descent with exact line search.
\end{enumerate}
You can experiment with different approximate linesearches, e.g.
backtracking with initial steplength of 1. Or you can use matlab to do
the exact line search for you.
(Please include well-documented programs.)

\end{enumerate}
\end{document}