\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{\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\sig{\sigma}

\begin{document}
\noindent {\Large AMATH/MATH 516 \hfill \\ Problem Set 6}
\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
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 described below
and the non-monotone backtracking line search. (if you can't get the non-monotone line search
working, just use Weak Wolf, see part (b) below).
\begin{quote}
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}
\end{quote}
\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. Note that Weak Wolfe is essential here.
\end{enumerate}

\item
We return to the nonlinear least squares problem, but now with box constraints:
$$
\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.
We consider two cases. In the first $B=\R^7$ as before while in the second
\[
B=\{x\in\R^7\, :\, -5\le x_i\le 5,\ i=1,2,\dots,7\}.
\]
\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 constrained problem using the Gradient Projection Algorithm with the 
backtracking line search and the search
direction given by
\[
d^{k+1}:=
\begin{cases}
P_B(x^{k+1}-\sig_k \nabla f(x^{k+1}))-x^{k+1},&\mbox{if $(s^k)^Ty^k> 0.001$,}\\
P_B(x^{k+1}-\nabla  f(x^{k+1}))-x^{k+1},&\mbox{otherwise,}
\end{cases}
\]
where $\sig_k=1/\|\nabla  f(x^{k+1})\|$ and  $\sig_k:=(s^k)^Ty^k/(y^k)^Ty^k$. Does the Barzilai-Borwein scaling improve
performance over vanilla steepest descent?
\item
Develop your own method to solve the constrained problem based on exterior penalization
using the objective function
\[
f_\alpha(x):=f(x)+\frac{\alpha}{2}\mathrm{dist}_2^2(x|\, B).
\]
How should $\alpha$ be updated? You might try the method in Corollary 8.1.1.1 of the
course notes.
\item
Develop your own method to solve the constrained problem based on a log-barrier method
for the constraints:
\[
f_t(x):=f(x)+t\sum_{j=1}^7\ln(5+x_j)(5-x_j)\ .
\]
Use the ideas developed in previous homeworks if you wish.
%Can central path ideas be used to tell you how fast the barrier parameter $t$ can be taken to zero?
\end{enumerate}


\end{enumerate}
\end{document}
