\documentclass{amsart}
%\documentstyle{article}

\topmargin 0pt
%\advance \topmargin by -\headheight
%\advance \topmargin by -\headsep
\advance \topmargin by -.4in

\textheight 8.9in
%\textheight 9.8in

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

%\textwidth 6in
\textwidth 7in


%\setlength{\textheight}{8.5truein}
%\setlength{\textwidth}{6.5truein}
%
%\voffset-1in
%\hoffset-.5in

\usepackage{amsmath,amssymb}

\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]{\Vert #1 \Vert}
\newcommand{\tnorm}[1]{\Vert #1 \Vert_2}
\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}{\mathcal{P}}
\newcommand{\lam}{\lambda}
\newcommand{\ulam}{\underline{\lam}}
\newcommand{\olam}{{\bar\lam}}
\newcommand{\ip}[2]{\left\langle #1 ,#2\right\rangle}
\newcommand{\set}[2]{\left\{#1\,\left|\, #2\right.\right\}}

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

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

\noindent
This first problem set is mostly a warm-up exercise intended help you
review some basic concepts from linear algebra and multi-variable calculus
used in this course. Problems
1-3 are exercises that you should work out for your own benefit, but
they will not be graded.
Problems 4 and 5 will be graded and are  
due by class time Monday April 2. 
These problems set will be  
difficult for some and 
straightforward for others. If you are having
any difficulty, please feel
free to discuss the problems with me at any time.
I am very open with giving hints. 
\bigskip

\begin{enumerate}
\item
Let $Q$ be an $n\times n$ symmetric positive definite matrix.
The following fact for symmetric matrices can be used to answer
the questions in this problem.
\begin{quote}
{\bf Fact}: 
{\it If $M$ is a real symmetric $n\times n$ matrix, then
there is a real orthogonal $n\times n$ matrix $U$ ($U^TU=I$)
and a real diagonal matrix $\Lambda=\mbox{diag}(\lam_1,\lam_2,\dots,
\lam_n)$ such that $M=U\Lambda U^T$.} 
\end{quote}

\begin{enumerate}
\item[(a)]
Show that the eigenvalues of $Q^2$ are the square of the eigenvalues
of $Q$. 
\item[(b)]
If $\lam_1\ge\lam_2\ge\dots\ge\lam_n$ are the eigen values of
$Q$, show that
$$
\lam_n\tnorm{u}^2\le u^TQu\le \lam_1\tnorm{u}^2\ \forall\ u\in\Rn.
$$
\item[(c)]
If $0< \ulam <\olam$ are such that
$$
\ulam\tnorm{u}^2\le u^TQu\le \olam\tnorm{u}^2\ \forall\ u\in\Rn,
$$
then all of the eigenvalues of $Q$ must lie in the interval
$[\ulam,\olam]$.
\item[(d)]
Let $\ulam$ and $\olam$ be as in Part (c) above.
Show that 
$$
\ulam\norm{u}_2\le\norm{Qu}_2\le \olam\norm{u}_2\ \forall\ u\in\Rn\ .
$$
Hint: $\tnorm{Qu}^2=u^TQ^2u$.
\end{enumerate}
\item 
Consider the quadratic function $\map{f}{\Rn}{\R}$ given by
$$f(x):=\frac{1}{2} \tpose{x} Q x -\tpose{a}x +\alpha \  ,$$
where $Q \in \Rnn$, $a \in \Rn$, and $\alpha \in \R .$
\begin{enumerate}
\item Write expressions for both $\grad f(x)$ and $\grad^2 f(x)$.
Since it is not assumed that $f$ is symmetric, be careful in
how you express $\grad^2 f(x)$.
\item If it is further assumed that $Q$ is symmetric, what is
$\grad^2 f$?
\item State first-- and second--order necessary conditions for
optimality in the problem 
%
%\noindent
$\min \{f(x)\, :\, x\in\Rn\}$.
\item State a sufficient condition on the matrix $Q$ under which 
the problem $\min f$ has a unique global solution and then display
this solution in terms of the data $Q$ and $a$.
\end{enumerate}

\item 
Consider the linear equation $$Ax=b,$$ where $A \in \Rmn$
and $b \in \Rm$. When $n<m$ it is often the case that this
equation is over-determined in the sense that no solution $x$
exists. In such cases one often attempts to locate a `best'
solution in a least squares sense. That is one solves the
{\it linear least squares problem}
$$\hbox{(lls) : minimize } \half \norm{Ax-b}^2_2$$
for $x$. Define $\map{f}{\Rn}{\R}$ by
$$f(x):= \half \norm{Ax-b}^2_2.$$
\begin{enumerate}
\item Show that $f$ can be written as a quadratic function, 
that is, it
can be written in the same form as the function of the
preceding exercise.
\item What are $\grad f(x)$ and $\grad^2 f(x)$?
\item Show that $\grad^2 f(x)$ is positive semi-definite.
\item Show that $\mbox{Nul}(A^TA)=\mbox{Nul}(A)$ and
$\mbox{Ran}(A^TA)=\mbox{Ran}(A^T)$.
\item Show that a solution to (lls) must always exist. 
\item Provide a necessary and sufficient condition on the matrix
$A$ under which (lls)
has a unique solution and then display this solution in terms
of the data $A$ and $b$.
\end{enumerate}

\item 
Consider the minimization problem
$$\begin{array}{cll}
\hbox{$\mathcal{P}$ : }& \hbox{minimize }& f(x) \\
 & \hbox{subject to }& Ax=b \ ,
\end{array}$$
where $\map{f}{\Rn}{\R}$ is assumed to be twice continuously
differentiable, $A \in \Rmn$ has full rank with $m \leq n$,
and $b \in \Rm$. Set
$$P:=I-\tpose{A}(A\tpose{A})^{-1}A \ .$$
\begin{enumerate}
\item Show that $P$ is well--defined, that is, show that the matrix
$A\tpose{A}$ is non--singular.
\item Show that $P$ is the {\it orthogonal projector} onto the nulspace of
$A$. That is, show that $P$ is an orthogonal projector 
($P^2=P$ and $P=P^T$) and
$\mathrm{Ran}\,(P)=\mathrm{Nul}\,(A)$.
\item Set $h(z)=f(x_0+Pz)$ where $x_0$ is any point satisfying $Ax_0=b$.
Compute both $\nabla h(z)$ and $\nabla^2h(z)$.
\item
Show that if $\bar z$ solves 
$\widehat{\mathcal{P}}:\ \min\{h(z)\, :\, z\in\Rn\}$, then
$\bar x=x_0+P\bar z$ solves $\mathcal{P}$. Conversely, show that if
$\bar x$ solves $\mathcal{P}$, then there exists $\bar z$ 
solving $\widehat{\mathcal{P}}$ such that
$\bar x=x_0+P\bar z$.
\item
The set of first-order stationary points for the problem
$\widehat{\mathcal{P}}$ is the set of points
$\mathcal{S}_h=\set{z}{\grad h(z)=0}$. We define the set of
first-order stationary points for $\mathcal{P}$ to be
$\mathcal{S}_{f}=\set{x_0+Pz}{z\in \mathcal{S}_h}$.  
Show that 
\[
\mathcal{S}_{f}=\set{x}{P\nabla f(x)=0,\ Ax=b}
=\set{x}{Ax=b,\ \nabla f(x)\perp \mathrm{Nul}(A)}\ .
\]
%\item Show that if $P\nabla f(\bx )=0$ and $f$ is convex, the
%$\bx$ is a globally optimal solution to $\cP$.
\end{enumerate}

\item
Let $H\in\Rnn_s$, $u\in \Rn$, and $\alpha\in\R$ where $\Rnn_s$ is
the linear space of all real symmetric $n\times n$ matrices.
Recall that $H$ is said to be {\it positive definite} if $x^THx > 0$ for
all $x\in\Rn$ with $x\neq 0$. Moreover, $H$ is said to be {\it positive 
semi--definite} if $x^THx \ge 0$ for
all $x\in\Rn$. We consider the block matrix
$$\hat H:=\left[ \begin{array}{cc}
H&u\\u^T&\alpha
\end{array}\right]\, .
$$
\begin{enumerate}
\item Show that $\hat H$ 
is positive semi--definite if and only if $H$ is positive semi--definite
and there exists a vector $z\in\Rn$ such that $u=Hz$ and $\alpha \geq
z^THz$.
\item Show that $\hat H$
is positive definite if and only if $H$ is positive definite
and $\alpha > u^TH^{-1}u$.
\item Let $A\in\Rmn$, $b\in\Rm$, $c\in\Rn$, and $\delta \in\R$.
Use either Part (a) or Part (b) to show that $x\in\Rn$ is a solution to the
quadratic inequality
$$
(Ax+b)^T(Ax+b)\leq c^Tx+\delta
$$
if and only if the block matrix
$$
\left[\begin{array}{cc}
I&(Ax+b)\\
(Ax+b)^T&(c^Tx+\delta)
\end{array}\right]
$$
is positive semi--definite.
\item Suppose $H$ is positive definite. Show that
$$
\left[\begin{array}{cc}
H&u\\0&(\alpha -u^TH^{-1}u)
\end{array}\right]
=
\left[\begin{array}{cc}
I&0\\(-H^{-1}u)^T&1 
\end{array}\right]
\left[\begin{array}{cc}
H&u\\u^T&\alpha 
\end{array}\right]\, .
$$
\item Recall that the {\it kth principal minor} of a matrix 
$B\in \Rnn$ is the determinant of the upper left--hand corner
k$\times$k--submatrix of $B$ for $1\leq k\leq n$. Use an
induction argument and Parts
(b) and (d) above to show that $H$ is positive definite
if and only if every principal minor of $H$ is positive.

\noindent
\underline{Note}: Your argument {\bf must} use either Part (a)
or Part (b) above. 

\noindent
\underline{Hint}: det($AB$)=det($A$)det($B$), 
and the determinant of an upper or lower block triangular
matrix is the product of the determinants of the diagonal blocks.
\end{enumerate}


\end{enumerate}

\end{document}