\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_4_1}{}\section*{{Homework 4}}\label{homework_4_1}

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

\hypertarget{problem_1_covering_the_basics_2}{}\subsection*{{Problem 1: Covering the basics.}}\label{problem_1_covering_the_basics_2}

\begin{enumerate}%
\item \textbf{Decrease alone is insufficient!} Construct a sequence of iterates such that $f(x_{k+1}) < f(x_k)$, but that do not converge to a minimizer of $f$ for a convex function $f$. (Hint: think $f(x) = x^2$.)


\item \textbf{Back to calculus.} Let

\begin{displaymath}
L_k(\alpha) = f(\vx_k + \alpha \vp_k)
\end{displaymath}
be the line search function at the $k$th iteration of an optimization algorithm. Use the definition of the directional derivative to show that $L_k'(\alpha) = g(\vx_k + \alpha \vp_k)^T \vp_k$.



\end{enumerate}
\hypertarget{problem_2_finally_an_optimization_algorithm_3}{}\subsection*{{Problem 2: Finally! An optimization algorithm}}\label{problem_2_finally_an_optimization_algorithm_3}

Non-negative least squares is an important variant. Formally, it is:

\begin{displaymath}
\MINone{}{\normof{\mA \vx - \vb}}{\vx \ge 0.}
\end{displaymath}
We'{}ll see this problem again when we study constrained optimization. Here, we'{}ll investigate a log-barrier function to approximate it in an unconstrained manner:

\begin{displaymath}
\MIN{}{\normof{\mA \vx - \vb} - \mu \ve^T \log(\vx),}
\end{displaymath}
where log is an elementwise function. Use the definition where: $\log(x) = -\infty$ if $x \le 0$.

\begin{enumerate}%
\item Determine the gradient and Hessian.


\item What did you learn in class that you should always do after step 1? Do it.


\item Implement a backtracking line search routine that satisfies sufficient decrease. Convince your professor and TA that your implementation does not have any flaws. Discuss any flaws you known.


\item Modify the {\colorbox[rgb]{1.00,0.93,1.00}{\tt gradient\char95descent\char95\char49\char46m}} and {\colorbox[rgb]{1.00,0.93,1.00}{\tt newtons\char95method\char95\char49\char46m}} functions to use your backtracking line search. Read page 59 of Nocedal and Wright and follow the advice.\newline (Use (3.60) if applicable.)


\item Suppose that $\vx\itn{0}$ is strictly positive.\newline Does $\vx\itn{k}$ stay strictly positive with these two algorithms? Discuss or prove.


\item Show plots of the convergence in terms of function values and of infinity norms of the gradients of the methods for the matrices:



\end{enumerate}
\begin{verbatim}     A = [
         0.0372    0.2869
         0.6861    0.7071
         0.6233    0.6245
         0.6344    0.6170];
     b = [
         0.8587
         0.1781
         0.0747
         0.8405];
     mu = 0.1;\end{verbatim}
\begin{enumerate}%
\item Suppose we say that a method converges if the infinity norm of the gradient is less than $10^{-4}$. Plot the number of function evaluations of your new steepest descent method and the Newton method for the values of $\mu = \{10^{-1}, 10^{-2}, 10^{-3}, 10^{-4}, 10^{-5}, 10^{-6} \}.$ \newline Show your solutions for each of these cases. Compare the solutions to Matlab'{}s {\colorbox[rgb]{1.00,0.93,1.00}{\tt fminunc}} routine.

\end{enumerate}

\end{document}
