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

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

\begin{flushleft}
{\large  Due on Tuesday, Mar. 14,~~~~   Instructor H. Wolkowicz
}
\end{flushleft}

\begin{enumerate}
\item
Suppose that $C$ is a convex set in $\Re^n$ and the point $y \notin \bar{C},$
the closure of $C$. Prove that there exists $\phi$ such that
\[  \phi^ty < \phi^tx,~~\forall x \in C. \]
(Hint: First prove that there is a point $\bar{x} \in \bar{C}$ which is
closest to $y$.)

\item
Suppose that $K_1,K_2$ are convex sets in $\Re^n$ and the interior of
$K_1$ is not empty, $\mbox{int}\,(K_1) \neq \emptyset.$ In addition,
suppose that
  \[  K_2 \cap \mbox{int}\,(K_1) = \emptyset. \]
Prove that there exists a hyperplane separating $K_1,K_2.$

\item
Suppose that $S \subset \Re^n.$ Prove that $S^{++}=S$ if and only if $S$
is a closed convex cone. ($\cdot^+$ denotes polar)

\item
Consider the trust region subproblem (TRS)
\[ \min x^tAx-2b^tx ~\mbox{subject to}~ x^tx - \delta^2 \leq 0, \]
where $A=A^t.$ Using the min-max and max-min approach, derive a dual
program to (TRS) which is a simple constrained concave maximization
program. Then derive the dual to this dual and relate it to the original
(TRS) problem.

\end{enumerate}
\end{document}

