\documentstyle[12pt]{article}
\begin{document}
\begin{center}
{\large\bf C\&O 666 \\ 
Midterm Exam  Mar 1, 1995.
}
\end{center}
\begin{flushleft}
{\large   Instructor H. Wolkowicz \\
}
\end{flushleft}
\section{}
\marginpar{[10]}
Suppose that the functions $f,g_j:\Re^n \rightarrow \Re,~j=1, \cdots m$,
are all convex. Define $L(x,\lambda) = f(x) + \lambda^tg(x),$ where
$0 \leq \lambda \in \Re^n, ~g=(g_j),$ and suppose $\nabla L(x^*,\lambda^*) = 0$,
for given $x^*,\lambda^*.$
Show the following:
\begin{enumerate}
\item
$L$ is a convex function of $x$.
\item
$x^*$ is a minimum point of $L$.
\item
Suppose that $\lambda^tg(x^*)=0$ and that $g(x) \leq 0$. Then $f(x) \geq
f(x^*).$
\item
Deduce a set of first order sufficient optimality conditions for a
minimum point of the problem:
\[ \min_x f(x) ~{\rm s.t.}~ g(x) \leq 0. \]
\end{enumerate}
\section{}
\marginpar{[10]}
Consider the quadratic programming problem:
\[ (QP) ~~~\min_x (\max_x) h(x)=x^tQx-b^tx~~{\rm s.t.}~~ Ax=b,\] 
where $Q=Q^t$ is a fixed non-singular $n \times n$ matrix, and $A$ is a $m
\times n$ matrix. Suppose that $Ax^*=b$ and
$x^* = Q^{-1} (b + A^t \lambda )$, for
some $\lambda \in \Re^m$. 
\begin{enumerate}
\item
Show that one of the following holds:
\begin{enumerate}
\item
$x^*$ is a {\bf global} minimum for (QP);
\item
$x^*$ is a {\bf global} maximum for (QP);
\item
$x^*$ is a saddle point (neither a local minimum nor local maximum) for (QP).
\end{enumerate}
\item
Using the above results (or otherwise) derive a projected Newton method
for finding the local minimum of the program:
\[ \min_x f(x) ~~{\rm s.t.}~~ Ax=b ,\]
where $f:\Re^n \rightarrow \Re$ is in $C^2$.
\end{enumerate}
\section{}
\marginpar{[10]}
Consider the problem: $\min_x
f(x)=x^3+\frac{y^3}{3}-x^2-\frac{y^2}{2}+xy-10x-4y$.
\begin{enumerate}
\item
Verify that $(2,2)^t$ is a local minimum point.
\item
Using Newton's method, complete the first iteration from the initial
point $(0,0)^t$. What can you say about the Newton direction?
\end{enumerate}
\section{}
\marginpar{[10]}
\begin{enumerate}
\item
Show that the following problem is a convex programming problem, i.e.
show that the objective function and constraints are convex functions on
the domain $x,y \geq 0.$
\[
\begin{array}{crcl}
 \min & f(x)=x^3+\frac{y^3}{3}+\frac{x^2}{2}+y^2+xy-2x-y&&\\
   {\rm s.t.} &  -4x-3y+x^2+y^2+5 &\leq& 0 \\
              &  -x-2y +3 &\leq& 0 \\
              &  x,y &\geq& 0
\end{array}
\]
\item
Show that $(1,1)^t$ is an optimum solution using
weak duality.
\end{enumerate}
\section{}
\marginpar{[10]}
Consider the function
\[  f(x,y) = (x^2-4)^2+4y^2. \]
\begin{enumerate}
\item
Show that the points $(2,0)$ and $(-2,0)$ are minimum points of $f$ and
the origin is a saddle point of $f$.
\item
Draw the level curves for $f(x,y)=e$ for $e=12,16,25.$
\item
Find the Hessian of $f$ and determine where it is singular, positive
definite, and indefinite.
\item
State the Newton algorithm for $f$, i.e. write down the function $g$ for
the Newton iteration $x_{k+1}=g(x_k).$ Then determine the regions of the
plane where the iteration converges and find which points it converges to.
\end{enumerate}
\end{document}