\documentclass{amsart}
%\input macros

\pagestyle{empty}
\textwidth 7.5in
\textheight 9.6in
\oddsidemargin -0.5in
\evensidemargin -0.5in
\topmargin -0.5in

\usepackage{amsmath,epsfig,amssymb}

\newcommand{\eps}{\epsilon}
\newcommand{\lam}{\lambda}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Rn}{\R^n}
\newcommand{\half}{\frac{1}{2}}
\newcommand{\norm}[1]{\left\Vert #1 \right\Vert}
\newcommand{\map}[3]{#1:#2\rightarrow #3}
\newcommand{\grad}{\nabla}

\def\uball{\mathbb{B}}

\begin{document}
\noindent {\Large AMATH/MATH 516 \hfill Problem Set 4\\ FIRST PROGRAMMING ASSIGNMENT}
\medskip

%\noindent
%Due Monday, May 1.
\medskip

\begin{enumerate}
%\item  
%Use the conjugate gradient algorithm to determine the polynomial of degree 6  that best fits the data
%$$
%y_i=\sin x_i \ , \mbox{   with  } x_i:=-1+{i\over 5} \mbox{  for  }
%i=0.1.\cdots ,10,
%$$
%in the least squares sense. Take $p^0=0$.
%Run the algorithm as an iterative procedure terminating when the magnitude of the 
%gradient of the least squares objective is less than $10^{-12}$. Explain what you observe.
%In particular, compare the theoretical finite convergence result with what you actually observe.

\item
Apply the steepest descent algorithm with backtracking to minimize the Rosenbrock function
(see website for Matlab files for the Rosenbrock function).
In this algorithm choose the steepest descent search direction in the following three ways:
\begin{enumerate}
\item $d^k:=-\nabla f(x^k)/\norm{\nabla f(x^k)}$.
\item $d^k:=-\nabla f(x^k)/\theta_k$, where $\theta_k:=(s^k)^Ty^k/(s^k)^Ts^k$ whenever
$(s^k)^Ty^k>0$ and $\theta_k:=\norm{\nabla f(x^k)}$ otherwise, with $s^k:=x^k-x^{k-1}$ and 
$y^k:=\nabla f(x^k)-\nabla f(x^{k-1})$ (take $\theta_0:=\norm{\nabla f(x^k)}$).
\item $d^k:=-\nabla f(x^k)/\theta_k$, where $\theta_k:=(y^k)^Ty^k/(y^k)^Ts^k$ whenever
$(s^k)^Ty^k>0$ and $\theta_k:=\norm{\nabla f(x^k)}$ otherwise, with $s^k:=x^k-x^{k-1}$ and 
$y^k:=\nabla f(x^k)-\nabla f(x^{k-1})$ (take $\theta_0:=\norm{\nabla f(x^k)}$).
\end{enumerate}

\item
Apply the steepest descent algorithm with weak Wolfe line search to minimize the Rosenbrock function
(see website for Matlab files for the Rosenbrock function).
In this algorithm choose the steepest descent search direction in the following three ways:
\begin{enumerate}
\item $d^k:=-\nabla f(x^k)/\norm{\nabla f(x^k)}$.
\item $d^k:=-\nabla f(x^k)/\theta_k$, where $\theta_k:=(s^k)^Ty^k/(s^k)^Ts^k$ whenever
$(s^k)^Ty^k>0$ and $\theta_k:=\norm{\nabla f(x^k)}$ otherwise, with $s^k:=x^k-x^{k-1}$ and 
$y^k:=\nabla f(x^k)-\nabla f(x^{k-1})$ (take $\theta_0:=\norm{\nabla f(x^k)}$).
\item $d^k:=-\nabla f(x^k)/\theta_k$, where $\theta_k:=(y^k)^Ty^k/(y^k)^Ts^k$ whenever
$(s^k)^Ty^k>0$ and $\theta_k:=\norm{\nabla f(x^k)}$ otherwise, with $s^k:=x^k-x^{k-1}$ and 
$y^k:=\nabla f(x^k)-\nabla f(x^{k-1})$ (take $\theta_0:=\norm{\nabla f(x^k)}$).
\end{enumerate}



\item Consider the nonlinear least squares problem
$$
\min_{\R^7}f(x):=\half \norm{g(x)}^2_2
$$
where matlab function files for the function $\map{g}{\R^7}{\R^8}$, 
its Jacobian, and its Hessians  are available on the course website.

\noindent \begin{enumerate}
\item Solve this problem using steepest descent with backtracking 
(or weak Wolfe) line search
%the dog-leg method with $H_k=\grad^2f(x_k)$. 
Choose your own
iteration parameters and stopping criteria. However, if you reduce
the norm of the gradient to less than $10^{-12}$ then you have done
well and your procedure should terminate.
\item Solve this problem with the Levenberg-Marquardt method for
choosing the search direction and a backtracking line search to choosing the
step-length. In the Levenberg-Marquardt method, the search
directions $d^k$ are chosen to solve the subproblems
$$
\min_{d^k\in \Rn} \half \norm{g(x^k)+g'(x^k)d}_2^2+\frac{\alpha_k}{2} 
\norm{d}_2^2\ .
$$
Show that these search directions are directions of strict descent
for $f$ at $x_k$ as long as $\grad f(x_k)\neq 0$.
Solve these subproblems with the conjugate gradient algorithm.
The $\alpha_k$'s used to adjust for the magnitude of the $d^k$'s.
For example, one could take
$$
\alpha_0:=10+\half \norm{g(x^0)}_2^2
$$
and
$$
\alpha_{k+1}=\left\{ \begin{array}{ll}
\alpha_k+10\ , &\mbox{ if  } \lambda_k< 10^{-3} ,\\
\alpha_k\ ,&\mbox{ if  } 10^{-3}\le \lambda_k\le 1 ,\\
\alpha_k/2\ ,&\mbox{ if  } \lambda_k>1 .
\end{array}\right.\ ,
$$
where $\lambda_k$ is the step length.
Is the role of the $\alpha_k$'s significant and, if so, why?
Is this a reasonable rule for updating the $\alpha_k$'s and if so
why ? Can you suggest a better alternative? If you can, then use
that method in your program and justify its use.
\end{enumerate}
\medskip

Initialize the iterations at $x^0=0$. Choose your own line search
parameters and termination criteria. Again, if you are able to attain
$\norm{\grad f(x)}\leq 10^{-12}$, then you have done very well.
%\end{enumerate}
\item  
Newton's method for minimizing a function
$\map{f}{\Rn}{\R}$ is just Newton's method applied to the
equation $\nabla f(x)=0$. Thus, the Newton direction ignores
the underlying minimization problem. For this reason the Newton direction,
if it exists, may not be a direction of descent for the function, or
even if it is a direction of descent, it may require an excessive number
of steps in a line search procedure to induce descent. Even so, the full
Newton step may still be a very good choice of direction even if it
may occasionally increase the value of the objective function. For this
reason a number of authors have propose {\it non--monotone} line
search procedures in order to increase the likelihood of accepting
a Newton (or Newton like) step even if it may occasionally increase
the value of the objective. In this problem, we consider one such proposal.

Let $p$ be some positive integer (usually $p=3$ or $p=4$). Suppose
that $x^0\in\Rn$ is given and define $x^{-\ell}=x^0$ for
$\ell = 1,2,\dots,p-1$. Consider the
following backtracking procedure for choosing a step length.
\medskip

\noindent
\underline{Non--Monotone Backtracking:} $0<c<1$ and $0<\gamma <1$

\noindent
Let $d^k\in\Rn$ be such that $\nabla f(x^k)^Td^k<0$. Set
\[
\begin{array}{lll}\lam_k =&\max &\gamma^s\\
&\mbox{subject to}&s=0,1,2,\dots\\
&&f(x^k+\gamma^sd^k)\le\left[\displaystyle\max_{\ell =0,1,\dots ,p-1}
f(x^{k-\ell })\right]+c\gamma^s\nabla f(x^k)^Td^k\ .
\end{array}
\]
Observe that this line search procedure does not guarantee that
$x^{k+1}=x^k+\lam_kd^k$ satisfies $f(x^{k+1})<f(x^k)$.
\begin{enumerate}
\item Show that the sequence $\{ f^{\max}_k\}$ given by
$$f^{\max}_k=\displaystyle\max_{\ell =0,1,\dots ,p-1}
f(x^{k-\ell })$$ for $k=0,1,...$ is non-increasing.
\item 
Show by induction that the sequence $\{ f^{\max}_k\}$
is {\bf $p$--step strictly} decreasing
sequence, i.e. $f^{\max}_{k+p}<f^{\max}_k$ for $k=0,1,...$.
\item 
For each $k=0,1,\dots$, define $m(k)$ to be the smallest integer
in the set $\{ k,k-1,\dots,k-p+1\}$ such that
$$
f(x^{m(k)})=\max_{\ell =0,1,\dots ,p-1}f(x^{k-\ell }),
$$
so that $f^{\max}_k=f(x^{m(k)})$.
By paralleling the proof of Theorem 2.1.1, prove the following result.
\bigskip

\noindent
%\begin{quote}
{\bf Theorem} Suppose $f\, :\, \Rn\rightarrow \R$ is continuously
differentiable with $\nabla f$ Lipschitz continuous on the closed
convex hull of the set $\{ x\, :\, f(x)\le f(x^0)\}+\delta\uball$
where $\delta > 0$ and $x^0\in \Rn$ are given. Let $\{x^k\}$ be a
sequence of iterates given by the following algorithm:
%\medskip
%
%%\noindent
%%\underline{Caution}: I haven't proven this result yet, so the statement
%%may need tweaking. Once I get the time to prove it, I'll give you an update.
%%\medskip
%
\begin{quote}
\noindent
\underline{Non-Monotone Descent Algorithm}
\begin{enumerate}
\item[Step 1:] If $D_k\subset \{d\, :\ f'(x^k;d)<0\}$ is empty, STOP;
otherwise choose $d^k\in D_k$.
\item[Step 2:] Choose the step length $\lam_k$ by the 
non-monotone backtracking 
procedure specified above.
\item[Step 3:] Set $x^{k+1}=x^k+\lam_kd^k,\ k=k+1$, and return to Step 1.
\end{enumerate}
\end{quote}
\smallskip

If $\norm{d^k}\le \delta$ for all $k=0,1,\dots$, then one of the
following must occur:
\begin{enumerate}
\item There is a $k_0$ such that $D_{k_0}=\emptyset$.
\item $f^{\max}_k\downarrow -\infty$.
\item $f'(x^{m(k)-1};d^{m(k)-1})\rightarrow 0$.
\end{enumerate}
%\end{quote}
\bigskip

\item 
Use the Newton search direction with $d^\nu =-\nabla^2f(x^\nu )^{-1}\nabla f(x^\nu)$ 
($H_\nu:=\nabla^2f(x^\nu )$)
in conjunction with this non-monotone line search
procedure to minimize the Rosenbrock function. 
Safeguard the Newton search direction by two checks:
\begin{enumerate}
\item If $\norm{H_k^{-1}\nabla f(x_k)}\ge 100\norm{\nabla f(x_k)}$, reset $d_k=-\nabla f(x_k)$.
\item If $-\nabla f(x_k)^Td_k\le 10^{-4}\norm{\nabla f(x_k)}\norm{d_k}$,
reset $d_k=-\nabla f(x_k)$.
\end{enumerate}
Use the starting point  and
stopping criteria from the previous problem set.
Try the values 
$p=3$ and $p=4$ as suggested above. 
Compare the outcome of this numerical experiment with
those of the previous problem set.
\end{enumerate}

\item
In this problem set we revisit the nonlinear least squares problem of 
the previous problem set.
That is, we are interested solving the nonlinear least squares problem
$$
\mathcal{P}\qquad\min_{x\in B}f(x):=\half \norm{g(x)}^2_2
$$
where matlab function files for the function $\map{g}{\R^7}{\R^8}$,
its Jacobian, and its Hessians are available through the course webpage.
\medskip

\noindent
Each of the algorithms described below
is to be initiated at the point $x^0=zeros(7,1)$
with a stopping criteria of $\norm{\nabla f(x)}\leq 10^{-12}$. As part
of your output, you need to include
\begin{enumerate}
\item[(i)] a graph of the primary stopping criteria, e.g. the norm of the gradient in the unconstrained case
\item[(ii)] a graph of the function values
\item[(iii)] a graph of the magnitude of
the steps taken at each iteration
\item[(iv)] a table listing the total
number of function, gradient, and Hessian evaluations.
\end{enumerate}
Use a $\mathtt{maxit}$ in excess of $5000$.
\medskip

\begin{enumerate}
\item
Solve the problem using the safe-guarded Newton step of the previous problem
and the non-monotone backtracking line search.
\item
Solve the problem using the safe-guarded Newton step of the previous problem
and the weak Wolfe line search.
\item
Solve the problem using (inverse) BFGS updating in conjunction with the 
weak Wolfe line search.
\end{enumerate}
\end{enumerate}

\vfill\eject
\end{document}

%\item Solve this problem using the BFGS method with inverse
%updating. Initiate the line--search with backtracking and then
%check the condition for positive definiteness of the update
%(use $\beta=0.95$ (is this a good choice for $\beta$?)).
%If this condition is not satisfied, initiate at the
%current value for the step--length given by backtracking a one
%dimensional global optimization routine based on the safe--guarded
%secant method with backtracking and stopping criteria given by
%the condition for positive definiteness of the updates.  Allow the
%one--dimensional routine 3 iterations to converge. If the
%one--dimensional stopping criteria is not met after 3 iterations, then
%do not update the Hessian approximation and continue.

\vfill\eject
\end{document}
