\documentclass{article}

% Packages required to support encoding
\usepackage{ucs}
\usepackage[utf8x]{inputenc}

% Packages required by code


% Packages always used
\usepackage{hyperref}
\usepackage{xspace}
\usepackage[usenames,dvipsnames]{color}
\hypersetup{colorlinks=true,urlcolor=blue}

\input{homework.tex}


\begin{document} 
\hypertarget{homework_6_1}{}\section*{{Homework 6}}\label{homework_6_1}

Please answer the following questions in complete sentences in a typed manuscript and submit the solution to me in class on February 28th, 2012.

\hypertarget{problem_0_list_your_collaborators_2}{}\subsection*{{Problem 0: List your collaborators.}}\label{problem_0_list_your_collaborators_2}

Please identify anyone, whether or not they are in the class, with whom you discussed your homework. This problem is worth 1 point, but on a multiplicative scale. (Note that collaboration is not allowed on the bonus question below.)

\hypertarget{problem_1_implement_a_quasinewton_method_3}{}\subsection*{{Problem 1: Implement a Quasi-Newton method}}\label{problem_1_implement_a_quasinewton_method_3}

\begin{enumerate}%
\item Nocedal and Wright state the BFGS update to the \emph{inverse Hessian} as:

\begin{displaymath}
\mH_{k+1} = (\mI - \rho_k \vs_k \vy^T) \mH_k (\mI - \rho_k \vy_k \vs_k^T) + \rho_k \vs_k \vs_k^T.
\end{displaymath}
Describe the amount of work required for this update.


\item Create a new function called {\colorbox[rgb]{1.00,0.93,1.00}{\tt quasi\char95newton\char95bfgs\char46m}} based on {\colorbox[rgb]{1.00,0.93,1.00}{\tt newtons\char95method\char95\char49\char46m}} and implement a Quasi-Newton method with the BFGS update to the \emph{inverse Hessian}, use the Strong Wolfe line search routine from the Poblano toolbox. Make sure your function has an appropriate help description (the comments at the top of the file) and a reasonable set of parameters. \emph{There is a good chance you'{}ll use this code later in the course.} This function should record:



\end{enumerate}
\begin{itemize}%
\item number of function evaluations in iteration {\colorbox[rgb]{1.00,0.93,1.00}{\tt i}}
\item the time taken from the start until the end of iteration {\colorbox[rgb]{1.00,0.93,1.00}{\tt i}}
\item the value of the function at iteration {\colorbox[rgb]{1.00,0.93,1.00}{\tt i}}
\item the infinity norm of the gradient at iteration {\colorbox[rgb]{1.00,0.93,1.00}{\tt i}}
\item the size of the step at iteration {\colorbox[rgb]{1.00,0.93,1.00}{\tt i}}

\end{itemize}
\begin{enumerate}%
\item Modify the {\colorbox[rgb]{1.00,0.93,1.00}{\tt gradient\char95descent\char95\char49\char46m}} code to use the same line search routine.


\item I'{}ve provided a list of problems in \href{matlab/testfuncs.zip}{matlab/testfuncs.zip}.\newline Look at the file {\colorbox[rgb]{1.00,0.93,1.00}{\tt driver\char95eval\char95methods\char46m}}. It shows how to loop over all the test cases. For test case {\colorbox[rgb]{1.00,0.93,1.00}{\tt ii}}, {\colorbox[rgb]{1.00,0.93,1.00}{\tt function\char95min\char95values\char40ii\char41}} is the exact minimizer, and the code creates {\colorbox[rgb]{1.00,0.93,1.00}{\tt f}} and {\colorbox[rgb]{1.00,0.93,1.00}{\tt g}} to evaluate the function and gradient at a point; also {\colorbox[rgb]{1.00,0.93,1.00}{\tt x\char48}} is the starting value. Use \href{matlab/fcombine.m}{matlab/fcombine.m} to join {\colorbox[rgb]{1.00,0.93,1.00}{\tt f}} and {\colorbox[rgb]{1.00,0.93,1.00}{\tt g}} into a single function for use in your routines above.

Show how many function evaluations, iterations, and seconds is required to find a point where the infinity norm of the gradient is smaller than $10^{-5}$ for each problem.



\end{enumerate}
\hypertarget{problem_2_a_little_theory_4}{}\subsection*{{Problem 2: A little theory}}\label{problem_2_a_little_theory_4}

According to the book, the SR1 BFGS update is a special case of the Broyden class of quasi-Newton updates (pages 150, 151). Show that this is the case.

\hypertarget{problem_3_comparing_optimization_codes_5}{}\subsection*{{Problem 3: Comparing optimization codes.}}\label{problem_3_comparing_optimization_codes_5}

\textbf{BONUS} We are getting close to the midterm. This is a bonus question worth 15 points of extra-credit.

\begin{itemize}%
\item \textbf{You may not collaborate on this question.}
\item \textbf{You must complete all parts of this question.}

\end{itemize}
We'{}ve discussed optimization algorithms frequently in this class. So far, we have seen:

\begin{itemize}%
\item Steepest Descent with a line-search
\item Newton'{}s Method with a line-search
\item Hessian based Trust Region methods
\item Non-linear CG methods with a line search
\item DFP Quasi-Newton method with a line search
\item BFGS Quasi-Newton method with a line search
\item SR1 Quasi-Newton method with a line search Given two methods, how should we compare them?

\end{itemize}
\begin{enumerate}%
\item Please fill in the blank in the following question, keeping in mind the requirements on this bonus question.

``{}I --{}fill this in--{} this problem entirely by myself and did not discuss with anyone.''{}


\item Read the following paper \url{http://www.tops-scidac.org/papers/DM_benchmark.pdf}


\item Implement a function \emph{yourself} to compute and display a performance profile. \textbf{I'{}ll post the best solution to the class web-page as a reference.}


\item Show a performance profile for number of function evaluations for the steepest descent and quasi-newton methods computed in problem 1.



\end{enumerate}

\end{document}
