
\documentstyle[12pt]{article}

\topmargin 0pt
%\advance \topmargin by -\headheight
%\advance \topmargin by -\headsep
\advance \topmargin by -1in

\textheight 10in
%\textheight 9.8in

\oddsidemargin 0pt
\evensidemargin \oddsidemargin
\marginparwidth 0.5in

%\textwidth 6in
\textwidth 7in


%\input{macros}

\newcommand{\R}{I\!\!R}
\newcommand{\Rn}{\R^n}
\newcommand{\Rm}{\R^m}
\newcommand{\Rnn}{\R^{n\times n}}
\newcommand{\Rmn}{\R^{m\times n}}
\newcommand{\map}[3]{#1:#2\mapsto #3}
\newcommand{\dd}[3]{#1'(#2:#3)}
\newcommand{\norm}[1]{|\!| #1 |\!|}
\newcommand{\abs}[1]{|#1|}
\newcommand{\tpose}[1]{#1^{\scriptscriptstyle T}}
\newcommand{\e}{\hbox{e}}
\newcommand{\grad}{\nabla}
\newcommand{\half}{\frac{1}{2}}
\newcommand{\bx}{\bar x}
\newcommand{\cP}{{\cal P}}
\newcommand{\cl}{\mbox{\, \rm cl}}
\newcommand{\tp}{{\scriptscriptstyle T}}
\newcommand{\lam}{\lambda}
\newcommand{\blam}{\bar \lambda}
\newcommand{\Span}{\mbox{Span}}
\newcommand{\ip}[2]{\left\langle #1 ,#2\right\rangle}

\begin{document}
\small
\centerline{\bf \Large MATH/AMATH 516}
\medskip

\centerline{\bf \Large  SECOND HOMEWORK SET}
\bigskip

%\noindent Homework Due Friday, April 22. 
%Please leave time for the programming assigment in problem 4.

\bigskip

\begin{enumerate}
\item Consider minimizing the continuously differentiable
function $\map{f}{\Rn}{\R}$ on
$\Rn$. Let $x\in\Rn$ and $d\in\Rn$ be such that $\grad f(x)^\tp d< 0$.
These properties of $f$, $x$, and $d$ are assumed and used in Parts (a) and
(b) of this problem.

Recall that in the backtracking line--search, we are given parameters
$0< \gamma <1$ and $0< c_1 <1$ and we
obtain an update to $x$,
say $x_+$, of the form $x_+=x+\lambda d$ where
$$\begin{array}{lll}
\lambda=&\max \gamma^k&\\
&\mbox{subject to}&k\in\{ 1,2,\dots\},\ \mbox{and}%\\
%&&
\ f(x+\gamma^kd)-f(x)\leq c_1\gamma^k\grad f(x)^\tp d\ .
\end{array}
$$
The key inequality
\begin{equation}\label{ag}
f(x+\lambda d)-f(x)\leq c_1\lambda\grad f(x)^\tp d
\end{equation}
is called the Armijo--Goldstein inequality.
A shortcoming of this step length is that it is
unrelated to the one dimensional problem
$
\min\{f(x+\lambda d)\, :\, \lambda \geq 0\}\ .
$
In this regard, we will study methods that require the step length
$\lam$ to satisfy both the Armijo--Goldstein inequality and
an inequality of the form
\begin{equation}\label{ww2}
\grad f(x+\gamma^kd)^\tp d\ge c_2 \grad f(x)^\tp d
\end{equation}
for a given $c_2\in (0,1)$.
The conditions (\ref{ag}) and (\ref{ww2}) taken together are called the
{\it weak Wolfe conditions}.
 
\begin{enumerate}
\item[(a)]
Show that if $0<c_1<c_2<1$
and the set $\{ f(x+\lambda d)\, :\, \lambda \geq 0\}$ is bounded below, 
then the 
two conditions (\ref{ag}) and (\ref{ww2}) can be satisfied simultaneously.
In particular, show that the set
$$
\left\{ \lambda \, \left| \begin{array}{c}
\lambda > 0, \grad f(x+\lambda d)^\tp d
\ge c_2 \grad f(x)^\tp d,\ \mbox{and}\\
f(x+\lambda d)-f(x)\leq c\lambda\grad f(x)^\tp d\end{array}
\right.\right\}
$$
has non--empty interior.
\item[(b)]
Let $0<c_1<c_2<1$
and assume that
the set $\{ f(x+\lambda d)\, :\, \lambda \geq 0\}$ is bounded below.
Show that the following bisection method is finitely terminating
at a value for $t$ at which the weak Wolfe conditions are satisfied.

\noindent
{\bf A Bisection Method for the Weak Wolfe Conditions}
\begin{enumerate}
\item[]{\sc Initialization}: Choose  
$0<c_1<c_2<1$, and set $\alpha =0$, $t>0$, and $\beta=+\infty$. 
\item[]
\item[]{\sc Repeat}
\begin{enumerate}
\item[] If $f(x +td)>f(x)+c_1tf'(x;d)$,
\item[]\qquad set $\beta =t$ and reset $t=\half(\alpha +\beta)$.
\item[]Elseif $f'(x+td;d)<c_2f'(x;d)$,
\item[]\qquad set $\alpha =t$ and reset
$$
t=\left\{\begin{array}{cl}
2\alpha,&\mbox{if $\beta=+\infty$}\\
\half(\alpha +\beta),&\mbox{otherwise.}
\end{array}\right.
$$
\item[] Else, {\sc STOP}.
\end{enumerate}
\item[] {\sc End Repeat}
\end{enumerate}
\end{enumerate}

\vfill\eject

\item 
Consider the function
$$
f(x)=\half x^TQx+c^Tx,
$$
where $Q\in\R^{n\times n}$ is symmetric and $c\in\Rm.$
\begin{enumerate}
\item
Under what condition on the matrix $Q\in \Rnn$ is $f$ convex?
Justify your answer.
\item
If $Q$ is symmetric and positive definite, show that there is a 
nonsingular matrix $L$ such that $Q=LL^T$.
\item
With $Q$ and $L$ as defined in the part (b), show that
\[
f(x)=\half\norm{L^Tx+L^{-1}c}_2^2-\half c^TQ^{-1}c.
\]
\item
If $f$ is convex, under what conditions is 
$\min_{x\in\Rn}f(x)=-\infty$?
\item
Assume that $Q$ is symmetric and positive definite and let
$S$ be a subspace of $\Rn$. Show that $\bx$ solves the
problem
\[
\min_{x\in S}f(x)
\]
if and only if $\grad f(\bx)\perp S$.
\end{enumerate}


\item 
Let $\map{F}{\Rn}{\Rm}$ be continuously differentiable, and let
$\norm{\cdot}$ be {\bf any} norm on $\Rm$. In this problem we consider
the function $f(x)=\norm{F(x)}$ and properties of the the associated Gauss-Newton
direction for minimizing $f$. Recall that $\bx\in\Rn$ is a first-order
stationary point for $f$ if $0\le f'(\bx;d)$ for all $d\in\Rn$.
\begin{enumerate}
\item\label{2.1}
Given $x,d\in\Rn$ and $t>0$ show that
\[
|\,\norm{F(x+td)}-\norm{F(x)+tF'(x)d}\, |\,\le\,\norm{F(x+td)-(F(x)+tF'(x)d)}\ .
\]
\item\label{2.2}
Why is it true that 
\[
\lim_{t\rightarrow 0}\frac{\norm{F(x+td)-(F(x)+tF'(x)d)}}{t}=0\ ?
\]
Hint: What is the definition of $F'(x)$?
\item\label{2.3}
Use parts \ref{2.1} and \ref{2.2} to show that
\[
f'(x;d)=\lim_{t\downarrow 0}\frac{\norm{F(x)+tF'(x)d}-\norm{F(x)}}{t}
\ .\]
\item\label{2.4}
Use part \ref{2.3} and the convexity of the norm to show that 
\[
f'(x;d)\le \norm{F(x)+F'(x)d}-\norm{F(x)} \ .
\]
Hint: $F(x)+tF'(x)d=(1-t)F(x)\,+\,t(F(x)+F'(x)d)$
\item\label{2.5}
Use parts \ref{2.3} and \ref{2.4} to show that
$0\le f'(x;d)$ for all $d$ if and only if
$\norm{F(x)}\le  \norm{F(x)+F'(x)d}$ for all $d$.
\item\label{2.6}
If $x$ is not a first-order stationary point for $f$ and $\bar d$ solves
\[
{\mathcal{GN}}\quad \min_{d\in\Rn} \norm{F(x)+F'(x)d} \ ,
\]
show that $\bar d$ is a descent direction for $f$ at $x$ by showning that
\[
f'(x;\bar d)\le \norm{F(x)+F'(x)\bar d}-\norm{F(x)} <0\ .
\]
\item
Show that the problem
\[
\min_{d\in\Rn} \norm{F(x)+F'(x)d}_1
\]
can be written as a linear program.
\item Suppose at a given point $x\in\Rn$ one solves the problem $\mathcal{GN}$ in Part \ref{2.6} above
to obtain a direction $\bar d$ for which $\norm{F(x)+F'(x)\bar d}<\norm{F(x)}$. Show that the
following backtracking line search procedure is finitely terminating in the sense that the solution
$\bar t$ is not zero.
\begin{quote}
Line Search: Let $0<c<1$ and $0<\gamma <1$ and set
\[
\begin{array}{rll}\bar t:=&\max& \gamma^s\\
&\mbox{s.t.}&s\in\{0,1,2,3,....\}\mbox{ and }\\
&&\norm{F(x+\gamma^s \bar d)}\le(1-\gamma^sc)\norm{F(x)}+c\gamma^s\norm{F(x)+F'(x)\bar d}.
\end{array}
\]
\end{quote}
\smallskip

\noindent
Hint: $(1-\gamma^sc)\norm{F(x)}+c\gamma^s\norm{F(x)+F'(x)\bar d}=\norm{F(x)}+c\gamma^s
[\norm{F(x)+F'(x)\bar d}-\norm{F(x)}]$. Then use Part \ref{2.6}.
\end{enumerate}



%\item 
%%\begin{enumerate}
%%\item 
%Let $\map{f}{\Rn}{\R}$ be the quadratic function
%$$
%f(x)=\half x^\tp Qx+g^\tp x +\alpha\ ,
%$$
%where we will assume that $Q$ is symmetric and positive definite.
%Let $x_0$ and $d_0$ be given vectors in $\Rn$. Find a closed form
%representation for the global solution to the problem
%$$\min\{\phi (\lambda ):\lambda\in\R\}$$ where the function 
%$\map{\phi}{\R}{\R}$ 
%is given by
%$\phi(\lambda)=f(x_0+\lambda d_0)$. A step length $\lambda_0$ chosen
%in this way is called the {\it Curry step size}.
%%\item
%%Now consider the special case $\map{f}{\R^2}{\R}$ given by
%%$$
%%f(\xi_1,\xi_2)=\half (\xi_1^2+\mu\xi_2^2)\ ,
%%$$
%%for some $\mu > 0$. 
%%\begin{enumerate}
%%\item Given $(\xi_1,\xi_2)^\tp$, show that the update
%%$(\xi_1,\xi_2)_+^\tp$ obtained by employing the steepest decent algorithm
%%with Curry step size satisfies
%%$$
%%\left( \begin{array}{c}\xi_1\\ \xi_2\end{array}\right)_+
%%=\frac{\mu -1}{\xi_1^2+\mu^3\xi_2^2}
%%\left( \begin{array}{c}\mu^2\xi_1\xi_2^2\\ -\xi_1^2\xi_2\end{array}\right)\ .
%%$$
%%\item Show that the relationship between successive iterates given above
%%implies the relationship
%%$$
%%\frac{\xi_2^{(k+2)}}{\xi_1^{(k+2)}}=\frac{\xi_2^{(k)}}{\xi_1^{(k)}}\ .
%%$$
%%Thus, every other iterate of the steepest decent method lies on the same
%%ray from the origin.
%%\item Let $\mu=4$ and $(\xi_1^{(0)},\xi_2^{(0)})^\tp=(1,1)^\tp$. 
%%Sketch the progress of steepest decent with Curry step size for
%%this value of $\mu$ and this starting point. Draw the two rays from the
%%origin alluded to in the previous question and draw the polygonal path
%%that connects the successive iterates. You need only compute a few of
%%the iterates to get the idea. This is called zig-zagging or hemstitching
%%and illustrates the typical behaviour of steepest decent near a solution. 
%%\end{enumerate}
%%\end{enumerate}
%
%\item Let $Q\in \Rnn$ be symmetric and positive definite and consider
%the quadratic function $f:\Rn \rightarrow \R$ given by
%$$
%f(x):=\frac{1}{2}x^\tp Qx-b^\tp x
%$$
%where $b\in \Rn$.
%\begin{enumerate}
%\item What is the unique point $\bx \in \Rn$ that achieves the
%global minimum value of $f$ on $\Rn$?
%\item A set of vectors $\{ d^0,d^1,\dots ,d^k\}\subset \Rn \backslash
%\{ 0\}$ are said to be {\it $Q$-conjugate} if
%$$
%{d^i}^\tp Qd^j=0\ \mbox{ whenever  }i\neq j\ .
%$$
%If the vectors $\{ d^0,d^1,\dots ,d^k\}$ are $Q$-conjugate, show that
%they are necessarily linearly independent.
%\item Given $x,d\in \Rn$ compute the unique solution to the  
%one dimensional
%optimization problem
%$$
%\min_{t\in \R}f(x+td)\ .
%$$
%(Hint: Review Part (a) of problem 2.)
%\item Consider the following algorithm:
%
%
%\fbox{\begin{minipage}{3.5in}
%\underline{Initialization:} $x_0\in \Rn,\ \{ d^0,d^1,\dots ,d^k\}
%\in \Rn$.
%\medskip
%
%Having $x^i$ obtain $x^{i+1}$ as follows:\\
%$$
%x^{i+1}:=x^i+t_id^i
%$$
%where $t_i$ solves $\min_{t\in \R}f(x^i+td^i)$.
%\end{minipage}}
%
%\noindent If the vectors $\{ d^0,d^1,\dots ,d^k\}$ are $Q$-conjugate 
%show that $x^{k+1}$ solves the problem
%$$
%\begin{array}{ll}
%\min f(x)& \\
%\mbox{subject to  }&x\in x^0+\Span \{ d^0,d^1,\dots ,d^k\}\ .
%\end{array}
%$$
%\item If $x^0\in \Rn$ and $\{ d^0,d^1,\dots ,d^{n-1}\}$ are
%$Q$-conjugate, show that the $n^{th}$ iterate of the algorithm
%described above solves the problem $\min_{x\in \Rn}f(x)$.
%\end{enumerate}

%\item
%Given a function $\map{f}{\Rn}{\R}$, a point $x\in\Rn$, a
%direction $d\in\Rn$ such that $\dd{f}{x}{d}<0$, and
%scalars $\gamma\in (0,1)$ and $c\in(0,1)$, 
%%write a Matlab function m--file 
%the backtracking line-search requires one 
%to solve the problem
%$$
%\max\{ \gamma^s\, :\, s=0,1,\dots,\ f(x+\gamma^sd)
%\leq f(x)+c\gamma^s\dd{f}{x}{d}\}\ .
%$$
%%The m-file should conform to the following guidelines:
%A sample m-file for solving this problem is provided in on the course
%webpage under {\it Matlab Sample Code}. The sample code is written for
%Matlab 5. Upgrade the code so that it executes in Matlab 6 (or higher)
%using the latest type and pointer features and abiding by the following
%conditions.
%\begin{enumerate}
%\item[(i)]
%The m--file should take as input the values of the variables
%$x,\ d,\ \gamma$ and the value of the product $cf'(x;d)$
%(this value is to be
%computed outside
%of the m-file). In addition, the m-file should also take as
%input a character string
%naming the function $f$. The function can then be evaluated using
%a pointer for the function $f$. In Matlab 5 this was done using the 
%{\it feval} command.
%\item[(ii)]
%The
%output should be the vector $x+\gamma^sd$ and
%the value $f(x+\gamma^sd)$.
%\item[(iii)]
%In order to evaluate the
%function within the m--file use use pointers.
%\item[(iv)]
%Calculate $\gamma^s$ within a {\it while
%loop}.  This loop should be limited to 14 trials.
%\item[(v)]
%An expression like  $\gamma^s$ should not appear
%in your code.
%\end{enumerate}
%Once this upgrading of the code is completed do the following.
%\begin{enumerate}
%\item Apply your subroutine to the test function
%$$
%f(x_1,x_2)=100(x_2-x_1^2)^2+(1-x_1)^2\ .
%$$
%This function is called {\it Rosenbrock's function}. It has a 
%global minimum value of $f(x)=0$ uniquely occuring at the point
%$(x_1,x_2)=(1,1)$.
%Take $x=(-1.9,2)$ and $d=-\nabla f(x)/\norm{-\nabla f(x)}$.
%Compare the performance for $$(\gamma ,c)=(.9,.01),(.8,.01),(.8,.2),
%(.5,.01),(.5,.2).$$ 
%\item Now use this line search subroutine in conjunction with the 
%direction of steepest descent ($d=-\nabla f(x)/\norm{-\nabla f(x)}$)
%to implement a Matlab subroutine to
%locate an approximate global solution to the problem $\min_{x\in\R^2}f(x)$,
%where $f$ is the Rosenbrock function given above.
%Your subroutine should use the stopping criteria 
%\begin{eqnarray*}
%\norm{\grad f(x)}&\le& 10^{-6}\ ,\\
%\mbox{number of iterations} &\le &100\quad \mbox{or},\\
%\norm{x^{n +1}-x^{n}}&\le& 10^{-14}\ .
%\end{eqnarray*}
%Describe the performance of your subroutine using the {\it Programming
%Guidelines} from the course webpage.
%\end{enumerate}
%\end{enumerate}
%\end{document}
%
%\item  Recall the following theorem concerning second--order
%optimality conditions for the the problem
%$$
%\begin{array}{ll}
%\cP&\min f(x)\\
%&\mbox{subject to $x\in \Omega$}
%\end{array}
%$$
%where $\map{f}{\Rn}{\R}$ is smooth and $\Omega\subset \Rn$ is
%nonempty closed and convex.
%
%\begin{Thm} \label{thm:second-order-opt-cvx-constr}
%Let $f_0 : \R^n \to \R$ be $C^2$ and $\overline x$ be an element of the
%convex set $\Omega$.
%\begin{description}
%\item{(1)} (necessity) If $\overline x \in \R^n$ is a local
%solution to $\cP$ with $\Omega$ a polyhedral convex set, then
%$\nabla f_0 (\overline x)^\tp (y-\overline x) \geq 0$ for all
%$d \in T_\Omega(\bx )$ and
%$$d^\tp \nabla^2 f_0 (\overline x) d \geq 0$$
%for all $d \in T_\Omega (\bx )$ with $\nabla f (\overline x)^\tp d = 0$.
%\item{(2)} (sufficiency) If $\overline x \in \R^n$ is such that
%$\nabla f_0 (\overline x)^\tp (y-\overline x) \geq 0$ for all
%$d \in T_\Omega(\bx )$ and
%$$d^\tp \nabla^2 f_0 (\overline x) d > 0$$
%for all $d \in T_\Omega(\bx ) \backslash \{ 0 \}$ with $\nabla f_0 (\overline x)
%^\tp d = 0$,
%then there exist $\eps, \nu >0$ such that
%$$f_0 (\overline x) \leq f_0 (x) - \nu \Vert x-\overline
%x\Vert^2$$
%for all $x\in \Omega$ with $\norm{x-\bx}\leq \eps$.
%\end{description}
%\end{Thm}
%
%\noindent
%Here $T_\Omega(x )$ denotes the {\it tangent cone} to the set
%$\Omega$ at the point $x\in\Omega$. It is defined to be the
%closure of the set
%$$
%\bigcup_{\lambda \geq 0}\lambda (\Omega -x):=\{ \lambda (y-x)\,
%:\, y\in\Omega,\ \lambda\geq 0\}\ .
%$$
%Also, recall that if $\Omega $ is polyhedral, then the
%closure operation is not required.
%
%\begin{enumerate}
%\item Use the following example to show that the assumption of
%polyhedrality is required to obtain the {\it necessity} part of the
%above result:
%$$\begin{array}{ll}
%\min \half (x_2 -x_1^2)& \\
%\hbox{subject to } &-x^3_1\leq x_2^2,\ x^3_1\leq x_2^2.\\
%\end{array}$$
%\item In employing the second-order conditions given above, one needs to
%be careful about the relationship between the hessian of $f_0$ and the
%set $K:=T_\Omega(x)\cap [\grad f_0(x)]^\perp$. In particular, the positive
%definiteness (or semidefiniteness) of the hessian of $f_0$ on the
%cone $K$ does not necessarily imply the positive
%definiteness (or semidefiniteness) of the hessian of $f_0$ on the
%subspace spaned by $K$. Use the following example to illustrate
%this point:
%$$\begin{array}{ll}
%\min (x_1^2 -\half x_2^2)& \\
%\hbox{subject to } &-x_1\leq x_2\leq x_1.\\
%\end{array}$$
%\item Verify that the following is an example of a
%convex program in which the global solution $\bx$
%satisfies
%$$f_0 (x)\geq f_0 (\overline x) + \nu \Vert x-\overline
%x\Vert^2$$
%for all $x\in \Omega$ near $\bx$
%and yet the second-order sufficiency condition
%given in Theorem \ref{thm:second-order-opt-cvx-constr} is not
%satisfied. This example illustrates that
%Theorem \ref{thm:second-order-opt-cvx-constr} is
%primarily useful only in the polyhedral case.
%$$\begin{array}{ll}
%\min x_2& \\
%\hbox{subject to } &x_1^2\leq x_2.\\
%\end{array}$$
%\item Use the next example to show that
%in cases where the constraint region $\Omega$ is nonconvex, the
%second-order sufficiency condition given in
%Theorem \ref{thm:second-order-opt-cvx-constr} can be satisfied at
%points which are not local solutions even if the
%objective function $f_0$ is convex.
%$$\begin{array}{ll}
%\min x_1^2 -x_2& \\
%\hbox{subject to } &0 \leq x, x_2^2 \leq x^3_1.\\
%\end{array}$$
%\end{enumerate}


\end{enumerate}

\end{document}

