\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_5_1}{}\section*{{Homework 5}}\label{homework_5_1}

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

The previous homework was focused heavily on implementations and studying these methods in a practical setting. In this homework, we will return our focus back to theory.

\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.

\hypertarget{problem_1_solving_the_trust_region_problem_griva_nash_and_sofer_1166_3}{}\subsection*{{Problem 1: Solving the trust region problem (Griva, Nash, and Sofer, 11.6.6)}}\label{problem_1_solving_the_trust_region_problem_griva_nash_and_sofer_1166_3}

In class, your professor mentioned that any solution to the trust region sub-problem,

\begin{displaymath}
\MINone{\vp}{f(\vx_k) + g(\vx_k)^T \vp + 1/2 \vp^T \mH(\vx_k) \vp \quad = \quad m_k(\vp)}{\normof{\vp} \le \Delta,}
\end{displaymath}
could be characterized as follows:

\begin{itemize}%
\item $(\mH(\vx_k) + \lambda \mI) \vp^* = -\vg$
\item $\lambda (\normof{\vp^*} - \Delta) = 0$
\item $\mH(\vx_k) + \lambda \mI \succeq 0$ (it'{}s positive semi-definite).

\end{itemize}
Use these conditions to show that, if $\lambda \not= 0$, then $\vp$ solves:

\begin{displaymath}
\MINone{\vp}{f(\vx_k) + g(\vx_k)^T \vp + 1/2 \vp^T \mH(\vx_k) \vp}{\normof{\vp} = \Delta.}
\end{displaymath}
\emph{Hint} First show that $m_k(\vp^*) \le m_k(\vp) + 1/2 \lambda (\vp^T \vp - {\vp^*}^T \vp^*)$ for any $\vp$.

\hypertarget{problem_2_advantages_and_disadvantages_4}{}\subsection*{{Problem 2: Advantages and disadvantages}}\label{problem_2_advantages_and_disadvantages_4}

Is a dog-leg method or a subspace minimization method better when using a trust region method on a convex optimization problem? Discuss and explain why.

\hypertarget{problem_3_read_and_prove_5}{}\subsection*{{Problem 3: Read and prove}}\label{problem_3_read_and_prove_5}

Read the proof of Lemma 4.2. There is one missing step. Let $\mB$ be symmetric positive definite. Prove the inequality:

\begin{displaymath}
\frac{(\vg^T \vg)^2}{\vg^T \mB \vg \vg^T \mB^{-1} \vg} \le 1.
\end{displaymath}
(Hint: Use Cauchy-Schwarz!) Can you remove any of the conditions from this proof? When do you have equality?


\end{document}
