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

{\large\bf C\&O 367 \\ 
Assignment 3 
}
\end{center}
\begin{flushleft}
{\large  Due on Thursday, Oct. 28,~~~~   Instructor H. Wolkowicz
}

\end{flushleft}

\begin{enumerate}
\item

Consider the classical steepest descent method
\[ x_{k+1} = x_k + \alpha_k d_k, \]
where $\alpha_k = \mbox{arg}\min_\alpha f(x_k + \alpha d_k)$ 
is the steplength and $d_k = -\nabla f(x_K)$ is the steepest descent
direction. 
\begin{enumerate}
\item
Let $\Delta x = x_k - x_{k-1}$ and 
$\Delta g = \nabla f(x_k) - \nabla f(x_{k-1})$.
Derive two new steplengths (called the Barzilai-Borwein steplengths,
see \cite{BaBo:88,Ray:93}) 
by solving the following problems:
\begin{enumerate}
\item
\[
\min_\alpha || \Delta x - \alpha \Delta g ||;
\]
\item
\[
\min_\alpha || \alpha \Delta x - \Delta g ||.
\]
What do these steplengths correspond to in the one dimensional case?
\end{enumerate}
\item
Let   $f(x)=0.5 x^TAx - b^Tx$, where
$A$ is the diagonal matrix with diagonal elements $( 20,10,2,1)$,
and $b= (1,1,1,1).$
Minimize the function $f$.
Use the starting point $x_0=0$ and compare the above two steplengths
with the classical steepest descent algorithm, i.e. iterate until the
norm of the gradient is less than $1E-10$, ten zeros.
\end{enumerate}
\item
Let $\lp v_1, v_2, \ldots, v_n \rp$ denote the eigenvectors of an $n
\times n$ symmetric positive definite matrix $Q$, and consider the problem
\[
	\min_x  f(x) = \half x^T Q x - b^T x.
\]
For initial point $x_0$ let $x_k$ be generated by Steepest Descent with
exact line search.  Let $\grad f(x_0) = \sum_j \alpha_j v_j$, and let $M =
\Span{v_i \mid \alpha_i \neq 0}$.  Show that $\grad f(x_k) \in M$ for all
$k$.  Find the constant of the rate of convergence for the sequence $x_k$.
\item
Consider the problem
\[
	\min_x  f(x,y) = 5 x^2 + 5y^2 - xy - 11x + 11y + 11.
\]
\begin{enumerate}
\item 
Find a point satisfying the first-order necessary conditions.
\item 
Show that this point is a global minimum.
\item 
What is the constant for the
rate of convergence for steepest descent for this problem?
\item 
For $x_0 = (0,0)^T$, how many steepest descent iterations are necessary to ensure that
the function value is reduced to $10^{-11}$?
\end{enumerate}
\item
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}HT^{-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}HT^{-1}=I$, or $H = T^TT$.

\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},
\]
where $s=x_+-x$ is the step taken, and $u=y-Bs,
~y=g_+-g,$ is the error in the secant equation.
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) = \min_{x\in S} \|x-y \|.
\]
Prove that $f$ is convex.

\end{enumerate}
\bibliography{/home/hwolkowicz/.master}
\end{document}