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

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

{\bf NOTE:} Several exercises are marked: {\bf Do not hand in.}
\begin{enumerate}
\item
({\bf Do not hand in.}) 
Consider the function $f(t) = 1 - t e^{-t}$.  Find the acceptable range of $t$
in the Goldstein-Wolfe-Armijo conditions for $\rho = \sig = .1$ and $\rho = \sig =
.25$.
\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
({\bf Do not hand in.}) 
Let $\lp v_1, v_2, \ldots, v_n \rp$ denote the eigenvectors of an $n
\times n$ symmetric positive definite matrix $Q$, and consider the problem
\[
	\min_x  f(x) = \half 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 $\grad f(x_0) = \sum_j \alpha_j v_j$, and let $M =
\Span{v_i \mid \alpha_i \neq 0}$.  Show that $\grad f(x_k) \in M$ for all
$k$.  Find the rate of convergence for the sequence $x_k$.
\item
Consider the problem
\[
	\min_x  f(x,y) = 5 x^2 + 5y^2 - xy - 11x + 11y + 11.
\]
\begin{enumerate}
\item 
Find a point satisfying the first-order necessary conditions.
\item 
Show that this point is a global minimum.
\item 
What is the rate of convergence for steepest descent for this problem?
\item 
For $x_0 = (0,0)^T$, how many steepest descent iterations are necessary to ensure that
the function value is reduced to $10^{-11}$?
\end{enumerate}
\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}
	\hes f(x_k) v_k = -\grad f(x_k).
\end{equation}
\begin{enumerate}
\item
Show that if $\hes 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 $\hes 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}
The previous questions should convince you that Pure Newton is not
suitable for unconstrained optimization.  Next, we describe two
modifications of Newton's algorithm to make it more suitable.  First, we
add a linesearch so that $x_{k+1} = x_k + t_k v_k$ where $v_k$
solves (\ref{e:newton}) and $t_k$ is chosen to satisfy the
Goldstein-Wolfe-Armijo conditions.  Second, let $\delta$ be a fixed
positive constant, and for $x\in \Rn$ define $\eps(x)$ to be the smallest
positive constant such that the minimum eigenvalue of $\hes
f(x) + \eps(x) I$ is $\delta$ (where $I$ is the identify matrix). 

We define the modified Newton
direction $v_k$ by
\begin{equation} \label{e:newton2}
	\lsb \hes f(x_k) + \eps(x_k)I \rsb v_k = -\grad f(x_k)
\end{equation}
and the modified Newton Method by
\[
	x_{k+1} = x_k + t_k v_k
\]
where $t_k$ is chosen to satisfy the Goldstein-Wolfe-Armijo conditions.
\begin{enumerate}
\item
({\bf Do not hand in.}) 
Show that such a $\eps(x)$ exists.  Can you derive an explicit
expression for $\eps(x)$?
\item
({\bf Do not hand in.}) 
Show that the Modified Newton method is globally convergent.
\item
({\bf Do not hand in.}) 
Show that if $\xk$ converges to a local minimum $x^*$ for which $\hes
f(x^*)$ is positive definite and $\delta> 0$ is less than the minimum
eigenvalue of $\hes f(x^*)$, then the Modified Newton Method converges
quadratically.
\end{enumerate}
\end{enumerate}
\end{document}