\documentstyle[12pt]{article}
\input{newcmds}
\begin{document}

\begin{center}
{\large\bf C\&O 666 \\ 
Assignment 1 
}
\end{center}

\begin{flushleft}
{\large  Due on Thursday, Jan. 19,~~~~   Instructor H. Wolkowicz
}
\end{flushleft}

\begin{enumerate}


\item
Consider the following program:
\begin{center}
h=1/2\\
x=2/3-h\\
y=3/5-h\\
e=(x+x+x)-h\\
f=(y+y+y+y+y)-h\\
q=f/e
\end{center}
Explain the value of $q$ on the computer and on a calculator.

\item
In the $xy$-plane, sketch the ellipse $F(x,y)=3x^2+2y^2-12x-12y=0$ and
find its center $(x_0,y_0).$ Determine the values of $c$ such that the
center $(x_c,y_c)$ of the circle $c(x^2+y^2)-12x-12y=0$ is interior to
the ellipse $F(x,y)=0.$ Show that these circles are tangent to the
ellipse at the origin. Find $c$ such that $(x_c,y_c)$ is closest to
$(x_0,y_0).$ Determine $c$ such that $F(x_c,y_c)$ has a minimum value.

\item
Recall that $\lambda$ is an {\em eigenvalue} of a symmetric matrix $A$ if
there is a vector $x \neq 0$ such that $Ax = \lambda x$. The vector $x$
is an {\em eigenvector} of $A$ corresponding to $\lambda.$
Show that if $x$ is an eigenvector of $A$, the corresponding eigenvalue
$\lambda$ is given by the formula $\lambda = R(x),$ where $R$ is the
{\em Rayleigh quotient}
\[  R(x) = \frac{x^tAx}{x^tx}~~~(x \neq 0)
\]
of $A$. Show that $R(\alpha x) = R(x)$ for all numbers $\alpha \neq 0.$
Hence, conclude that $R$ attains all of its functional values on the
unit sphere $||x|| =1.$ Show that the minimum value $m$ of $R$ is
attained at a  point $X_m$ having $||x_m|| = 1.$ Show that $x_m$ is an
eigenvector of $A$ and that $m=R(x_m)$ is the corresponding eigenvalue
of $A$. Hence $m$ is the least eigenvalue of $A$. Show that the maximum
value $M$ of $R$ is the largest eigenvalue of $A$ and that a
corresponding eigenvector $x_M$ maximizes $R$. Show that
\[  m||x||^2 \leq x^tAx \leq M ||x||^2,
\]
for every vector $x$. Finally, show that if $A$ is positive definite,
then we have the additional inequalities
\[
\frac{||x||^2}{M}
\leq x^t A^{-1} x \leq
\frac{||x||^2}{m},
\] 
where $m$ and $M$ are respectively the smallest and largest eigenvalues
of $A$.

\item
Consider the following two-variable problem.
\[  \max f(x) = 2x_1x_2 +2x_2-2x_2^2.
\]
\begin{enumerate}
\item
Perform two steps of steepest descent (by hand). Use the origin as the
starting point.
\item
Use the optimization toolkit in matlab to find the maximum and verify
this using the optimality conditions.
\end{enumerate}
\item
The system of equations
\begin{eqnarray*}
2(x_1+x_2)^2+(x_1-x_2)^2-8 & = & 0 \\
5x_1^2+(x_2-3)^2-9 & = & 0 
\end{eqnarray*}
has a solution $(1,1)^t.$ Carry out one iteration of Newton's method
from the starting point $(2,0)^t.$ Then solve the system using matlab
with the same starting point.
\item
For each of the functions $f(x)=x, f(x)=x^2+x, f(x)=e^x-1,$ answer the
following questions:
\begin{enumerate}
\item
What is $f^{\prime} (x)$ at the root 0.
\item
What is a Lipschitz constant for $f^{\prime}$ in the interval $[-a,a];$
i.e. what is a bound on $|f^{\prime}(x)-f^{\prime}(0))/x|$ in this
interval?
\item
What region of convergence of Newton's method on $f(x)$ is predicted by
the convergence theorem?
\item
In what interval containing 0 is Newton's method on $f(x)$ actually
convergent to 0?
\end{enumerate}
\item
Use the answers from the above problem and consider applying Newton's
method to finding the root of
\[
F(x)=\left[
\begin{array}{c}
x_1 \\
x_2^2 +x_2 \\
e^{x_3} -1
\end{array}
\right]
\]
\begin{enumerate}
\item
What is the Jacobian $J(x)$ at the root $(0,0,0)^t?$
\item
What is a Lipschitz constant on $J(x)$ in an interval of radius $A$
around the root?
\item
What is the predicted region of covergence for Newton's method on
$F(x)?$
\end{enumerate}
\end{enumerate}
\end{document}