\documentstyle[12pt]{article}
\begin{document}
\begin{center}

{\large\bf C\&O 367 \\ 
Assignment 5 
}
\end{center}
\begin{flushleft}
{\large  Due on Thursday, Mar. 12,~~~~   Instructor H. Wolkowicz
}
\end{flushleft}

{\bf NOTE:} Several exercises are marked: {\bf Do not hand in.}
\begin{enumerate}
\item
({\bf Do not hand in.}) 
We have seen how important a well-scaled minimization problem is, e.g.
applying steepest descent to a poorly scaled problem results in poor
convergence while the best scaling leads to Newton's method. A quadratic
minimization problem could be considered perfectly scaled if its Hessian
were the identity. 

If we rescale the variable space by $\hat{x}=Tx$, then in the new
variable space, the quadratic model around $\hat{x}_+$ has gradient
transformed to $T^{-T} \nabla f(x)$ and model Hessian $T^{-T}H_+T^{-1}$,
where $H_+$ is the model Hessian in the original variable space. Thus,
the rescaling that leads to an identity Hessian in the model around
$\hat{x}_+$ satisfies $T_+^{-T}H_+T_+^{-1}=I$, or $H_+ = T^T_+T_+$.

\begin{enumerate}
\item
Show that the BFGS update is invariant under linear transformations of
the variable space.
\item
The PSB update of $B$ is defined
\[
B_+ = B + \frac{us^T +su^T}{s^Ts} - \frac{(u^Ts)ss^T}{(s^Ts)^2}.
\]
Show that the PSB update is not invariant under linear transformations of
the variable space.
\end{enumerate}
\item
Prove that exactly one of the following two systems has a solution:
\begin{enumerate}
\item 
$Ax > 0$.
\item 
$A\T y = 0$, $y \ge 0$, and $y \neq 0$.
\end{enumerate}
\item
Derive an explicit form for the dual cone $C^*$ of the following
cones:
\begin{enumerate}
\item 
$C = \lp (x,y) \mid 0 \le y\le x \rp$.
\item 
$C = \lp (x,y) \mid y \ge - |x| \rp$.
\end{enumerate}
\item
Which of the following functions are convex, concave, or neither.
\begin{enumerate}
\item $f(x,y) = x^2 + 2xy - 10 x + 5y$.

\item $f(x,y) = x {\rm e}^{-(x+y)}$.

\item $f(x,y,z) = xy + 2x^2 + y^2 + 2z^2 - 6xz$.
\end{enumerate}
\item
Let $S$ be a nonempty closed 
convex subset of $\Rn$, and define $f\colon \Rn \mapsto
\Re$ by
\[
	f(y) = \inf_{x\in S} \|x-y \|.
\]
Prove that $f$ is convex.
\item
({\bf Do not hand in.}) 
Give an example of a set $S$ whose tangent cone at some point $x$ is not
convex.
\item
({\bf Do not hand in.}) 
Find the tangent cones $T_S(0)$ and $TL_S(0)$ for the following sets:
\begin{mlist}
\item $S = \lp (x,y) \mid y \ge x^3 \rp$.
\item $S = \lp (x,y) \mid y > x^2 \rp$.
\item $S = \lp (x,y) \mid y = -x^3 \rp$.
\end{mlist}
\item
Consider Rosenbrock's test function
\[
f(x) = 100(x_2-x_1^2)^2+(1-x_1)^2.
\]
Find the minimum point for this function
from the initial estimate $x^{(1)} = (-1~1)^T$.
Use the matlab package as well as the following three methods:
\begin{enumerate}
\item
Newton with approximate linesearch,
\item
quasi-Newton with BFGS update with approximate linesearch,
\item
steepest descent with exact line search.
\end{enumerate}
You can experiment with different approximate linesearches, e.g.
backtracking with initial steplength of 1. 
(Please include well-documented programs.)
\end{enumerate}
\end{document}